我可以使用明文差异算法来跟踪XML更改吗？

Question

我在Flex/AS3上工作(为简单起见)是一个XML编辑器.我需要提供撤消/重做功能.

当然,一种解决方案是在每次编辑时存储整个源文本.但是,为了节省内存,我想存储差异(这些差异也将用于将更新传输到服务器以进行自动保存).

---

我的问题是 - 我可以使用明文差异算法来跟踪这些XML更改吗？

我对互联网的研究表明我不能这样做.但是,我显然错过了一些东西.Plaintext diff提供的功能据称是:

diff(text, text') -> diffs
patch(text, diffs) -> text'

XML只是文本,为什么我不能只使用diff()和patch()来可靠地转换文本？

例如:让我们说我是一个诗人.当我写诗时,我会使用很多时髦的标点符号......你知道,就像<,/和>.(你可能会看到我要去的地方...)如果我在一个使用差异提供撤消/重做功能的应用程序中编写我的诗歌,当我撤消/重做我的编辑时,我的诗歌会变得乱码吗？这只是文字!为什么它会对算法产生影响？

我显然在这里得不到什么......谢谢你的解释!:)

更新:

我遇到过一些关于使用明文算法区分XML的讨论:

• http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
• 是否有一个针对htmlstring的JS diff库就像纯文本上的google-diff-match-patch一样？

---

另外,我知道Command模式可能是实现Undo/Redo的更好方法.为简单起见,我简化了我的用例,我仍然认为XML差异是最好的方法.

Answer 1

我是Google的纯文本差异/匹配/补丁库的作者.

关键问题是你的补丁是否准确.在一个理想的世界:

  diff(old_text, new_text) -> edits
  patch(edits, old_text) -> new_text

请注意,两个操作中的基本文本(old_text)是相同的.在这种理想情况下,无论内容的类型如何,简单的纯文本差异和补丁都将完美地工作.如果这种情况适用于你,那么你就完成了.

问题在于模糊修补.这是相应的例子:

  diff(old_text, new_text) -> edits
  patch(edits, old_forked_text) -> new_forked_text

请注意,两个操作中的基本文本不同.它们应该是相似的,但补丁操作现在必须使用"判断"它应该做什么.一些补丁可能完全符合编辑中指定的要求,其他补丁可能需要针对位置进行调整,其他补丁可能需要针对更改的上下文进行调整,其他补丁可能根本不适合应该被删除.如果您的修补算法在做出决策时不了解XML的结构,那么最终可能会遇到错误的XML.这是一个示例:

  old_text = Jabberwock<SPAN>Hello<SPAN>World</SPAN></SPAN>
  new_text = Jabberwock<DIV>Hello<SPAN>World</SPAN></DIV>
  diff(old_text, new_text) -> edits
  edits = ["SPAN" -> "DIV" @ character 11,
           "SPAN" -> "DIV" @ character 41]
  old_forked_text = <SPAN>Hello<SPAN>World</SPAN></SPAN>
  patch(edits, old_forked_text) -> new_forked_text
  new_forked_text = <SPAN>Hello<DIV>World</SPAN></DIV>

让我们仔细看看这个.原始差异返回两个编辑,将最外面的SPAN更改为DIV.简单的改变.不幸的是,正在应用此编辑的文本已从原始文本更改."Jabberwock"一词已被删除.现在,第一个SPAN-> DIV更改与第二个SPAN标记匹配,而不是第一个.由于补丁算法不了解XML规则,因此会导致非法嵌套标记.

有一些hacks允许您在使用纯文本补丁时保证有效的XML,但是它们会导致一些灵活性的损失(原始问题已经链接到我写的关于此的wiki页面).修补XML的最终解决方案当然是使用XML感知的差异和补丁算法.这些更加复杂和昂贵,但它们存在.谷歌的名字是Tancred Lindholm和SebastianRönnau,他们在XML领域所做的出色工作(特别是关于DocEng).

如果还有什么我可以补充的,请告诉我.

- 尼尔弗雷泽