这主要取决于您使用的文本更改。当序列包括插入和删除时,理论上不可能知道每个插入的细节,因为插入的一些符号可能随后被删除。因此,您必须选择您真正想要的结果:
- 出于某些目的,即使某些插入的符号必须保留为“?”,您也必须知道更改的确切顺序。
- 出于其他目的,您必须确切地知道新文本与旧文本有何不同,而不是确切的更改顺序。
我将使用技术来实现这些结果中的每一个。我过去使用过这两种技术,所以我知道它们是有效的。
得到准确的顺序
如果您正在实施历史记录或撤消日志或搜索特定操作,这更合适。
对于这些用途,您描述的过程可能是最好的,有一个可能的变化:而不是“找到未知符号和真实符号之间的映射”,只需向前运行扫描以找到每个“删除”的文本然后运行它向后查找每个“插入”的文本。
换句话说:
从初始文本开始,按顺序处理更改。对于每个插入,插入“?” 符号。对于每次删除,删除指定数量的符号并将它们记录为删除的文本。
从最终文本开始,以相反的顺序处理更改。对于每个delete,插入 '?' 符号。对于每个insert,删除指定数量的符号并将它们记录为插入的文本。
完成后,据我们所知,您的所有“插入”和“删除”更改条目都将具有关联的文本,任何插入并立即删除的文本都将是“?” 符号。
获得差异
这更适合修订标记或版本比较。
对于这些用途,只需使用文本更改信息来计算可能会发现更改的一组整数范围,然后使用标准差异算法来查找实际更改。这在处理增量更改方面往往非常有效,但仍为您提供最佳更新。
当您粘贴与原始段落几乎相同的替换段落时,这特别好:使用文本更改信息将表明整个段落是新的,但使用差异(即这种技术)将仅标记那些实际上是的符号运行不同的。
计算变化范围的代码很简单:将变化表示为四个整数(oldstart、oldend、newstart、newend)。运行每个更改:
- 如果 changestart 在 newstart 之前,则将 newstart 减少到 changestart 并减少 oldstart 等量
- 如果changeend在newend之后,则将newend增加到changeend并增加oldend等量
完成此操作后,从旧文档中提取范围 [oldstart, oldend] 和从新文档中提取范围 [newstart, newend],然后使用标准 diff 算法进行比较。