2

我有一个大文本文档，并且有一个搜索查询（例如：攀岩）。我想从文本中返回 5 个最相关的句子。可以遵循哪些方法？我是这个文本检索领域的新手，因此感谢您的帮助。

我能想到的一种方法是：逐句扫描文件，在句子中查找整个搜索查询，如果匹配则返回该句子。

仅当某些句子包含整个搜索查询时，上述方法才有效。如果没有包含整个查询的句子并且某些句子仅包含一个单词怎么办？或者如果它们不包含任何单词怎么办？有什么帮助吗？

我的另一个问题是我们可以预处理文本文档以使构建索引更容易吗？trie 是一个很好的预处理数据结构吗？

4

1 回答 1

5

一般来说，相关性是您使用某种评分函数定义的。我会给你一个简单的评分算法的例子，以及一种常见的搜索引擎排名算法（用于文档，但我将其修改为用于教育目的的句子）。

天真的排名

这是一个朴素排名算法的示例。排名可以很简单：

  1. 根据查询词之间的平均接近度（例如所有可能的查询词对之间的最大词数）对句子进行排名，这意味着句子“攀岩很棒”的排名高于“我不喜欢攀岩，因为我像石头一样懒惰。”
  2. 更多的词匹配排名更高，例如“攀岩很有趣”的排名高于“慢跑很有趣”。
  3. 如果出现平局，请按字母顺序或随机选择最爱，例如“攀登就是生活”的排名高于“我是一块石头”。

一些常见的搜索引擎排名

BM25

BM25 是一种很好的鲁棒算法，用于对与查询相关的文档进行评分。出于参考目的，这里有一篇关于BM25 排名算法的 Wikipedia 文章。您可能希望对其进行一些修改，因为您正在处理句子，但您可以采取类似的方法，将每个句子视为“文档”。

就这样吧。假设您的查询由关键字 q 1 , q 2 , ... , q m组成，句子S相对于查询Q的分数计算如下：

SCORE(S, Q) = SUM(i=1..m) (IDF(q i * f(q i , S) * (k 1 + 1) / (f(q i , S) + k 1 * ( 1 - b + b * |S| / AVG_SENT_LENGTH))

k 1和 b 是自由参数（可以在 [1.2, 2.0] 和 b = 0.75 中选择 k ——你可以根据经验找到一些好的值） f(q i , S) 是 q i在句子中的词频S（可以视为该术语出现的次数），|S| 是句子的长度（以单词为单位），AVG_SENT_LENGTH 是文档中句子的平均句子长度。最后，IDF(q i ) 是 q i 的逆文档频率（或者，在这种情况下，逆句子频率），通常计算为：

IDF(q i ) = log ((N - n(q i ) + 0.5) / (n(q i ) + 0.5))

其中N是句子总数，n(q i ) 是包含 q i的句子数。

速度

假设您不存储倒排索引或任何其他数据结构以进行快速访问。这些是可以预先计算的术语：N、*AVG_SENT_LENGTH*。

首先，注意匹配的词越多，这句话的得分就越高（因为总和）。因此，如果您从查询中获得前k个术语，您确实需要计算值 f(q i , S)、|S| 和 n(q i )，这将采用O(AVG_SENT_LENGTH * m * k)，或者如果您正在对最坏的情况是O(DOC_LENGTH * m)时间，其中k是匹配项数最多的文档数，m是查询项数。假设每个句子大约是 AVG_SENT_LENGTH，你必须为k个句子中的每一个走m次。

倒排索引

现在让我们看看倒排索引以实现快速文本搜索。我们会将您的句子视为用于教育目的的文件。这个想法是为您的 BM25 计算构建一个数据结构。我们需要使用倒排列表来存储词频：

单词i : (sent_id 1 , tf 1 ), (sent_id 2 , tf 2 ), ... ,(sent_id k , tf k )

基本上，您有哈希图，其中您的键word和您的值是(sent_id<sub>j</sub>, tf<sub>k</sub>)对应于句子 id 和单词频率的对列表。例如，它可能是：

摇滚：(1, 1), (5, 2)

这告诉我们，rock 这个词在第一句出现了 1 次，在第五句出现了 2 次。

此预处理步骤将允许您O(1)访问任何特定单词的术语频率，因此它会像您想要的那样快。

此外，您可能希望有另一个 hashmap 来存储句子长度，这应该是一项相当容易的任务。

如何建立倒排索引？在您的情况下，我将跳过词干提取和词形还原，但欢迎您阅读有关它的更多信息。简而言之，您遍历文档，为包含单词的哈希图不断创建对/增加频率。这里有一些关于建立索引的幻灯片。

于 2013-07-12T05:54:02.883 回答