Tho*_*ann 6 algorithm diff text levenshtein-distance
我正在编写一个diff文本工具来比较两个类似的源代码文件.
周围有很多这样的"差异"工具,但是我的工具会有所改进:
如果它发现一组线在两侧都不匹配(即在两个文件中),它不仅要突出显示这些线,还要突出显示这些线中的各个变化(我在这里称之为线间比较).
我有点工作的解决方案的一个例子:
alt text http://files.tempel.org/tmp/diff_example.png
它目前所做的是采取一组不匹配的线条并再次通过差异运行它们的单个字符,产生粉红色突出显示.
然而,包含"原始2"的第二组不匹配需要更多工作:这里,添加了前两条右线("添加线a/b"),而第三条线是左侧的改变版本.我希望我的软件能够检测到可能的更改和可能的新行之间的这种差异.
看一下这个简单的例子,我可以很容易地发现这种情况:
使用像Levenshtein这样的算法,我可以在3到5的集合中找到所有正确的行,5行最好匹配左行3,因此我可以扣除右边的行3和4被添加,并执行inter左线3和右线5的线比较.
到现在为止还挺好.但我仍然坚持如何将此转换为更通用的算法.
在更复杂的情况下,一组不同的线可以在两侧添加线,其间具有一些紧密匹配的线.这变得非常复杂:
我不仅要匹配左边的第一行和右边的最好的一行,反之亦然,依此类推所有其他行.基本上,我必须匹配左边的每一行与右边的每一行.在最坏的情况下,这可能会产生偶数交叉,因此不再容易清楚哪些线路是新插入的,哪些线路只是被改变了(注意:我不想在这样的块中处理可能移动的线路,除非这实际上会简化算法).
当然,这永远不会是完美的,但我试图让它比现在更好.任何建议不是太神论但相当实用(我不是很好理解抽象算法),这是值得赞赏的.
更新
我必须承认,我甚至不了解LCS算法是如何工作的.我只是给它提供了两个字符串数组,然后列出了哪些序列不匹配.我基本上使用的是这里的代码:http://www.incava.org/projects/java/java-diff
查看代码,我找到一个函数equal(),负责告诉算法两行是否匹配.根据帕维尔的建议,我想知道这是否是我做出改变的地方.但是怎么样？此函数仅返回布尔值 - 而不是可以识别匹配质量的相对值.而且我不能简单地使用一个固定的Levenshtein比率来决定一条相似的线是否仍然被认为是相同的 - 我需要一些自我采用的东西来处理整个线路.
所以,我基本上说的是,我仍然不明白我在哪里应用与不完全匹配的线的相对相似性相关的模糊值.
使用像 Levenshtein 这样的算法，我可以发现在 3 到 5 组中的所有右侧行中，第 5 行与左侧第 3 行最匹配，因此我可以推断右侧的第 3 行和第 4 行被添加，并执行中间行左第 3 行和右第 5 行的行比较。
确定后，使用相同的算法来确定这两个裂缝中的哪些线相互匹配。但你需要稍微修改一下。当您使用该算法来匹配相等的行时，这些行可能匹配也可能不匹配，因此会向您使用的表格的单元格添加 0 或 1。
当比较一大块中的字符串时，其中一些字符串比其他字符串“更平等”（确认奥威尔）。因此，在考虑到目前为止哪个序列最匹配时，他们可以将 0 到 1 之间的实数添加到单元格中。
要计算这个指标（从 0 到 1），您可以应用到您遇到的每一对字符串......对，再次使用相同的算法（实际上，您在执行Levenstein 算法的第一遍时已经这样做了）。这将计算 LCS 的长度，其与两个字符串的平均长度的比率将是度量值。
或者，您可以从 diff 工具之一借用该算法。例如，vimdiff可以突出显示您需要的匹配项。
