- @ThothChildren
- 2018.6.14
- PV 213
文書の差分箇所を検出したい
ー 概要 ー
二つの文書の差分がどこにあるかを検出したいときのアルゴリズムについて紹介します.多くのサイトで同様な解説はあるため、アルゴリズムの簡単な紹介に止めます.
この章を学ぶ前に必要な知識
条件
- 二つの文章ファイル
効果
- 二つの文章の差分を出力
ポイント
- 文章を文ごとに比較して差分がないかを検査
- O(ND)で算出可能なMyersアルゴリズムが有名
- それを高速化したWuのアルゴリズムもある
解 説
文章の差分を検出は簡単なようで意外と考えると難しいタスクです.
文章の差分は変更が最も少ない形を見つけるようにしなくてはなりません.もし、1行最初に挿入されていた場合、以後全てずれているので差分となってしまうと使い物にならないからです.その場合は最初の行だけを差分として出すのがあるべき形です.
最も愚直にやる場合は二つの文書内の互いのすべての文と文同士が対応していた組み合わせを計算して、最も変更する箇所が少ない数を探すことになりますが、これは両文章の長さを掛け合わせたO(MN)に比例します.
これはさすがに遅すぎるので別の方法が必要になります.
そこでここでは,
・Myresアルゴリズム
・上記を高速化したWuアルゴリズム
の二つについて簡単に紹介します. | 文書の差分箇所を検出したい
|
1.Myersアルゴリズム | |
Myersの概要だけ紹介します.
MyersアルゴリズムはEdit Graphを用いて比較するもの同士の最小コストでの移動経路を求めることで、最小の差分を検出します.
単語と単語がどれだけ似ているかを示す編集距離と同じような仕組みでEdit Graphを考えて適切な差分を検出します.(文同士のときも同様の考え方です.)コストが0のパスがあるかを探し、次第にかかってもよいコストをあげていき最小の差分を検出するようにするアルゴリズムです. | Myersアルゴリズムについて |
左がEdit Graphの例
CBABACとABCABBAの文字列の比較を行っています.
斜めに移動するパスはコストが0でそれ以外は1です.
縦または横に移動しなくてはならないときが文字を変更するタイミングです.編集距離はその回数ということになります.
Stackoverflow (https://stackoverflow.com/questions/33054560/end-points-on-myers-algorithm)より引用 | |
2.Wuアルゴリズム | |
WuアルゴリズムはMyersアルゴリズムのときにおいて考慮していない文章同士の長さの差分から生じる大きさを考慮して探索範囲をさらに絞った方法です. | Wuアルゴリズムについて |
右のリンク等に詳しい解説があるので参考にしてください. | 外部リンク GihyoによるWuアルゴリズム解説 |
この章を学んで新たに学べる
Comments