跟踪文本文件修订中行或段落的变化
我正在研究在维基上建立一个在线评论系统（但这不是我想问的问题）。首先想到的是，能够把评论和某一行、段落或字符串关联起来，并给它们一个独特的ID。这样，即使维基经过多次编辑，这种关联依然有效。
举个例子，假设有以下输入：
R1:
1 One
2 Two
3
4 Three
5 Four
R2:
1 One
2 Three
3 Two
4
5 Four
我希望能有一个映射关系，比如第1行对应第1行，第2行对应第3行，第3行对应第4行，第5行对应第5行，并且知道新增了一行2，删除了一行4。至于第4行移动到第2行的情况，可能就有点难以预测了，我不太确定。
有很多工具可以进行类似的文本操作（不，我并不是在找工具）。比如说，比较、版本控制和修订合并等。有没有一些著名的算法可以用来跟踪文件内容的变化呢？我比较喜欢用Python，但也想了解其他语言的情况。
1 个回答
2
既然你听说过 diff，那么你可能对它所基于的 Hunt-McIlroy算法 感兴趣。顺便提一下，diff 在Python中可以用 difflib 来实现。
真正的版本跟踪（就像Word在“跟踪更改”开启时那样）需要以某种方式标记文本，而单纯的文本是无法做到这一点的。不过，diff和合并算法在这方面的表现非常出色，能够很好地处理这些问题。