相关搜索引擎的剖析（第一部分）

下载 SimplestSearchEngine.zip - 26.16 KB

引言

我的意图是为互联网上语义搜索的相关性建立一个新的基础，并为从大型文本数据库中信息检索带来一种实用的方法。实际上，我将要说的内容并非新鲜事，因为如今它在主要的互联网搜索引擎中运行得非常好。只是其中的细节被忽略或未被观察到，即使它们一直都存在，这就是为什么今天我们只有少数真正相关的搜索引擎。

目标读者

从事信息检索、语义搜索的人，以及所有使用互联网的人。有很多内容要说，复杂性可能会增加，但我相信从事搜索引擎工作或想了解搜索引擎内部结构的人会有耐心阅读。

我们身处何地

在大型网站中进行搜索时，尤其是在拥有活跃论坛或讨论区的网站中，存在许多问题。大多数这些网站通常在主题表中执行精确搜索，有时使用数据库提供的全文搜索引擎，但相关性非常低。在下面的图片中，我在 Codeproject 网站上搜索了搜索引擎，尽管内部搜索引擎比普通网站提供的搜索引擎好得多，但我们仍然可以在第一页上看到至少一个不相关的结果。当这种情况发生时，一种方法证明很有用，我在浏览器中输入类似 `site:website.com words to find`，一个主要的搜索引擎会显示比网站本身提供的搜索更好的结果。在这个特定的例子中，我们可以使用查询 `site:www.codeproject.com search engines`

在线报纸也存在同样的问题，搜索档案提供的结果非常糟糕。在更多情况下，本地搜索确实很差，你最好使用互联网搜索引擎以获得更好的相关性。但有时你希望索引你的数据，而信息是敏感的——你不能只使用公共搜索引擎来索引它。
如果你在电脑前工作，每天使用主要搜索引擎进行多次搜索，你很快就会发现选择并不多。尝试改变它，你会对新的结果感到失望。你仍然会在第一页结果中找到没有标题的批量文本文档……

而这一切都发生在超过20年的信息检索理论之后。难道这一切都没有问题吗？为什么有些引擎能提供相关结果，而其他的却不能？

一点历史

这一切都始于我试图优化我的一个网站以适应爬虫，并注意到将文档归类为“相关”的技术。在深入研究细节时，我阅读了更多关于信息检索的内容，最终得出了一系列新的结论，并开发了我自己的搜索引擎。当这个搜索引擎被证明是相关的时候，我就知道我所有的假设都是正确的。与此同时，我的网站在一些非常困难的关键词上获得了第一名，因为这里的软件公司大多都在使用它们，当然，了解搜索引擎的内部结构也大有帮助。
今天的互联网上，事情已经基本稳定下来，你很难做出什么来超越大公司。但也许这个理论会改进小型本地相关搜索引擎的生成，从而改进网站搜索。

定义

我将从一组定义开始，这将帮助我们以不同的视角看待事物。其中一些是经典的，另一些将改进现有的定义。

相关性

根据维基百科，_相关性表示检索到的文档集（或单个文档）在多大程度上满足了用户的信息需求_。这对我们来说足够了，我们可以坚持这个定义。或者我们可以将相关性视为搜索引擎检索正确信息的能力。

文档

同样根据维基百科，_信息主体的有界物理表示，其设计具有（通常意图）进行交流的能力_。我们将仅指文本文件，因为录制的语音邮件消息也可以被视为文档。因此，本文档中的任何“文档”都指“文本文件”。

文档摘要（或主题）

文档中产生的思想，通常体现在标题或主题中。

重要提示： 当文档是人工制作且有摘要时，摘要能很好地反映文档的相关性（也许是最好的），因为我们必须同意由人来决定什么才是相关的，机器只搜索人类可能认为相关的文档。

格式良好的文档

一份基于人类语言的相关文档，带有标题（摘要）。这些是最常见的文档形式，由人们为了交流而制作。_格式良好的文档_指的是单一主题，与_复合文档_（见下文）不同。它们都有标题，因为人们倾向于将文档内容总结成标题/主题。当然，它们可以有附加信息，如副标题、日期、描述、外部关键词、段落、噪音等。“格式良好”不指文档的内部表示，如 HTML 格式或其他类似格式。基本上，大多数人类制作的文档都是_格式良好的文档_。
格式良好的文档示例：Word 文档、电子邮件、博客文章、一个好的网页等。它们都有标题，并代表着小块的相关信息。我们也可以将一个名为“旅游网站链接”且没有短语只有链接的网页视为格式良好的文档，因为信息是相关的并被总结在标题中。

批量文本文档

没有标题的文本信息。_批量文本_可以是从（无标题的）论坛帖子到机器生成的日志文件。它没有人为制作的摘要。

重要提示：从_格式良好的文档_和_批量文本_中提取信息有巨大差异。 在第一种情况下，肯定会从中产生一个想法/主题/摘要，通常通过标题体现；而在第二种情况下，尝试提取相关信息可能只是徒劳。其中一些可能只是_不相关的批量文本_，例如日志文件，在这种情况下，只有基本搜索是合理的。
在另一些情况下，它们是_相关的批量文本_，比如论坛帖子，它们可能有也可能没有想法/摘要（参见“哇哈哈”或类似内容的论坛帖子）。这些应该尽可能分开处理。对于互联网用户来说，通常_格式良好的文档_很重要，尽管也应该在_批量文本_中进行搜索。
然而，当用户试图在日志文件中查找某个IP的出现次数时，我们不能谈论语义搜索，但一个好的搜索引擎也会这样做。有时一组批量文本可以有一个标题，并形成一个格式良好的文档，例如一个论坛帖子。如果分析发生在数据库级别，那么它涉及_批量文本_；如果它发生在页面级别，那么我们有一个_格式良好的文档_。搜索引擎应该优先考虑格式良好的文档，同时不忽略批量文本。

复合文档

添加此类别是因为有时我们会在同一个文件中找到混合内容。例如，文档的一部分有一个摘要，文档的另一部分有一个完全不同的想法。就像新闻网站的第一页包含头条新闻，该页面没有真正的摘要，它只是文档引用的总和。如果可能的话，它们应该被分割成“格式良好的文档”，或者被视为“既然它们谈论一切，它们就什么也没谈论”。有时它们可能包含相关信息，但很难相信能够生成相关内容的人会将苹果和鸡蛋混在一起，因此从统计学上讲，它们可能不像其他文档那样具有相关性。

那么，这一切到底是为了什么呢？嗯，基本上，我们将尝试找到符合我们搜索条件的带有_摘要_的_相关文档_。我们偏爱_格式良好的文档_，但它们也可以是_批量文本_或_复合文档_。例如，如果我们搜索“search engine crawler”，我们期望找到包含互联网爬虫/蜘蛛软件或源代码的文档。请注意，那些只提供“search engines”信息的文档与我的搜索并不完全相关。

我不会定义_查询_、_术语_、_权重_、_密度_（_频率_）等术语，因为它们是众所周知的。如果您想进一步阅读但还不了解这些术语，您可以在互联网上搜索它们：）。

一个搜索引擎在数十亿可用页面中，在第一页结果中提供了摘要不相关的文档。

逆文档频率

我将从当今最常见的理论开始，它主要用于学术领域，但并非仅限于此。事实上，如此多的搜索引擎都基于它，以至于很难忽视它。当然，这些搜索引擎会提供一些结果，有时甚至是相关的结果，但并非最相关的结果。我也不会在此赘述，因为我认为关于它的一切都基于一个错误的根基。

逆文档频率理论的基础是

给定一个包含关键词q1,...,qn的查询Q，文档D的BM25得分计算如上，其中f(qi,D)是qi在文档D中的词频，|D|是文档D的词长，avgdl是文档集合中文档的平均词长。k1和b是自由参数，通常选择k1 = 2.0和b = 0.75。IDF(qi)是查询词qi的IDF（逆文档频率）权重。IDF通常计算为

tf-idft = log (N / n(q))，其中 N 是集合中的文档数量，N(q) 是包含 q 的文档数量。

假设一个查询词 q 出现在 n(q) 个文档中。那么随机挑选的文档 D 将以概率（其中 N 再次是集合中的文档集）包含该词。因此，消息“D 包含 q”的信息内容是（见上文）。这个权重是一个统计度量，用于评估一个词对集合或语料库中文档的重要性。重要性与一个词在文档中出现的次数成正比增加，但会受到该词在语料库中频率的抵消。tf-idf 加权方案的变体通常被搜索引擎用作根据用户查询对文档相关性进行评分和排名的核心工具。

好的，我将在这里停止引用，并提出第一个结论。

• 一个词在文档中的权重，如果它在少数文档中多次出现，则权重更高（从而赋予这些文档高区分力）
• 一个词的权重较低，当该词在文档中出现的次数较少，或出现在许多文档中时（因此提供不太明显的相关性信号）
• 当词几乎出现在所有文档中时，其权重最低。

到目前为止看起来还不错，但是……相关性并非一门精确的科学，我们可能会同意某些公式可能效果很好，但这个公式存在一些非常严重的问题。如果成百上千的人不照单全收，并在此基础上构建整个理论，然后尝试制作搜索引擎，那也不会那么糟糕。所以，关于这种_用于文档检索（如网页搜索）的最新检索函数…（维基百科）_，接下来有一些非常明显的问题

• 一个词在文档中的权重，当它在少数文档中多次出现时，权重更高——当然，但仅限于这些文档内部。如果我搜索这个词，这些文档对查询很有用，但这并没有告诉我其中哪个文档相对于其他文档更相关。此外，IDF 假设提供一种通用的提取方法，即使是从批量文本中提取，而真正的问题是，我们是否需要在批量文本中搜索相关信息。
• 挑选包含两个词的文档的概率与这两个词在文档内部的内在相关性无关，因此也与文档与集合中其他文档相对于查询词的相关性无关。计算出的分数只是一种概率分数，与文档在其他文档中的相关性无关，也与查询无关。误导性的相关性概率是第一个重大错误。
• 该公式被扩展到拥有几乎无限文档（互联网）的数据库。它还涉及到词与其他词的关系，而不是文档与其他文档的关系。文档的长度确实很重要，但我稍后会回到这一点。
• 并非每个词的权重都相同，但它确实不取决于词出现的文档数量。我甚至没有提到当今互联网上搜索最多的三个字母的词，有很多文档包含它，看起来大多数人都认为它很重要……如果“car”出现的频率低于“phone”，那是因为人们购买手机比汽车更频繁，因为价格更低。同样，销售手机的公司也更多，原因相同。所以型号也是如此。没有什么能证明“car”不如“phone”重要，特别是如果你住在离办公室两小时的地方（哦，是的，又一个笑话）。无论如何，这就像说“v”字母更相关，因为它出现在更多的小词中，而不是字母“r”，这与相关性无关，这只是人类语言的方式。

关于逆文档频率就说这么多，但确实，并非每个词的权重都相同，我们稍后会看到真正的原因。在IDF之上建立了一整套理论基础，要动摇这样一个系统并不容易，成千上万的人为此工作了多年，花费了数百万。嗯，他们确实有些东西，但不是真正的核心。

例如，我们可以在这里查看一个已知数据库全文搜索引擎中使用的算法。一个几乎不出现的词得分高达100。看来有人走得太远了……

概念

人脑是一个巨大的神经网络，拥有惊人的能力。模式识别以令人难以置信的速度完成，信息的存储和检索也是如此。每当我们遇到一位朋友，我们的大脑就会进行快速搜索，以定位他的图像并将其与其他记忆关联起来。

当我们阅读一份文件时，同样的神经网络会分析书面语言，从中提取概念，形成一套摘要概念并将其作为记忆存储起来。这代表了我们对该文件的理解。如果有人问你这份文件到目前为止讲了什么，你可能会说“搜索引擎、相关性、互联网”等（“没什么大不了的，那家伙在浪费时间”也是可能的）。

大脑从文档中提取了摘要概念，忽略了周围的噪音。在评估文档相关性时，同样的过程也会发生。大脑试图将它正在寻找的概念与文档中的概念进行匹配。如果找到了所有概念，并且它们在文档中的其他概念中被足够_突出_，那么该文档就被认为是_相关的_。

示例

当搜索“汽车保险”时，将尝试将“汽车”和“保险”这两个概念与我们正在寻找的文档进行匹配。仅包含“汽车”的文档是不够的，它还应该包含另一个概念“保险”。“保险”也一样，可以是“房地产保险”或其他类型，所以每次都需要这两个概念。因此，所有包含“汽车”和“保险”的文档可能都很好，但有些可能比其他更好，这取决于这些概念在其中被突出/强调的程度。这些被认为是相关的文档。



每个文档都是一组概念。

• 包含查询中概念的文档 -> 对查询有用的文档
• 带有突出概念的文档 -> 相关文档（在良好文档集中）

我建议查看一个包含人们在互联网上搜索内容的列表，这里或这里都有。现在，你可以计算列表中的动词和形容词；动词很少或根本没有——没有人搜索“walks”或“bring”，形容词也很少。

人们在寻找概念。在人类语言中，概念通常通过_名词_来传递。即使所有词语中除了名词之外的词都缺失，文本也可以被理解（或评估）（我们在快速阅读时也会发生这种情况）。下面是本文档第一句话忽略名词之外的所有内容后的样子

"意图 基础 相关性 搜索 互联网 方法 信息 规模 文本 数据库 互联网 搜索引擎"

现在是没有名词的相同短语

"我的 是 去 设置 一个 新 的 对于 语义 的 在 和 去 带来 一个 实用 的 在 从 大 的 基于"

显然，在第一个例子中，对本文档一无所知的人可以估计本文档是关于_搜索引擎_和_互联网_的。从第二个例子中你很难说本文档是关于什么的……_名词_周围有很多估计性的词，通常是形容词，用来描述概念。这就是为什么我们都搜索名词，并期望找到的名词与我们所寻找的名词相匹配。
它们实际上是_概念_，目前我们姑且将概念与文档中的_名词_关联起来。我确信未来的研究将更接近人类语言，并找到更好的方法来提取概念，即使这些概念并非直接由名词表达。对短语进行语义分析可能会带来更好的结果，我不知道一些“实验室”的进展到了什么程度。

关于名词检索有几种很好的理论，但还有很长的路要走。有时概念是间接的，不是通过直接名词表达的，我们需要学习如何处理它们。

在实践层面，让我们考虑有人搜索“最好的汽车”。实际上要寻找的概念是“汽车”，“最好”只是描述性的。假设我们找到了两个相似的文档，一个包含突出显示（或更多出现次数）的“最好”，另一个包含“汽车”。对于简单的出现次数排名，假设第一个文档有5个“最好”和7个“汽车”出现次数，另一个文档有7个“最好”和5个“汽车”出现次数，文档长度相同。显然，从统计学上讲，突出显示“汽车”的文档更重要。另一个文档可能谈论的是“最好的手机”，而“汽车”可能只是一个次要概念。

词在文档中的权重不同，但不是因为它们在其他文档中出现次数多或少，而是因为它们是或不是概念.

有人会说“best”这个词在互联网上出现的频率比“car”多，我会说“hypanthial”这个词出现的频率真的比“car”少。（我不知道那个词是什么，我只是在韦氏词典中找到了它，它是一个形容词）所以，如果我们需要为文档构建一个“词权重”函数，我们 somehow 需要给予概念/名词更多的重要性（否则“best car 5-7”文档和“best car 7-5”文档会得到相同的分数）。但在文本信息检索中还有很多其他更重要的事情，这就是为什么人们已经主要搜索名词/概念的原因。我这样做更多是为了解决逆文档频率问题，并将“概念”问题引入场景。

总结：
- 文档是一组概念，主要通过名词表达，但这些概念也可以是间接的。搜索时，我们尝试将查询概念与文档中的概念进行匹配。



信不信由你，即使是布兰妮·斯皮尔斯也是一个概念，而且很多人都在寻找它。

 

标题与概念

进一步来说，我们已经认定标题代表着文档中的思想或摘要，它们大部分时间都由概念组成。你很少会发现像“德国汽车很好”这样的标题，这更属于内容，但你可以找到内容总结成标题的例子，比如“德国汽车”，因此是“汽车”概念。当搜索“汽车”时，一个标题为“德国汽车”的文档至少可能存在于好的文档集中，如果不是相关文档的话。
例如。亚马逊的主标题，制作精良：_Amazon.com: 在线购买电子产品、服装、电脑、书籍、DVD_——几乎充满了概念。当你构建一个查询来搜索某物时，请始终记住你在搜索概念，并尝试将其可视化。这将帮助搜索引擎提供更好的结果。

检查标题在内容中的相关性是一项挑战，有时如果你怀疑有垃圾信息或文档制作不佳，你必须在从标题中选择概念还是从文本中选择概念之间做出选择。但是，仅仅依靠从内容中自动检索概念并不能提供更好的结果，因为从统计学上讲，互联网上大多数格式良好的文档都是出于良好意图制作的，因此标题与内容相关，而且你猜怎么着——它是人工制作的。

我还会给一个巧妙的例子。让我们搜索查询“产品是如何制作的？”，我们会找到相当多的匹配项。更重要的是，它们与确切的词（查询中的所有词）匹配，并且内容与标题非常相关。搜索“产品”将为查询“产品是如何制作的？”提供完全不相关的结果。那么为什么“产品”概念不能为“产品是如何制作的”提供相关结果呢？嗯，答案是我在执行搜索之前没有正确地从查询中提取出正确的概念。“产品是如何制作的？”中的概念是“产品制造”而不是单独的“产品”，这将提供更好的结果。

由于从查询中提取间接概念很困难，搜索引擎更倾向于执行_精确搜索_，并查找过去被忽略的词，如停用词。对于“产品是如何制造的”的第一个结果是一个互联网论坛档案，其中第一句话是“产品是如何制造的”解释和详细介绍了各种产品的制造过程，从日常家居用品到复杂的电子设备和重型机械。”所以他们在文档中谈论的概念是“产品制造”，但他们将其总结成一个带有间接概念（制造）的标题。这个命中可能也出现在类似“产品制造过程”的查询结果中，因为这些概念明确地包含在文档中。文档本身并不是真正相关的，但它包含一个指向真正相关文档的链接（我宁愿直接找到那个）。如果我将文档和查询都简化为概念，那么在所有“产品制造”文档中匹配“产品制造”查询会更容易。

我们今天使用的_精确搜索_可能只是通向理解人类语言以及从询问和文档中提取正确概念的临时方法。

分类

既然我们已经决定，大多数情况下，在批量文本中搜索的问题是关于是否而非相关性，并且用户通常寻找结构化信息（_格式良好的文档_），我将讨论一个与相关性计算相关的额外因素。我稍后会回到批量文本的全文搜索，并介绍如何改进当今数据库的全文搜索引擎。基于找到词的简单出现次数或基于IDF（权重之和 - 出现次数乘积）的公式的排名可能不是最佳的。

首先，我将展示一个简单的例子，这是我及时收集的搜索查询列表中观察到的。人们正在寻找实际事件，很多时候这些事件最近在媒体上得到了强调。例如，关于安吉丽娜·朱莉或其他一些明星的新闻——人们会在新闻发生时开始寻找那个名字，并且他们期望找到细节。对于这些人来说，他们找到的文档的_新闻_性质很重要，因此是_相关的_。所以在这种特殊情况下，文档的日期在相关性计算中扮演着重要角色。

从内容角度来看，我们可能会找到更多相关的旧文档，但是，从统计学上讲，即使它们内容很好，对于特定日期的搜索来说，它们也不会像实际文档那样相关。
因此，新闻网站的文档在文档创建日期方面应该与其余网站有不同的处理方法。为了获得良好的结果列表，应在近期_创建日期_和_相关内容_之间取得平衡。第一个结论是，文档分类在排名中必须发挥重要作用。同一文档来自不同来源时可能具有不同的相关性，因此需要对来源进行分类并计算页面排名。但这适用于其他计算之上，即使没有源相关性系统（页面排名），文档也可以很好地排名，我们目前将重点放在由于文档内部概念强调而产生的相关性上。

结论（第一部分）

• 文档是概念的集合。
• _搜索_意味着将查询中的概念与文档中的概念进行匹配。
• 名词比其他词更重要，因为它们通常代表概念。
• 标题和标题总结了文档中的概念。
• 格式良好的文档比批量文本文档更相关。
• 排名也是一个分类问题。

最简单的搜索引擎

为了避免某些先看代码再阅读注释（有时我自己也这样做）的人的负面评论，我附上了一个最简单的搜索引擎模型。没有优化，没有开销，它只是解析几个文本文件，构建倒排索引并执行搜索。它可以改进的第一件事是统一倒排索引中的字符大小写（是的，使用 ToLower()）。



当点击索引按钮时会发生这种情况。只需选择几个长度适中的 .txt 文件。

        // index files
        private void buttonIndex_Click(object sender, EventArgs e)
        {

            if (openFileDialog.ShowDialog() != DialogResult.OK)
                return;
            
            // parse each file and build the inverted index. 
            foreach (string fileName in openFileDialog.FileNames)
            {
                string text = File.ReadAllText(fileName).Replace("\r", " ").Replace("\n", " ");
                string[] terms = text.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);

                // parse each term (word) in text file and put it in dictionary
                foreach (string term in terms)
                {
                    if (!InvertedIndex.ContainsKey(term))
                        InvertedIndex.Add(term, new List());

                    if (!InvertedIndex[term].Contains(fileName))
                        InvertedIndex[term].Add(fileName);
                }
            }

            // update label
            labelIndex.Text = openFileDialog.FileNames.Length.ToString() + " files indexed";
        }

文件被索引后，我们填写搜索文本框并执行多词搜索。结果没有排名，我们只显示包含查询中词语的文档。

        // perform a seach over the inverted index built earlier
        private void buttonSearch_Click(object sender, EventArgs e)
        {

            // split query in terms
            string query = textBoxQuery.Text;
            string[] terms = query.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);


            // see documents for each term and merge them
            List commonDocuments = null;
            foreach (string term in terms)
            {
                // if one term not in index, end search
                if (!InvertedIndex.ContainsKey(term))
                {
                    if (commonDocuments != null)
                        commonDocuments.Clear();
                    break;
                }

                // find documents containing all terms
                if (commonDocuments == null)
                    commonDocuments = InvertedIndex[term];
                else
                    commonDocuments = GetCommonDocuments(commonDocuments, InvertedIndex[term]);
            }


            // display results
            if (commonDocuments != null)
            {
                listBoxResults.Items.Clear();
                foreach (string fileName in commonDocuments)
                    listBoxResults.Items.Add(fileName);
            }
        }




        // merge two arrays of file indexes
        private List GetCommonDocuments(List documentList, List newDocumentsList)
        {
            List common = new List();
            foreach (string file in documentList)
                if (newDocumentsList.Contains(file))
                    common.Add(file);

            return common;
        }

我真的相信上面的代码不需要更多的注释了。就这样，用处不大，只是一个模型，但我们第一部分有源代码。请随时给我发电子邮件到我的 hotmail 地址，adrian_pirvu

历史

2009年3月7日 - 第一部分

参考文献

http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html
http://www.texaswebdevelopers.com/docs/pagerank.pdf
http://en.wikipedia.org/wiki/Probabilistic_relevance_model_(BM25)
http://xapian.org/docs/bm25.html
https://queue.org.cn/detail.cfm?id=988407

搜索引擎的剖析