html - 上下文敏感的差异实现

Question

总结和基本问题

使用 MS Access 2010 和 VBA(叹气..)

我正在尝试实现一个专门的 Diff 函数，该函数能够根据已更改的内容以不同方式输出更改列表。我需要能够生成一个简明的更改列表以提交我们的记录。

我想使用诸如 <span class="references">These are references 1, 6</span> 之类的 html 标签之类的东西。这样我就可以使用代码查看更改并自定义更改文本的输出方式。或其他任何东西来完成我的任务。

我认为这是一种提供自定义输出的可扩展方式的方法，并且可能将事情移动到更强大的平台并实际使用 html/css。

有谁知道一个类似的项目可以为我指明正确的方向？

我的任务

我有一个包含工作操作说明表的 Access 数据库 - 通常有 200-300 次操作，其中许多操作从一个修订版更改为另一个修订版。我目前实现了一个函数，它遍历表，查找已更改的指令并比较它们。

请注意，每个操作指令通常是几个句子，末尾有几行，并附有一些文档引用。

我的算法基于 "An O(ND) Difference Algorithm and Its Variations"而且效果很好。

Access支持“富”文本，它只是美化了简单的html，所以我可以很容易地生成带有格式化添加和删除的全文，即添加像<font color = "red"><strong><i>This text has been removed</i></strong></font>这样的标签。 . Diff 过程的主要输出是操作的全文，其中包括彼此内联的未更改、删除和插入的文本。 diff 程序添加 <del>和 <ins>稍后被格式化文本替换的标签(结果类似于堆栈交换编辑的更改 View )。

但是，就像我说的，我需要以人类可读格式列出的更改。事实证明，这很困难，因为许多变化会产生歧义。

例如:如果一种化学品正在从“A 类”更改为“C 类”，那么容易生成的更改文本是“将 'A' 更改为 'C'”，这对于查看变化。更常见的是末尾的文档引用:将 SOP 3 添加到列表中，例如“SOP 1, 2, 3”会生成文本“Add '3'”。显然也没有用。

什么最有用是指定为“SOP”文本的文本的自定义输出，因此输出将是“添加对 SOP 3 的引用”。

我从以下解决方案开始:

将单词组合在一起，例如将诸如“SOP 1, 2, 3”之类的文本视为要比较的一个标记。这会生成文本“将‘SOP 1、2’更改为‘SOP 1、2、3”。当列表很大并且您试图确定实际更改的内容时，此操作会很困惑。

我现在在哪里

我现在试图在运行差异算法之前添加额外的 html 标签。例如，我将通过“预处理器”运行文本，该“预处理器”会将“SOP 1, 2”转换为 SOP 1, 2

一旦 Diff 过程返回完整的更改文本，我就会扫描它，注意当前的“类”文本以及何时存在 <del>或 <ins>我捕获标签之间的文本并使用 SELECT CASE阻止类以解决每个更改。

这实际上在大多数情况下都可以正常工作，但是我必须解决许多问题，例如添加 Diff 决定最短路径是删除某些开始标签并插入其他开始标签。这将创建一个场景，有两个 <span>标签但只有一个 </span>标签。

终极问题

我正在寻求建议，要么继续我已经开始的方向，要么尝试不同的方法，然后再将更多时间投入到次优解决方案中。

提前谢谢大家。

另请注意:

典型的运行时间大约为 1.5 到 2.5 秒，我尝试了更多花哨的东西和一堆 debug.prints。因此，通过额外的一两次传球不会是杀手锏。

Answer 1

很明显，在您拥有的结构的最小变化方面报告差异并不是您想要的；你想报告一些上下文。

要做到这一点，您必须确定要报告的上下文，以便您决定其中的哪一部分是有趣的。您勾画了一个想法，将结构的某些元素融合在一起(例如，“SOP”“1”“2”变成“SOP 1 2”)，但在我看来，这似乎是错误的方式。它正在做的是改变最小结构元素的大小，而不是报告更好的上下文。

虽然我不确定这是正确的方法，但我会尝试使用语法来表征您的结构，例如 BNF。例如，您可能拥有的一些语法规则是:

 action = 'SOP' sop_item_list ;
 sop_item_list = NATURAL ;
 sop_item_list = sop_item_list ',' NATURAL ;

现在，一个实际的 SOP 项可以被描述为一个抽象语法树(显示嵌套的子项，可通过常量索引以到达子树):

 t1: action('SOP',sop_item_list(sop_item_list(NATURAL[1]),',',NATURAL[2]))

您仍然希望使用您建议的动态编程算法之类的方法计算差异，但现在您需要最小的树增量。做对了(我的公司为传统计算机语言的语法制作了工具，您可以找到公开可用的树差异算法)，您可以获得如下增量:

  replace t1[2] with op_item_list(sop_item_list(sop_item_list(NATURAL[1]),',',NATURAL[2]),',',NATURAL[3]

这本质上是您通过将 (SOP,1,2) 粘合到单个项目中而得到的，但没有您个人决定这样做的外部临时决定。

我认为，这其中的真正值(value)在于您可以使用树 t1 来报告上下文。特别是，您从树的根部开始，并打印子树的摘要(显然您不想打印完整的子树，因为这只会返回完整的原始文本)。
通过将子树打印到 1 或 2 个级别的深度并消除任何深度(例如，将列表表示为“...”，将单个子树表示为“_”)，您可以打印如下内容:

replace 'SOP' ... with 'SOP',...,3

我认为这就是您在具体示例中要寻找的内容。

不，这不是算法；这是一个想法的草图。事实上，我们有计算有用增量的树增量算法，以及总结思想(坦率地说，取自 LISP 调试器)表明这可能会推广到一些有用的东西，或者至少将您带入一个新的方向。

有了 AST 方面的答案，还应该可以相对容易地根据需要生成 HTML。 (人们一直在使用 XML，而 XML 基本上是一种树表示)。