模糊句子搜索算法

Question

假设我有一组短语-大约10000个-平均长度- 7-20个单词，我想在其中找到一些给定的短语。我正在寻找的短语可能会有一些错误-例如遗漏了一两个单词，一些单词放错了地方，或者一些随机的单词-例如，我的数据库包含“当我骑着我的红色自行车，我看到了Christine"，我非常想要它”因为我骑着我的蓝色自行车，看到Christine"，或者“我正在骑我的自行车，我看到Christine和Marion”。有什么好的方法可以解决这个问题呢？我知道列文斯坦的距离，我也认为这个问题可能没有简单的，好的解决方案。

Answer 1

一个好的文本搜索引擎会提供你所描述的功能，fsh。一种典型的方法是创建匹配任何单词出现的查询，并使用基于彼此邻近出现的项的数量的权重对结果进行排序，并且与它们出现的概率相反地加权，因为不常见的单词将不太可能偶然地共同出现。这类事情有一套完整的理论，叫做信息检索，但你可能对此有所了解。此外，您希望通过规范化大小写、标点符号等并应用一些基本的语言转换(词干)，以及在某些情况下引入同义词字典，特别是当有可用的领域知识来限制它时，来确保单词级别的模糊性得到解释。

如果你对这方面的东西感兴趣，可以试试开源搜索引擎，this article by Vik从2009年的角度给出了一个合理的调查，this one by Middleton and Baeza-Yates对这个主题做了很好的详细介绍。