设计搜索引擎

2001年4月10日，作者：Pete Sergeant

几个月前，一家我曾为其工作过的公司找到我，要求我为他们构建一个搜索引擎，以索引大约200MB的HTML。然而，我对能做什么和不能做什么有一系列严格的规定。首先，搜索引擎必须从头开始构建，以便完全拥有其权利。其次，我不被允许使用任何非标准模块。第三，数据必须存储在纯文本文件中。第四，我被告知所有的DB*模块都无法工作，也无法使其工作，这有点令人惊讶。最后，必须能够执行布尔搜索，包括使用括号。

正如你可以想象的那样，这提出了相当大的挑战，所以我接受了这个任务并开始工作。我想讨论这个项目中最有趣的两个部分：如何有效地存储和检索数据，以及如何解析搜索词。

由于我对解析搜索词的想法，这将在后面讨论，我需要一个系统，它可以接受一个单词并将其返回到一个列表，该列表包含所有包含该单词的文件及其出现次数。这必须尽可能快，而不需要使用大量的磁盘空间。其次，我需要能够快速获取关于索引文件的有关信息，而无需实际打开它们 - 文件可能很大，并且可能存储在远程位置。

要做的第一件事是为每个索引文件分配一个唯一的数字 - 这将使我能够在引用它时节省空间，并使我能够轻松地查找有关该文件的信息。每个单词下都会列出这些数字的列表，例如，我可以取单词“camel”，然后获取文件编号的列表。

对我来说，实现这一点的最明显的方式是使用一个tied hash。然而，我的项目规则规定我不被允许这样做。我试图想出其他方法来实现一个tied-hash系统，而不使用DB或DBI模块。我的第一个想法是利用几乎在所有操作系统中都使用的一个类似功能；或者更准确地说，每个文件系统。通过将每个单词作为一个文件来创建，我可以很容易地使用open (DATA, "camel")来获取我的数据。

此时，我有两种类型的索引：一种按文件编号列出每个文件的摘要信息，另一种包含每个单词的信息。

然而，使用文件系统作为我的hash存在两个问题。虽然对于少量单词来说这相当快，但大多数操作系统使用线性搜索来定位目录中的文件，所以在一个包含10,000个文件的目录中打开“zulu”很快就变得非常慢。另一个问题是最小文件大小，尤其是在Windows下。当你的最小文件大小是16kb时，这是一个大问题 - 在fat16和1GB硬盘上，100个文件等于1.6MB。当你索引的数据是20MB时，你得到大约四倍的索引文件，你做错了什么。

对于文件编号的解决方案相当简单：我会输出关于每个文件在文件索引中存储的信息的文件偏移量。然后，在每次搜索的开始时读取这些偏移量，所以如果我想获取关于文件15的信息，我可以说$file[15]，然后定位到那个点。

我曾经对找到一个优雅的单词索引解决方案感到绝望，直到Simon Cozens指出神奇的Search::Dict。Search::Dict是一个标准模块，用于在字典文件中搜索键。本质上，它允许你给它一个单词和一个文件句柄，其中文件句柄绑定到一系列按字母顺序排列的行，然后会将文件句柄的下一个读取位置更改为以该单词开头的行。例如

look *INDEX, "camel";
$line = <INDEX>;

将把$line赋值为文件句柄中以camel开头的第一行。此外，由于它使用有效的二分搜索来实现这一点，因此数据检索速度快。问题解决了。

布尔搜索词的解析是程序中最困难的部分。用户必须能够输入类似于cat和(dog not sheep)的词，并得到合理的结果。我认为唯一能处理这个问题的方法是从左到右沿着搜索词进行，并保持一个仍适用的文件编号数组。

为此，我创建了三个子程序，分别命名为&array_and、&array_not和&array_both。&array_and将接受我们的当前结果数组，并添加来自给定单词的文件编号列表。&array_not将从我们的结果数组中“减去”一个单词的文件编号，而&array_both将返回结果数组和搜索词的文件编号之间的共享元素。

我从一个叫做Perl Cookbooks的代码库中提取了大量代码来制作这些数组函数。这些函数的代码如下所示

sub array_both {
 my $prev = 'nonesuch';
 my @total_first = (@{$_[0]}, @{$_[1]});
 @total_first = sort(@total_first);
 my $current;
 my @return_array;
 foreach $current (@total_first) {
  if ($prev eq $current) { push(@return_array, $prev);  }
  $prev = $current;
 }
 @return_array = @{&add_array(\@return_array, \@return_array)};
 return \@return_array;
}

sub array_and {
 my $prev = 'nonesuch';
 my @total_first = (@{$_[0]}, @{$_[1]});
 my %seen = (); # These next two lines are from the PCB
 my @return_array = grep { ! $seen{$_} ++ } @total_first ;
 return \@return_array;
}

sub array_not {

 # Again this is ripped straight from PCB

 my @a = @{$_[0]};
 my @b = @{$_[1]};
 my %hash = map {$_ => 1} @a;
 my $current;
 foreach $current (@b) {
  delete $hash{$current};
 }
 @a = keys %hash;
 @a = sort(@a);
 return \@a;
}

唯一剩下的大问题是处理括号。我能想到的唯一解决方案是将搜索词解析代码变成一个返回数组的子程序。这样，当遇到括号中的逻辑时，我可以将其发送回子程序，从而获得一个单词列表，就像逻辑是一个单独的单词一样。我预见到的主要问题是让Perl处理像sheep and (dog not cat) and (camel not panther)这样的表达式。我是如何让Perl匹配第一组括号的，或者如果有嵌套括号，如何匹配所有逻辑呢？Damian Conway编写了一个名为Text::Balanced的出色模块，我正准备开始使用，但在项目规范更改(!)之前，我被告知不再需要允许嵌套括号搜索。

当编写搜索引擎时，Perl再次大放异彩。以模块形式提供的解决我问题的方案节省了我大量时间，并使任务免于被我自己相当糟糕的代码淹没。使用Perl快速从HTML文档中提取标题和仅用几行代码剥离HTML标签的能力也使我的生活变得更加容易。

标签

数据