移動塊檢測的序列比較

我需要比較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

移動塊檢測的序列比較

回答

相關問題