在 Linux 环境 Python 下开发全文索引

随着信息量的增长，高效地定位特定信息变得越来越重要。本文将探讨全文索引领域，并集中讨论作者的公共域 indexer 模块。

本文将探讨我的 Python 项目：indexer 模块，并且还有一项特殊目的：我和你们一样也一直尽力学习更多知识，为此，本文欢迎读者提出自己的意见和想法。

我希望 indexer 模块，即使是早期的版本也能证明给读者是有用的。此全文 indexer 可作为单独的实用工具或大型项目的一个模块。其设计说明了可重复使用的面向对象编码的准则和文本索引（极其精妙而丰富的主题）的基本原理。尽管 Knuth曾经忠告我们：“不成熟的优化是问题的根源”，但索引的目的在于快速地找到信息，因此本文同时也将讨论性能问题。

indexer 模块大约是来源于某大学希望寻求一种好的方法来查找大量文本和 HTML 帮助文档。也是我想利用多年积累下来的信件、新闻和写作档案的一个小动机。很简单， indexer 让用户定位文档时，很难甚至无法以规则表达式来指定搜索条件，并且快速的执行。虽然有些商业软件或免费工具能完成类似的工作，但大多都是针对 Web 索引。他们（即使是通过 LOGALHOST 也）需要 CGI 接口，安装和使用都相当困难，其中只有唯一一个为 Python 设计的软件（有不同的侧重点）。另一方面，indexer 必须设计成易于使用。当然，有些更早期并且更复杂的软件功能更强大，但 indexer 设计目的是在不失其简单易用特性的前提下拓展功能。

关于搜索引擎

本文的名称“全文 indexer”隶属于另一个更宽泛的类别 -- “搜索引擎”。对大多数用户，搜索引擎通常是用来定位 URL 和 WWW 的。的确，WWW 肯定是人类有史以来最大的公共文档库，它的非正规组织结构使其非常需要有好的搜索引擎。而且，其他文档集 -- 特别是包括本地硬盘上不断增加的文件 -- 也将获益于搜索引擎。分级文件系统和文件命名规范是好方法，但他们的发展还远远不够；有些时候您只需找到 包含某条信息的文档。

互联网搜索引擎有一半的问题在于定位其内容要被索引的文档。虽然有很多方法可以找到许多相关的 URL，但却没有罗列每个有效 URL 的算法。幸运的是，当索引本地文档（正如目前版本的 indexer 这样）时，找到所有文档非常简单；这些文档都位于明确而可定位的地方。而当用户进一步希望索引某些目录的子目录树而非其它时，文档列表就能变得精确而无遗漏。

在设计本地搜索引擎时有两种不同的策略。可以在搜索时察看文件的实际内容以判断是否和搜索条件相符，也可以准备一个包含每个文件内容的数据库，然后搜索数据库而不搜索文件本身。第一种方法的优点在于始终保持精确，始终能准确的定位在哪里有您想要的哪些内容。这种特别方法的 最大缺点在于速度特别慢，而且如果进行许多次搜索的话，成本很高。

第二种方法的优点在于如果实施得当，它将快得多。一次搜索传递能生成文档可搜索特性的摘要，后继搜索就不必再次阅读这些文档。这使得搜索成本 更低。缺点在于，数据库可能与文件内容不同步，需要周期性重新索引，而且这种做法会占用额外的空间（被索引文本的大小的 1% 到 100%，由搜索特性和设计选择而定）。

这种特殊方法的示例有 Windows 下的 "File Find"、类 Unix 操作系统的 find 和 grep 工具（与 KDE 中的 kfind）、OS/2 中的 PMSeek.exe 工具和 "Find Object" 还有 MacOS 7 中的 "Finder"。数据库方法包括 Microsoft Office 中的 "Fast Find"，Corel Office 中的 "QuickFinder"、 MacOS 8+ 中的 "Sherlock" 还有很有局限性的 Linux 的 locate 实用工具。BeOS 的 "Find" 是两种方法的结合，但功能非常局限 -- 非全文搜索。其他操作系统也提供类似的实用工具。

有许多不同方法来指定要搜索的内容。以下为一些示例：

词语出现频率指出一系列搜索词语在文档中的出现频度。此处假设对于给定的搜索，文档中被搜索到的条件出现的比较频繁，就属于“更好”的匹配。

布尔搜索允许出现的文字与短语之间有复杂的关系。例如 "(spam AND eggs) OR (ham AND cheese)" 中，任何括号中的组合都将符合条件，而不必包括另一头分离的词汇。

规则表达式搜索满足（尽可能复杂）的模式。这种方法更有利于查找高度结构化的数据，而不适合识别概念化的内容。

短语搜索只是允许多词条件的搜索。规则表达式搜索虽然能完成相同的搜索，但更简单的系统也能做到。

近似搜索查找一系列相互“接近”的词语或短语。有多接近通常是一项查找选项。

词干搜索，有时候搜索词干而不是整个单词。将 "run"、"runner"、"running" 和 "runs" 当作相关词汇来考虑而将他们全部找到，而不是试图单独搜索符合条件的每个词语，这种做法有时非常有效。

概念搜索通过辨别具有类似涵义的词语来查询具有类似主题的文档。此类搜索需要在搜索引擎中集成某些词典。

探测法搜索可以查询不规则拼写，特别是针对英语。搜索并不使用单词在文中的拼写，而是根据发音将其转换为规则拼写。然后将转换后的文字与转换后的搜索条件做比较。

关于 indexer

indexer 使用出现的词语的数据库。版本 0.1X （alpha 测试版）只能搜索全文单词结构固定的文档。作为可选项，搜索能将符合条件的文档按照搜索词语的出现频率并且对比文档长度来排列。 indexer 能以不同方式进行扩展，某些扩展方式逻辑化而直接，其它则更为复杂。

布尔能力很简单而且也已经在按计划实施。由于 indexer 跟踪哪些文档中包含哪些单词（和出现次数），因此如果要在规则中加入逻辑或者根据搜索词语出现或不出现来包括文件是很容易实现的。实际上，目前的功能本质上默认为在每个查找词语中间加 AND。（我的直觉是大多数现行的搜索都是这种 "x AND y AND z" 方式的搜索。）

规则表达式几乎无法加入到 indexer 中，据我所知没有一个数据库搜索系统具有哪些文件包含符合哪些规则表达的内容的列表。实用起见，规则表达式需要以特殊方式处理 -- 为此我们使用 grep。

短语和近似搜索现在并未实行，但实施并不困难。基本上，除了每个文件中的每个词语的出现频率，还必须收集每个文件中词语出现的偏移列表。根据该列表，我们能推论短语和近似度。然而，我认为这样做会大幅增加数据库的大小和搜索时间。

概念上，词干和探测法搜索可能已在现有的基本框架之中，但其需要花费很大的工作量。这种方法的确能减小数据库大小，因为只需存储正则形式而不必存储变化形式，但词语转换需要消耗外部类属词典和变化规则形态。

indexer 编程

建议读者下载 indexer 源代码 （请参阅本文后的参考资料）。它只有一个文件，而且有详尽的注解，相当于一本编程书籍。

以下是有关程序结构的备注。请注意文档是编号的，每个文档都关联一个整数 "fileid"。

indexer 有一个 Python 词典，其关键字为词语，其值本身又是词典，这个词典的关键字为 "fileid"，其值为 "fileid" 指定的词语在文件中的出现次数。Python 词典的查找效率很高，而且连结 "fileid" 和实际文件名的附加工作相对很少。

从大体上说，indexer 包含一个被称为 GenericIndexer 的抽象类。在 GenericIndexer 中定义的最重要的方法为 add_files() 和 find()。如果存储机制需要最终化（大部分都需要）的话， save_index() 方法也很重要。

使 GenericIndexer 抽象的原因是它不能被实例化；而其子类只要完成进一步的工作后就能被实例化。术语"抽象"来源于 C++，在 C++ 中它可以是类的正规声明。在 Python 中并没有该正规声明，而类的“抽象”只是类的开发者给其用户的建议。Python 是这样处理的 -- 不强制数据隐藏、成员可见、继承需求和类似的做法，而是遵从在何时完成的规范。然而， GenericIndexer 能很好的强制执行其建议，因为它的许多方法由 "raise NotImplementedError" 行组成。特别是 __init__() 调用 "NotImplemented" 的方法之一的 load_index()。

GenericIndexer 的派生在实际存储索引中有不同的实现方法。其中最实用的是 ZPickleIndexer，将 zlib 和 cPickle 合并，存储压缩的词典。一方面为了兴趣，一方面又由于令人吃惊的性能测试结果（请参阅基准测试模块），我创建了许多其它 SomethingIndexer 类。如果愿意，shelve、XML、flat-file 和 cPickle 的类都已经具备。创建 NullIndexer 派生，高效地将每个索引存放到 /dev/null 是可能的（虽然有些无意义），而且每次开始搜索时都需要重新索引。

在提供 load_index() 和 save_index() 实现的同时，具体的（与“抽象”相反） SomethingIndexer 类从“mixin 类”中继承 SomethingSplitter。目前，这样的类只有 TextSplitter，但是其他相似的类会不断出现。SomethingSplitter 提供非常重要的 splitter() 方法，它获得一个文本字符串并把它分割成组成其的单词。这种方法比想象的要难得 多；区分是或者不是一个单词是非常微妙的。以后，我希望创建 TextSplitter 的派生，比如 XMLSplitter、TeXSplitter、PDFSplitter 和相似的类。而现在我们试图以相对原始的方法查找文本单词。

“mixin 类”是个有趣的概念，也常常是个很好的设计选择。类似 TextSplitter 的类（或其未来的派生类）往往会包含针对许多具体派生类的有用功能。和抽象类相似，mixin 类不能直接被实例化（其有效性与禁止不同，在 mixin 中我并没有提出 NotImplementedError。）然而，与抽象类不同的是，mixin 并不试图包括子类的框架。TextSplitter.splitter() 基本上类似于全局通用函数，但其对范围的控制更好。

公开 indexer 的问题

indexer 中有些具体的问题需要解决。最终，这些问题都归结到性能。

在目前的设计中，索引被保存在单一的数据库中，数据库在启动时被读入内存（ ShelveIndexer 实际上使用三个 "书架"，但是 WORD 书架是唯一的容易引起问题的大型书架）。在一台 333 Mhz、96 MB 的 Linux 系统上读取 3 到 4-MB 的数据库，找到匹配的单词然后生成结果只需要 5 秒钟。这是非常合理的，而且比特别的搜索工具快得多。然而，随着数据库的扩大，性能急剧地呈非线性发展。一个 12-MB 的数据库的读入、装载和查找时间增加到一分钟。这实在难以接受，与数据库大小增长 4 倍不成比例。看上去就象是高速缓存丢失的影响，但根据系统的实际内存它不会对于我有任何意义。

对于大型数据库问题的一种很简单的解决方法是将数据库分解开。例如，不同字母开头的索引单词可使用不同的文件。由于大多数搜索只有几个单词 -- 只命中极少的首字母 -- 对于一个给定的搜索只有一小部分文件会被装载。即使是不规则分配首字母，这样也能很大程度上减少读取。当然，读取每个数据库文件后在内存中合并词典需要额外的处理，但这也比读取所有文件的消耗小得多。

另一个更好的解决读取数据库的消耗的方法是完全避免读取。使用 shelve 似乎可以做到这一点，它能把磁盘文件作为词典使用而不必读入内存。然而，在两台测试机上安装的 dbm 产生了 dumbdbm 和 dbhash，两者荒唐地生成了膨胀的数据库（其规模比 ZPickleIndexer 还大）。这不能接受，我想读者可能也无法安装更好的类似 gdbm 或 bsddb 的 dbm。

然而，数据库大小的问题还会引起更重大的问题。理想状态下，当更多文件被索引时，不会引起词语词典恶性增长。但是，某种情况下，好像所有可能的单词都会被加入。可是很不幸，这样的理想状态并不存在。

识别真实单词以及把它们与乱码区分开变得非常困难，这些真实单词中有许多在普通的英语词典上也无法查到。一种原因是由于文档是其它语言写成的。商标、用户名、URL、公司名、开放源码项目以及许多其它场所使用的文字在 indexer 的理解下当然都是“单词”。某些包含数据和文本的文件，类似 base64 和 uuencoding 的半二进制编码，甚至二进制编码意外地生成了假词。TextSplitter 使用某些启发式方法消除了部分此类乱码，但是改进的 splitter 类将会使索引更接近恶性状况。将单词限制在一系列字母能减少大量的乱码，但是又有太多的真实字母与数字的组合（"P2P"、"Win95"、"4DOM" 等）。欢迎提出您的建议。

总结

本文只涉及了 indexer 模块和全文索引这个更广泛主题的皮毛。随着模块的不断改进以及读者的献计献策，后续专栏将再次谈及模块和其背后的更多理论。

原文转自：http://www.ltesting.net