diffの仕組みについて調べてまとめてみた

お久しぶりです。してんしです。

新年度が始まりましたね。ちなみに私には彼女ができました。

嘘です…。

昨年度を振り返ると様々な出来事がありました。

まあいろいろありましたが、中でも大きなものと言ったら卒業論文ですね。とてもめんどくさかったです。

世の中には差分を管理するソフトウェアなど便利なものがあります。なぜあの時使わなかったのか…。

ということで、差分管理の仕組みについて理解を深めるため、本当に基本的な部分を私なりにまとめることにしました。備忘録みたいな感じです。間違えが絶対あると思われます。もしあったらコメントなどで教えてくださるとありがたいです。

~~うまくいけば部活の発表のネタとして使い回すこともできますしね…~~

２つのディレクトリとかファイルとかの差分を取得するコマンドをdiffって言ったりします。UNIX系のコマンドです。

Gitとかのバージョン管理システムを通して使う人もいるかもしれないです。(プログラム書く人とかは特に。)

LCSは最長共通部分列というものです。

名前が難しそうでそれだけじゃよくわかんないです。簡単に言うと２つの文の中で共通な部分で最も長い列の事です。

例えば"あいうえお"と"かいうえあ"という2つの列のLCSは"いうえ"です。 LCSではない文字、例えば"あ"の場合は前者ではLCSの"いうえ"の前、後者は"いうえ"の後になってます。

またLCSは複数あることがあります。

先ほどの文の前者を①、後者を②にすると、①の文を②にするための一番短い手順のことです。簡単に言うと、LCSの文字はそのまま、それ以外の文字を削除して、その後に必要な文字を足します。

先ほどの例でやってみます。

もとの文字列は"あいうえお"でした。

“か"を追加します。(かあいうえお)

“あ"はLCSではないので削除します。

(かいうえお)

“い"はLCSなのでそのままにします。

(いうえお)

“う"や"え"も同様にそのまま、"お"はLCSでないので削除します。(かいうえ)

最後に"あ"を追加します。(かいうえあ)

これで完成です。

編集距離はずばり追加と削除の数です。

ここでは4です。

ここまでに説明した3つの要素を使えば差分が求められます。

しかし実際はこれほど単純では無いそうです。というのも今回はたった5文字でしたが普段用いるであろう文字列でさっき言った処理を行うのは現実的ではないですから。

なのでほんとはもう少し工夫が必要なのです。

なのでWuなどの工夫されたアルゴリズムがあるのですがその仕組みについてはなかなか難しかったのでそこまでは書けませんでした…。

ではまた。

してんしのブログ