1. 有一个给定的字符串s和一个字符串数组a，字符串s的长度和字符串数组a的维数相同。要完成的操作是向右移动字符串数组a中的各个字符串，使得在数组a中的某一列上出现给定的字符串s，要求给出最小的移动次数，如果不能达到这个要求，则返回-1。例如：s = "TOP",a[] = {"AT","SOSO","PSP"},结果讲返回1，因为只需要讲“PSP”右移一位即可。

2.给定两个字符串a,b，并且规定a比b长，且a中的字符包含b中的字符，a,b中的字符均为1~9的字符。要求在a中删除b中出现的每一个字符，给出删除所有字符后得到的最大的数。例如a = "15235", b = "135",这样从a中删除b之后，可以得到“52“和"25"，所以返回52

思路：因为最后要得到的整数为|a| - |b|位，要使该数最大，所以必须保证留下的数大的尽量在高位。所以采用贪心算法，依次选取从高位到低位的数，并且保证每个位置上的数都是能保留下的数中最大的。

关键点：首先将a中的数按照从大到小进行排列，相同的数位置靠前的数仍然排在前面，并且记录该数的位置。这样在生成最后的整数时，每次挑选当前队列中最大的数，而这个最大的数能否保留，则需要保证该位置前面的数都能被删掉，并且当前这个数能够被保留（也就是说如果要求被删除的数中如果有这个数的话，这个数在改位置后的串中还能找到）。如果该条件能够保证，则取出这个数，否则，检查队列中的下一个数...

[概念]：所谓的disjoint sets，也就是两个集合A和B不存在共同的元素，或者就是A和B的交集为空。disjoint sets可以用来计算无向图中的连通分量。

[基本操作] 

1. MakeSet(x):创建一个单元素的集合{x}，保证x没有出现在其他的集合中，并将该集合的leader设为自己。（每个集合只有唯一的leader）
2. Find(x): 找到x所在集合的leader
3. Union(A,B): 合并两个集合A和B

[实现]

• Reverse Trees ：用树来表示集合。树的子结点有一条指向其父结点的边。表示如下：

    可以看到，当使用这种结构表示集合的时候，操作MakeSet是常数时间，而Find和Union（实际上也就是Find操作）操作取决于树的深度，如果能够保证合并结点的时候将深度浅的树作为深的树的子结点来插入，这样就总能保证树的深度是lg n的，所以相应的操作可以优化如下：

    其实上面的方法还可以利用path compression的方法进行进一步的优化，也就是在进行Find操作的时候，将一条路径上的所有结点都提升为leader的直接子结点。这样可以进一步的减少树的深度。

• Shallow Threaded Tree：使用Shallow Threaded Tree表示集合的时候，相当于在树之间进行穿线。每个结点都直接有指向leader的链接，结点之间通过next指针进行链接。这样Find操作时间为O(1),Union操作的时间取决于两个合并集合的大小。

    同样，为了使得union操作的时间降低，将size小的集合链接到size大的集合后边，这样来减少时间。这样各个操作就变成如下：

   经过上面的操作之后，每个不同的树就是图的一个连通分量，当然图的连通分量还可以通过一次DFS来实现。上述方法的具体复杂度分析可以见原文(Disjoint Set). 上述方法一般适用于无向图，对于计算有向图中的SCC可以使用kosaraju算法。

    一个将tex文件转化为html文件的工具，用的时候小折腾了一番。考虑到以后可能会用到，怕遇到的问题又忘记了，所以把过程记录一下。

(一)准备工作：因为latex2html是基于perl开发的工具，所以要保证系统已安装了perl。所以在使用latex2html之前，首先安装好perl，选择安装一个版本的active perl。另外对于tex中的图形和公式，需要借助一个NetPBM的图象的格式转换和简单编辑软件来实现图形的转化。（当然在这之前需要安装好CTEX-FULL）

(二)安装latex2html 下载latex2html可以到它的主页，它有很多版本，选择一个较新的版本就可以了，解压后运行文件夹下的config.bat文件就可以进行安装了。（安装之前可以修改一下prefs.pm文件里的$prefs{'PREFIX'}，当然也可以不用修改，到时候安装的文件都会以这个字串为前缀）。在运行config的过程中，在检测dvips版本时会停止，直接回车就行了。当这一步完成之后，会生成install.bat/pstoimg.bat/test.bat/texexpand.bat. 如果没有生成成功，要检查自己的tex软件是否安装的正确。接着就运行install.bat就会把一系列文件安装到刚才指定的文件下面。然后记得将那个文件下的bin和NetPBM的bin文件夹加入环境变量path。

(三)如何使用 在命令行下运行latex2html，会看到latex2html的一系列的参数，有点太多了，也没有仔细研究。有时间可以慢慢看看，贴一个我用到的参数吧。

latex2html -split 0 -lcase_tags -nonavigation -notop_navigation 
-auto_prefix -noinfo -image_type png -show_section_numbers -noaddress 
-numbered_footnotes your-paper.tex

这样就会创建一个your-paper的文件夹，下面是一些html文件，png文件和相应的css文件。点击index.html就可以看到转化好的html文件了。 在我使用的latex2html的版本中，转化的公式图片在底部都有一条黑线，网上查了一下好像是一个很普遍的问题，和版本用关系，我自己的解决方法就是用photoshop将图片下的黑线去掉了。：）

(四)进一步转化为满足XHTML1.0 strict标准 使用tidy工具进行转化

tidy -output your-paper-xhtml.html -indent -bare -asxhtml -latin1 your-paper.html

完了之后可以使用w3c的XHTML Validator进行验证，直到满足标准，这样你的大作就可以变成网上可以通行流传的版本了。：）

什么是doxygen呢？下面的介绍录自doxygen的网页：

“doxygen是一种用于C++、IDL（Corba、Microsoft和KDE-2 DCOP风格）和C的文档系统。它可以通过三种方式来帮助你：

1. 它可以从一组标有文档的源文件中生成在线文档浏览器（HTML格式），以及/或者离线参考手册（LATEX格式）。同时还支持生成RTF（MS-Word）、Postscript、超链接PDF、压缩HTML和UNIX man页面格式的输出。文档是从源文件中直接提取的，从而十分容易保持文档和源码的一致。

2. 可配置doxygen，用以从没有标注文档的源文件中提取代码结构。这对于要在大量源文件中快速地找到所需的东西来说是非常有用的。通过include依赖图、继承图和协作图等手段（它们都是自动生成的），可以使不同成分之间的关系可视化。

3. 你甚至还可以“滥用”doxygen，创建普通文档。”

---------------------------------------------------------------------------------------------------------------    在看到了上面的介绍之后，所以就忍不住的用了，因为正好也要看Lucene的代码。发现doxygen确实还是挺好用的。看代码很方便，并且类的结构和依赖关系一目了然。下面简单说一下我的使用经历：

１. doxgen -g <configfile>. 当然这里也可以不要参数configfile,default的值是Doxyfile。

2. 记下来就是配置Doxyfile里面的各个参数了，好像Doxygen也有图形化的界面，不过没有试过。其实配置Doxyfile里面的参数也挺简单的。它里面主要有这么几个类别的设置：

• 工程相关的配置选项（Project Related Configuration Options）
• 构造相关的配置选项（Build Related Cofiguration Options）
• 警告和进度消息相关的配置选项（Configuration Related to Warning and Progress Message）
• 输入文件的配置选项 （Configuration Related to Input Files）
• 源代码浏览的配置选项（Configuration Related to Source Browsing）
• 字母序索引的配置选项（Configuration Related to Alphabetical Class Index）
• HTML输出的配置选项 （Configuration Related to HTML Output）
• PDF输出的配置选项 (Configuration Related to PDF Output)
• RTF输出的配置选贤 (Configuration Related to RTF Output)
• ......................... (Skip)

上面是常用到的需要配置的选项，其实在很多的类别中只需要使用默认的值就可以了。真正需要自己去修改的配置不是很多。有些选型也是要根据自己的实际需求去设置的。常用的一些设置有下面一些：

• PROJECT_NAME
• *OUTPUT_DIRECTORY （输出的文件夹）
• OUTPUT_LANGUAGE   (可以支持中文的，另它等与Chinese就好了)
• *INPUT                    （源所在位置）
• *INPUT_PATTERNS      (要产生文档的文件类型，e.g.  *.java / *.c / *.cpp)
• RECURSIVE
• SOURCE_BROWSER      （能够直接查看源代码）
• SEARCHENGINE          （是否提供搜索）

一般将上面的几个选项设置好之后，就能够生成令人满意的文档了。默认的情况下，它除了生成html外还会生成tex文件。但一般html就很够用了，呵呵！上面的*是必须要填写的。填完上面的配置文件，保存！

3. doxgen就OK了，它会去找文件名默认为Doxyfile的配置文件。和Makefile原理一样。

接下来就是好好看代码了，：）    

转载连接：http://www.chedong.com/tech/lucene.html  作者：车东

Lucene是一个基于Java的全文索引工具包。

1. 基于Java的全文索引引擎Lucene简介：关于作者和Lucene的历史
2. 全文检索的实现：Luene全文索引和数据库索引的比较
3. 中文切分词机制简介：基于词库和自动切分词算法的比较
4. 具体的安装和使用简介：系统结构介绍和演示
5. Hacking Lucene：简化的查询分析器，删除的实现，定制的排序，应用接口的扩展
6. 从Lucene我们还可以学到什么

基于Java的全文索引/检索引擎——Lucene

Lucene不是一个完整的全文索引应用，而是是一个用Java写的全文索引引擎工具包，它可以方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。

Lucene的作者：Lucene的贡献者Doug Cutting是一位资深全文索引/检索专家，曾经是V-Twin搜索引擎(Apple的Copland操作系统的成就之一)的主要开发者，后在Excite担任高级系统架构设计师，目前从事于一些INTERNET底层架构的研究。他贡献出的Lucene的目标是为各种中小型应用程序加入全文检索功能。

Lucene的发展历程：早先发布在作者自己的www.lucene.com，后来发布在SourceForge，2001年年底成为APACHE基金会jakarta的一个子项目：http://jakarta.apache.org/lucene/

已经有很多Java项目都使用了Lucene作为其后台的全文索引引擎，比较著名的有：

• Jive：WEB论坛系统；
• Eyebrows：邮件列表HTML归档/浏览/查询系统，本文的主要参考文档“TheLucene search engine: Powerful, flexible, and free”作者就是EyeBrows系统的主要开发者之一，而EyeBrows已经成为目前APACHE项目的主要邮件列表归档系统。
• Cocoon:基于XML的web发布框架，全文检索部分使用了Lucene

• Eclipse:基于Java的开放开发平台，帮助部分的全文索引使用了Lucene

对于中文用户来说，最关心的问题是其是否支持中文的全文检索。但通过后面对于Lucene的结构的介绍，你会了解到由于Lucene良好架构设计，对中文的支持只需对其语言词法分析接口进行扩展就能实现对中文检索的支持。

全文检索的实现机制

Lucene的API接口设计的比较通用，输入输出结构都很像数据库的表==>记录==>字段，所以很多传统的应用的文件、数据库等都可以比较方便的映射到Lucene的存储结构/接口中。总体上看：可以先把Lucene当成一个支持全文索引的数据库系统。

比较一下Lucene和数据库：

全文检索 ≠ like "%keyword%"

通常比较厚的书籍后面常常附关键词索引表（比如：北京：12, 34页，上海：3,77页……），它能够帮助读者比较快地找到相关内容的页码。而数据库索引能够大大提高查询的速度原理也是一样，想像一下通过书后面的索引查找的速度要比一页一页地翻内容高多少倍……而索引之所以效率高，另外一个原因是它是排好序的。对于检索系统来说核心是一个排序问题。

由于数据库索引不是为全文索引设计的，因此，使用like "%keyword%"时，数据库索引是不起作用的，在使用like查询时，搜索过程又变成类似于一页页翻书的遍历过程了，所以对于含有模糊查询的数据库服务来说，LIKE对性能的危害是极大的。如果是需要对多个关键词进行模糊匹配：like"%keyword1%" and like "%keyword2%" ...其效率也就可想而知了。

所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制，将数据源（比如多篇文章）排序顺序存储的同时，有另外一个排好序的关键词列表，用于存储关键词==>文章映射关系，利用这样的映射关系索引：[关键词==>出现关键词的文章编号，出现次数（甚至包括位置：起始偏移量，结束偏移量），出现频率]，检索过程就是把模糊查询变成多个可以利用索引的精确查询的逻辑组合的过程。从而大大提高了多关键词查询的效率，所以，全文检索问题归结到最后是一个排序问题。

由此可以看出模糊查询相对数据库的精确查询是一个非常不确定的问题，这也是大部分数据库对全文检索支持有限的原因。Lucene最核心的特征是通过特殊的索引结构实现了传统数据库不擅长的全文索引机制，并提供了扩展接口，以方便针对不同应用的定制。

可以通过一下表格对比一下数据库的模糊查询：

全文检索和数据库应用最大的不同在于：让最相关的头100条结果满足98%以上用户的需求
Lucene的创新之处：

大部分的搜索（数据库）引擎都是用B树结构来维护索引，索引的更新会导致大量的IO操作，Lucene在实现中，对此稍微有所改进：不是维护一个索引文件，而是在扩展索引的时候不断创建新的索引文件，然后定期的把这些新的小索引文件合并到原先的大索引中（针对不同的更新策略，批次的大小可以调整），这样在不影响检索的效率的前提下，提高了索引的效率。

Lucene和其他一些全文检索系统/应用的比较：

关于亚洲语言的的切分词问题(Word Segment)

对于中文来说，全文索引首先还要解决一个语言分析的问题，对于英文来说，语句中单词之间是天然通过空格分开的，但亚洲语言的中日韩文语句中的字是一个字挨一个，所有，首先要把语句中按“词”进行索引的话，这个词如何切分出来就是一个很大的问题。

首先，肯定不能用单个字符作(si-gram)为索引单元，否则查“上海”时，不能让含有“海上”也匹配。

但一句话：“北京天安门”，计算机如何按照中文的语言习惯进行切分呢？
“北京 天安门” 还是“北 京 天安门”？让计算机能够按照语言习惯进行切分，往往需要机器有一个比较丰富的词库才能够比较准确的识别出语句中的单词。

另外一个解决的办法是采用自动切分算法：将单词按照2元语法(bigram)方式切分出来，比如：
"北京天安门" ==> "北京 京天 天安 安门"。

这样，在查询的时候，无论是查询"北京" 还是查询"天安门"，将查询词组按同样的规则进行切分："北京"，"天安安门"，多个关键词之间按与"and"的关系组合，同样能够正确地映射到相应的索引中。这种方式对于其他亚洲语言：韩文，日文都是通用的。

基于自动切分的最大优点是没有词表维护成本，实现简单，缺点是索引效率低，但对于中小型应用来说，基于2元语法的切分还是够用的。基于2元切分后的索引一般大小和源文件差不多，而对于英文，索引文件一般只有原文件的30%-40%不同，

目前比较大的搜索引擎的语言分析算法一般是基于以上2个机制的结合。关于中文的语言分析算法，大家可以在Google查关键词"wordsegment search"能找到更多相关的资料。

安装和使用

下载：http://jakarta.apache.org/lucene/

注意：Lucene中的一些比较复杂的词法分析是用JavaCC生成的（JavaCC：JavaCompilerCompiler，纯Java的词法分析生成器），所以如果从源代码编译或需要修改其中的QueryParser、定制自己的词法分析器，还需要从https://javacc.dev.java.net/下载javacc。

lucene的组成结构：对于外部应用来说索引模块(index)和检索模块(search)是主要的外部应用入口

简单的例子演示一下Lucene的使用方法：

索引过程：从命令行读取文件名（多个），将文件分路径(path字段)和内容(body字段)2个字段进行存储，并对内容进行全文索引：索引的单位是Document对象，每个Document对象包含多个字段Field对象，针对不同的字段属性和数据输出的需求，对字段还可以选择不同的索引/存储字段规则，列表如下：

public class IndexFiles { 
  //使用方法：: IndexFiles [索引输出目录] [索引的文件列表] ... 
  public static void main(String[] args) throws Exception {
    String indexPath = args[0];
    IndexWriter writer;
    //用指定的语言分析器构造一个新的写索引器（第3个参数表示是否为追加索引）
    writer = new IndexWriter(indexPath, new SimpleAnalyzer(), false);

    for (int i=1; i<args.length; i++) {
      System.out.println("Indexing file " + args[i]);
      InputStream is = new FileInputStream(args[i]);

      //构造包含2个字段Field的Document对象
      //一个是路径path字段，不索引，只存储
      //一个是内容body字段，进行全文索引，并存储
      Document doc = new Document();
      doc.add(Field.UnIndexed("path", args[i]));
      doc.add(Field.Text("body", (Reader) new InputStreamReader(is)));
      //将文档写入索引
      writer.addDocument(doc);
      is.close();
    };
    //关闭写索引器
    writer.close();
  }
}
　

索引过程中可以看到：

• 语言分析器提供了抽象的接口，因此语言分析(Analyser)是可以定制的，虽然lucene缺省提供了2个比较通用的分析器SimpleAnalyser和StandardAnalyser，这2个分析器缺省都不支持中文，所以要加入对中文语言的切分规则，需要修改这2个分析器。
• Lucene并没有规定数据源的格式，而只提供了一个通用的结构（Document对象）来接受索引的输入，因此输入的数据源可以是：数据库，WORD文档，PDF文档，HTML文档……只要能够设计相应的解析转换器将数据源构造成成Docuement对象即可进行索引。
• 对于大批量的数据索引，还可以通过调整IndexerWrite的文件合并频率属性（mergeFactor）来提高批量索引的效率。

检索过程和结果显示：

搜索结果返回的是Hits对象，可以通过它再访问Document==>Field中的内容。

假设根据body字段进行全文检索，可以将查询结果的path字段和相应查询的匹配度(score)打印出来，

public class Search { 
  public static void main(String[] args) throws Exception {
    String indexPath = args[0], queryString = args[1];
    //指向索引目录的搜索器
    Searcher searcher = new IndexSearcher(indexPath);
    //查询解析器：使用和索引同样的语言分析器
    Query query = QueryParser.parse(queryString, "body", 
                              new SimpleAnalyzer());
    //搜索结果使用Hits存储
    Hits hits = searcher.search(query);
    //通过hits可以访问到相应字段的数据和查询的匹配度
    for (int i=0; i<hits.length(); i++) {
      System.out.println(hits.doc(i).get("path") + "; Score: " + 
                         hits.score(i));
    };
  }
}

Hacking Lucene

简化的查询分析器

个人感觉lucene成为JAKARTA项目后，画在了太多的时间用于调试日趋复杂QueryParser，而其中大部分是大多数用户并不很熟悉的，目前LUCENE支持的语法：

Query ::= ( Clause )*
Clause ::= ["+", "-"] [<TERM> ":"] ( <TERM> | "(" Query ")")

中间的逻辑包括：and or + - &&||等符号，而且还有"短语查询"和针对西文的前缀/模糊查询等，个人感觉对于一般应用来说，这些功能有一些华而不实，其实能够实现目前类似于Google的查询语句分析功能其实对于大多数用户来说已经够了。所以，Lucene早期版本的QueryParser仍是比较好的选择。

添加修改删除指定记录（Document）

Lucene提供了索引的扩展机制，因此索引的动态扩展应该是没有问题的，而指定记录的修改也似乎只能通过记录的删除，然后重新加入实现。如何删除指定的记录呢？删除的方法也很简单，只是需要在索引时根据数据源中的记录ID专门另建索引，然后利用IndexReader.delete(Termterm)方法通过这个记录ID删除相应的Document。

根据某个字段值的排序功能

lucene缺省是按照自己的相关度算法（score）进行结果排序的，但能够根据其他字段进行结果排序是一个在LUCENE的开发邮件列表中经常提到的问题，很多原先基于数据库应用都需要除了基于匹配度（score）以外的排序功能。而从全文检索的原理我们可以了解到，任何不基于索引的搜索过程效率都会导致效率非常的低，如果基于其他字段的排序需要在搜索过程中访问存储字段，速度回大大降低，因此非常是不可取的。

但这里也有一个折中的解决方法：在搜索过程中能够影响排序结果的只有索引中已经存储的docID和score这2个参数，所以，基于score以外的排序，其实可以通过将数据源预先排好序，然后根据docID进行排序来实现。这样就避免了在LUCENE搜索结果外对结果再次进行排序和在搜索过程中访问不在索引中的某个字段值。

这里需要修改的是IndexSearcher中的HitCollector过程：

...
　scorer.score(new HitCollector() {
	private float minScore = 0.0f;
	public final void collect(int doc, float score) {
	  if (score > 0.0f &&			  // ignore zeroed buckets
	      (bits==null || bits.get(doc))) {	  // skip docs not in bits
	    totalHits[0]++;
	    if (score >= minScore) {
              /* 原先：Lucene将docID和相应的匹配度score例入结果命中列表中：
	       * hq.put(new ScoreDoc(doc, score));	  // update hit queue
               * 如果用doc 或 1/doc 代替 score，就实现了根据docID顺排或逆排
               * 假设数据源索引时已经按照某个字段排好了序，而结果根据docID排序也就实现了
               * 针对某个字段的排序，甚至可以实现更复杂的score和docID的拟合。
               */
              hq.put(new ScoreDoc(doc, (float) 1/doc )); 
	      if (hq.size() > nDocs) {		  // if hit queue overfull
		hq.pop();			  // remove lowest in hit queue
		minScore = ((ScoreDoc)hq.top()).score; // reset minScore
	      }
	    }
	  }
	}
      }, reader.maxDoc());

更通用的输入输出接口

虽然lucene没有定义一个确定的输入文档格式，但越来越多的人想到使用一个标准的中间格式作为Lucene的数据导入接口，然后其他数据，比如PDF只需要通过解析器转换成标准的中间格式就可以进行数据索引了。这个中间格式主要以XML为主，类似实现已经不下4，5个：

数据源: WORD       PDF     HTML    DB       other
         \          |       |      |         /
                       XML中间格式
                            |
                     Lucene INDEX

目前还没有针对MSWord文档的解析器，因为Word文档和基于ASCII的RTF文档不同，需要使用COM对象机制解析。这个是我在Google上查的相关资料：http://www.intrinsyc.com/products/enterprise_applications.asp
另外一个办法就是把Word文档转换成text：http://www.winfield.demon.nl/index.html

索引过程优化

索引一般分2种情况，一种是小批量的索引扩展，一种是大批量的索引重建。在索引过程中，并不是每次新的DOC加入进去索引都重新进行一次索引文件的写入操作（文件I/O是一件非常消耗资源的事情）。

Lucene先在内存中进行索引操作，并根据一定的批量进行文件的写入。这个批次的间隔越大，文件的写入次数越少，但占用内存会很多。反之占用内存少，但文件IO操作频繁，索引速度会很慢。在IndexWriter中有一个MERGE_FACTOR参数可以帮助你在构造索引器后根据应用环境的情况充分利用内存减少文件的操作。根据我的使用经验：缺省Indexer是每20条记录索引后写入一次，每将MERGE_FACTOR增加50倍，索引速度可以提高1倍左右。

搜索过程优化

lucene支持内存索引：这样的搜索比基于文件的I/O有数量级的速度提升。
http://www.onjava.com/lpt/a/3273
而尽可能减少IndexSearcher的创建和对搜索结果的前台的缓存也是必要的。

Lucene面向全文检索的优化在于首次索引检索后，并不把所有的记录（Document）具体内容读取出来，而起只将所有结果中匹配度最高的头100条结果（TopDocs）的ID放到结果集缓存中并返回，这里可以比较一下数据库检索：如果是一个10,000条的数据库检索结果集，数据库是一定要把所有记录内容都取得以后再开始返回给应用结果集的。所以即使检索匹配总数很多，Lucene的结果集占用的内存空间也不会很多。对于一般的模糊检索应用是用不到这么多的结果的，头100条已经可以满足90%以上的检索需求。

如果首批缓存结果数用完后还要读取更后面的结果时Searcher会再次检索并生成一个上次的搜索缓存数大1倍的缓存，并再重新向后抓取。所以如果构造一个Searcher去查1－120条结果，Searcher其实是进行了2次搜索过程：头100条取完后，缓存结果用完，Searcher重新检索再构造一个200条的结果缓存，依此类推，400条缓存，800条缓存。由于每次Searcher对象消失后，这些缓存也访问那不到了，你有可能想将结果记录缓存下来，缓存数尽量保证在100以下以充分利用首次的结果缓存，不让Lucene浪费多次检索，而且可以分级进行结果缓存。

Lucene的另外一个特点是在收集结果的过程中将匹配度低的结果自动过滤掉了。这也是和数据库应用需要将搜索的结果全部返回不同之处。

我的一些尝试：

• 支持中文的Tokenizer：这里有2个版本，一个是通过JavaCC生成的，对CJK部分按一个字符一个TOKEN索引，另外一个是从SimpleTokenizer改写的，对英文支持数字和字母TOKEN，对中文按迭代索引。
• 基于XML数据源的索引器：XMLIndexer，因此所有数据源只要能够按照DTD转换成指定的XML，就可以用XMLIndxer进行索引了。
• 根据某个字段排序：按记录索引顺序排序结果的搜索器：IndexOrderSearcher，因此如果需要让搜索结果根据某个字段排序，可以让数据源先按某个字段排好序（比如：PriceField），这样索引后，然后在利用这个按记录的ID顺序检索的搜索器，结果就是相当于是那个字段排序的结果了。

从Lucene学到更多

Luene的确是一个面对对象设计的典范

• 所有的问题都通过一个额外抽象层来方便以后的扩展和重用：你可以通过重新实现来达到自己的目的，而对其他模块而不需要；
• 简单的应用入口Searcher, Indexer，并调用底层一系列组件协同的完成搜索任务；
• 所有的对象的任务都非常专一：比如搜索过程：QueryParser分析将查询语句转换成一系列的精确查询的组合(Query),通过底层的索引读取结构IndexReader进行索引的读取，并用相应的打分器给搜索结果进行打分/排序等。所有的功能模块原子化程度非常高，因此可以通过重新实现而不需要修改其他模块。 
• 除了灵活的应用接口设计，Lucene还提供了一些适合大多数应用的语言分析器实现（SimpleAnalyser,StandardAnalyser），这也是新用户能够很快上手的重要原因之一。

这些优点都是非常值得在以后的开发中学习借鉴的。作为一个通用工具包，Lunece的确给予了需要将全文检索功能嵌入到应用中的开发者很多的便利。

此外，通过对Lucene的学习和使用，我也更深刻地理解了为什么很多数据库优化设计中要求，比如：

• 尽可能对字段进行索引来提高查询速度，但过多的索引会对数据库表的更新操作变慢，而对结果过多的排序条件，实际上往往也是性能的杀手之一。
• 很多商业数据库对大批量的数据插入操作会提供一些优化参数，这个作用和索引器的merge_factor的作用是类似的，
• 20%/80%原则：查的结果多并不等于质量好，尤其对于返回结果集很大，如何优化这头几十条结果的质量往往才是最重要的。
• 尽可能让应用从数据库中获得比较小的结果集，因为即使对于大型数据库，对结果集的随机访问也是一个非常消耗资源的操作。

字符集和编码 (一)

     现在的记忆力还真是不行，回家前听pb老师讲了关于字符集和编码的相关的问题时觉得有种

查。唉~，真是应了好记性不如烂笔头，何况现在记忆力是江河日下，所以还是系统的将字符和

编码的问题写下来加强一下记忆。

     字符和编码一直是编程和文本处理的时候不得不面临的问题。而字符和编码也是这个问题不

同的两个方面：

字符：很好理解，就是我们用来表情达意的符号。而可以想象，全世界人们使用的

符号不尽相同，并且不同符号的使用频率也不相同。所以就存在确定一个字符集的问题。

编码：则更多考虑的是字符的存储和传输方面的问题，需要对一个给定的字符集中的字符进行一

定方法 的编码以便能有效地表示各个字符。而编码上我们通常又会听到内码和外码一说。简单说来，

内码是汉字在计算机内部存储，处理和传输用的信息编码。它必须与ASCII码兼容但又不能冲突。

外码汉字的输入码称为"外码"。输入码即指我们输入汉字时使用的编码。常见的外码分为数字编码(如区位码)，

拼音编码和字形编码(如五笔)。  下面提到的编码都是指内码。接下来就以“纪传体”的方式对

常见的字符和编码进行介绍。

1. ASCII码

ASCII码应该是大家最熟悉也是最为简单的字符集。它是由美国国家标准局(ANSI)制定的。

ASCII码（American Standard Code for Information Interchange，美国标准信息交换码），它已被国际

标准化组织（ISO）定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母，ASCII码有7位码和8位码

两种形式。7位ASCII码是用七位二进制数进行编码的，可以表示128个字符。
在计算机的存储单元中，一个ASCII码值占一个字节(8个二进制位)，其最高位(b7)用作奇偶校验位。所谓奇偶校验，

是指在代码传送过程中用来检验是否出现错误的一种方法，一般分奇校验和偶校验两种。

奇校验规定：正确的代码一个字节中1的个数必须是奇数，若非奇数，则在最高位b7添1；

偶校验规定：正确的代码一个字节中1的个数必须是偶数，若非偶数，则在最高位b7添1。

2. GBK, GB2312, Big5, CJK, HZ等

GB2312 & GBK

为了处理汉字，程序员设计了用于简体中文的GB2312和用于繁体中文的big5。
GB2312(1980年)一共收录了7445个字符，包括6763个汉字和682个其它符号。汉字区的内码范围

高字节从B0-F7，低字节从A1-FE，占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。
GB2312支持的汉字太少。1995年的汉字扩展规范GBK1.0收录了21886个符号，它分为汉字区和图形符号区。

汉字区包括21003个字符。2000年的GB18030是取代GBK1.0的正式国家标准。该标准收录了27484个汉字，

同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字。现在的PC平台必须支持GB18030，对嵌入式产品

暂不作要求。所以手机、MP3一般只支持GB2312。
从ASCII、GB2312、GBK到GB18030，这些编码方法是向下兼容的，即同一个字符在这些方案中总是有相同

的编码，后面的标准支持更多的字符。在这些编码中，英文和中文可以统一地处理。区分中文编码的方法是高

字节的最高位不为0。按照程序员的称呼，GB2312、GBK到GB18030都属于双字节字符集 (DBCS)。
有的中文Windows的缺省内码还是GBK，可以通过GB18030升级包升级到GB18030。不过GB18030相对GBK

增加的字符，普通人是很难用到的，通常我们还是用GBK指代中文Windows内码。 

Notes: 
GB2312的原文还是区位码，从区位码到内码，需要在高字节和低字节上分别加上A0。
在DBCS中，GB内码的存储格式始终是big endian，即高位在前。 GB2312的两个字节的最高位都是1。但符合

这个条件的码位只有128*128=16384个。所以GBK和GB18030的低字节最高位都可能不是1。不过这不影响

DBCS字符流的解析：在读取DBCS字符流时，只要遇到高位为1的字节，就可以将下两个字节作为一个双字节

编码，而不用管低字节的高位是什么。

BIG5

大五码（Big5），又称为五大码，是使用繁体中文字社群中最常用的电脑汉字字符集标准，共收录13,060个中文字，

其中有二字为重覆编码。Big5常用于台湾、香港和澳门等使用繁体中文的地区。在1990年代初期，当中华人民共和国

的电邮和转码软件还未普遍之时，在深圳的港商和台商公司亦曾经使用Big5系统，以方便与总部的文件交流、以及避免

为中国的办公室再写一套不同内码的系统。在Big5码诞生後，大部分台湾的电脑软体都使用了Big5码。
历史及名称。
“五大码”(Big5) 是在1984年由中华民国财团法人资讯工业策进会和五间有意愿共同推动电脑中文化的资讯公司所共同创立，

故称五大码。此五间公司为：宏基、神通、佳佳、零壹及大众。“五大码”的英文名称“Big5”后来被人按英文字序译回中文，

以致现在有“五大码”和“大五码”两个中文名称。

CJK

CJK统一汉字编码字符集是完全等同于国际标准通用多八位编码字符集(UCS)。它其中最重要的也经常被采用的是其双字节形式

的基本多文种平面。在这65536个码位的空间中，定义了几乎所有国家或地区的语言文字和符号。其中从0x4E00到 0x9FA5

的连续区域包含了 20902 个来自中国（包括台湾）、日本、韩国的汉字，称为 CJK (Chinese Japanese Korean) 汉字。

CJK 是GB2312-80、BIG5等字符集的超集。

HZ

众所周知,国标码是一种基于简体汉字的双字节汉字编码,并在我国、新加坡等使用简体汉字的国家通行。国标字符集的基本

集(GB2312-80)共收录图形字符7445个(包括标点符号、数字、外文字母等,其中汉字6763个),这7000余个图形字符被排

列成一个94×94的方阵,每个汉字在这个方阵中的坐标被称为该汉字的区位码。由于美标ASCII图形字符的编码是从33到

126,汉字区、位码各加上32,就会与ASCII图形字符的码值重合,如"啊"字的区位码为(16,01),区、位码各加上32得(48,33),

把这两个数字的16进制数放在一起得(30,21),这就是该汉字的"国标码",而与其对应的两个ASCII图形字符0!,也就是该字的

"国标符"了。为了将汉字的国标码与ASCII码区分开,国标码在计算机内实现时是通过将两个国标符的码值各加上128,使其

高位变为"1"来实现的。采用这种方法,虽然将汉字与ASCII字符区分开了,但由于汉字文件各字节的高位均变成了1,采用国标

码编码的汉字文件就不再是标准的ASCII文本文件了,这种文件在Internet上用SMTP传输时很可能出现问题。因此,人们在

Internet上用E-mail传输国标码的汉字文件时,通常是用uuencode编码后再传输,到达目的地后再用uudecode解码阅读。

 为了解决国标码的汉字文件在Internet上传输不便的难题,海外的中国学者又设计了一种新的汉字编码———HZ码。HZ码

属双字节7位汉字编码,它以"国标"为基础,用两个ASCII图形符来表示一个汉字。HZ码与国标码的主要区别是将国标码的高位

还原为0,并通过在HZ码的前后分别加上"逃出码"(～{)和"选入码"(～})来将HZ码与ASCII码区分开。～{和～}里面为HZ码,

外面即为正常的ASCII码。采用这种编码的汉字文件不仅解决了中西文的区分、混排问题,而且从表面上看是一个标准的ASCII

文本文件,因而可以在Internet上自由传输,这就是HZ码在Internet上比较流行的一个重要原因。

3. UNICODE

Unicode（统一码、万国码、单一码）是一种在计算机上使用的字符编码。它为每种语言中的每个字符设定了统一并且

唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。1990年开始研发，1994年正式公布。随着计算

机工作能力的增强，Unicode也在面世以来的十多年里得到普及。
大概来说，Unicode 编码系统可分为编码方式和实现方式两个层次。

编码方式
Unicode 的编码方式与 ISO 10646 的通用字元集(亦称[通用字符集])（Universal Character Set，UCS）概念相对应，

目前的用于实用的 Unicode 版本对应于 UCS-2，使用16位的编码空间。也就是每个字符占用2个字节。这样理论上一共

最多可以表示 65,536(2的16次方) 个字符。基本满足各种语言的使用。实际上目前版本的 Unicode 尚未填充满这16位

编码，保留了大量空间作为特殊使用或将来扩展。
上述16位 Unicode 字符构成基本多文种平面（Basic Multilingual Plane, 简称 BMP）。最新（但未实际广泛使用）的

Unicode 版本定义了16个辅助平面，两者合起来至少需要占据21位的编码空间，比3字节略少。但事实上辅助平面字符

仍然占用4字节编码空间，与 UCS-4 保持一致。未来版本会扩充到 ISO 10646-1 实现级别3，即涵盖 UCS-4 的所有

字符。UCS-4 是一个更大的尚未填充完全的31位字符集，加上恒为0的首位，共需占据32位，即4字节。理论上最多能表示

2,147,483,648(2的31次方)个字符，完全可以涵盖一切语言所用的符号。

实现方式
Unicode 的实现方式不同于编码方式。一个字符的 Unicode 编码是确定的。但是在实际传输过程中，由于不同系统平台

的设计不一定一致，以及出于节省空间的目的，对 Unicode 编码的实现方式有所不同。Unicode 的实现方式称为Unicode

转换格式（Unicode Translation Format，简称为 UTF）。
例如，如果一个仅包含基本7位ASCII字符的 Unicode 文件，如果每个字符都使用2字节的原 Unicode 编码传输，其第一

字节的8位始终为0。这就造成了比较大的浪费。对于这种情况，可以使用 UTF-8 编码，这是一种变长编码，它将基本7位

ASCII字符仍用7位编码表示，占用一个字节（首位补0）。而遇到与其他 Unicode 字符混合的情况，将按一定算法转换，

每个字符使用1-3个字节编码，并利用首位为0或1进行识别。这样对以7位ASCII字符为主的西文文档就大大节省了编码长度

（具体方案参见UTF-8）。类似的，对未来会出现的需要4个字节的辅助平面字符和其他 UCS-4 扩充字符，2字节编码的

UTF-16 也需要通过一定的算法进行转换。
再如，如果直接使用与 Unicode 编码一致（仅限于 BMP 字符）的 UTF-16 编码，由于每个址都不相同，Macintosh机

和PC机上对字节顺序的理解是不一致的。这时同一字节流可能会被解释为不同内容，如编码为 U+594E 的字符“奎”同编码为

 U+4E59 的“乙”就可能发生混淆。于是在 UTF-16 编码实现方式中使用了大尾序（big-endian）、小尾序（little-endian）

的概念，以及BOM（Byte Order Mark）解决方案。（具体方案参见UTF-16）

此外 Unicode 的实现方式还包括 UTF-7、Punycode、CESU-8、SCSU、UTF-32等，这些实现方式有些仅在一定的国家

和地区使用，有些则属于未来的规划方式。目前通用的实现方式是 UTF-16小尾序（BOM）、UTF-16大尾序（BOM）和

 UTF-8。在微软公司Windows XP操作系统附带的记事本中，“另存为”对话框可以选择的四种编码方式除去非 Unicode

编码的 ANSI 外，其余三种“Unicode”、“Unicode big endian”和“UTF-8”即分别对应这三种实现方式。
                                                                                                                         (未完待续)

     MapReduce是Google开发的C++编程工具，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（化简）"，和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。 当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

     映射和化简简单说来，一个映射函数就是对一些独立元素组成的概念上的列表（例如，一个测试成绩的列表）的每一个元素进行指定的操作（比如前面的例子里，有人发现所有学生的成绩都被高估了一分，他可以定义一个“减一”的映射函数，用来修正这个错误。）。事实上，每个元素都是被独立操作的，而原始列表没有被更改，因为这里创建了一个新的列表来保存新的答案。这就是说，Map操作是可以高度并行的，这对高性能要求的应用以及并行计算领域的需求非常有用。 而化简操作指的是对一个列表的元素进行适当的合并（继续看前面的例子，如果有人想知道班级的平均分该怎么做？他可以定义一个化简函数，通过让列表中的元素跟自己的相邻的元素相加的方式把列表减半，如此递归运算直到列表只剩下一个元素，然后用这个元素除以人数，就得到了平均分。）。虽然他不如映射函数那么并行，但是因为化简总是有一个简单的答案，大规模的运算相对独立，所以化简函数在高度并行环境下也很有用。

     分布和可靠性 MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性；每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔，主节点（类同Google File System中的主服务器）记录下这个节点状态为死亡，并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的原子操作以确保不会发生并行线程间的冲突；当文件被改名的时候，系统可能会把他们复制到任务名以外的另一个名字上去。（避免副作用）。 化简操作工作方式很类似，但是由于化简操作在并行能力较差，主节点会尽量把化简操作调度在一个节点上，或者离需要操作的数据尽可能进的节点上了；这个特性可以满足Google的需求，因为他们有足够的带宽，他们的内部网络没有那么多的机器。

     MapReduce用在非常广泛的应用程序中，包括“分布grep，分布排序，web连接图反转，每台机器的词矢量，web访问日志分析，反向索引构建，文档聚类,机器学习，基于统计的机器翻译...”值得注意的是，MapReduce实现以后，它被用来重新生成Google的整个索引，并取代老的ad hoc程序去更新索引。 MapReduce会生成大量的临时文件，为了提高效率，它利用Google文件系统来管理和访问这些文件。

信息熵(Entropy )和互信息(Mutual Information)

信息熵

1948 年，香农提出了“信息熵”的概念，解决了对信息的量化度量问题。在信息论中，熵描述了一个随机变量的不确定性。信息的不确定性越大，则它对应的熵也就越大。熵的定义的形式化描述如下：

H(X) = － Sum(p(x)* log(p(x)))      （其中x为X所可能的取值）

其中X是一个取有限个值的随机变量，p(x)表示X某个值x的分布密度。而在信息论中，log的底数一般为2，此时熵的单位为比特。

熵有如下的一些基本的性质：

1．H(X) >= 0     (等号成立的条件是Ｘ是确定性变量)

2．H(X) <= log|X|  (等号成立的条件是X为等概分布)

除了可以定义一个随机变量的信息熵之外，还可以对多个变量定义相应的熵变量。

条件熵    H(X|Y) =   －Sum_x( Sum_y (p(x,y)*log(p(x|y))))         

                                                                     (其中x，y为对应变量X，Y的所有取值)        

联合熵   H(X,Y) =   －Sum_x( Sum_y (p(x,y)*log(p(x,y))))        

                                                                   (其中x，y为对应变量X，Y的所有取值)                   

互信息

互信息描述两个变量之间，一个变量中包含另外一个变量的信息。互信息的形式化描述为：

I(X;Y) = －Sum_x{ Sum_y {p(x,y)*(log(p(x,y) / p(x)*p(y)))}}

对于多个变量的信息熵和互信息有如下的一些基本性质：

1．I(X; Y) = H(X) — H(X|Y) = H(Y) — H(Y|X)

2．I(X; Y) = I(Y; X)

3．I(X; X) = H(X)

4．I(X; Y) >= 0

5．I(X; Y) <= H(X) & I(X; Y) <= H(Y)

6．I(X; Y) = H(X) + H(Y) — H(X, Y)

上面的这些性质可以由信息熵的定义和互信息的定义推导而出。并且由上面的一些性质可以知道，信息熵和互信息都有明确的上下界。

      由于不同的随机变量的信息熵变化很大，所以变量之间的互信息也有很大的不同，它是一个全局的定量表示。有时为了比较多个变量对之间的互信息的相互关系的时候，全局的互信息由于各自的熵不同，使其不具有可比较性，所以需要对其进行规格化，此时的互信息称作规格化的互信息(Normalized Mutual Information)。

规格化互信息

规格化互信息的形式化描述如下

I'(X;Y) = I(X;Y) / Max{I(X;X), I(Y;Y)}

同样，规格化的互信息也具有一些特殊的性质：

1．I'(X; Y) = I'(Y; X)

2． 0 <= (X; Y) <= 1

3． I'(X; Y) = Min{(H(X) - H(X|Y)) / H(X) , H(Y) - H(Y|X) /H(Y) }

信息熵和互信息具有很广泛的用途，信息熵可以用于研究噪音信道，语言模型，编码系统等。

也可以用于研究两个信息之间的相关性等。下面将介绍Mutual Information在挖掘相关模式(Correlated Pattern)中的运用。