我最近在为一个客户开发 CD-ROM 目录，他要求该目录具有关键字搜索功能。我搜索此类请求的解决方案，结果总是出现专有操作系统软件，这些软件需要在用户的机器上安装，并且每份分发副本都需要支付许可费。这种安装要求具有局限性，并且随着时间的推移会花费大量资金。此外，所有 CD-ROM 用户都不会使用单一的专有操作系统，因此这自动减少了潜在客户群。在坐下来思考情况时，我注意到邮箱里有一个包裹——《Linux Journal》存档 CD。我认为如果有人解决了这个问题，那肯定会在《LJ》存档中找到。令我失望的是，我发现《LJ》存档 CD 有一个非常好的索引，但没有搜索引擎。如果想要找到解决方案，我必须自己找到它。本文是关于用 jsFind 解决这个众所周知的难题。

我最早的考虑之一是如何分发和许可我的解决方案 jsFind。我向同事展示了早期版本，他们认为我应该遵循许可代码然后进行营销的模式。这样，jsFind 将使用与同类型内容的其他竞争搜索引擎相同的模式。就我个人而言，我宁愿花时间编写代码而不是营销，而且我怀疑总市场规模并不大。我更希望获得信息丰富的 CD-ROM，并且能够使用我选择的任何浏览器和平台轻松搜索它们。

GNU 通用公共许可证 (GPL) 更符合我的目标。通过自由分发 jsFind，它将根据自身的优点进行营销，并在发展过程中获得改进和贡献。冒着对合唱团布道的风险，专有系统的目标之一是通过一切可能的手段将用户锁定在必须使用他们的系统中。例如，当一个人获得 CD-ROM 并被要求使用特定的浏览器和特定的操作系统来使用搜索引擎时，那么该用户就被迫访问该操作系统的副本。CD-ROM 生产商也被迫不断购买该操作系统的开发工具以保持最新。结果是消费者和生产商都被锁定在专有操作系统供应商中。根据 GPL 发布 jsFind 将打破这种循环。

jsFind 关键字搜索引擎本身是一个大约 500 行的小型 JavaScript 程序。支持 DOM Level 3 JavaScript 扩展的浏览器可以加载 XML 文件。当前版本的 Mozilla、Netscape 和 Microsoft Internet Explorer 都支持这些扩展，即将发布的 Konqueror 也将支持。索引存储为一组 XML 文件，JavaScript 以高效的方式搜索这些文件以生成关键字搜索结果。然后可以使用 JavaScript 将这些结果发布回请求它们的网页。

jsFind 的关键依赖项之一是 CD-ROM 必须是一组静态信息。与 Web 搜索引擎或任何其他动态数据集不同，CD-ROM 一旦压制完成，就不会再改变。SWISH-E 更适合动态索引，尤其是在可以配置服务器进行关键字搜索的情况下。因此，jsFind 基于这样的理念：唯一可用的东西是带有 JavaScript 的标准 Web 浏览器和一组可浏览的文件——这是对可能解决方案的严重限制。

大多数索引方法算法都试图在插入、更新、删除和选择时间之间取得平衡。由于 CD-ROM 是静态的，因此永远不会有删除或更新。插入发生在 CD 刻录之前，可能非常耗时。选择时间对于用户响应至关重要。还需要额外的空间限制，因为典型的 CD-ROM 无法容纳超过 700MB 的内容。

基于这些约束重新检查索引方法，得出了一个有趣的解决方案：B 树和哈希是两种最常用的索引方法。我选择使用 B 树，因为文件系统以树状结构组织文件；这可以用来存储 B 树的结构，从而节省一些宝贵的空间。其次，可以分析键/链接对，并创建一个平衡的 B 树。XML 文件本身的结构保持尽可能简洁，因此使用单字母标签作为节省空间的措施。

B 树是一种数据结构，常用于数据库索引和存储例程。它提供高效的搜索时间，并且存储/检索以块为单位完成，这与当前的硬件配合良好。B 树由节点（或块）组成，这些节点（或块）具有有序的键列表。每个键引用一个关联的数据集。如果请求的键落在排序中的两个键之间，则提供对另一个键节点的引用。平衡 B 树是指在搜索中可能加载的最大节点数保持在最小值的 B 树。

jsFind 通过使用 XML 文件作为树的节点来创建 B 树，文件系统上的目录对应于对另一组节点的引用。这允许 B 树的部分结构在文件系统上编码。如果所有 XML 文件都在同一目录中，则文件打开时间可能会变长，因此有效地使用文件系统需要子目录。

图 1. jsFind 创建一个 B 树，其中 XML 文件代表每个节点。

最终用户无需担心这些。他们只需在网页上键入要搜索的单词，jsFind 就会返回指向包含这些关键字的页面的链接。无需安装，无需担心，只需无缝体验。

图 2. 搜索结果示例

但是，作为内容开发人员，您的生活并没有那么简单。jsFind 工具集试图尽可能简化您的工作。首先，您需要 Perl 和相当多的 CPU 时间来生成索引。最有可能的是，您还需要所有目标浏览器的副本，以便您可以测试结果。在 jsFind 发行版中可以找到带有 Makefile 的示例，但有几个步骤需要根据您的个人需求进行定制。

第一步是获取包含关键字和链接的数据集；输入格式需要是 XML。我使用了 SWISH-E 和自定义补丁来提取和创建索引，然后将结果导出为适合 jsFind 的 Perl 脚本处理的 XML 格式。假设 SWISH-E 索引在文件 mystuff.index 中，以下命令将文件导出为 XML

$ swish-e -f mystuff.index -T INDEX_XML > mystuff.xml

此 XML 文件的结构如下

<index>
 <word>
  <name>akeywordhere</name>
  <path freq="11" title="Something neat">
    /cdrom/blah.html
  </path>
  <path freq="10" title="More cool stuff">
    /cdrom/blah2.html
 </path>
 </word>
 <word>
 ...

</index>

XML 文件按关键字名称的顺序排序。

生成的数据集可能仍然太大，因为 SWISH-E 不关心过滤掉诸如“and”、“this”和其他常见的英语单词。可以使用两个 Perl 程序来过滤结果，occurrences.pl 和 filter.pl。occurrences.pl 创建一个关键字列表，并确定它们在索引中出现的次数

$ occurrences.pl mystuff.xml | sort -n -k 2 \
  > mystuff.keys

此文件每行都有一个关键字，后跟出现次数

$ tail mystuff.keys
you 134910
for 138811
i 149471
in 168657
is 179815
of 252424
and 273283
a 299319
to 349069
the 646262

此时，执行创建关键字排除文件的枯燥任务。编辑 key 文件，并保留所有应从最终索引中排除的单词。更好的是，从 ZingMan 获取一份 300 个最常见的英语单词的副本，网址为 www.zingman.com/commonWords.html。

接下来，运行过滤器。此软件包中包含的 Perl 脚本 filter.pl 过滤结果集。它目前设置为排除任何单字符索引键（字母 C 除外）、任何以两个数字开头的键（因此像 3com 和 0xe3 这样的可以）以及指定排除文件中的任何内容

$ filter.pl mystuff.xml mystuff.keys > \
  mystuff-filtered.xml

此步骤需要相当长的时间。确保文件的最终大小在可用空间的限制范围内。最终索引的大小应约为过滤索引大小的 75%。如果太大，请使用更长的关键字排除文件将其缩小到所需大小。

第二个大步骤是创建索引本身。提供了一个脚本，用于将此索引分解为一组 B 树 XML 文件

$ mkindex.pl mystuff-filtered.xml 25
blocksize: 20
keycount: 101958
depth: 4
blockcount: 5098
maximum keys: 194480
fill ratio: 0.524259563965446
bottom fill: 92698
Working: 11%

接下来要考虑的是参数。blockcount 声明需要创建多少个 B 树块。每个块创建一个键节点文件和一个数据节点文件以及一个目录。如果文件和目录的总数太高，请增加 blocksize 直到适合为止。depth 显示树中的级别数。如果 blocksize 变得太大，搜索时间会变慢，因此 bottom fill 是保持平衡的方式。一旦将该数量的键放入底层行，底层行将关闭以进行进一步的节点创建，从而创建平衡树。

如果一切顺利，您应该在当前目录中得到三个文件：0.xml、_0.xml 和目录 0。这些是索引文件。下一步是按照提供的示例将结果集成到您的 HTML/JavaScript 中。然后将结果传递给提供的例程，并且需要将其发布回当前网页。该示例使用 JavaScript 创建动态 HTML 来执行此操作。

jsFind 有许多可能的改进，并且随着开源用户的使用，这些改进将会出现。诸如具有带缩略图的图像存档搜索、多页结果集和更强大的浏览器兼容性检查等功能都可以使用此代码作为跳板来实现。

2002 年的《LJ》存档 CD-ROM 包含 jsFind 搜索引擎。如果您是 CD-ROM 内容的开发人员，请考虑使用 jsFind 而不是使用专有操作系统的解决方案。这样做会更便宜，并且会将您与更大的潜在用户群联系起来。作为最终用户，我希望不必安装程序和双启动只是为了搜索 CD-ROM 上的内容。该软件的其他创新用途也可能，因此请将其视为开源工具箱中的又一个工具。