将文本增量合并为单个 'Superstring' 的算法

Question

我正在编写软件来跟踪作者对一本书的多个版本所做的更改。我已经编写了生成一组描述两个版本之间差异的增量的代码。

现在我正在寻找一种算法来组合所有这些内联差异以创建一个“ super 字符串”，其中包含在每个版本中插入和删除的所有文本。然后我想用有关文本添加和删除位置的信息标记 HTML 中的字符串。

这样我就可以通过简单地向文档应用不同的 CSS 属性来可视化文本之间的差异。

例子

如果作者这样改一个句子

-0-    --1--    ---2---    ---3---
' ' -> 'cat' -> 'crate' -> 'crane'

我的代码产生这些增量

0-1) <insert 'cat' at 0>
1-2) <insert 'r' at 1> <insert 'e' at 3>
2-3) <remove from 3 to 4> <insert 'n' at 3>

我想处理创建这样的文件:

<span class="inserted-1">c</span>
<span class="inserted-2">r</span>
<span class="inserted-1">a</span>
<span class="inserted-1 removed-3">t</span>
<span class="inserted-3">n</span>
<span class="inserted-2">e</span>

问题

完成此任务的最佳算法是什么？这个问题有名字吗？

Answer 1

您可以连接您的更改并跟踪它们何时被插入/删除。请注意，数字给出了字符串中的索引(请注意，删除的字符不会增加索引)。

第 1 步: 0-1) <insert 'cat' at 0>

• [0] c inserted at step 1
• [1] a inserted at step 1
• [2] t inserted at step 1

第 2 步: 1-2) <insert 'r' at 1> <insert 'e' at 3>

• [0] c inserted at step 1
• [1] r inserted at step 2 <= 这是在这一步的位置 1 处插入的
• [2] a inserted at step 1
• [3] t inserted at step 1
• [4] e inserted at step 2 <= 这是在这一步的位置 3 处插入的

请注意，由于另一个插入，'e' 的位置实际上已移动到 4。

第 3 步: 2-3) <remove from 3> <insert 'n' at 3> <=我把这个改成了最小差异

• [0] c inserted at step 1
• [1] r inserted at step 2
• [2] a inserted at step 1
• [3] t inserted at step 1, removed at step 3 <= 不再计数，因此下一个索引相同
• [3] n inserted at step 3 <= 这是在这一步的位置 3 处插入的
• [4] e inserted at step 2

所以基本算法是:

• 维护一个字符列表，以及插入步骤和删除步骤
• 对每一步做
  • 将此步骤中的差异分解为单个字符插入和删除
  • 要在位置 P 插入一个新的字符 X，请执行以下操作:
    • 在列表中索引为 P 的最新字符之后插入新字符 X，将插入步骤设置为当前步骤并调整后续项的索引(即添加一个)。
  • 对于位置 P do 的删除
    • 通过将删除步骤设置为当前步骤并调整后面的索引(即减去一个)，用索引 P 标记列表中的字符(其中只有一个仍然存在，即未设置删除步骤的地方) )

在这两种情况下，请注意，此步骤中之前的插入/删除操作可能会改变当前操作的位置(轻松解决此问题的一种方法是从字符串末尾向后执行插入/删除操作)。

结果将是您在问题中指定的更改列表。对于很多更改，它可能变得非常难以阅读，但它仍然会描述您的文本的完整历史。