移动块检测的序列比较

我需要比较2个序列并找到编辑距离。编辑可以包括缺失和插入操作（每个码元修改权重为1），以及块移动操作（与0.1重量每符号）
例如：
ABCDE FGH
FGH ABC ý d X E
Block FGH已移到此处。
有没有现有的算法有效地解决这个任务？移动块检测的序列比较

来源

2010-09-09 jifuyo

Block Edit Models for Approximate String Matching的摘要看起来很有希望。

来源

2010-09-09 04:47:55

你可以尝试A technique for isolating differences between files（通过here）：

它采用运营商P.赫克尔的 1978 paper

（对不起，我scribd接口描述的 '搬家' 的算法，但我猜这篇论文没有被OCR检测过。）

来源

2010-09-09 04:28:35 LarsH

哇...划线是可怕的。我宁愿在浏览器中打开Adobe Acrobat，而不是那个怪物。当然没有冒犯你，我从来没有使用它的“快感”，选择citeseerx之类的东西。 – nlucaroni 2010-09-09 17:25:55

@nlucaroni：是的，我同意。如果您可以在网络上的其他地方找到Heckel论文（全文）的链接，请发布。 – LarsH 2010-09-09 19:22:18

是的;有许多关于生物学的算法和理论;基因组比对和染色体重排。在不知道数据的情况下，很难提及更具体的内容。我提到煎饼分拣作为另一个stackoverflow post重新排列的措施，还有其他一些很好的选择（特别是压缩）。当然，这种方法将无法将你的数据分解成块。处理小序列数据你应该没有问题产生所有分组。

来源

2010-09-09 04:42:28 nlucaroni

移动块检测的序列比较

回答

相关问题