匹配兩個文檔之間的差異

我有一組字符串以及它們的座標和矩形邊界int兩個相似的頁面。這些字符串有三種可能的方式。（i）字符串可以移動到頁面上的新位置。（ii）一個字符串在相同的位置，但它被修改。說（abc - > abd或ABC）（iii）（i）和（ii）的組合。（iv）可能缺少一個字符串。匹配兩個文檔之間的差異

我試圖使用局部敏感哈希，但無法找到一個很好的哈希函數。任何人都可以請建議我一個很好的散列函數或其他算法來解決這個問題。在此先感謝

來源

2013-12-09 programer8

什麼是你的成本函數？例如，在你喜歡算法而不是報告字符串丟失之前，有多少個字符可以在匹配中有所不同？ –

現在它是分鐘（字數/ 2,4）。 – programer8

其他事情：是在「源」頁面中的「目標」頁面中的每個字符串？字符串是否改變長度，還是隻有字母替換？這些琴絃是否脫節？ –

因此，我們有一個源字符串列表S和大小至多爲|S|的目標字符串列表T。我們希望找到一種方法，每根弦在T分配給不同的字符串S使得不匹配的字符的數量最小化

（請注意，因爲我們正在尋找一種方式來匹配T到S，案件其中S字符串缺少的是處理隱含的）

如果這是你的問題@ programer8的準確解釋，我相信這是一個assignment problem，並且可以通過在立方時間Hungarian algorithm解決：稱爲「打工皇帝」在wiki文章中是您的目標字符串，「任務」是源字符串，以及源之間的不匹配字符數目標字符串是執行任務的工作人員的成本。

唯一的問題是你的工作人員/目標字符串比任務/源字符串少，但是你可以通過添加虛擬工作人員來解決這個問題。

來源

2013-12-10 01:11:53

我幾天前檢查了這個算法。由於運行時間，這是不可行的，但這會完成工作。 – programer8

它需要什麼運行時纔可行？ –

您是否願意接受解決方案的近似值？如果是這樣，他們需要成爲多好？ –

匹配兩個文檔之間的差異

回答

相關問題