http://gihyo.jp/dev/column/01/prog/2011/diff_sd200906 2011年3月11日
初出：Software Design2009年6月号（2009年5月18日発売）
久保達彦
UNIXの基本的なコマンドの1つであるdiff。
これに実装されているアルゴリズムは実に興味深い世界が広がっています。
本稿では，筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。
本記事は，Software Design 2009年6月号の記事を，現在の状態に合わせて加筆／修正しています。
はじめに
diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。
ソフトウェア開発を行っている方であれば，SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。
差分の計算の際に重要な3つの要素
差分を計算するというのは次の3つを計算することに帰結します。
- 編集距離
- 2つの要素列の違いを数値化したもの
- LCS（Longest Common Subsequence）
- 2つの要素列の最長共通部分列
- SES（Shortest Edit Script）
- ある要素列を別の要素列に変換するための最短手順
dtlを使って文字列の差分を計算する
本稿ではdtlというdiffライブラリとそのサンプルプログラムを利用して，これらの用語について具体的に解説します。dtlはdiff template libraryの略で，筆者が開発しているC++製のdiffライブラリです（注1）。
dtlのサンプルプログラムのビルドにはSCons（注2）を使用しているので，まずはSConsをインストールしてください。DebianやUbuntuであれば次のコマンドでインストールできます。
$ sudo aptitude install scons
また，C++プログラムをコンパイルするために，次のパッケージもインストールします。
$ sudo aptitude install build-essential
その後，次のコマンドを実行してください。
$ wget http://dtl-cpp.googlecode.com/files/dtl-1.12.tar.gz
$ tar zxvf dtl-1.12.tar.gz
$ cd dtl-1.12/examples
$ scons strdiff
これで準備が整いました。dtlのサンプルプログラムの1つであるstrdiffを使って2つの文字列の差分を計算してみます。
たとえば，「abcdef」と「dacfea」という文字列があるとしましょう。strdiffにこの2つの文字列を引数として与えて実行すると，図1のようにeditDistance（編集距離），LCS，SESを計算してその結果を出力してくれます。
図1 strdiffの実行結果
$ ./strdiff abcdef dacfea
効率的な差分アルゴリズム
差分の計算をするには「編集距離」「LCS」「SES」を求めれば良いということがわかりました。しかし，差分の計算というのは非常に重い処理で，単純に2つの要素列を比較するようなプログラムでは，計算量がO(MN)，必要なメモリがM×Nになってしまいます注3。そのため，実用的なdiffのプログラムには計算量や計算に必要なメモリの量を小さくする工夫が求められます。ここでは効率的なアルゴリズムの1つであり，dtlやSubversionで使用されているWuのアルゴリズムについて解説します。
- 注3）
- M，Nはそれぞれの要素列の長さ。
Wuのアルゴリズム
Wuのアルゴリズムは平均的な計算量がO(N+PD)，最悪の計算量がO(NP)であるアルゴリズムで，Nは2つの要素列の長さの和，PはSESにおける「削除」の合計数を表しています注4。
エディットグラフと最短経路問題
Wuのアルゴリズムの基本的な考え方は，差分を計算するという問題を2つの要素列を図2のように，エディットグラフと呼ばれるグラフに見立てて，点(0,0)から点(M,N)注5までの（ある条件つきの）最短経路を求める問題に還元することにあります。言葉で説明するよりも図で説明したほうがわかりやすいと思うので，図2を見てください。
図2 エディットグラフ
※エディットグラフは，xを縦軸，yを横軸でよく扱うので，本稿でもそれに従っています。
図のように，SESにおける「追加」を「y軸方向に+1」，「削除」を「x軸方向に+1」，また，互いの要素列の現在の
要素が同一の場合，「y軸とx軸の対角線上に+1」というふうに定義します。そして「y軸方向に+1」，もしくは「x軸方向に+1」進むのに必要なコスト
を1，「y軸とx軸の対角線上に+1」進むのに必要なコストを0とします。このように考えると，2つの要素列の差分を計算するというのは，図2のようなエ
ディットグラフの点(0,0)から点(M,N)まで進むのに必要なコストを最小限にする経路（SES）を求めることと等価だと考えることができます。
- 注4）
- Dは編集距離。
- 注5）
- M，Nはそれぞれ比較するそれぞれの要素列の長さです。また，N≧Mです。
Wuのアルゴリズムの動作原理
エディットグラフ上の最短経路を求めれば差分を計算できることがわかりました。
では，どのようにして最短経路を計算するのでしょうか。単純に1つひとつ総当たりで調べていくアルゴリズムだと，計算量はO(MN)，またエディットグラフを表すデータ構造（たとえばM×Nの2次元配列）のためにM×Nのメモリが必要になります。
Wuのアルゴリズムは計算量が最悪の場合でもO(NP)，また平均的な計算量がO(N+PD)となるので，かなりの改善が期待できます。それでは，このような少ない計算量を実現しているWuのアルゴリズムがどのように動作しているのか解説していきます注6。
D＝Δ+2P（※Δはデルタ）
まず，次のような約束事をします。
- 2つの要素列の長さをM，N（N≧M）とし，Δ=N-Mとする
- 編集距離をDとする
- SESにおける「削除」の合計数をPとする
Δは2つの要素列の長さだけがわかっている際に，考えられる最小編集距離です。これは図3のよう考えるとわかりやすいと思います。
図3のように，片方の要素列が2つの要素列のLCSと完全に一致する場合（図3の例では「abc」），編集距離はΔ＝N-M(N≧M)で表すことができます。
図3 Δ＝Dとなる場合のエディットグラフ
つまり，どんなにがんばっても編集距離はΔよりも小さい値にはならないわけです。
しかしそれ以外の場合，たとえば，「abec」と「abcdef」の場合，図4のように編集距離はΔよりも大きくなります。
図4 LCSとSESを求める
$ ./strdiff abec abcdef
editDistance:4
LCS:abe
SES
a
b
+ c
+ d
e
+ f
探索の仕方
まず，図7のように各点への対角線kをy-xと定義します。
図7 エディットグラフで対角線kを定義する
たとえば，点(M,N)や(M-1,N-1)だとk＝Δ，点(P,0)だとk＝-P，点(0,Δ+P)だとk=Δ+Pになります。
このように-P≦k≦Δ+Pを探索範囲，P＝pの場合の各対角線k上における到達可能な最遠点をfp(k,p)，任意の点(x,y)から到達可能な最遠点fp(k,p)注7を計算する関数をsnake(k,y)と定義します。
図8と図9に対角線k-1，k，k+1とそれぞれの最遠点fp(k-1,p')，fp(k,p)，fp(k+1,p'')注8との関係を示します。
図8 fp(k,p)=snake(k,fp(k-1,p"))
図9 fp(k,p)=snake(k,fp(k-1,p')+1))
図8は対角線k+1の最遠点fp(k+1,p'')から対角線上に進む経路がfp(k,p)として採用される場合，つま
り，fp(k,p)＝snake(k,fp(k+1,p''))となることを，図9は対角線k-1の最遠点fp(k-1,p')+1から対角線上に進む経
路がfp(k,p)として採用される場合，つまり，fp(k,p)＝snake(k,fp(k-1,p')+1となることを示しています。
このことからfp(k,p)の値はk＝Δを境にsnakeを使って図10のように式で表すことができます。
図10 snake関数とfp(k,p)の関係
最終的に，kの取り得る値の範囲を探索してfp(Δ,p)の値がNになったとき，点(M,N)に到達したことになるの
で，このときのpの値が，SESにおける「削除」の合計数Pになります。D＝Δ+2Pなので，これで編集距離が求まります。fp(Δ,p)＜Nの場合はp
の値（初期値は0）をインクリメントして，同じことを繰り返します。
また，LCSやSESを求めるにはいろいろ方法がありますが，たとえば探索途中（snake関数内）で使うx，yおよびどの最遠点を通過したかという情報を記録することによって求めることができます。
- 注6）
- ただし，コラムで後述していますが，全然違う2つの要素列を単純なWuのアルゴリズムで比較すると，かなりのメモリ容量が必要になります。
- 注7）
- ただし，fp(k,p)=(x,y)ではなく，fp(x,y)=yというふうに最遠点のy座標のみを示します。
- 注8）
- p'，p''はpもしくはp-1。
Wuのアルゴリズムを使ったサンプルプログラム
以上のことをもとに，実際にWuのアルゴリズムを使って引数として与えられた2つの文字列間の編集距離を求めるC++プログラムをリスト1に示します。
リスト1 文字間の編集距離を求めるプログラム
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Diff
{
public :
Diff(const string &a, const string &b) { --------①
M = a.length();
N = b.length();
if (M < N) {
A = a;
B = b;
} else {
A = b;
B = a;
swap(M, N);
}
}
int editDistance () const { --------②
const int offset = M + 1;
const int delta = N - M;
const int size = M + N + 3;
int fp[size];
for (int i=0;i<size;++i) fp[i] = -1;
int p = -1;
do {
++p;
for (int k=-p;k<=delta-1;++k) {
fp[k+offset] = snake(k, max(fp[k-1+offset]+1, fp[k+1+offset]));
}
for (int k=delta+p;k>=delta+1;--k) {
fp[k+offset] = snake(k, max(fp[k-1+offset]+1, fp[k+1+offset]));
}
fp[delta+offset] = snake(delta, max(fp[delta-1+offset]+1, fp[delta+1+offset]));
} while (fp[delta+offset] != N);
return delta + 2 * p;
}
private :
int snake (int k, int y) const { --------③
int x = y - k;
while (x < M && y < N && A[x] == B[y]) {
++x;
++y;
}
return y;
}
string A;
string B;
int M;
int N;
};
int main(int argc, char *argv[]){
if (argc < 3) {
cerr << "few augument" << endl;
return -1;
}
string A(argv[1]);
string B(argv[2]);
Diff d(A, B);
int editDistance = d.editDistance();
cout << "editDistance: " << editDistance << endl;
return 0;
Wuのアルゴリズムの問題点
Wuのアルゴリズムは2つの要素列が似通っている場合，非常に高速に動作しますが，そうでない場合は探索する範囲が広く
なった分遅くなり，SESを求めるために記録する経路のサイズも大きくなります。今回のように比較対象となる要素列が短い文字列であればとくに問題ではな
いのですが，万単位の行からなるファイル同士を比較したりするとなると，実装によっては実用上使い物にならないくらい遅くなったり，メモリを大量に消費す
るようになってしまう可能性があるので，工夫が必要になります注9。
- 注9）
- リスト1のように編集距離だけを求めるのであれば，探索する範囲は広くなっても，メモリの消費はさほど大きくなりません。問題となるのはSESの経路記録です。
その他のアルゴリズム
本稿ではWuのアルゴリズムについて解説しましたが，ここでは他のアルゴリズムについて軽く紹介します。
動的計画法（Dynamic Programming）
動的計画法（以下，DP）とはひとつひとつの小さな問題の解を組み合わせて，より大きな問題を解くというもの
で，diffに限らずいろいろな応用ができるアルゴリズムです。DPを使った差分の計算における小さな問題の解とは，2つの要素列の先頭からの各部分列に
おけるLCSの長さです。各部分列のLCSの長さは各一要素分前の部分列のLCSの長さがわかっていれば計算することができるので，先頭からの各部分列の
LCSの長さを全部求めていけば最終的にもとの2つの要素列のLCSの長さが求められます。
また，各部分列のLCSの長さを求める過程で，どの部分列を選択したかという情報も保存します。
最後にこの情報を逆順にたどっていけば，編集距離，LCS，SESを求めることができます。
DPを使った差分の計算では単純に各部分列のLCSの長さを保存しようとすると，M×N（M, Nはそれぞれの要素列の長さ）の表が必要になるので計算量がO(MN)，計算に必要なメモリもM×Nになります。
Myersのアルゴリズム
MyersのアルゴリズムはWuのアルゴリズムと同じく，差分の計算問題をエディットグラフ上の最短経路問題に還元する
アルゴリズムです。Dは編集距離を表しており，Wuのアルゴリズムと同じような感じで探索範囲を-D<=k<=Dに絞り込むことによって，計
算効率を向上させています。
GNU diffutilsや分散型バージョン管理システムの1つであるGitのdiffエンジンとして採用されているXLibdiffの実装はこのアルゴリズムを基にしています（注10）。
- 注10）
- P≦Dなので，素のMyersのアルゴリズムはWuのアルゴリズムよりも計算コストが高いですが，これらの実装ではMyersのアルゴリズムに差
分をヒューリスティックに求める改良を施して，精度を落とす代わりに計算速度を向上させています（ここで言う「精度を落とす」とは，「最短経路ではない経
路で解を求める」という意味で，「差分の解析結果の精度を落とす」という意味ではありません）。実際，dtlやSubversionのdiffエンジンよ
りもこれらの実装のほうが計算速度は速いです。
Gestalt Approach
Gestalt
ApproachはWuのアルゴリズムやMyersのアルゴリズムと違い，差分の計算問題をエディットグラフ上の最短経路問題に還元するのではありませ
ん。2つの要素列中の連続する共通部分を探し出し，その共通部分を中心に2つの要素列をそれぞれ分割します。そして，その分割した2つの要素列の左部分と
右部分のそれぞれから再び共通部分を探し出すといったことを繰り返し，最後にその共通部分を全部つなげてLCSなどを算出するというアルゴリズムです。
最後に
本稿のサンプルコードでは，編集距離を求めるところまでしか紹介できませんでしたが，興味のある方は本稿でも紹介した拙
作のdtlやGNU
diffutilsまた各種バージョン管理システムのソースコードに含まれているdiffエンジンのソースコードを読んでみると良いでしょう。ま
た，githubに筆者が各種言語でWuのアルゴリズムを利用して実装した差分計算プログラムのソースコードがあります。
コラム「dtl開発の苦労話」
筆者はdtlを開発しているとき，本稿にある「Wuのアルゴリズムの問題点」に思いっきり当たりました。あるとき，数千
もしくは数万行からなるまったく内容の違う2つのファイルを比較すると動作が非常に遅くなったり，プログラムがメモリ不足で落ちてしまったりといった現象
に出くわしたのですが，最初は原因がわかりませんでした。そして詳しく調べてみると，全然違うファイルを比較した場合，SESを求めるのに必要な経路の座
標候補を記録している（動的）配列のサイズがとんでもない数になっていることに気づきました（注A）。
プログラムではWuのアルゴリズムの経路探索の過程でその配列にSESの経路候補の座標を追加していき，最後に，その記
録された座標から経路を逆にたどっていくことによってSESを算出していたのですが，最終的にどの経路がSESになるかというのは経路探索の途中ではわか
らないため，どうやって解決したものかと悩んだ記憶があります。
少々悩んだあと，私が取った解決策は，次のようなものです。
- ① SESの座標候補の配列に座標を追加していく
- ② SESの座標候補の配列のサイズが一定のサイズになったら，いったんそこまでのLCSやSESを計算する
- ③ 座標候補の配列を空にする
- ④ 2つの要素列の比較が最後まで終わっていない場合は①に戻る。終わっている場合は⑤へ
- ⑤ これまでに計算した複数のLCSやSESを全部つなげて1つにする
この方法により，全然違う要素列を比較する場合でも計算に必要な経路情報を一定のサイズ以下に抑えることができ，問題は発生しなくなりました。ただ，当然，このようなことをすると完全なLCSやSESを求めることができない可能性が出てきます。
しかし，実際問題として完全なLCSやSESが必要となるケースはそれほど多くなく，ふだん使われているようなdiffのプログラムでも近似アルゴリズム（注B）を使って，つねに最適解を求めるのではなく，計算速度を優先させて準最適解を求めるような実装になっているのが見受けられます。
- 注A）
- OSに付属のプロセスモニタを見ると，dtlを使ったプログラムのメモリ使用量が1Gバイトを越えていました。
- 注B）
- 近似アルゴリズムについて詳しく勉強したい方は参考文献の『近似アルゴリズム』が参考になるかもしれません。
- 参考文献・URL
- E.W.MYERS, "An O(ND) Difference Algorithm and Its Variations"
- S.W.Maner, G.Myers, W.Miller, "An O(NP) Sequence Comparison Algorithm"
- 『アルゴリズムイントロダクション「第2巻」アルゴリズムの設計と解析手法 改訂2版』
T.コルメン，C.ライザーソン，R.リベスト，C.シュタイン共著／浅野哲夫，岩野和生，梅尾博司，山下雅史，和田幸一共訳／近代科学社／ 987-4-7649-0335-7 - 『近似アルゴリズム』V.V.ヴァジラーニ著／浅野孝夫訳／シュプリンガー・ジャパン／987-4-4317-00991-6
- PATTERN MATCHING:THE GESTALT APPROACH
URL：http://www.ddj.com/184407970?pgno=5 - 文書比較アルゴリズム
URL：http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm - Webサイト「/0」内の記事――diff(1)，diff(2)，diff(3),
URL：http://www.slash-zero.jp/archives/program/466
URL：http://www.slash-zero.jp/archives/program/468
URL：http://www.slash-zero.jp/archives/program/476 - 各種言語(C, Go, Java, Lua, Perl, Python, Ruby)によるWuのアルゴリズムの実装
URL：https://github.com/cubicdaiya/onp
久保達彦（くぼたつひこ）
インフラ兼ソフトウェアエンジニア。ピクシブ株式会社所属。
pixivのインフラの最適化や運用の省力化を提案・実行する傍らレコメンド・エンジンなどのソフトウェアの開発も行っている。
HP：http://cccis.jp/
twitter：@cubicdaiya
プログラミング
- diffの動作原理を知る～どのようにして差分を導き出すのか
-
屮暴颪い討澆謄 團鵐哀顱△劼蕕?な枯で」ってて］れた泙儡呂匹犲…陥てとと思?SSTyping任文粉鬚犬文砲鬟ぅ鵐拭優奪箸藹γてて?ME...
Tracked : #1 assari (PukiWiki/TrackBack 0.3) （2011/03/11, 20:47）
-
2011年10月14～15日に，YAPC::Asia 2011が開催されます。それに先立ち，見所，押さえどころを，キーパーソンによるインタビューとともにお届けします。
-
IT界を揺るがす四コマ漫画家“シモダテツヤ”が，毎回楽しい四コマ漫画とふんわりしたコラムでお届けしていきます！
-
この連載では，現時点で利用されていることが多いレガシー版PHPである4.3/4.4/5.1/5.2のセキュリティ状態について，SRA
OSS Inc社のPHP4セキュリティパッチサービスで提供しているパッチとレガシー版PHPのセキュリティについて解説します。
-
Calibreはオープンソースの電子書籍管理ツールです。本連載ではCalibreを使って，電子書籍の面白さを説明していきます。
-
Ubuntuの強力なデスクトップ機能を活用するための，いろいろなレシピをお届けします。
-
ネットワークは受け身でしか利用できないイメージが定着していると思いますが，次世代ネットワーク制御技術「OpenFlow」の登場により状況が変化しつつあります。本連載では，OpenFlowでネットワークをプログラミングしていきます！
-
「アメーバブログ」や，「アメーバピグ」など，よく知られたソーシャルサービスを展開するインターネットサービス「Ameba」を運営する（株）サイバーエージェントの技術者に，数多くの魅力的なサービスを支える秘密を伺いました。
-
アプリケーションの開発効率を向上させるためには，自身のコーディング能力を向上させるのと同時に，開発をサポートするツールやライブラリ，フレー
ムワークを適切に使いこなすことが重要です。この連載では，アプリケーション開発をサポートするさまざまなツールについて，使い方を交えながら紹介してい
きます。
連載一覧
}
Wuのアルゴリズムでは2つの要素列をA，B，それぞれの長さをM，NとするとN≧Mなので，①のコンストラクタではN≧Mの関係がつねに成り立つようにします。
②のeditdistance関数がエディットグラフを探索するメインロジックになります。変数fpが各対角線上で到達
可能な最遠点のy座標を格納する配列になりますが，探索範囲が-p≦k≦Δ+pなので，そのままだと配列fpの添字が負の値になる場合があるため，添字が
負の値にならないように調整する必要があります。
pの最大値がM，またfp(k,p)を計算するにはfp(k-1,p')とfp(k-1,p'')が必要であることを考慮すると，配列fpの添字が負の値にならないためにはM+1個分配列の位置をずらせば良いことになります。
また，配列fpのサイズは同様にPの最大値がM,探索範囲が-p≦k≦Δ+pなので，k＝Δ+P＝Nの際に配列fpの添
字の値がk+1+offset＝N+1+M+1＝M+N+2で最大になるため，配列fpのサイズは（配列の添字が0から始まることを考慮して）M+N+3
になります。そしてp＝0からループを回していってfp(k,p)＝Nとなったときのpの値（SESにおける削除の合計数）をもとに編集距離を計算しま
す。
③のsnake関数の仕事はfp(k,p)から対角線上に進んで到達できる最大のy座標を返すことです。各要素列の現在
位置の要素を1つづつ比較して同一であればそれぞれの要素列の位置を+1進めて，最終的にy座標を返します。また，x座標はk＝y-xにより，x＝k-y
で求めることができます。
- c
この場合のエディットグラフを図5に示します。先述したように2つの要素列の長さだけからわかる最小の編集回数はΔです。
図5 Δ≠Dとなる場合のエディットグラフ
たとえばy軸方向へΔだけ進んだあとに(0,Δ)から(M,N)までの対角線k上を一気に進むことができれば，編集距離
はΔになります。しかし，そうならない場合，対角線kの上側（下側）を通ることになります。ここで，エディットグラフ上のある性質が見てとれます。それは
対角線k上からPだけy軸（x軸）方向に進んだ場合，最終的に点(M,N)にたどり着くには対角線k上に復帰する必要があるので，Pだけx軸（y軸）方向
に進まなければならないということです。
また，対角線k上の点にたどり着くには最低でもコストがΔかかります。よって次の関係が成り立ちます。
探索範囲を絞り込む
先ほど述べたように単純にひとつひとつ総当たりで調べていくのでは，計算量が大きくなってしまいます。そこで，Wuのアルゴリズムでは経路の探索範囲を図6のように絞り込むことによって，計算量を大幅に削減しています。このような絞り込みができるのは，最短経路がこの範囲外にある場合，「削除」の合計数Pの値が矛盾してしまうためです。
たとえば，図6のように対角線s上を通る経路では，どうがんばってもP=P+1となってしまいます。また，対角線t上を通る経路でも同様です。
図6 探索範囲の絞り込み
editDistance:6 --------①
LCS:acf --------②
SES ---┓
+ d ｜
a ｜
- b ｜
c ｜③
- d ｜
- e ｜
f ｜
+ e ｜
+ a ---┛
まず，①のeditDistance（編集距離）の説明からいきたいところですが，これは③のSESと関連するため，先に②のLCSについて解説し，そのあとで残りの2つをまとめて解説します。
- 注1）
- 執筆時点での最新版は1.12です。
- 注2）
- Python製のビルドツール。
LCS（Longest Common Subsequence）
LCSは最長共通部分列であると書きましたが，単に2つの要素列に共通して含まれる要素の列ではなく，2つの要素列の中
で共通する部分で最も長い列を指します。つまり，LCSはつねに連続しているわけではありませんが，もとの要素列の順序どおりに並んでいる必要がありま
す。これはどういうことかと言うと，「abcdef」と「dacfea」に共通して含まれる文字は「a」，「c」，「d」，「e」，「f」の5つになりま
す。これに対して，図1の結果を見ると，2つの文字列「abcdef」と「dacfea」のLCSは「acf」でした。
「d」と「e」がLCSに含まれていないのは，この2つの文字がLCSに含まれてしまうと，もとの文字列のどちらかの順序どおりに並ばなくなるからです。
たとえば，要素「d」は文字列「abcdef」では，LCSの要素である「a」と「c」よりも後ろに出現し，そのあとは出現しません。これに対して文字列「dacfea」では「a」と「c」よりも前にだけ出現します。
「e」と「f」についても，「abcdef」と「dacfea」とでは順序が逆になってしまうため，両方がLCSに含ま
れることはあり得ません。逆に，片方だけが含まれるLCSは存在します。というのも，図1の結果ではLCSは「acf」になっていますが，「ace」もま
たLCSです。「acf」も「ace」も長さは3で同じなので，どちらもLCSであると言えます。
このように，LCSはつねに1つとは限りません。また，LCSが変わると後述するSESも変わってしまうので，注意が必要です。
SES（Shortest Edit Script）
図1の結果からSESは③のようになりました。SESは先述したように「ある要素列を別の要素列に変換するための最短手順」を表します。つまり，③は「abcdef」という文字列を「dacfea」という文字列に変換するための最短手順を表しています。ふだんdiffを使っている人にとっては，これが一番なじみの深いものではないかと思います。③のSESをもう少し詳細にすると，表1のようになります。
表1 abcdefからdacfeaへのSES
- 「追加」の場合はマークしている文字の前に追加対象の文字を追加
- 「削除」の場合はマークしている文字を削除
- 「LCSの要素」の場合はマークしている文字から右に一文字進める
編集距離
表1から読み取れるように編集距離とはSESにおける要素の「追加」と「削除」の合計を表しています。図1の①を見るとeditDistance（編集距離）は6ですので，計算どおりです。
|
