在 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。



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



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