上个月，我们研究了一个用于网站的简单搜索引擎。该程序只不过是一个 CGI 程序，捆绑了 File::Find Perl 模块：每次用户在 HTML 表单中输入搜索词时，搜索程序都会忠实地打开并检查 Web 层次结构下的每个文件。

虽然这种搜索引擎可以工作，但效率极低。包含几十个文件的站点在 CGI 程序重复搜索其文档时不会感到太大的压力，但包含数百或数千个文件、每天吸引数千次访问的站点，服务器负载平均值将很容易飙升。

本月，我们将探索提高搜索引擎效率的方法。最终，我们将拥有一个搜索引擎，它可能不如其他软件那样高效，但易于安装和使用。最重要的是，我们将有机会探索一种有趣的软件类型，其内部工作原理通常对我们来说是不可见的。

顺序地搜索文件，试图找到与用户输入匹配的内容，本质上是一项低效的工作。每个文件都必须打开、读取、扫描和关闭，这需要时间。Perl 程序往往会消耗大量内存，因此执行速度慢意味着将同时运行更多 CGI 程序的副本。这反过来增加了 Web 服务器必须使用虚拟内存而不是物理 RAM 的风险。Web 服务器速度慢会让用户不满意，并且常常说服用户不再返回。

为了解决这个问题，我们必须减少或消除搜索程序读取文件的需求。如果 CGI 搜索程序不必打开每个单独的文件，速度就会快很多。

一个经过验证的解决方案是将它分为两个程序。每天一到两次，索引程序遍历 Web 文档树，读取每个文档并分析其单词使用情况。此程序在后台运行，无需用户干预或知晓。索引器不会将其结果发送给用户，而是将其拥有的关于单词频率和使用情况的所有信息转储并放入磁盘上的文件中。

这意味着用户通过 CGI 调用的搜索程序实际上不必搜索。相反，搜索程序只是打开索引文件，找到用户搜索词出现次数最多的那些文件，并在用户的浏览器中显示该列表。

在 Perl 中索引页面并不困难，因为它拥有丰富的正则表达式库。m// 运算符通常匹配其分隔符之间的正则表达式。当使用 /g 修饰符并在列表上下文中操作时，它会返回它可以找到的所有匹配项。因此，在表达式中

my $found = join ' ',
  ("encyclopedia" =~ m/[aeiou]/g);
print "$found\n";

第一条语句查找“encyclopedia”中的所有元音，并将它们作为列表返回给调用者。在本例中，调用者是 Perl 的 join 运算符，它将元素推送到一起，用空格分隔。执行上面的两行代码会在用户的屏幕上显示以下内容

e o a e i a

my $sentence = "The rain in Spain falls mainly\n\n on the plain.";
my $found = join '|', ($sentence =~ m/\b\S+\b/g);
print "$found\n";

The|rain|in|Spain|falls|mainly|on|the|plain

索引器必须考虑是否保持大小写相关。我个人的偏好是忽略大小写，因为用户不一定记得，并且它还消除了查找所需文本的障碍。因此，我们可以将所有单词转换为小写字母

my $sentence = "The rain in Spain falls mainly\n\n on the plain.";
my $found = join '|', map {lc $_}
   ($sentence =~
   m/\b\S+\b/g);
print "$found\n";

为了存储索引信息，我们将使用哈希 %IGNORE。键将是我们希望在索引时忽略的单词。任何非零值都将指示在索引时应忽略此单词

%IGNORE = ("the" => 1, "in" => 1, "on" => 1);
my $sentence = "The rain in Spain falls mainly\n\n on the plain.";
my $found = join '|',
   grep {!$IGNORE{$_}}
   map {lc $_} ($sentence =~ m/\b\S+\b/g);
print "$found\n";

请注意，我们可以将不同的项目堆叠在一起：m// 返回一个列表，该列表传递给 map，后者返回一个列表，该列表馈送到 grep，后者又馈送到 join，后者又分配给 $found。

最后，我们将通过创建一个哈希 (%index) 来索引单词，其中收集的单词是键。值将是哈希引用，其中键是当前文件的名称，值是该单词在文件中出现的次数。换句话说，

$index{spain}->{foo.html} = 5;

表示单词“spain”在 foo.html 中出现五次。以下是一些以这种方式执行索引的代码

%IGNORE = ("the" => 1, "in" => 1, "on" => 1);
my $sentence = "The rain in Spain falls mainly\n\n on the plain.";
my @found =
  grep {!$IGNORE{$_}} map {lc $_} ($sentence =~
m/\b\S+\b/g);
    foreach my $word (@found)
    {
        $index{$word}->{$filename}++;
    }

现在我们知道了如何从字符串中索引单词，我们将使用 File::Find 在整个 Web 层次结构上执行此任务。File::Find 随标准 Perl 发行版一起提供，并导出一个名为 find 的子例程。此子例程接受一个子例程引用和一个目录列表作为参数。它在命名目录中找到的每个文件上调用命名的子例程（称为“回调”）。子例程的职责是打开文件，检索其内容，并根据需要对其进行索引。

列表 3（请参阅“资源”）包含一个简单的程序 (index-files.pl)，它遍历 Web 层次结构，搜索内容，并将单词频率存储在 %index 哈希中。回调子例程忽略任何名为 .noindex 的目录中的文件，以及此类目录的任何子目录。这是通过另一个名为 %ignore_directory 的哈希完成的。它还忽略非 HTML 文件，并在索引文件内容中的单词之前从每个文件的内容中删除 HTML 标记。index-files.pl 不是完全删除 HTML 标记，而是将它们变成空格。这意味着由 HTML 标记（但没有空格）分隔的两个单词不会挤在一起，而是会保持分开的单词。

为了避免 HTML 实体（例如 >、& 以及符号和重音拉丁字符所需的其他项目）出现问题，我们使用 HTML::Entities 模块。此模块导出一个 decode_entities 子例程，该子例程将实体转换回其常规字符。通过运行此子例程，然后删除 HTML 标记，我们能够索引一个仅包含文本的干净文档。

虽然哈希方便快捷，但它们往往会消耗大量内存。指向另一个哈希的哈希会消耗更多内存，并且将每个单独的单词存储为主哈希中的键意味着内存使用量会进一步飙升。因此，运行 index-file.pl 不适合胆小的人或没有大量 RAM 的计算机。此特定版本的 index-file.pl 导致我的 Linux 系统（具有 72MB RAM 和 64MB 交换空间）耗尽内存，尤其是在通过 less 管道输出时。

虽然 index-files.pl 在索引 Web 层次结构中的文件方面做得非常出色，但它不会将信息写入磁盘。一旦 index-files.pl 退出，所有索引信息将永远丢失。

解决方案显然是将索引写入磁盘。但是如何写入呢？最明显的答案是使用 DBM 文件。DBM 文件最容易被描述为哈希的磁盘版本。DBM 文件中的每个条目都有一个键和一个值，它们都可以是任何字符串。与哈希一样，DBM 文件针对速度进行了优化，使其比直接文本文件快得多。有几种不同类型的 DBM 文件，从普通的旧 DBM 到 GNU 项目的 GDBM，再到 Berkeley DB，后者在过去几年中获得了很多欢迎，部分原因是它集成到了 Sendmail 中。

Perl 通过其“tie”接口支持多种类型的 DBM 文件，每种类型都有自己的对象模块。Tying 是一种使变量具有魔力的方法，每次存储或检索值时都会附加额外的行为。因此，将哈希绑定到 DBM 类意味着每次将值存储到哈希时，该值都会写入磁盘上相应的 DBM 文件。同样，每次检索值都会从磁盘读取信息。

但这里有一个问题：DBM 文件可以存储文本字符串，但不能存储更复杂的内容。由于 %index 的每个值都是对另一个哈希的引用，因此普通的 DBM 类将无法正常工作。尝试在普通 DBM 文件中存储引用实际上会存储它们的打印表示形式，这根本没有用。

解决方案是使用 MLDBM 类，它专门为此目的而设计。MLDBM 与另一个 DBM 类协同工作，以存储以后可以检索的格式的引用。

要使用 MLDBM，请使用 use 在程序顶部导入它，指定要与其一起使用的 DBM 文件类型

use MLDBM qw(DB_File);

在本例中，我们将使用 DB_File，它使用随 Perl 提供的 Berkeley DB 模块。（大多数 Linux 系统也附带 Berkeley DB。）也可以指定用于存储引用的底层方法；我们将使用默认方法，该方法利用 CPAN 上可用的 Data::Dumper 模块。其他选项包括 FreezeThaw 和 Storable，它们以不同的方式执行类似的任务。

然后可以使用 tie 命令将我们的哈希绑定到 DBM 文件

# In what file should the index be stored?
my $index_file = "/tmp/lj.db";
# Create the word index hash
my %data;
tie %data, "MLDBM", $index_file, O_RDWR|O_CREAT
or die "Error tying %data: $! ";

从那时起，存储到 %index 的任何值都将存储在文件 /tmp/lj.db 中。从 %index 检索的任何值实际上都将从 /tmp/lj.db 检索。在生产 Web 服务器上将索引数据存储在 /tmp 中是一个错误，因为该文件可能会被系统删除。

虽然 MLDBM 尝试尽可能透明地运行，但有时会导致令人困惑的错误。例如，通常以下 Perl 代码没有问题

$data{$word}->{$url}++;

正如我们之前看到的，这将增加特定文件中特定单词的计数器。当 %data 绑定到 MLDBM 时，上述代码将不再起作用。相反，必须分两个阶段执行赋值，检索哈希引用，对其进行赋值，然后将其放回 %data 中

my $hashref = $data{$word};
$hashref->{$url}++;
$data{$word} = $hashref;

虽然我们的 index-files.pl 版本不支持此类功能，但添加一个哈希键来指示上次索引文件系统的时间并不困难。然后可以更改 index-files.pl 以仅索引在特定日期之后创建或修改的那些文件。

现在我们已经创建了索引，我们将需要一个程序来从中检索结果。实际上，这仅仅是开始——如果我们愿意，我们可以编写多个程序来读取 DBM 文件，以各种方式进行搜索。

我们的第一个也是最简单的搜索将接受来自 HTML 表单的输入。该表单将允许用户指定要搜索的单个单词。不幸的是，我们索引文件的方式使得检索单个单词很容易，但检索短语却不可能。不同的数据结构会使执行此类搜索更容易，但无疑会增加索引的大小。

列表 1

列表 1 是一个简单的 HTML 表单，我们可以用来进行搜索。此表单期望将其结果提交给名为 dbsearch.pl 的 CGI 程序，该程序在列表 4 中（请参阅“资源”）。dbsearch.pl 打开 DBM 文件（再次使用 MLDBM 和 DB_File），并从与搜索词关联的哈希中检索键。通过按值（即整数，指示单词在文件中出现的次数）对键（包含 URL）进行排序，可以轻松创建简单的频率图表。在本例中，dbsearch.pl 显示所有结果，但仅显示前 20 个结果也并不困难。

搜索单个词可能很容易实现，但最好的搜索引擎允许 AND 和 OR 搜索。列表 2 是一个 HTML 表单，它与之前的版本不同之处在于添加了一个单选按钮。如果单选按钮设置为默认的 OR 位置，则任何一个搜索词都可能出现在文档中。AND 搜索要求文档中必须出现所有或所有搜索词才能匹配。

列表 2

better-dbsearch.pl 的一个版本，它允许 AND 和 OR 搜索，位于列表 5 中（请参阅“资源”）。

如果用户选择 OR，dbsearch.pl 将必须找到哈希组合的最高总数，而不仅仅是一个。一个简单的例子是哈希 %odds 和 %evens，如下所示

%odds =  (one => 1, three => 3, five => 5);
%evens = (two => 2, four => 4, six => 6);

我们可以通过将它们混合在一起来将其变成一个简单的哈希

%numbers = (%odds, %evens);

foreach my $word (@terms)
{
my $frequency = $data{$word};
foreach my $filename (keys %$frequency)
{
$full_results{$filename} += $frequency->{$filename};
}
}

为了处理 AND 搜索，我们必须跟踪每个文件中出现的搜索词数量。如果文件包含的搜索词数量与 @terms 中的数量相同，则该文件是可接受的。如果它包含的匹配项少于 @terms，则应从考虑中删除该文件。

我们可以通过使用 %match_counter 哈希来实现这一点，其中键是文件名，值是表示文件中包含的搜索词数量的整数。通过在 foreach 循环中添加一行代码，我们可以跟踪每个文件中出现的搜索词数量

$match_counter{$filename}++ if ($boolean eq "and");

一旦我们退出 foreach 循环，但在向用户宣布结果之前，我们从 %full_results 中修剪文件名。由于 %full_results 的键与 %match_counter 的键相同，因此代码相对简单

foreach my $filename (keys %full_results)
{
delete $full_results{$filename}
unless ($match_counter{$filename} == @terms);
}

另请注意，我们如何通过简单地命名数组本身来获取 @terms 的大小。== 对其两个操作数强制执行标量上下文，因此无需在 @terms 之前使用 scalar 关键字。

我们的预索引解决方案确实比我们上个月研究的搜索程序更快。我没有对这组程序进行任何认真的基准测试，但差异对肉眼来说显而易见。不仅如此，我们的预索引实现还使得根据匹配次数对文件进行排名变得容易。

但是，预索引并非万能药。首先，它需要大量的磁盘空间，对于少于 400 个文件的索引，重量为 2.6MB。但是，鉴于磁盘空间价格迅速下降，即使是 10MB 的索引对于大多数系统来说也不应成为太大的障碍。

更大的问题是预索引对搜索系统施加的灵活性不足。例如，我们的索引程序都使用了 Perl 的 lc 运算符来强制将所有字母转换为小写。现在我们已经从索引中删除了任何大小写痕迹，我们如何提供区分大小写的搜索？唯一真正的答案是以稍微不同的方式构建 DBM 文件，或许通过在每个文件的哈希中存储一个额外的 literal 元素。然后我们就会知道 abc 在特定文件中出现了五次，但其中两个是 ABC，其余三个是 abc。

预索引还意味着我们除了 AND 和 OR 搜索之外，不能再提供短语搜索。有一些方法可以解决这个问题；最简单的方法可能是将“下一个单词”信息存储在数据库哈希中。然后我们可以搜索短语的第一个单词，并使用“下一个单词”信息来查看是否逐个找到其他单词。

最后，预索引始终意味着索引将落后于网站上的其他内容。如果索引每 24 小时生成一次，则新文档可能需要长达一天的时间才能读入索引。一种解决方案是更频繁地运行索引器，例如每三到六小时一次。

搜索是每个优秀网站的重要组成部分。它意味着用户可以快速找到他们感兴趣的内容，并且可以执行网站管理员从未预料到的分析。但正如我们上个月所见，直接搜索网站文件可能需要很长时间才能执行。预索引是解决此问题的标准解决方案，它以额外的磁盘空间和略微过时的索引为代价，换取更快的执行速度。了解编写搜索引擎所涉及的权衡，可以更轻松地评估免费和商业产品，从而使您的网站成为用户更愉快的访问场所。

资源