代码之家 › 专栏 › 技术社区 › rinogo

我可以使用纯文本diff算法跟踪XML更改吗?

lcs diff algorithm xml

rinogo · 技术社区 · 15 年前

我正在使用flex/as3开发(为了简单起见)一个XML编辑器。我需要提供撤消/重做功能。

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

我的问题是-我可以使用纯文本diff算法来跟踪这些XML更改吗?

我在互联网上的研究表明不能这样做。不过,我显然错过了什么。明文diff提供的功能据称是:

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

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

例如:假设我是一个诗人。当我写诗的时候,我用了很多时髦的标点符号…您知道,比如<、/和>。(你可能会看到我要做什么…)如果我在一个使用diff提供撤消/重做功能的应用程序中写我的诗,当我撤消/重做我的编辑时,我的诗会变得乱七八糟吗?只是文字!为什么它会对算法产生影响?

很明显我这里没什么东西……谢谢你的解释!:)

更新:

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

另外,我理解命令模式可能是实现撤消/重做的更好方法。为了简单起见,我简化了我的用例,我仍然认为XML差异化是最好的方法。

4 回复 | 直到 12 年前

Neil Fraser 15 年前

我是谷歌纯文本diff/match/patch库的作者。

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

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

请注意,两个操作中的基础文本(旧文本)是相同的。在这种理想的情况下,不管内容的类型如何,简单的纯文本diff和补丁都能很好地工作。如果这个案子适用于你,那么你就完蛋了。

问题在于模糊修补。下面是相应的示例:

  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>

让我们仔细看看这个。原始diff返回两个编辑,将最外面的跨度更改为一个div.simple更改。不幸的是,应用此编辑的文本已从原始文本更改。“Jabberwock”一词已被删除。现在,第一个span->div更改与第二个span标记匹配,而不是第一个。由于补丁算法不知道XML的规则,因此会导致非法嵌套的标记。

在使用纯文本补丁时,有一些黑客允许您保证有效的XML,但它们会导致一些灵活性的损失(最初的问题已经有了指向我写过的wiki页面的链接)。修补XML的最终解决方案当然是使用支持XML的diff和patch算法。它们明显更为复杂和昂贵,但它们确实存在。通过谷歌搜索tancred lindholm和sebastian rnnau的名字,他们在XML领域(特别是与doceng有关)所做的伟大工作。

如果还有什么需要补充的,请告诉我。

--尼尔·弗雷泽

John Saunders 15 年前

我用 Beyond Compare 随时比较XML文档。它在一定程度上理解XML。

您可能需要预先处理这两个文档,以便进行文本比较,从而尽可能做到最好。例如,在一些XML文档中,某些元素的顺序可能并不重要。这对您的差异工具当然很重要!在比较两个排序的文件之前,您可能需要使用将这些元素排序为两个文件中的公共顺序的XML转换来预处理XML。

您还需要对两个文档使用相同的缩进。我发现在新行上开始每个元素,并对每个级别使用相同数量的缩进(带空格)是很有用的。如果您的文档非常深,您将希望每个级别只使用一个或两个空格,以便比较适合屏幕。您甚至可能希望每行使用一个属性(并将属性排序为一个公共顺序)。

Andy Dent 15 年前

如果您是撤消/重做点之间数据的唯一“所有者”,那么当然可以对它们使用纯文本diff。正如您所指出的,它相当于一组转换。

但是,根据您提供的操作,纯文本diff可能不是录制撤消/重做的最佳选择,您可能需要专门处理某些情况。想象一下,只记录一个replaceall命令,它可能只需要几个字节的开销加上搜索和替换字符串。这可能会产生大量的纯文本差异。

在更广泛的上下文中,如果您允许对这些文档进行外部编辑,并且您正在考虑如何在服务器上存储增量,那么您将模仿Git或其他版本控制系统。您必须使用某种diff算法,因为只记录命令显然不是转换的唯一来源。此时,您开始将撤消/重做与版本控制混合使用,您可能需要仔细考虑为用户混淆这些概念。

我将像在编辑会话中一样保留撤消/重做,并在文件打开时禁止外部编辑。这使您可以优化您的命令记录为广泛的情况,如我上面所说。

除此之外,要么使用传统的版本控制(考虑包装Git),要么实现自己的方式来处理在编辑器之外被更改的文件。

Codism 15 年前

我认为您可以对XML使用文本diff,特别是在这种情况下,人们将一行一行地编写XML。我不知道您得到了什么信息,您不能这样做,但我猜语句是基于这样一个事实:空格字符(空格、制表符、换行符…)与纯文本文件中的字符有些不同,这可能导致两个不同的文本文件与XML透视图相同。有意义的。但对于一个以人类为目标的编辑来说,我不明白你为什么不能。