4

我有以下情况:

String a = "网络爬虫是一种自动浏览万维网互联网的计算机程序"; String b = "Web Crawler 计算机程序浏览万维网";

是否有任何想法或标准算法来计算相似度的百分比?

例如,上述情况,通过手动查找估计的相似度应该是 90%++。

我的想法是标记两个字符串并比较匹配的标记数量。类似于 (7 个令牌 /1 0 个令牌) * 100。但是,当然,这种方法根本无效。比较匹配的字符数似乎也无效....

任何人都可以提供一些指导吗???

以上是我的项目抄袭分析器的一部分。

因此,匹配的单词将完全相同,没有任何同义词。

在这种情况下,唯一的问题是如何计算一个相当准确的相似度百分比。

非常感谢您的帮助。

4

6 回答 6

5

正如康拉德指出的那样,您的问题在很大程度上取决于“相似”的含义。一般来说,我会说以下指南应该有用:

  • 通过将单词简化为其基本形式并将其小写来规范化输入
  • 使用词频列表(可在网络上轻松获得)并使词的“相似性相关性”与其在频率列表中的位置成反比
  • 将总句子相似度计算为两个句子中出现的单词的聚合相似度除以句子的总相似度相关性

您可以改进该技术以包括词形、句子词序、同义词列表等之间的差异。虽然您永远不会得到完美的结果,但您有很多调整的可能性,我相信总的来说,您可能会获得非常有价值的相似性度量.

于 2010-03-06T16:34:17.770 回答
4

这取决于您对相似性的看法。形式上,您需要定义一个您认为“相似”字符串的度量标准,以便对它们应用统计信息。通常,这是通过假设问题来完成的:“第一个字符串是引入错误(例如通过键入)的第一个字符串的修改版本的可能性有多大?”</p>

对于这种相似性(或者更确切地说是逆),一个非常简单但有效的度量是两个字符串的编辑距离,可以使用动态编程计算,这通常需要时间O ( nm ),其中nm是字符串。

根据您的使用情况,可能需要更精细的度量(或完全不相关的度量,例如soundex metric)度量。

在您的情况下,如果您直接应用标记匹配(即仅字数),您将永远不会获得 > 90% 的相似性。要以有意义的方式获得如此高的相似性,需要高级语义分析。如果你完成了这件事,请发表这篇论文,因为这仍然是一个很大程度上未解决的问题。

于 2010-03-06T16:01:46.730 回答
2

我赞同康拉德鲁道夫已经说过的话。

其他人可能会推荐不同的距离度量。我要说的是伴随着这些,但更多地关注匹配语义的问题。

鉴于您似乎在寻找什么,我建议您应用一些标准的文本处理方法。所有这些都有潜在的缺点,所以我按照应用和难于做好的顺序列出它们

  1. 分句。找出你的比较单位。
  2. 停用词去除:取出a、an、the、of等。
  3. 词袋百分比:整体词匹配的百分比,与排序无关
  4. (更具侵略性)您可以尝试同义词扩展,将同义词视为匹配词。
于 2010-03-06T16:10:29.317 回答
1

这个问题的问题是:相似性可能是人性化相似性(如您所说的“+- 90% 相似性”)或统计相似性(康德拉德鲁道夫的回答)。

人类的相似度永远无法轻易计算:例如这三个词

cellphone car message

mobile automobile post

统计相似性非常低,而实际上它非常相似。因此:很难解决这个问题,我唯一能指出的就是贝叶斯过滤或贝叶斯网络人工智能。

于 2010-03-06T16:10:12.987 回答
1

一种常见的度量是 Levenshtein 距离,它是字符串编辑距离的一种特殊情况。它也包含在apache 字符串实用程序库中

于 2010-03-06T16:12:08.143 回答
0

最长公共子序列是众所周知的字符串不相似度度量,它在动态编程中实现

于 2010-03-06T16:07:56.580 回答