堆排序

堆排序(heapsort)兼有插入排序和合并排序的特点。类似于合并排序:它的运行时间是O(nlgn);类似于插入排序,它是一种原地排序算法:在任何时候,数组中只有常数个元素存储在输入数组意外。堆排序将插入排序和合并排序的优点结合起来。

堆数据结构是一种数组对象,可以被视为一棵完全二叉树。数的每一层都是填满的,最后一层可能除外。

表示堆的数组A是一个具有两个属性的对象:length[A]是数组中的元素个数,heap-size[A]是存放在A中的堆的元素个数。即A[heap-size[A]]之后的元素都不属于相应的堆,此处heap-size[A]<=length[A]。

数的根为A[1],给定某个节点下标i,父节点和左右儿子的关系为:

PARENT(i) = floor(i/2);

LEFT(i) = 2i;

RIGHT(i) = 2i + 1;

二叉堆有两种,最大堆:堆中某个结点的值之多和其父节点一样大;最小堆:堆中某个结点的值一定不小于父节点。堆排序算法中使用最大堆,最小堆通常在构造优先队列时使用。

堆结构上的基本操作和运行时间:

MAX-HEAPIFY:O(lgn),保持最大堆性质

BUILD-MAX-HEAP:以线性时间运行,在无序的输入数组基础上构造出最大堆

HEAPSORT:运行时间为O(nlgn),对一个数组进行原地排序

保持堆的性质MAX-HEAPIFY

对输入数组A和下标i,假定LEFT[i]和RIGHT[i]为根的两颗子树都是最大堆,但A[i]可能小于其子女,违反了最大堆性质。MAX-HEAPIFY用于调整A[i]的位置,使以i为根的子树成为最大堆。

MAX-HEAPIFY的基本方法是,从A[i],A[Left[i]]和A[Right[i]]中找出最大的,如果A[i]最大,则堆已经是最大堆;否则将i结点值和最大的子节点值交换,再对交换过的结点为根的子树递归调用MAX-HEAPIFY。

MAX-HEAPIFY的时间复杂度是O(lgn),即对一个高度为h的结点所需的运行时间为O(h)。

建堆BUILD-MAX_HEAP

建堆过程:自底向上地将一个数组A[1..n]变成一个最大堆。

子数组A[(floor(n/2)..n]都是叶子节点,BUILD-MAX_HEAP过程对堆中的非叶子节点有调用一次MAX-HEAPIFY。

BUILD-MAX_HEAP的时间复杂度是O(n)。

堆排序算法HEAPSORT

堆排序算法的过程:

1.用BUILD-MAX_HEAP将数组A[1..n]构造成一个最大堆;

2.交换数组中最大元素A[1]和A[n],并将堆中结点n去掉(减小heap-size[A]);

3.对A[1..n-1]调用MAX-HEAPIFY使其恢复为最大堆;

4.重复2-3步骤(此时n将为n-1)。

HEAPSORT过程的时间代价是O(nlgn)。

完整的java版堆排序代码如下:

[code lang=”java”]public class HeapSort{

private static int[] A = {3, 2, 6, 1, 9, 7, 8, 5, 4};

public static int left(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 1;
}

public static int right(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 2;
}

public static int parent(int i){
	return (int)Math.floor(i / 2 );
}

public static void maxHeapify(int i, int heapSize){
	int l = left(i);
	int r = right(i);
	int largest = 0;
	if(l &lt; heapSize &amp;&amp; A[l] &gt; A[i]){
		largest = l;
	}else{
		largest = i;
	}
	if(r &lt; heapSize &amp;&amp; A[r] &gt; A[largest]){
		largest = r;
	}
	if(largest != i){
		int temp = A[largest];
		A[largest] = A[i];
		A[i] = temp;
		maxHeapify(largest, heapSize);
	}else{
		return;
	}
}

public static void buildMaxHeap(){
	int heapSize = A.length;
	for(int i = (int)Math.floor(heapSize / 2) - 1; i &gt;= 0; i--){
		maxHeapify(i, heapSize);
	}
}

public static void heapSort(){
	buildMaxHeap();
	int heapSize = A.length;
	for(int i = A.length - 1; i &gt;0; i--){
		int temp = A[i];
		A[i] = A[0];
		A[0] = temp;
		heapSize--;
		maxHeapify(0, heapSize);
	}
}

public static void main(String[] args){
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	heapSort();
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]

Published: 24 Aug 2011

合并排序

合并排序(merge sort)是利用分治法(divede-and-conquer)进行排序的方法,即将一个较大问题分解为n个规模较小而结构相似的问题,分别处理这些子问题然后将结果合并。合并排序将待排序的元素分成两部分,对每部分进行合并排序后,将两个分别有序的字部分合并起来成为一个有序结果。

下面算法中,mergeSort(int[] A, int p, int r)对数组A[p, r]进行排序,将问题分解递归处理,当待排序元素分解为只有一个时视为已经排好序;merge(int[] A, int p, int q, int r)将排好序的两部分元素进行合并,把已经排好序的A[p, q]和A[q+1, r]合并成按序排列的A[p, r]。

[code lang=”java”]public class MergeSort{ public static int[] merge(int[] A, int p, int q, int r){ int n1 = q - p + 1; int n2 = r - q; int[] L = new int[n1 + 1]; int[] R = new int[n2 + 1]; for(int i = 0; i < n1; i++){ L[i] = A[p + i]; } for(int j = 0; j < n2; j++){ R[j] = A[q + j + 1]; } L[n1] = Integer.MAX_VALUE; R[n2] = Integer.MAX_VALUE; int i = 0, j = 0; for(int k = p; k <= r; k++){ if(L[i] < R[j]){ A[k] = L[i]; i++; }else{ A[k] = R[j]; j++; } } return A; }

public static int[] mergeSort(int[] A, int p, int r){
	if(p &gt;= r){
		return A;
	}
	else{
		//如果数据类型非整型,q要向下取整
		int q = (p + r) / 2;
		A = mergeSort(A, p, q);
		A = mergeSort(A, q + 1, r);
		A = merge(A, p, q, r);
		return A;
	}
}

public static void main(String[] args){
	int[] array = {3, 2, 6, 1, 9, 7, 8, 5, 4};
	for(int i : array){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	array = mergeSort(array, 0, array.length - 1);
	for(int i : array){
		System.out.print(i + &quot;,&quot;);
	}
} } [/code]

利用递归式和递归树可以证明,合并排序的时间复杂度是O(nlgn)。(见《算法导论》P21)

Published: 14 Aug 2011

插入排序

插入排序(InsertionSort)是一个对少量元素进行排序的有效算法,它的基本思想和打牌时整理牌的顺序方法类似:如果右手中有一组需要按照大小排序的牌,则依次从中取出一张牌放入左手,每次新取出的牌按照大小关系插入到左手牌中合适的位置,直到所有的牌都排序完成,因此称之为插入排序。

插入排序的Java代码如下所示:

[code lang=”java”]public class InsertionSort{ public static int[] sort(int[] array){ for(int i = 1; i < array.length; i++){
int key = array[i];
int j = i - 1; while(j >= 0 & array[j] > key) { array[j+1] = array[j]; j–; } array[j+1] = key; } return array; }

public static void main(String[] args){
	int[] array = {3, 2, 6, 1, 9, 7, 8, 5, 4};
	for(int i : array){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	array = sort(array);
	for(int i : array){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]

在最优情况下,即待排序数的顺序已经排好,则上面算法中,插入部分(while循环)不需要进行,插入排序的算法复杂度是O(n);在最坏情况下,待排序数是逆序的,插入部分需要进行最多次,则算法复杂度是O(n^2)。

总结:插入排序对部分有序的数据是极好的排序算法,对小型数据也是较好的排序方法。

Published: 13 Aug 2011

在Java程序和Lucene中使用中科院分词系统ICTCLAS

分词是文本处理、分析的基础,中科院分词系统ICTCLAS是中文领域中功能强大的分词系统。下面介绍如何在一般的Java程序和Lucene中使用ICTCLAS。

首先在ICTCLAS官方网站下载分词系统源码,地址是http://ictclas.org/ictclas_download.aspx,目前的版本如下图所示:


 

根据操作系统和编程语言的需要选择下载,本文使用的是ICTCLAS2011_Windows_32_jni版本。

将下载文件解压后,有四个文件夹:


其中,API中是完整的软件包,可以调用其中的函数实现分词功能;Demo是使用图形化界面演示分词效果的程序;Doc是软件文档;Sample是一个Java中调用ICTCLAS的例子。

1.一般Java程序

一般Java程序使用中科院分词系统ICTCLAS参考Sample文件夹中的示例程序即可。

示例程序TestMain.java的主要内容如下:

[code lang=”java”]class TestMain { //主函数 public static void main(String[] args) { try { //字符串分词 String sInput = "随后温总理就离开了舟曲县城,预计温总理今天下午就回到北京。以上就是今天上午的最新动态"; testICTCLAS_ParagraphProcess(sInput);//同testimportuserdict和testSetPOSmap } catch (Exception ex) { } }

public static void testICTCLAS_ParagraphProcess(String sInput)
{
	try
	{
		ICTCLAS50 testICTCLAS50 = new ICTCLAS50();
		String argu = &quot;.&quot;;
		//初始化
		if (testICTCLAS50.ICTCLAS_Init(argu.getBytes(&quot;GB2312&quot;)) == false)
		{
			System.out.println(&quot;Init Fail!&quot;);
			return;
		}

		//设置词性标注集(0 计算所二级标注集,1 计算所一级标注集,2 北大二级标注集,3 北大一级标注集)
		testICTCLAS50.ICTCLAS_SetPOSmap(2);

		//导入用户词典前分词
		byte nativeBytes[] = testICTCLAS50.ICTCLAS_ParagraphProcess(sInput.getBytes(&quot;GB2312&quot;), 0, 1);//分词处理
		System.out.println(nativeBytes.length);
		String nativeStr = new String(nativeBytes, 0, nativeBytes.length, &quot;GB2312&quot;);
		System.out.println(&quot;未导入用户词典的分词结果: &quot; + nativeStr);//打印结果

		//导入用户字典
		int nCount = 0;
		String usrdir = &quot;userdict.txt&quot;; //用户字典路径
		byte[] usrdirb = usrdir.getBytes();//将string转化为byte类型
		//导入用户字典,返回导入用户词语个数第一个参数为用户字典路径,第二个参数为用户字典的编码类型
		nCount = testICTCLAS50.ICTCLAS_ImportUserDictFile(usrdirb, 0);
		System.out.println(&quot;导入用户词个数&quot; + nCount);
		nCount = 0;

		//导入用户字典后再分词
		byte nativeBytes1[] = testICTCLAS50.ICTCLAS_ParagraphProcess(sInput.getBytes(&quot;GB2312&quot;), 2, 0);
		System.out.println(nativeBytes1.length);
		String nativeStr1 = new String(nativeBytes1, 0, nativeBytes1.length, &quot;GB2312&quot;);
		System.out.println(&quot;导入用户词典后的分词结果: &quot; + nativeStr1);
		//保存用户字典
		testICTCLAS50.ICTCLAS_SaveTheUsrDic();
		//释放分词组件资源
		testICTCLAS50.ICTCLAS_Exit();
	}
	catch (Exception ex)
	{
	}
} } [/code]

编译、运行此程序,分词结果如下。


其中,分词的词性标注是可选的,词性标注的含义在Doc目录下的文档中有详细说明。

2.Lucene

在Lucene中起到文本分析作用的类是Analyzer,Lucene中自带的不同Analyzer子类具有不同的分词功能。在较新的Lucene版本中(我使用的是3.0.3),Lucene自带的smartChineseAnalyzer是基于中科院分词系统实现的,中文分词效果比较好,已经能满足一般的中文分词需要。但是它不具备ICTCLAS原有的词性标注功能,如果想使用ICTCLAS的完整功能,则需要基于ICTCLAS编写自己的Analyzer子类。

ICTCLAS官网上有一个编写Analyzer子类的程序示例,地址如下:

给Lucene加入性能更好的中文分词

另外,我的同学cjy写了一个更为完整的Analyzer子类,可以参考,源代码下载地址为:

将中科院分词系统ICTCLAS应用到Lucene中的Analyzer源代码

 
 

Published: 08 Aug 2011

睡前读书时刻

  相比睡前上网和看电影,我还是更喜欢捧一本书读上半小时。看的书种类不定,但这一段时间我突然体会到,每天最后时刻要读的不应该再是功利性质的书,在这珍贵的时间里,应该读一读能让人安静下来,思考和领悟更接近人生本质的东西。关于时间,生死,回忆,宇宙,自我……大概思考这类终极的问题时人最容易抛弃日间凡事的纷扰,心中想着这些,并没有对过去的追悔,对现在的焦虑,对未来的担忧。也会抛弃了种种自傲自卑的心理,虚伪荒诞的想法。这种静静的状态对着电脑屏幕是得不到的——那只会让你更浮躁。不需要总结什么,计划什么,体会到那种单纯的状态,会觉得一切都是美好的。

近来读的两本书都很符合我的要求,《预约死亡》和《灵魂只能独行》。

睡前读书的那段时光,是每一天最好的结束。

PS:上面的这些文字写于两个月前,现在读来,觉得追求宁静固然是养心的好方法,然而”抛弃日间凡事的纷扰”只是暂时忘记了而已,如果不能真的把道理想通、把事情解决,这些问题迟早会浮现,那时宁静也就无从寻找了。毕竟只有佛才通过顿悟抛弃了烦恼,凡夫俗子终究要面对现实生活。所以,在执着和超脱,世事和宁静间寻求平衡才更应该追求。

Published: 06 Aug 2011

Lucene的重要基本类总结

  为了复习Lucene,今晚读了Lucene in Action英文第二版的第一章。发现读英文技术书并没有我想的那么困难,以前因为效率原因总是优先选择读翻译的内容,因为这个第二版还没有中文版本,转读原版,竟然读出点感觉来。

  这里翻译部分书中内容,总结Lucene里重要的类,即书中第一章的主要内容。这些类是整个Lucene的基础。

   核心类包括索引类和搜索类。

核心索引类


IndexWriter-一个对象,可以使你写入索引但是不能读或者搜索索引。它把索引存在Directory中。

Directory:存放索引的地方。IndexWriter只能索引分成单个词的文本——使用analyzer。

Analyzer:负责从文本抽取词项的抽象类;去掉停用词;转换大小写……。分析过程需要一个文件,它包含了各个需要被索引的域。

Document:一个域的集合。

Field:域Field是一个保存需要索引的文本内容的类,由名称和对应值,一些选项组成。

核心搜索类


IndexSearcher:是一个将索引以只读模式打开的类。提供一些搜索方法。

Term:用于搜索的基本单元。和field类似,包含一个域的名称和域的文本内容。在搜索时,组合Term对象以和TermQuery一起使用。

Query:Lucene有一些具体的Query子类,它提供一些使用的方法,如setBoost。TermQuery是复杂查询的组成构件。

TermQuery:Query的子类,最简单的查询类型之一,用于匹配包含具有制定值的域的文件。

TopDocs:是包含排名最前的N个搜索结果指针的容器。存储了文件编号和分数值。

Published: 07 Jul 2011

Book review:《激荡三十年》

读那些反映改革开放历史的书总能让人有种历史激荡、心潮澎湃的感觉,《平凡的世界》、《大江东去》都畅快淋漓的描写了打破僵化体制、用努力改变命运的故事,显示出一种旺盛勃发的生命力。吴晓波的《激荡三十年》回顾了这段历史中的中国企业,相比小说,这本书更富有学术和历史的观点,却也不乏生动的故事和人物。正如央视纪录片《公司的力量》所强调的,”你能看到多远的过去,就能看到多远的未来”,这本书不仅是在梳理过去,同样能帮助我们理解当今和未来的中国。

简单地记录我的几点困惑和感想:

一、产权问题

三十年企业史中,产权一直困扰着许多企业,这也是本书一直在论述的问题,但我还是没有深刻的理解它。上学期的一门政治课上,老师在最后时间也谈到了这个问题,由于时间所限没有展开分析,令人遗憾。从他的只言片语感觉到,产权问题牵涉了太多的复杂利益,我们所看到的可能只是表象。也许要进一步理解,需要从理论基础和现实问题两方面入手,并不简单。产权看上去是个理论问题,然而现实中,许多事情的根源正来自于此。

二、互联网企业

令我意外的是,作者对互联网企业有着独特的评价。吴晓波认为,如果中国能诞生真正伟大的企业,互联网是最有希望的行业。除此之外,另一个观点也让人印象深刻:

"在中国进行了15年的变革之后,世界把他的左脚踏进了互联网的河流之中,在这个意义上,中国是幸运的。"

互联网并不只是一种通信技术,它所影响的太多。

三、该学习什么?

走马观花的通读了全书,感到自己的知识储备还是薄弱。除了上面的产权,与证券相关的事件、税制问题等读完也只能说是略知一二。不谋全局,不足以谋一域,我一直觉得要想更多的了解世界和自己的国家,了解社会的发展规律,需要从原理层面去学习和思考,不能总是就事论事,在纷繁的现象层面停留。不过说到对这些问题的学习,该读些什么,本身就是个问题,因为在你有足够深刻的洞察力之前不容易知道哪些观点是相对客观,哪些观点带有自身目的。交些学费大概是免不了的吧。

后记:

读完后本来不想写评论,因为自己并没有新鲜的、有价值的观点。就像上面写的,问题更多一些。不过我还是不要太追求完美——这样容易使人畏难而不断拖延。先把第一感受记录下来,以后倘有机会再完善。

不要忌惮于暴露自己某些时候、某些方面的无知与浅薄,这可能是进步的源头。因为追求完美而选择拖延,不如降低要求,开始再说。

对这三十年感兴趣的读者,可以把此书和《大江东去》对照阅读,能对历史有多角度的了解。

Published: 04 May 2011

Lucene Demo中的编码问题

使用Lucene自带的示例程序lucene-demos-3.0.3.jar时,发现其中的索引程序IndexHTML.java索引一些网页时会报错:

Parse Aborted: Lexical error at line 63, column 16.

Encountered: "\u987b" (39035), after : ""

出错的地方都是HTML标签中Unicode编码的中文字符处。

经过一些搜索和试验,解决办法如下:

1. (见http://www.wenhq.com/article/view_448.html

第一:先下载一个javacc

第二:修改HtmlParser.jj文件的

options { IGNORE_CASE = true; STATIC = false;} 为:
options { IGNORE_CASE = true; STATIC = false; UNICODE_INPUT=true;}

第三:运行javacc HtmlParser.jj

第四:把产生出来的java文件覆盖JavaCC HTML Parser 的源文件

除了修改HtmlParse.jj外,还做了如下两处修改:

2.(见http://blog.eood.cn/lucene%E5%A6%82%E4%BD%95%E7%B4%A2%E5%BC%95utf-8%E6%A0%BC%E5%BC%8F%E6%96%87%E4%BB%B6

在IndexHtml.java文件中,

HTMLParser parser = new HTMLParser(fis);
改为:
HTMLParser parser = new HTMLParser(fis,"utf-8");

3.修改HTMLParser.java。

public Reader getReader() throws IOException {}中,
pipeIn = new InputStreamReader(pipeInStream, "UTF-16BE");
pipeOut = new OutputStreamWriter(pipeOutStream, "UTF-16BE");
将上面两行原来的编码都换为UTF-8。

完成上面的修改后,把java文件都编译为class文件,重新打包。

注意打包时,应该切换到/demo路径下,即此时在文件夹窗口可以看到的应该是org文件夹。

打包命令是:

jar cvf lucene-demos-3.0.3.jar org

完成上述修改后就可以使用新的jar包进行文件索引操作。

Published: 26 Apr 2011