文書比較のアルゴリズム
- - PR -
UNIXのdiffコマンドをご存じでしょうか。テキスト同士を比較して違いを表示するコマンドです。
ECサイトの多くでは、商品の感想の書き込み機能があります。感想が書き込まれたときは、そのまま掲載せず、サイト運営者が内容をチェックしてから誤字脱字などを校正します。その校正のときに、diffと同じように変更前と変更後の差分を表示してから確認する機能があると便利です。
こういった文書比較は、一見ひたすら総当りで泥臭いプログラムになっていそうです。しかし、実は非常にスマートなアルゴリズムで実現されています。そのアルゴリズムはエディットグラフという図を利用するものです。
エディットグラフ
では、具体的にどういったアルゴリズムになるのか見ていきましょう。
変更前のテキストと変更後のテキストを縦軸と横軸に並べます。左上から右下に最短距離で移動する方法を考えます。このとき縦と横の文字が同じ場合は斜めに移動できるものとします。
まず、縦と横に同じ文字があるところは斜めに移動できるので斜線を引きます。あとはすべての経路の中で斜めを一番多く通る経路を見つけます。
この経路に従って移動していきます。縦移動の場合は、縦軸の文字が変更によって消えたことを表します。横移動の場合は、横軸の文字が変更によって増えたことを表します。消えた文字を横線、追加された文字を太字で表すと次のようになります。
エディットグラフの実装（前半）
それではエディットグラフを実装してみましょう。長いので半分に分けて解説します。
●エディットグラフのソースコード（前半）
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行目
- 縦と横の文字が同じ場合は斜めに移動できます。
ここまでで、すべての点について方向と移動距離が計算されます。合わせて最短距離の経路も決定します。
 |
2/5 |
 |
| Index | |
| レコメンデーションとエディットグラフ | |
| Page1 実際のアプリケーションで使われるアルゴリズム レコメンデーション 協調フィルタリングの実装 |
|
 |
Page2 文書比較のアルゴリズム エディットグラフ エディットグラフの実装（前半） |
| Page3 エディットグラフの実装（後半） より効率的なエディットグラフ |
|
| Page4 O(ND)アルゴリズムの実装 連載の終わりに |
|
| Appendix 協調フィルタリングの実装（全ソースコード） |
|
 |
コーディングに役立つ！ アルゴリズムの基本 |
| Coding Edgeお勧め記事 |
 |
いまさらアルゴリズムを学ぶ意味 コーディングに役立つ！ アルゴリズムの基本（1） コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう |
|
Zope 3の魅力に迫る Zope 3とは何ぞや？（1） Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？ |
|
貧弱環境プログラミングのススメ 柴田 淳のコーディング天国 高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？ |
|
Haskellプログラミングの楽しみ方 のんびりHaskell（1） 関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう |
|
ちょっと変わったLisp入門 Gaucheでメタプログラミング（1） Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう |
フィード 2.0／1.0／0.91
Coding Edge フォーラム 新着記事
- Rによるオープン・データの可視化（2） （2010/9/2）
美しいグラフが手軽に作成できるグラフィックパッケージを使い、世界銀行のデータやアフガン戦争のデータを可視化する - プログラムの実行を制御しよう （2010/8/23）
今回は条件分岐や繰り返し処理をCで学びます。条件によってプログラムの実行を制御することは、プログラムに欠かせない要素です - Rによるオープン・データの可視化（1） （2010/8/20）
今回はパブリックに入手可能な“オープン・データ”とRを使い、人口動態統計や株式相場などのデータを可視化する - GAE+SQL4GでRailsアプリ開発（リベンジ編） （2010/8/17）
最終回となる今回は、進化したGAE上のJRuby環境で、リアルなRailsアプリを動かしてみます
 |
|
|
|
|
RSSフィード
＠IT 新着記事
スキルアップ／キャリアアップ（JOB@IT）
スポンサーからのお知らせ
お勧め求人情報
*＊先週の人気講座ランキング＊*
〜ITIL編〜
ソリューションFLASH
Copyright(c)
2000-2010
ITmedia Inc.
著作権はアイティメディア株式会社またはその記事の筆者に属します。（著作権について）
当サイトに掲載されている記事や画像などの無断転載を禁止します。
「＠IT」「＠IT自分戦略研究所」「＠IT情報マネジメント」「JOB＠IT」「＠ITハイブックス」「＠IT MONOist」「ITmedia」「誠」「BARKS」は、アイティメディア株式会社の登録商標です。
当サイトに関するお問い合わせは「＠ITへのお問い合わせ」をご覧ください。
著作権はアイティメディア株式会社またはその記事の筆者に属します。（著作権について）
当サイトに掲載されている記事や画像などの無断転載を禁止します。
「＠IT」「＠IT自分戦略研究所」「＠IT情報マネジメント」「JOB＠IT」「＠ITハイブックス」「＠IT MONOist」「ITmedia」「誠」「BARKS」は、アイティメディア株式会社の登録商標です。
当サイトに関するお問い合わせは「＠ITへのお問い合わせ」をご覧ください。