当前位置:数据库 > SQLite >>

走进全文搜索(PHP+SQLite) 一

答案:

为什么我要写这种东西?因为趋势。或者说是为了实现。我总是喜欢做一些看起来无意义的事情……

    搜索,是互联网的每一步!

    提到搜索,最有名的当然是Google、baidu这类全网搜索引擎,提到开发工具,恐怕要算是Lucene了。Lucene是一个开源的全文搜索的工具包,由Java编写,是Apache软件基金会的一个项目。Lucene现在有了很多Java之外的语言版本,比如.NET、Perl等,Lucene4c也在开发中。c语言版本似乎要等上一段时间,因为c版本的结构将和标准的Java版差很多,因为这两种语言根本是一种写法……

    在ZendFramework里还有一个Lucene的PHP版本实现,也可以算是Lucene的一种语言分支,不过PHP Lucene并不像Perl Lucene实现得那么完整,它有很多的方法都是空的,它只是实现了Lucene的功能,提供一个可用的平台。当然PHP Lucene的代码质量还是很不错的。

    前些日子有看过PHP Lucene和标准Java Lucene在相同环境下的比较,PHP Lucene可以说是惨不忍睹,创建索引的速度和搜索速度都已经超过可承受极限,或者是我们使用的方法不当,但是PHP Lucene对索引文件的Optimizer动作是空的,这个让打散的索引无法合并。虽然根据以往的经验,PHP的IO性能要好过Java,但是这次对比应该反应的是PHP Lucene的实现方式上有问题,因为后来我把它的索引文件转移到tmpfs上,发现没有任何好转。

    与此不同的是Perl Lucene,前一阵刚升级到1.25,它的性能是很稳定的,它没有严格地追随Java版的实现结构,因为Perl的语法很灵活,而且它的IO和字符串性能都足够好,Perl Lucene我没有做过什么详细的测试。

    这次的目的是在BSM中扩展全文搜索模块,我不打算用Lucene,因为PHP Lucene确实还不成熟,我也不希望有BSM中有Java成分。BSM里只有几个Daemon是Perl的。我不需要Lucene那么复杂,只要用自己的方式实现一个简单的全文搜索功能就可以了。BSM的整体概念就是简单高效很多模块只有一个文件,我不需要那么多的功能,只要它够快够稳定就可以了。虽然在PHP上追求“快”有一点变态。


* * * * * * * * * * * *
    全文搜索不是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数据库,它包含以下结构:

CREATE TABLE bsm_index (
       t_id INTERGER DEFAULT 0,
       position INTERGER DEFAULT 0,
       d_flag BOOLEAN DEFAULT f
      )

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

Oracle
MySQL
Access
SQLServer
DB2
Excel
SQLite
SYBASE
Postgres
如果你遇到数据库难题:
请访问www.zzzyk.com 试试
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,