用Perl构建向量空间搜索引擎

2003年2月19日 by Maciej Ceglowski

- 用Perl构建向量空间搜索引擎 - 关于向量的一些话 - 着手进行 - 构建搜索引擎 - 使其更好 - 进一步阅读

为什么浪费时间重新发明轮子，当你可以重新发明引擎呢？ -Damian Conway

作为一名Perl程序员，迟早你会有机会构建一个搜索引擎。就像许多编程任务——解析日期、验证电子邮件地址、写入临时文件——做起来很容易，但要做到正确却很难。大多数人最终都会尝试使用某种反向索引，这是一种将单词与文档列表关联起来的数据结构。然后，他们会在其上构建一种按相关性排序结果的方案。

今天使用的几乎每个搜索引擎——从Google到其他——都是基于一种反向关键词索引。你可以在Perl中编写这样的关键词引擎，但随着你的项目增长，你不可避免地会转向某种关系数据库系统。由于数据库是为快速查找和索引而优化的，因此大多数关键词搜索引擎都会大量使用它们。但为它们编写代码并不有趣。

更重要的是，像Google和Atomz这样的公司已经为小型网站提供了优秀的免费搜索服务。你可以立即获得一个可定制的界面搜索引擎，无需花费时间处理布尔搜索、文本高亮或排名算法。为什么还要重复所有这些努力呢？

作为Perl程序员，我们知道懒惰是一种美德。但我们也知道，做事情有很多种方法。尽管反向索引搜索无处不在，但还有许多其他方法可以构建搜索引擎。它们大多数起源于信息检索领域，研究人员在那里有很多乐趣。不幸的是，关于这些替代方案的文档很难找到。大多数在线资料要么过于技术化，要么过于不切实际，无法用于实际数据集。因此，程序员会留下一个错误的印象，即普通的搜索就是一切。

在这篇文章中，我想向大家展示如何使用一种向量空间模型构建和运行一个搜索引擎，这是一种反向索引查找的替代方案，不需要数据库，实际上也不需要任何文件存储。向量空间搜索引擎消除了许多关键词搜索的缺点，同时引入的自身缺点并不多。最好的是，你只需用几十行Perl代码就可以将其设置起来。

关于向量的一些话

向量空间搜索引擎使用“项空间”的概念，其中每个文档都表示为高维空间中的一个向量。维度数量与整个集合中唯一单词的数量一样多。由于文档在项空间中的位置由其包含的单词决定，因此具有许多共同单词的文档会靠近，而具有少量共同单词的文档则会远离。

为了搜索我们的集合，我们将查询投影到这个项空间，并依次计算查询向量与所有文档向量之间的距离。那些在一定阈值距离内的文档将被添加到我们的结果集中。如果你觉得这些听起来像是胡言乱语，那么不要担心——当我们编写代码时，它会变得清晰。

向量空间数据模型为我们提供了一种具有几个有用功能的搜索引擎

搜索在RAM中进行，没有磁盘或数据库访问
查询可以任意长
用户无需担心布尔逻辑或正则表达式
在返回的文档上执行“查找相似”搜索非常简单
您可以设置一个“保存结果”篮子，并对其中的文档进行相似度搜索
您可以谈论“向量空间”并让您的朋友印象深刻

开始工作

通过一个具体的例子，您最容易理解向量模型。

假设您有一组10个文档，总共包含50个独特的单词。您可以通过计算文档中每个单词出现的次数来表示每个文档为一个向量，然后沿着适当的轴移动相应的距离。所以如果文档A包含句子“cats like chicken”，那么您找到cat的轴，移动一个单位，然后对like和chicken做同样的事情。由于其他47个单词没有出现在您的文档中，所以您根本不需要沿着相应的轴移动。

绘制这个点和从原点到它的线，您就得到了您的文档向量。像任何向量一样，它有大小（由每个单词出现的次数决定），以及方向（由哪些单词出现以及它们的相对丰富度决定）。

这里有几点需要注意

第一点是，我们丢弃了所有关于单词顺序的信息，并且无法保证向量是唯一的。如果我们以句子“chickens like cats”开始（暂时忽略复数），那么我们最终会得到一个相同的文档向量，尽管文档并不相同。

这看起来可能是一个很大的限制，但事实是，自然语言中的单词顺序很少包含关于内容的信息 - 您可以通过研究单词列表来推断出文档的大部分内容。这对英语专业的人来说是坏消息，对我们来说却是好消息。

第二点是，在我们的文档向量中，有50个可能的值中有三个是非零的，因此我们的文档向量是稀疏的。这对于任何自然语言集合都是正确的，因为给定的文档将只包含语言中所有可能单词的一小部分。这使得即使对于大型集合，也可以在内存中构建搜索引擎，尽管细节超出了本文的范围。重要的是，您可以在不依赖磁盘访问的情况下将此模型扩展得相当大。

要运行向量空间搜索引擎，我们需要做以下几步

组装一个文档集合
创建一个词空间并将文档映射到其中
将查询映射到相同的词空间
将查询向量与存储的文档向量进行比较
返回按距离排列的最近文档列表

现在让我们看看如何在Perl中实现这些步骤。

构建搜索引擎

我们将从一个由四个文档组成的微小集合开始，每个文档只有几个单词长

        "The cat in the hat"

        "A cat is a fine pet."

        "Dogs and cats make good pets."

        "I haven't got a hat."

我们的第一步是找到文档集中所有的独特单词。最简单的方法是将每个文档转换为单词列表，然后将列表合并成一个。这里有一个（糟糕）方法

        sub get_words { 
                my ( $text ) = @_;
                return map { lc $_ => 1 }
                       map { /([a-z\-']+)/i } 
                       split /\s+/s, $text;
        }

子例程将文本字符串按空白分隔，移除所有标点符号（除了连字符和撇号），然后在返回单词的哈希之前将所有内容转换为小写。

好奇的do语句只是一个创建查找哈希的紧凑方式。%doc_words最终将包含我们的单词列表作为其键，其值将是每个单词出现的次数。

如果我们依次对这个“解析器”运行所有四个文档，那么我们会得到一个主单词列表

        a
        and
        cat
        cats
        dogs
        fine
        good
        got
        hat
        haven't
        i
        in
        is
        make
        pet
        pets
        the

请注意，这个列表中的许多单词都是垃圾单词 - 代词、冠词和其他在搜索环境中没有用处的语法杂波。搜索引擎设计中常用的一个程序是使用一个停用词表来删除这些单词。下面是这个子例程，添加了一个简单的停用词表，过滤掉最常见的单词

        our %stop_hash;
        our @stop_words = qw/i in a to the it have haven't was but is be from/;
        foreach @stop_words {$stop_hash{$_}++ };


        sub get_words {


                # Now with stop list action!


                my ( $text ) = @_;
                return map { $_ => 1 }
                       grep { !( exists $stop_hash{$_} ) }
                       map lc,
                       map { /([a-z\-']+)/i } 
                       split /\s+/s, $text;
        }

一个真正的停用词表会更长，并且会根据我们的文档集合量身定制。你可以在列表1的DATA部分找到一个真正的停用词表，以及这里描述的搜索引擎的完整实现。注意，由于Perl快速的散列查找算法，我们可以在不牺牲程序速度的情况下拥有一个庞大的停用词表。因为自然语言中的单词频率遵循幂律分布，去除最常见的单词可以从我们的向量中去除不成比例的大量内容。

这是我们在用停用词表处理后单词列表看起来像什么

        cat
        cats
        dogs
        fine
        good
        got
        hat
        make
        pet
        pets

我们已经将列表缩小了很多，这是好的。但请注意，我们的列表包含一些变体（“cat”和“cats”，“pet”和“pets”），它们只在数量上有所不同。另外，请注意，在搜索集合中的“dog”时，即使复数形式的“dogs”是一个有效的匹配项，也不会得到任何匹配。这是不好的。

这是搜索引擎设计中的常见问题，所以CPAN上当然有一个模块来解决这个问题。我们需要的那段代码被称为一个词干提取器，它是一套从英语单词中去除后缀的启发式算法，留下一个共同的根。我们可以从CPAN获得的词干提取器使用的是Porter词干提取算法，这是一种不完美但非常优秀的在英语中找到词干的方法。

        use Lingua::Stem;

我们将把词干提取器包裹在我们的子例程中，以隐藏Lingua::Stem的繁琐语法

        sub stem {
                my ( $word) = @_;
                my $stemref = Lingua::Stem::stem( $word );
                return $stemref->[0];
        }

下面是如何将其折叠到get_words子例程中的方法

        return map { stem($_) => 1 }
               grep { !( exists $stop_hash{$_} ) }
               map lc,
               map { /([a-z\-']+)/i } 
               split /\s+/s, $text;

请注意，我们在提取词干之前应用了停用词表。否则，一个像beings这样的有效单词（它提取为be）会被过于热情的停用词表捕获。在搜索算法设计中小心翼翼地犯这种小错误很容易，所以要格外小心。

添加了词干提取器后，我们的单词列表现在看起来像这样

        cat
        dog
        fine
        good
        got
        hat
        make
        pet

好多了！我们已将原始列表的大小减半，同时保留了所有重要内容。

现在我们有了完整的内容单词列表，我们准备好进行第二步——将我们的文档映射到术语空间。因为我们的集合有八个内容单词，所以每个文档将映射到一个八维向量。

这里是一个例子

        # A cat is a fine pet



        $vec = [ 1, 0, 1, 0, 0, 0, 1 ];

句子“A cat is a fine pet”包含三个内容单词。查看我们的单词排序列表，我们发现cat、fine和pet分别位于一、三、八个位置，所以我们创建一个匿名数组，在这些位置上放一，其他位置放零。

如果我们想反向操作，那么我们可以取向量，并在排序的单词列表中查找适当位置的零值，从而得到文档中的内容单词（但没有任何关于单词顺序的信息）。

在这里使用Perl数组的问题在于它们不会扩展。Perl数组消耗大量内存，而且没有比较数组的本地函数。我们不得不循环遍历我们的数组，这很慢。

一个更好的数据处理方法是使用PDL模块，这是一套专为与矩阵代数一起使用而编译的Perl C扩展。您可以在CPAN上找到它。PDL代表“Perl数据语言”，确实是一种强大的语言，它优化了进行巨大多维矩阵的数学运算。我们将会使用其功能的一小部分，就像驾驶法拉利去邮箱一样。

结果发现，PDL向量（或“piddle”）看起来与我们的匿名数组相似

        use PDL;
        my $vec = piddle [ 1, 0, 1, 0, 0, 0, 1 ];


        > print $vec

        [1 0 0 1 0 0 0 1]

我们将piddle构造函数的参数设置为相同的匿名数组，然后将其转换为更小的数据结构，从而减少存储需求。

由于我们已经知道每个文档向量中的大部分值将是零（记得自然语言是多么稀疏），向piddle构造函数传递完整长度的数组可能会有些繁琐。因此，我们将使用一个快捷方式来创建一个零填充的piddle，然后显式设置非零值。为此，我们有zeroes函数，它将向量的尺寸作为其参数

        my $num_words = 8;
        my $vec = zeroes $num_words;



        > print $vec

        [0 0 0 0 0 0 0 0 0]

要将某个零值设置为其他值，我们必须使用神秘的PDL语法

        my $value = 3;
        my $offset = 4;



        index( $vec, $offset ) .= $value;

        > print $vec;

        [0 0 0 3 0 0 0 0 0]

在这里，我们说的是“取这个向量，并将位置4的值设置为3”。

结果是，我们只需要创建一个文档向量。现在我们只需遍历每个文档的单词列表，并在相应的向量中设置适当的值。以下是一个完成整个过程的子程序

        # $word_count is the total number of words in collection
        # %index is a lookup hash of word to its position in the master list



        sub make_vector {
                my ( $doc ) = @_;
                my %words = get_words( $doc );  
                my $vector = zeroes $word_count;


                foreach my $w ( keys %words ) {
                        my $value = $words{$w};
                        my $offset = $index{$w};
                        index( $vector, $offset ) .= $value;
                }
                return $vector;
        }

现在，我们能够为我们的文档集合中的每个文档生成一个向量，以及将查询转换为查询向量（通过将查询输入到make_vector子程序），我们所缺少的只是一个计算向量之间距离的方法。

有很多种方法可以实现这一点。其中最简单（也是最直观）的一种是余弦度量。我们的直觉是，具有许多共同单词的文档向量将大致指向同一方向，因此两个文档向量之间的角度是衡量它们相似性的良好指标。取该角度的余弦值将给我们一个从零到一之间的值，这很方便。没有共同单词的文档将具有余弦值为零；完全相同的文档将具有余弦值为一。部分匹配将具有中间值 - 该值越接近一，文档的相关性就越高。

计算余弦的公式是

        cos  = ( V1 * V2 ) / ||V1|| x ||V2||

其中V1和V2是我们向量，竖线表示2-范数，而*表示内积。您可以相信数学，也可以在任何线性代数书籍中查找。

使用PDL，我们可以轻松表达这种关系

        sub cosine {
                my ($vec1, $vec2 ) = @_;
                my $n1 = norm $vec1;
                my $n2 = norm $vec2;
                my $cos = inner( $n1, $n2 );    # inner product
                return $cos->sclr();  # converts PDL object to Perl scalar
        }

我们可以使用norm函数将向量归一化为单位长度，因为我们不感兴趣的是它们的绝对大小，只关心它们之间的角度。

现在，我们已经有了计算向量之间距离的方法，我们几乎准备好运行我们的搜索引擎。最后的拼图是一个子程序，用于接受一个查询向量并将其与所有文档向量逐一比较，返回一个按顺序排列的匹配列表

        sub get_cosines {
                my ( $query_vec ) = @_;
                my %cosines;
                while ( my ( $id, $vec ) = each  %document_vectors ) {
                        my $cosine = cosine( $vec, $query_vec );
                        next unless $cosine > $threshold;
                        $cosines{$id} = $cosine;
                }
                return %cosines;
        }

这将返回一个哈希，其文档ID作为键，余弦值作为值。我们将从这个search子程序中调用它，这将是我们的模块与外界交互的接口

        sub search {
                my ( $query ) = @_;
                my $query_vec = make_vector( $query );
                my %results = get_cosines( $query_vec );
                return %results;
        }

现在剩下的事情只是按余弦值（降序）对结果进行排序，格式化，并将它们显示给用户。

您可以在列表1中找到这种代码的面向对象实现，其中包括内置的停用词列表和一些使搜索更快的小改动（好奇的人可以知道，我们在存储文档向量之前对其进行归一化，以避免每次运行cosine子程序时都进行归一化）。

一旦我们实际编写了代码，使用它就很简单了

    use Search::VectorSpace;



    my @docs = get_documents_from_somewhere();


    my $engine = Search::VectorSpace->new( docs => \@docs );


    $engine->build_index();
    $engine->set_threshold( 0.8 );


    while ( my $query = <> ) {
        my %results = $engine->search( $query );
        foreach my $result ( sort { $results{$b} <=> $results{$a} }
                             keys %results ) {
                print "Relevance: ", $results{$result}, "\n";
                print $result, "\n\n";
        }


        print "Next query?\n";
    }

就这样，一个即时搜索引擎，全部用Perl实现。

使其更完善

有很多种方法可以改进这个基本模型。以下是一些可以考虑的想法

更好的解析
我们的get_words子例程是基础的——代码相当于一把磨尖的棍子。一方面，它在包含超链接、缩写或XML的文本上会完全失败。它也不会识别专有名词或包含多个单词的术语（如“独立国家联合体”）。你可以通过使用像HTML::TokeParser这样的模块来移除HTML和其他标记，并内置一个词性标注器来找到专有名词和名词短语（寻找即将到来的我们的Lingua::Tagger::En，很快将在CPAN上发布）。

非英语集合
Perl拥有出色的Unicode支持，而向量模型不关心语言，所以我们为什么只限于英语？只要你能编写解析器，你就可以将搜索适配到任何语言。

你可能需要一个特殊的词干算法。对于某些语言（如中文、意大利语）来说，这可能像做馅饼一样简单，而对于其他语言（如阿拉伯语、俄语、匈牙利语）来说则非常困难。这完全取决于语言形态。你可以在网上找到针对几个西欧语言的已发表词干算法，包括德语、西班牙语和法语。

相似度搜索
给搜索引擎添加“查找相似”功能很容易。只需使用现有的文档向量作为查询，其他一切都会就位。如果你想对多个文档进行相似度搜索，那么就添加这些向量。

词项加权
词项加权是一种说“一些词比其他词更重要”的时髦方式。如果做得适当，它可以大大提高搜索结果。

你在构建文档向量时计算权重。局部加权根据单词在单个文档中出现的次数为单词分配值，而全局加权则根据整个集合中的单词频率分配值。直觉上，罕见单词比常见单词更有趣（全局加权），而文档中只出现一次的单词不如多次出现的单词相关（局部加权）。

纳入元数据
如果你的文档有元数据描述符（日期、类别、作者姓名），那么你可以将它们纳入到向量模型中。只需为每个类别添加一个槽，就像你为关键词所做的那样，并应用你想要的任何类型的加权。

精确短语匹配
你可以通过向结果集添加一系列过滤器来添加任意约束到你的结果集。精确短语匹配的一个简单方法是使用正则表达式遍历你的结果集。这种后处理也是按除相关性之外的其他因素对结果进行排序的便捷方式。

进一步阅读

关于搜索引擎设计的材料非常丰富，但其中很少是针对业余爱好者或初学者的。以下是一些良好的起点

http://hotwired.lycos.com/webmonkey/code/97/16/index2a.html?collection=perl
这篇文章可以追溯到1997年，但仍然是Perl编写反向索引搜索引擎的最好教程。

https://web.archive.org/web/20010409205457/http://moskalyuk.com/software/perl/search/kiss.htm
这是一个简单的关键词搜索引擎示例——没有数据库，只是对Perl快速解析文件的能力充满信心。

http://www.movabletype.org/download.shtml
可移动类型是一款流行的博客应用程序，用Perl编写。搜索引擎位于MT::App::Search中，并支持多个高级功能。它外观并不美观，但确实是实际的生产代码。

http://jakarta.apache.org/lucene/docs/index.html
Lucene是一个基于Java的关键字搜索引擎，是Apache项目的一部分。它是一个设计精良的开源搜索引擎，适用于大型项目。文档讨论了实现大型搜索引擎的一些挑战；即使你不懂Java，也值得一读。

http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=3391
统计自然语言处理基础，麻省理工学院出版社（精装教科书）。不要被标题吓到——这本书是关于文本搜索所有问题的绝佳介绍，并详细讨论了向量空间模型。

http://www.nitle.org/lsi/intro/
潜在语义索引的介绍，这是一种增强的向量模型。本文档面向非技术读者，但提供了一些关于使用向量技术搜索和可视化数据集合的背景信息。

冒险者还可以在http://www.nitle.org/lsi.php.下载一些用于潜在语义索引的Perl代码。代码和文章都来自我为国家技术自由教育研究所所做的个人工作。

标签

工具