文書比較(diff)

📓 Contents

---

文書比較には基本として

• 編集グラフ

の理解が必要である。このグラフを基に

• $O(ND)$
• $O(NP)$

のアルゴリズムが考えられている。
これらのアルゴリズムは文字列比較で説明を行っているが文書の行をハッシュコードにし文字と置き換えれば文書比較ができる。

計算量は

• $O(ND) > O(NP)$

であるが、$O(ND)$は処理に並行性があり、計算時間として $O(ND) < O(NP)$ の可能性がある。

📖 参考資料

• http://constellation.hatenablog.com/entry/20091021/1256112978 external_link
• http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm external_link
• diffの動作原理を知る～どのようにして差分を導き出すのか - 技術評論社 external_link

🌏 Map

same layer	lower layer