相关文本在大文本文件中搜索

Question

我有一个大文本文档,我有一个搜索查询(例如:攀岩).我想从文本中返回5个最相关的句子.有哪些方法可以遵循？我是这个文本检索域的新手,所以任何帮助都表示赞赏.

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

只有当某些句子包含整个搜索查询时,上述方法才有效.如果没有包含整个查询的句子,并且某些句子只包含其中一个单词,该怎么办？或者如果它们不包含任何单词怎么办？任何帮助？

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

Answer 1

通常,相关性是您使用某种评分函数定义的.我将举例说明一个天真的评分算法,以及一个常见的搜索引擎排名算法(用于文档,但我为了教育目的将其修改为句子).

天真的排名

这是一个天真排名算法的例子.排名可以简单到:

1. 句子的排名基于查询术语之间的平均接近度(例如,所有可能的查询术语对之间的最大单词数),这意味着"攀岩很棒"的句子排名高于"我不是攀登的粉丝,因为我像岩石一样懒惰."
2. 更多单词匹配排名更高,例如"Climbing is fun"排名高于"Jogging is fun".
3. 在领带的情况下选择按字母顺序或随机的收藏,例如"攀登就是生命"的排名高于"我是摇滚".

一些常见的搜索引擎排名

BM25

BM25是一种很好的稳健算法,用于对与查询相关的文档进行评分.出于参考目的,这是一篇关于BM25排名算法的维基百科文章.您可能希望稍微修改它,因为您正在处理句子,但您可以采用类似的方法将每个句子视为"文档".

在这里.假设您的查询由关键字q ₁,q ₂,...,q _m组成,则句子S相对于查询Q的得分计算如下:

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

ķ ₁和b是自由参数(在[1.2,2.0]而可以被选择为k B = 0.75 -你可以找到一些凭经验良好的值)的F(Q _我,S)是q的术语频率_我在一个句子S(可以视为术语发生的次数),| S | 是句子的长度(以单词表示),AVG_SENT_LENGTH是文档中句子的平均句子长度.最后,IDF(Q _我)是逆文档频率(或者,在这种情况下,逆句子频率)将q的_我,通常计算为:

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 ₁,tf ₁),(sent_id ₂,tf ₂),...,(sent_id _k,tf _k)

基本上,你有关键字的哈希图,你word的值是(sent_id<sub>j</sub>, tf<sub>k</sub>)与句子的ids和单词的频率相对应的对的列表.例如,它可能是:

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

这告诉我们单词rock出现在第一句1次,第5句出现2次.

这个预处理步骤将允许您O(1)访问任何特定单词的术语频率,因此它将根据您的需要快速进行.

此外,您还希望有另一个哈希映射来存储句子长度,这应该是一个相当容易的任务.

如何构建倒排索引？我在你的案例中跳过词干和词形还原,但欢迎你阅读更多关于它的内容.简而言之,您遍历文档,不断为包含单词的hashmap创建成对/增加频率.以下是构建索引的一些幻灯片.