* * * * * * * * * * * *
    全文搜索不是MySQL的LIKE %%，对于普通的数据库索引，LIKE %%几乎是无效的，全文索引的实际概念是有效地把文字拆成词，再对这些词做反向的索引，Lucene中这个叫做“倒排”，区别于传统索引的“这篇文章中有 什么词”，倒排实际上记录的是“这个词在哪些文章中出现”，搜索的时候实际就是把搜索字符串按照同样的规则再次拆分成词或非词单元，然后在索引中取出这些 词所在的文章号的并集（或交集）。比如有一个词“中国”，它的索引可能是这个样子：
    中国：1-25:12-84:37-90

    它的含义是“中国”这个词在1号文章的第25个字处、12号文章的第84字处、37号文章的第90字处出现。这就是一个包含位置信息的倒排索引。当用户搜 索“中国”的时候，引擎只要按照一定的规则定位到这条索引上，就可以迅速地取出“中国”出现的位置。然后它可以根据文章ID来到数据库或者其它上地方取出 一部分文章做摘要返回给用户，而不需要每篇文章都从头到尾遍历一次查找“中国”。

    基于这个概念，Lucene创建了非常有效的倒排索引，同时Lucene的索引是包含词频的。然而Lucene是基于“大索引”的，它实际上在维护一个大 的数据库，在创建索引的时候它也会创建一些小的索引，当小索引达到一定量的时候，Lucene会把它们合并在一起，也就是PHP Lucene缺少的Optimizer部分。

    BSM中的搜索部分依然使用倒排，不过不同于Lucene，我的实现方式是散列。当然它会导致不小的空间浪费，不过可以省去很多计算文件偏移量的麻烦。 BSM把索引打散成几乎无数个小的部分，每一个部分通过SQLite引擎来维护，处理这些小的数据表，SQLite是很拿手的。而且一个特定的Hash算 法可以一次就定位到文件，它的效率是很高的。

* * * * * * * * * * * *
    搜索的一个最重要的问题就是如何有效地拆分文字，西方的拉丁语系比较容易处理，因为它就是以词为单位的书写方式，比如英文，可以简单地通过空格、标点符 号、特殊字符完成有效地切分，稍微麻烦一点的就是词性，比如英文的时态、复数形式、特殊的宾格等等，处理这个问题已经有了很多成熟的方案，比如Perl的 Linhua包。英文的分词实际上是很容易的。

    对于东方文字，最典型的就是中文，它是按照字为单位组织句子的，词与词之间没有明显的分割，不像英文中有空格，如何有效地分割中文是个极其复杂的全球性问 题。汉语是世界上最难学的语种之一，也表现在计算机处理上……目前比较通用的中文分词技术包括字元分词、词典匹配、语义分词等。

    字元分词是最简单直接的分词方法，包括如二元、三元等。它的划分方式就是相邻的字就按照词来计算，而不管它有没有什么实际意义。比如“我是中华人民共和国 的公民”，按照二元分词可以划分为“我是 是中 中华 华人 人民 民共 共和 和国 国的 的公 公民”。二元分词简单高效，但是它会制造出很多冗余数据，因为像“民共”、“国的”这些根本就是毫无意义的“词”。二元分词的索引通常比原文还要大。

    词典分词是依靠词典匹配的方式来完成划分，实现它需要一个词库表，包含了大量的中文词汇，分词就是以这个词库表（词典）为基础进行，词典划分有正向、逆 向、双向以及最大划分、最小划分、最优划分等方式，还有混合几种的变体。举上例“我是中华人民共和国的公民”，按照正向最大分词方法，从句首开始，到句尾 逐字递减，直到匹配出词典中的一个词，或者剩下一个单字。首先匹配到的是“我是”，然后将“我是”从句子中拿掉，重复上面的过程，匹配出“中华人民共和 国”，再重复过程，这次找不到词典中的词，剩下一个“的”字，最后匹配出“公民”。这样整句划分为“我是 中华人民共和国 的 公民”。它实现了比二元分词更有效的划分。其中“的”字可以根据需要做出取舍。

    也可以从逆向匹配，就是从句尾开始查词典。根据统计学观点来看，汉语的词组一般都是前后等长或前短后长，所以一些人认为逆向匹配比正向匹配产生歧义的几率 要小。比如“研究生命的起源”，按照逆向匹配可以正确地划分为“研究 生命 的 起源”，但是按照正向匹配，结果就是“研究生 命 的 起源”，这就是一个错误的划分。

    基于语义分析的分词技术是目前研究最多，也相对不成熟的分词方式，它的基本概念是对中文语义的理解，它也需要依靠词典，不过这个词典更趋近于知识库，它的 词是包含词性的，语义分析器依靠高效的人工智能算法提取出句子的摘要部分，也就是中学语文课上我们常做的“划分句子结构”“提取主干”（好多横线竖线圈圈 叉叉把语文书画得乱七八糟）。

    BSM中包含了一个二元分词和一个正向最大匹配的词典分词（可以很容易地改为逆向），它简单地实现了中文切分，同时它的结果包含有位置信息（字节偏移量）。或者过段时间我会用更好的分词方法来替换它，不过就我现在的情况，只打算做到这个程度。人懒没办法。

    我公开PHP实现部分（其实就是全部，但是PHP只是一个低效率的实现方式，我没有使用太多的PHP本身特性，甚至mb函数都没有用，就是为了方便地向C 和perl迁移）。区别于BSM的其它模块，搜索部分的SQLite连接没有使用数据库封装类，因为它的性质是“文件操作”。

    BsmSearch的索引保存方式如下：单词的MD5前2位和次2位组成两级hash目录，一共有65536个目录，从第16位到第24位为文件名，后面 剩下8位以后可能会留下做校验。当然这个hash算法可以随时修改。这样一个12字节的key，我已经测试过目前的26万词库，没有重复出现。每一个索引 文件是一个SQLite数据库，它包含以下结构：

t_id是文章编号，可以修改为CHAR，如果不使用数字ID话。t_id上创建有索引。
    它用以下的函数生成key：

生成索引的函数如下：

首先它会判断两级目录是否存在，不存在的话会自动创建，如果为了节省IO时间，可以预先准备好所有的目录。然后函数根据传入的tokens（分词结 果）在SQLite的bsm_index表中插入信息。根据使用了一段时间后的情况，每个词的索引添加量都不大，所以INSERT没有使用事务。

这是一个简单的搜索，它还不完整，比如没有处理交并复合的情况，结果也没有带有位置信息，不过这个容易解决，昨天晚上太困了……哈哈。搜索使用建立 索引同样的分词方式_tokenizer_dict来创建queries，根据word_key快速地定位到某个SQLite文件上。在早期版本使用纯文 件时，它的定位速度极快，现在使用SQLite，包括库文件初始化，也可以保证在几毫秒的时间内完成搜索定位。