我需要为我的个人项目计算树之间的编辑距离. 该论文描述了一种算法,但我不能做正面或反面出来.您是否了解以更平易近人的方式描述适用算法的任何资源？伪代码或代码也会有所帮助.
使用MS Access 2010和VBA(叹息..)
我正在尝试实现一个专门的Diff函数,它能够根据更改的内容以不同的方式输出更改列表.我需要能够生成一个简明的更改列表,以便为我们的记录提交.
我想使用诸如html标签之类的东西,<span class="references">These are references 1, 6</span>以便我可以使用代码查看更改并自定义更改文本的输出方式.或其他任何东西来完成我的任务.
我认为这是一种提供自定义输出的可扩展方式的方法,并可能将事物移动到更强大的平台并实际使用html/css.
有谁知道一个类似的项目可能能指出我正确的方向？
我有一个访问数据库,其中包含工作操作指令表 - 通常是200-300个操作,其中许多操作从一个修订版更改为另一个修订版.我目前已经实现了一个迭代表的函数,查找已更改的指令并进行比较.
请注意,每个操作指令通常是几个句子,最后有几行,带有一些文档引用.
我的算法基于"An O(ND)差分算法及其变化",效果很好.
Access支持"Rich"文本,这只是美化简单的html,因此我可以轻松生成带有格式化添加和删除的全文,即添加标签<font color = "red"><strong><i>This text has been removed</i></strong></font>.Diff过程的主要输出是操作的全文,其中包括彼此内联的未更改,已删除和插入的文本.diff过程添加<del>和<ins>标签稍后将替换为格式化文本(结果类似于堆栈交换编辑的更改视图).
但是,就像我说的,我需要以人类可读格式列出的更改.事实证明这很困难,因为许多变化产生了模糊性.
例如:如果某种化学品从"A类"变为"C类",则容易生成的更改文本是"将'A'更改为'C'",这对于审核该类型的人来说并不是非常有用.变化.更常见的是文档参考结尾:将SOP 3添加到列表中,例如"SOP 1,2,3",生成文本"添加'3'".显然也没用.
最有用的是指定为"SOP"文本的文本的自定义输出,以便输出为"添加对SOP 3的引用".
将单词组合在一起,例如将诸如"SOP 1,2,3"的文本作为一个标记来进行比较.这将生成文本"将'SOP 1,2'改为'SOP 1,2,3'.当存在大型列表并且您试图确定实际更改的内容时,这会变得混乱.
我现在正在尝试在运行diff算法之前添加额外的html标签.例如,我将通过"预处理器"运行文本,将"SOP 1,2"转换为SOP 1,2
一旦Diff过程返回完整的更改文本,我会浏览它,注意文本的当前"类",当有一个<del>或<ins>我捕获标记之间的文本并使用SELECT CASE类上的块来解决每个更改.
这实际上在大多数情况下都可以正常工作,但是我必须解决许多问题,例如添加Diff决定最短路径是删除某些开放标记并插入其他开放标记.这会创建一个场景,即有两个<span>标签,但只有一个</span>标签.
我正在寻找建议,要么继续我已经开始的方向,要么在投入更多时间进入次优解决方案之前尝试不同的方法.
在此先感谢所有人.
典型运行的时间大约是1.5到2.5秒,我尝试了更多花哨的东西和一堆debug.prints.因此,通过一两个额外的通行证不会是杀手.