我一直在致力于一个项目,开发一种更可扩展的方式来创建古代文本的概要(本质上是与突出显示的差异进行并排比较,但可以选择仅关注语义上有用的差异。)这意味着它使用字符差异是最有意义的(主要是因为其中一些差异是一个额外的元音字母,可以这么说,这并不“重要”。)我已经实现了迈尔斯差异算法,如上所述在 Javascript 中的 https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/(以及后续两部分)的精彩博客文章中,我将其附加在这篇文章的底部。
Coglan 指出,Myers diff 算法是贪婪的 - “在进行更改之前尝试消耗尽可能多的相同行” - 从而避免了所谓的“错误结束”问题:
Good: class Foo Bad: class Foo
def initialize(name) def initialize(name)
@name = name @name = name
end + end
+ +
+ def inspect + def inspect
+ @name + @name
+ end end
end end
我想知道在逐个字母比较时是否有办法避免这种情况。使用上面的示例,Coglan 描述的实现在“逐个字母”的情况下会产生以下结果: 代码认为我已添加的“end”实例(应该是最后三个字母)是相反,def 中的“e”,inspect 中的“n”,以及第一端中的“d”。
在我的用例中,当我尝试跳过因使用阿拉姆语首字母缩略词而出现的差异时,我遇到了这个问题。所述首字母缩略词的形式为LLL"L,其中每个L(字母)取自其所代表的单词的第一个字母,并且双引号置于首字母缩略词的倒数第二个和最后一个字母之间。注意,没有阿拉姆语中的大写字母(这自然是测试英语中潜在缩写词的第一件事。)我在示例中用包含缩写词的黄色标记突出显示(在其他文本中完全拼写出来)被 diff 删除的空格显示为向下的箭头: 正如您可能看到的,非突出显示的差异就像一个魅力。很容易分辨出“额外”或“交换”的字母在哪里,这些数据对我来说很重要。并且还可以显示所有首字母缩略词/纯文本对(除了第一个突出显示的对)都展示了一种规则模式。 (共享黑色字母,然后删除字母直到单词末尾 - 即直到出现红色箭头 - 然后另一个共享黑色字母,等等...)像这样的首字母缩略词类似于将“C.G.I”与“计算机生成”进行比较图像”,全文“计算机生成的魔法”中没有一个字母是缩写词中的字母。但是,当首字母缩略词类似于“A.C.M”和“association [for]computer Machinery”时,其中“computing”包含 M/m(同样在这种情况下没有大写的约束下),差异将使用该 m 。这就是 א״ר 和 אמר רבй 的情况。尽管前者是后者的缩写,但分析认为,אמר单独变成א״ר;再次,由于错误的结束问题。
我知道单独解决这个问题的首选方法可能只是返回差异词,但随后我就失去了我开发的许多其他功能...... 无论如何,这是代码(同样是 Javascript;基于上面的博客文章。)
function myersDiff(oldTokens, newTokens) {
const m = oldTokens.length;
const n = newTokens.length;
const max = m + n;
//max amount of moves we may need to make
const v = new Map();
//map contains trace in order
v.set(1, 0);
let path = [];
//get shortest edit graph using the 45-degree k-lines at each depth d
for (let d = 0; d <= max; d++) {
path[d] = new Map();
for (let k = -d; k <= d; k += 2) {
/* e.g. if depth is 6, consider all options from -12 to 12 since the trace is a sparse binary tree
if k = -d, we're on the edge of the graph. We can only go downward (i.e. left). If k = d, we can only go up-right (i.e. right.)
Otherwise, check the elements to the right and left (k+1, k-1) and take the highest x-value
*/
let x;
if (k === -d || (k !== d && v.get(k - 1) < v.get(k + 1))) {
x = v.get(k + 1);
} else {
x = v.get(k - 1) + 1; //when moving rightward, the k-line index is higher
}
let y = x - k;
//edit graph should consider diagonals to add 0 cost
while (x < m && y < n && oldTokens[x].letter === newTokens[y].letter) {
x++;
y++;
}
v.set(k, x);
path[d].set(k, { x, y });
//check for end
if (x >= m && y >= n) {
return buildChanges(path, oldTokens, newTokens);
}
}
}
}
function buildChanges(path, oldTokens, newTokens) {
const changes = [];
let d = path.length - 1;
let x = oldTokens.length;
let y = newTokens.length;
while (d >= 0) {
const k = x - y;
const step = path[d].get(k);
let prevK;
if (k === -d || (k !== d && path[d - 1] && path[d - 1].has(k - 1) && path[d - 1].get(k - 1).x < path[d - 1].get(k + 1)?.x)) {
prevK = k + 1;
} else {
prevK = k - 1;
}
const prevStep = path[d - 1]?.get(prevK);
//backtrack to construct the list, privileging diagonals
while (x > (prevStep?.x || 0) && y > (prevStep?.y || 0)) {
changes.unshift({ type: "unchanged", token: oldTokens[x - 1].letter, capital: oldTokens[x-1].capital });
x--;
y--;
}
if (x > (prevStep?.x || 0)) {
changes.unshift({ type: "removed", token: oldTokens[x - 1].letter, capital: oldTokens[x-1].capital });
x--;
} else if (y > (prevStep?.y || 0)) {
changes.unshift({ type: "added", token: newTokens[y - 1].letter, capital: newTokens[y-1].capital });
y--;
}
d--;
}
return changes;
}
我通常使用更常见的最长公共子序列算法来完成此类操作,但随后会在开始或结束比赛(对角序列)的路径成本中添加决胜局惩罚。
惩罚的大小应根据开始或结束位置的理想程度而变化。
各处的小惩罚将导致算法更倾向于连续匹配,而不是总大小相同的破碎匹配,这通常很好。
您可以提高在单词中间开始或结束的惩罚,这将有利于整个单词匹配。
请注意,这将需要跟踪矩阵中每个位置的 3 个数字:总编辑成本、通过匹配(对角线移动)到达那里时的最佳惩罚,以及通过非匹配到达那里时的最佳惩罚。