3

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

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

问题

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

4

1 回答 1

4

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

第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 的删除
      • 通过将删除步骤设置为当前步骤并调整以后的索引（即减一），用索引 P 标记列表中的字符（其中只有一个仍然存在，即未设置删除步骤）

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

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

于 2011-06-27T19:49:26.307 回答