百分比相似度分析（Java）

Question

我有以下情况：

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

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

例如，上述情况，手动查看估计的相似性应该是90% ++。

我的想法是对两个字符串进行标记化处理，并比较匹配的标记数。类似于（7个标记/ 10个标记）* 100。但是，当然，这种方法并不有效。比较匹配字符数似乎也不起作用...

有人能给出一些指导吗？

以上是我的项目Plagiarism Analyzer的一部分。

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

在这种情况下，唯一要考虑的是如何计算相似度的相当准确的百分比。

非常感谢任何帮助。

- Mr CooL

Answer 1

正如Konrad所指出的，你的问题在很大程度上取决于你对“相似”一词的理解。一般来说，我认为以下几点指南可能会有用：

• 通过将单词缩减到其基本形式并将其转换为小写来使输入标准化
• 使用单词频率列表（可轻松获取）并使单词的“相似性相关性”与其在频率列表中的位置成反比
• 将总句子相似性计算为两个句子中出现的单词的聚合相似性除以句子的总相似性相关性

你可以完善这种技术，包括单词形式、句子单词顺序、同义词列表等的差异。虽然你永远无法得到完美的结果，但你有很多调整的可能性，我相信通常你可以得到相当有价值的相似度测量。

- Tomislav Nakic-Alfirevic

---

是的，包括频率的倒数权重是一个不错的选择。停用词去除可能是这个过程的一级近似。 - John with waffle

Answer 2

这取决于您对相似性的理解。从形式上讲，您需要定义一种度量方式来确定哪些字符串是“相似”的，以便将统计方法应用于它们。通常，这是通过假设问题来完成的：“第一个字符串是第二个字符串的修改版本，其中引入了错误（例如打字错误），这种情况有多大可能发生？”

一种非常简单但有效的相似度度量方式（或者说是相反的）是两个字符串的编辑距离，可以使用动态规划计算，通常需要O(nm)时间，其中n和m是字符串的长度。

根据您的用途，可能需要更复杂的度量方式（或者完全不相关的，例如soundex度量）。

在您的情况下，如果您直接应用令牌匹配（即仅仅计算单词数量），您将永远无法获得超过90%的相似度。要以有意义的方式获得如此高的相似度需要进行先进的语义分析。如果您完成了这项工作，请发表论文，因为这仍然是一个基本未解决的问题。

- Konrad Rudolph

---

实际上，我现在提出的问题是我“抄袭分析器”项目的一部分...我已经成功地进行了相似性分析，其中一个句子被发送进行分析... 例如，在10个单词中，有7个单词匹配...因此，最终的结果将是相似度百分比，这对我来说是个头疼的问题。你能给我一个关于O(nm)的例子吗？ - Mr CooL

在我的情况下，绝对不会出现拼写错误等问题。无论如何，我会尽可能准确地编写一个计算百分比的程序...感谢提供信息。 - Mr CooL

@Mr CooL：你的使用情况可能排除了编辑距离，因为它总是基于字符相似性。对于抄袭分析器，John的答案可能是最好的、易于实现的解决方案。然而，我预测会有非常高的误报率，因为表达技术属性的简洁方式只有那么多种。因此，在计算相似度时，我会考虑考虑单词顺序。 - Konrad Rudolph

Answer 3

我赞同Konrad Rudolf已经说过的话。

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

考虑到您似乎正在寻找的东西，我建议您应用一些标准文本处理方法。 所有这些都有潜在的缺陷，因此我按照应用和良好执行的难度顺序列出它们：

1. 句子分割。 确定您的比较单位。
2. 停用词去除：去除a，an，the，of等单词。
3. 词袋百分比：总体单词数量的百分之几相匹配，独立于顺序
4. （更积极的）你可以尝试使用同义词扩展，将同义词计为匹配的单词。

- John with waffle

---

非常感谢你，约翰。我已经考虑了你提到的那些。我可以问一下你的意见吗？我的想法是：1）计算每个字符串的标记（单词）并进行比较。2）我发现如果差异在1到10之间，则百分比的机会约为70到90。我应该使用简单的if else来确定百分比。由于这里提出的问题只是我的项目的一部分，所以我有点时间不够用。 - Mr CooL

如果你真的时间不够用，我的建议是：1. 去除停用词 2. 通过编辑距离计算词袋和依赖于单词顺序的百分比（先实现哪个更容易就做哪个）3. 创建百分比阈值（使用简单的 if-else）4. 将实际抄袭文本与非抄袭文本进行比较，并手动修正百分比（如果你有很多样本，请先在一部分文档上进行调整，然后使用其余部分来查看效果）。我的建议是尽快迭代到最后，然后在有时间的情况下想办法变得更加复杂。 - John with waffle

好的。谢谢您的建议和想法。 ;) - Mr CooL

Answer 4

这个问题的难点在于：相似度可能是人性化相似度（如你所说的“+- 90%相似度”）或统计相似度（Kondrad Rudolph的回答）。

人性化相似度永远不容易计算：例如，这三个单词。

cellphone car message

mobile automobile post

统计相似度非常低，但实际上它们是相当相似的。因此：解决这个问题将会很困难，我唯一能指向的就是 贝叶斯过滤 或带有 贝叶斯网络 的人工智能。

- Pindatjuh

Answer 5

一种常见的度量是Levenshtein距离，它是字符串编辑距离的特殊情况。它也包含在apache string util库中。

- bertolami

Answer 6

最长公共子序列是一种著名的字符串不相似度量，它是通过动态规划实现的。

- guest