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

建议读者下载 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 模块和全文索引这个更广泛主题的皮毛。随着模块的不断改进以及读者的献计献策，后续专栏将再次谈及模块和其背后的更多理论。

查看本文来源