模糊差异度量的差异算法

Question

模糊差异度量的差异算法

3

我正在寻找一种类似于最长公共子序列算法的算法，它具有字母相似度量。我的意思是，已知的算法将字母表中的所有字母视为完全不同，而我的用例中有些字母更容易编辑成另一个字母，因此应该由diffing算法视为相似。

例如，您可以考虑在文本行上工作的diffing算法，其中某些行与其他行更相似。

论文An O(ND) Difference Algorithm and Its Variations在第4页上指出：考虑为每个边添加权重或成本。将对角线边缘赋予权重0，非对角线边缘赋予权重1。我想有一个选项来分配任何从[0;1]区间内的权重。

- Gracjan Polak

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hmicn · Accepted Answer

最长公共子序列（LCS）问题通常通过动态规划方法计算，您可以调整现有的方法以将其应用于您的用例。

在这个解释LCS如何工作的示例中（来自维基百科https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example），您应该考虑调整算法，使得：

不是得分： score_j = socre_i + 1，对于j = i +1（也就是说，当找到新的公共项时，您会添加1），当向LCS添加新项时，您应该得分： score_j = F(score_i, p(letter_i, letter_j))无论如何。

p(letter_i, letter_j)是从letter_i更改为letter_j的概率（即您所说的权重[0,1]）
F是一个聚合函数，用于根据概率p从score_i到score_j。

例如，F 可以被定义为 operator +。然后它将产生： score_j = score_i + p(letter_i, letter_j)) 或者更精确地说： score_j = score_i + p(letter_i, letter_j)) x 1 （将x 1读作字符的）。这将给出您可以在算法结束时通过回溯找到的2个子序列的最大相似度（字符）。

您可以找到自己的函数F以获得更好的结果。