创建自己的搜索引擎
创建自己的搜索引擎
关于网络搜索引擎的文章和传闻有不少夸张之处，所以你也许会有这样一种印象：编写它非凡夫俗子所能胜任。但是编写小的搜索引擎实际上非常简单。不相信？好吧，在这篇文章中，我们会向你们展示如何只写几行Perl程序就把你自己的搜索引擎加到你的网点上。当然，你所连的服务器必须运行UNIX系统，而且你要具有安装CGI脚本的能力。
提出一个算法
在大多数情况下，一个网点只是一个目录树。如果你不介意效率或者响应时间，你可以用find和grep来编写一个脚本，它和通过命令来搜索你的网点的方法类同。但是这种野蛮的方法会随着你网点容量的扩充而陷入绝境，因为每次搜索都必须读取你网点上的所有文件。
创建一个倒序索引（或称倒序索引文件）则好多了。这是一个文字表单，非常像书末尾部分的索引。假定我们有一个非常简单的网点，它只包含两页，如下所示：
one.html:
<html><head>
<title>Doc One</title>
</head><body>
<p>Here document one.
</body></html>
two.html:
<html><head>
<title>Doc Two</title>
</head><body>
<p>Here another document.
</body></html>
为了对此网点进行索引，我们需要生成两个表单。首先，我们将每个页面进行编号，并列出每页的标题和URL。这样以后我们就可以拿数字来代表页面，会省出不少空间。
1 => /one.html, "Doc One"
2 => /two.html, "Doc Two"
下一步，我们通过列出每个字及其所在的文件来生成倒序索引：
another=>2
doc=>1,2
document=>1,2
here=>2
is=>1,2
one=>1
this=>1
two=>2
要想实现搜索，在倒序索引中查出你要找的字，然后查看这个字后面列出的网页。当你想搜索“here”这个字时，我们的脚本将在倒序索引中查找“here”，得到“2”，再去看“2”代表的网页，并把关于此文件的信息以链接的形式显示出来:
<a href="/two.html">Doc Two</a>
同样地，如果你键入两个字，脚本将把两个字都查找一遍，并且都列出把两个字都包含在内的网页。
决定数据结构
将倒序索引存在普通的文件中，并且用grep对它进行搜索来查找文字并不困难。因为索引比整个网点要小，所以此方法比用find和grep来搜索整个网点要有所进步。
然而，大网点的索引文件依然是庞大的，查找几个字就得在每次搜索时都把整个文件读一遍，这无疑是在浪费时间。所以，我们用DBM文件。当网页表单和索引文件中只含有(name=>value)类型的记录时，可以很容易就将它们在DBM文件的字符串中定位。用Perl编写的例索引如下所示：
%dbm = (
'-1'=>'<a href="/one.html">Doc One</a>',
'-2'=>'<a href="/two.html">Doc Two</a>',
'another'=>'-2',
'doc'=>'-1-2',
'document'=>'-1-2',
'here'=>'-2',
'is' => '-1-2',
'one' => '-1',
'this' => '-1',
'two' => '-2'
);
创建一个牵引文件
现在我们要编两个脚本：读取你网点上的所有文件和创建倒序索引（牵引文件）的代码，以及查找用户在查找表中输入的字的CGI脚本。我们先来写牵引文件。
首先，我们打开将要存储倒序索引的DBM文件。我将使用Berkeley DB来完成，因为它速度快而且不限定记录的长度。这个功能对我们非常有用，因为在网点中象“the”这样的普通词汇出现的次数是不限的。
这样打开索引文件：
use DB_File;
dbmopen(%db,"search_index.db", 0644) or die "dbmopen: $!";
当然，在UNIX中查找文件的最简单的方法是利用UNIX find命令。此例中我们用它列出网点中所有的.html 文件:
open(FILES, "find . -name '*.html' -print|") or die "open
for find: $!";
我们逐个打开HTML并把它们的内容放在一个变量中：
my $filename;
while(defined($filename = <FILES>)) {
print "indexing $filename";
chop $filename;
open(HTML, $filename) or do { warn "open $filename: $!"; next;
};
my $html = join('', <HTML>);
close HTML;
然后用规则表达式取出标题并在网页表单中为此页建一个入口:
my($title)=($html=~/<title>([^<]*)/i);
$title = $filename if(!defined $title);
$db{--$fileno}="<a href=\"$filename\">$title</a>";
现在我们要列出网页上所有的字。首先我们去掉HTML标签：
$html=~s/<[^>]+>//g;
如果我们的搜索对大小写不敏感，那么把所有文字存成同样的字体将简化查询，现在把文件都换成小写字体：
$html=~ tr/A-Z/a-z/;
下面，我们要把文件中所有字都列出：
my @words=($html=~/ \w+/g);
最后，我们把这个字加入倒序索引文件中相应的行，确保同一个字没有索引两遍：
my $last = "";
for (sort @words) {
next if($_ eq $last);
$last = $_;
$db{$_} = defined $db{$_} ? $db{$_}.$fileno : $fileno;
}
基本上就是这样。这是整个脚本。当你在网点上运行它时，它会在你网点的高层目录中生成一个名为“search_index.db”的文件。这个文件包含有你网点上所有字的索引。
注意：脚本运行时间很长，而且会产生一个相当大的文件，这取决于你文件数的多少。我曾做过一个测试，索引文件的大小是原文件大小的百分之四十。
创建搜索用的CGI
我们已有一个索引，现在该考虑让用户使用它。我将执行一次简单的搜索，寻找包含用户输入的所有字的网页。搜索表非常简单：
<form action="/search.cgi">
<p><input name=s><input type=submit value="Search">
</form>
search.cgi读取表单变量并将它剖析成字：
my $query = $ENV{'QUERY_STRING'};
$query =~ s/s=//;
$query =~ s/%[0-9a-fA-F]{2}/ /g;
my @words = ($query =~ /\w+/g);
下面，它打开包含倒序索引的 DBM文件：
use DB_File;
dbmopen(%db,"search_index.db",0);
我们执行查询的策略是为每个相关文件保留一个计数器。我们逐个字进行搜索，如果找到所需的字就让文件的计数器加１：
my %counters;
my $word;
for $word (@words) {
my $pages = $db{lc $word};
my $page;
for $page ($pages =~ /(-\d+)/g) {
$counters{$page}++;
}
}
如果一个文件包含全部要查找的字，它的计数器在每次循环时都增加１，所以它的值将和要查找的字数相等。下面的脚本找出那些文件并显示出来：
for $page (sort keys %counters) {
if($counters{$page}==scalar(@words)) {
my $href = $db{$page};
print "$href<br>";
}
}
这就可以了。这里是整个脚本。当然，这个小搜索引擎还有不少需要改进的地方，但那只是编程的问题了。
（Brian Slesinsky）