解决Myers字符差异算法的‘错误匹配末端’问题

我最近在做一个项目，想开发一种更灵活的古代文本摘要生成方式——本质是带高亮差异的并排对比，还能只聚焦语义上有用的差异。因为有些差异只是多了一个元音字母，这种差异不重要，所以用字符级别的对比是最合理的。我参考Coglan的经典博客系列，用JavaScript实现了Myers差异算法，代码放在了帖子末尾。

Coglan提到Myers算法是贪心的——“在做修改前尽可能匹配更多相同的行”，因此能避免所谓的“错误末端”问题：

（以下是正确和错误的差异示例）

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"和第一个end里的"d"。

在我的使用场景中，处理阿拉姆语缩写时就遇到了这个问题。这类缩写的形式是LLL"L，每个L代表所对应单词的首字母，双引号放在缩写的倒数第二个和最后一个字母之间。注意阿拉姆语没有大写字母（这在英语里是识别缩写的天然特征）。我在下图中用黄色高亮了包含缩写的词（在另一文本中是完整拼写的），被差异算法移除的空格显示为向下的箭头：[字符差异示例]

你大概能看到，未高亮的差异效果很好，很容易分辨出哪些是“额外”或“替换”的字母，这些数据对我很重要。而且除了第一对高亮的缩写-完整拼写外，其他所有对都呈现出规律的模式：（共享的字母是黑色，然后是直到单词末尾的被移除字母——也就是红色箭头标记的空格，然后又是黑色的共享字母，等等...）

这类缩写就像把“C.G.I”和“computer generated imagery”做对比，完整文本里剩下的“omputer enerated magery”没有一个字母和缩写重合。但如果缩写是“A.C.M”，对应的完整文本是“association [for] computing 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;
}

备注：内容来源于stack exchange，提问作者shman613