使用Levenshtein距离计算两个完整文本的相似度

Question

我有两个文本文件需要进行比较，我的做法是：

1. 将它们分成句子。
2. 测量每个来自一个文件的句子与来自第二个文件的每个句子之间的Levenshtein距离。

我想计算这两个文本文件之间的平均相似度，但我遇到了一些问题，因为明显的算术平均数（所有距离[标准化]之和除以比较次数）不是个好主意。

如何解释这样的结果？

编辑： 距离值已被标准化。

- user2207055

---

你可以将距离进行归一化处理，即 d(A,B) / max(length(A), length(B))，然后报告算术平均值。 - Fred Foo

@larsmans，距离已经被归一化了。 - user2207055

那么为什么平均值不是一个好主意呢？ - Fred Foo

@larsmans 由于数据量大：考虑到我已经找到了1个完全匹配和99个距离>0.8的匹配项。平均值与100个>0.8的匹配项不会有明显的区别。 - user2207055

也许如果您说出要比较的文本类型以及对结果的处理方式会更有帮助。我担心的是，一些只有微小编辑距离但意义完全不同的句子（例如“这是一个完整的证明”与“这完全是愚蠢的”）会导致问题。 - us2012

Answer 1

Levenshtein距离具有最大值，即两个输入字符串的最大长度。它不能比这更糟糕。因此，可以将两个字符串a和b的归一化相似性指数（0 = 差，1 = 匹配）计算为1- distance(a,b)/max(a.length, b.length)。

从文件A中选取一个句子。您说要将其与文件B中的每个句子进行比较。我猜您正在寻找B中距离最小（即相似性指数最高）的句子。

简单地计算所有“最小相似性指数”的平均值。这应该给您两个文本之间相似度的粗略估计。

但是，您如何知道两个类似的文本可能会打乱它们的句子？我个人认为，您还应该引入停用词列表、同义词等。

尽管如此：请同时检查三元匹配(trigram matching)，这可能是您正在寻找的另一种好方法。

- alzaimar

---

它还具有最小值，通常与0不同，并且为abs(a.length - b.length)。因此，适当的归一化应该是(distance(a,b)-minval) / (maxval-minval)。 - blues

你确定吗？检查“x”与“The quick frown box”。你的定义得出0（d=19，minval=18）。这两个字符串绝对不相等。 - alzaimar