レコメンデーションとエディットグラフ：コーディングに役立つ！アルゴリズムの基本（10）（2/4 ページ）

» 2009年05月01日 00時00分公開

[山下寛人，オイシックス株式会社]

文書比較のアルゴリズム

　UNIXのdiffコマンドをご存じでしょうか。テキスト同士を比較して違いを表示するコマンドです。

　ECサイトの多くでは、商品の感想の書き込み機能があります。感想が書き込まれたときは、そのまま掲載せず、サイト運営者が内容をチェックしてから誤字脱字などを校正します。その校正のときに、diffと同じように変更前と変更後の差分を表示してから確認する機能があると便利です。

　こういった文書比較は、一見ひたすら総当りで泥臭いプログラムになっていそうです。しかし、実は非常にスマートなアルゴリズムで実現されています。そのアルゴリズムはエディットグラフという図を利用するものです。

エディットグラフ

　では、具体的にどういったアルゴリズムになるのか見ていきましょう。

　変更前のテキストと変更後のテキストを縦軸と横軸に並べます。左上から右下に最短距離で移動する方法を考えます。このとき縦と横の文字が同じ場合は斜めに移動できるものとします。

　まず、縦と横に同じ文字があるところは斜めに移動できるので斜線を引きます。あとはすべての経路の中で斜めを一番多く通る経路を見つけます。

　この経路に従って移動していきます。縦移動の場合は、縦軸の文字が変更によって消えたことを表します。横移動の場合は、横軸の文字が変更によって増えたことを表します。消えた文字を横線、追加された文字を太字で表すと次のようになります。

~~BFEAB~~CDA

エディットグラフの実装（前半）

　それではエディットグラフを実装してみましょう。長いので半分に分けて解説します。

●エディットグラフのソースコード（前半）

 1 <html>
 2 <head>
 3 <script type="text/javascript">
 4 function getStringById(id) {
 5     var element = document.getElementById(id);
 6     var str = element.value;
 7     if (str == undefined) {
 8         str = element.innerHTML;
 9     }
10     return (str == undefined) ? "" : str;
11 }
12 
13 window.onload = function() {
14     var text = getStringById('text');
15     document.getElementById('area').innerHTML = text;
16 }
17 
18 function minus_ch(ch) { 
19     return '<span class="minus">' + ch + '</span>';
20 }
21 
22 function plus_ch(ch) { 
23     return '<span class="plus">' + ch + '</span>';
24 }
25 </script>
26 <style type="text/css">
27 span.plus { background-color:#FFFF00; font-weight:bold }
28 span.minus { background-color:#FF0000; text-decoration:line-through }
29 </style>
30 </head>
31 
32 <body>
33 
34 <div id="text">テキスト差分のとり方</div><br>
35 <textarea id="area" rows="10" cols="100"></textarea><br>
36 
37 <script type="text/javascript">
38 var EGD_X = 0;
39 var EGD_Y = 1;
40 var EGD_XY = 2;
41 var EGD_END = 3;
42 
43 function makeEditGraph(str1, str2) {
44     var edit_graph = new Array();
45 
46     edit_graph[str1.length] = new Array();
47     edit_graph[str1.length][str2.length] = 
48         {cost:0, direction:EGD_END};
49 
50     for (var x = str1.length-1; 0 <= x; x--) {
51         edit_graph[x] = new Array();
52         edit_graph[x][str2.length] = {cost:str1.length-x, direction:EGD_X};
53     }
54     for (var y = str2.length-1; 0 <= y; y--) {
55         edit_graph[str1.length][y] = {cost:str2.length-y, direction:EGD_Y};
56     }
57 
58     for (var x = str1.length-1; 0 <= x; x--) {
59         for (var y = str2.length-1; 0 <= y; y--) {
60             var cost;
61             var direction;
62             if (edit_graph[x+1][y].cost <= edit_graph[x][y+1].cost) {
63                 cost = edit_graph[x+1][y].cost;
64                 direction = EGD_X;
65             } else {
66                 cost = edit_graph[x][y+1].cost;
67                 direction = EGD_Y;
68             }
69 
70             if((str1.charAt(x) == str2.charAt(y))
71                && (edit_graph[x+1][y+1].cost <= cost)) {
72                 cost = edit_graph[x+1][y+1].cost;
73                 direction = EGD_XY;
74             }
75 
76             edit_graph[x][y] = {cost:cost+1, direction:direction};
77         }
78     }
79 
80     return edit_graph;
81 }
82 //末尾1

4～11行目
汎用関数です。指定したIDのHTMLを取得します。
13～16行目
初期表示のときに差分結果のところに変更前の文字列を表示しておきます。
18～24行目
消えた文字、増えた文字のHTMLを返す関数です。
38～41行目
エディットグラフの進む方向を表す定数を定義しています。
44行目
edit_graphという変数がエディットグラフ全体を表します。縦と横の2次元配列になっています。それぞれの要素は右下からの移動距離（cost）と次に進む方向（direction）を持っています。
46～48行目
グラフの右下は移動距離0、移動方向は「なし（EGD_END）」です。
50～53行目
グラフの一番下の行は、常に右に移動するのが最短距離になるのでそれを設定します。
54～56行目
同様にグラフの一番右は、常に下に移動するのが最短距離になります。
58～78行目
右下から1つ左上に行った点から、すべての点について移動の方向と距離を計算していきます。
62～68行目
下に移動するか、右に移動するか、どちらのほうが移動距離が少なくて済むか比較して、その点の移動距離と方向を決めます。
70～74行目
縦と横の文字が同じ場合は斜めに移動できます。