連載
» 2009年05月01日 00時00分 UPDATE

コーディングに役立つ! アルゴリズムの基本(10):レコメンデーションとエディットグラフ (2/4)

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

文書比較のアルゴリズム

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

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

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

エディットグラフ

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

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

エディットグラフ

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

斜めを一番多く通る経路

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

BFEABCDA

エディットグラフの実装(前半)

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

エディットグラフのソースコード(前半)
 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行目
    縦と横の文字が同じ場合は斜めに移動できます。

 ここまでで、すべての点について方向と移動距離が計算されます。合わせて最短距離の経路も決定します。

Copyright© 2017 ITmedia, Inc. All Rights Reserved.

@IT Special

- PR -

TechTargetジャパン

この記事に関連するホワイトペーパー

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。