如何比较短语的相似性？

Question

输入问题时，stackoverflow 会向您显示它认为可能涵盖同一主题的问题列表。我在其他网站或其他程序（例如帮助文件系统）上也看到过类似的功能，但我自己从未编写过类似的功能。现在我很好奇人们会使用哪种算法来实现这一点。

我想到的第一个方法是将短语拆分为单词并查找包含这些单词的短语。在此之前，您可能想扔掉无关紧要的单词（例如“the”、“a”、“does”等），然后您需要对结果进行排名。

嘿，等等 - 让我们对网页这样做，然后我们就可以有一个......手表卡利特...- 一个“搜索引擎”，然后我们可以销售广告，然后......

不，说真的，解决这个问题的常用方法是什么？

Answer 1

一种方法是所谓的词袋模型。

正如您所猜测的，首先计算单词在文本（在 NLP 术语中通常称为文档）中出现的次数。然后你扔掉所谓的停用词，例如“the”、“a”、“or”等等。

你只剩下单词和字数了。这样做一段时间，您就会得到文档中出现的一组全面的单词。然后您可以为这些单词创建索引：“aardvark”是 1，“apple”是 2，...，“z-index”是 70092。

现在你可以把你的词袋变成向量。例如，如果您的文档包含土豚的两个引用而没有其他内容，则它将如下所示：

[2 0 0 ... 70k zeroes ... 0].

之后你可以计算两个向量之间的“角度” 点积. 。角度越小，文档越近。

这是一个简单的版本，还有其他更高级的技术。愿 维基百科与你同在.

Answer 2

@Hanno你应该尝试Levenshtein距离算法。给定一个输入字符串 s 和一个字符串列表 t 迭代每个字符串 你 在 t 并返回编辑距离最小的那个。

http://en.wikipedia.org/wiki/Levenshtein_distance

请参阅 Java 实现示例 http://www.javalobby.org/java/forums/t15908.html

Answer 3

为了增强词袋的想法：

您还可以通过多种方式关注 n 元语法，即两个或多个按顺序排列的单词组成的字符串。您可能想要这样做，因为搜索“空间复杂性”不仅仅是搜索其中包含“空间”和“复杂性”的事物，因为该短语的含义不仅仅是其各个部分的总和；也就是说，如果你得到的结果谈论的是外层空间和宇宙的复杂性，那么这可能不是搜索“空间复杂性”的真正含义。

自然语言处理的一个关键思想是 互信息, ，它允许您（从算法上）判断一个短语是否真的是一个特定的短语（例如“空间复杂度”）或只是巧合相邻的单词。从数学上讲，主要思想是从概率上询问这些单词彼此相邻出现的频率是否比您仅根据它们的频率猜测的频率要高。如果您在搜索查询中（或在索引时）看到互信息得分较高的短语，则可以通过尝试保持这些单词的顺序来获得更好的结果。

Answer 4

根据我（相当少的）开发全文搜索引擎的经验：我会查找包含查询中的一些单词的问题（在您的情况下，查询就是您的问题）。当然，干扰词应该被忽略，我们可能想要检查“强”词（如“ASP.Net”）的查询，以缩小搜索范围。http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>倒排索引通常用于查找包含我们感兴趣的单词的问题。

从查询中找到包含单词的问题后，我们可能想要计算问题中我们感兴趣的单词之间的距离，因此包含“短语相似性”文本的问题的排名高于包含“讨论相似性，您听到以下短语...”文本的问题。