总结和基本问题
使用 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。因此,通过额外的一两次传球不会是杀手锏。
最佳答案
尝试从 Prolog 风格的重写规则的角度思考,这些规则将您的指令转换为规范形式,这将导致 diff 算法产生您需要的内容。您指定的问题将通过此规则解决:
SOP i1, i2, ... iN -> SOP j1, SOP j2, ... SOP jN where j = sorted(i)
换句话说,在以下整数的排序列表上“分发”SOP。这将使diff算法欺骗以提供完全合格的更改报告“Add SOP 3”。
通过在输入中搜索左侧的匹配项并替换为相应的右侧来应用规则。
您可能已经在执行此操作,但是如果对输入进行标记化,则将获得更多的常识分析:对于diff算法,“SOP”应被视为单个“字符”。如果空格和换行符很重要或被忽略,它们可能会被简化为标记。
您可以在字符级别执行另一种差异,以测试标记的“模糊”相等性,以解决匹配左侧时的打印错误。 “SIP”和“SOP”将被视为“匹配”,因为它们的编辑距离仅为 1(并且 I 和 O 在 QUERTY 键盘上仅相隔一个键!)。
如果您考虑现在获得的输出中的所有怪癖,并且可以将每个怪癖纠正为重写规则,将输入转换为一种形式,其中 diff 算法生成您需要的内容,那么剩下的就是实现重写系统。以一种有效的通用方式执行此操作,以便更改和添加规则不会涉及大量的临时编码,这是一个困难的问题,但已被研究过。有趣的是@Ira Baxter 提到了 lisp,因为它非常适合作为这类事情的工具。
Ira 对语法树的建议自然属于重写规则方法。例如,假设 SOP 有章节和段落:
SOP 1 section 3, paras 2,1,3
是一个层次结构,应该重写为
SOP 1 section 3 para 1, SOP 1 section 3 para 2, SOP 1 section 3 para 3
重写规则
paras i1, i2, ... iN -> para j1, para j2, ... para jN where j = sorted(i)
section K para i1, ... para iN ->s section K para j1, ... section K para j1
SOP section K para i1, ... section K para i1 -> SOP section K para j1, ... SOP section K para j1
在三遍应用时,将产生类似“SOP 1 第 3 节,第 4 段已添加”的结果。
虽然有许多策略可以实现规则和重写,包括在 VB 中将每个策略编码为一个过程(啊……),但还有其他方法。 Prolog 是一个尽可能普遍地做到这一点的宏伟尝试。 There is a free implementation. 还有其他的。我已经使用 TXL 来完成有用的重写。 TXL 的唯一问题是它假设您对输入有相当严格的语法,这听起来不像您的问题。
如果您在当前输出中发布更多关于怪癖的示例,我可以跟进有关重写规则的更多详细信息。
关于html - 上下文敏感的差异实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20751740/