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

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

O(ND)アルゴリズムの実装

　それでは、O(ND)アルゴリズムを実装しましょう。前のソースコードの「末尾2」のコメントの下に以下のコードを追加してください。2回に分けます。

●O(ND)アルゴリズムのソースコード（前半）

  1 <script type="text/javascript">
  2 var V_INIT = 0;
  3 var V_X = 1;
  4 var V_Y = 2;
  5 
  6 function getV_Status(v_minus, v_plus) {
  7 
  8     if ((v_minus == undefined) && (v_plus == undefined)) { return V_INIT; }
  9     if (v_minus == undefined) { return V_X; }
 10     if (v_plus == undefined) { return V_Y; }
 11 
 12     if (v_minus.x < v_plus.x) {
 13         return V_X;
 14     } else {
 15         return V_Y;
 16     }
 17 }
 18 
 19 function getEndPoint(str1, str2) {
 20     var v = new Array(str1.length+str2.length+3);
 21     var offset = str2.length + 1;
 22 
 23     for (var d = 0; d <= str1.length+str2.length; d++) {
 24         var k_max = (d <= str1.length) ? d : (str1.length - (d - str1.length));
 25         var k_min = (d <= str2.length) ? d : (str2.length - (d - str2.length));
 26 
 27         for (var k = -k_min; k <= k_max; k+=2) {
 28             var index = offset + k;
 29             var x;
 30             var y;
 31             var parent;
 32 
 33             switch(getV_Status(v[index-1], v[index+1])) {
 34             case V_INIT:
 35                 x = 0;
 36                 y = 0;
 37                 parent = {x:0, y:0, parent:null};
 38                 break;
 39 
 40             case V_X:
 41                 x = v[index+1].x;
 42                 y = v[index+1].y + 1;
 43                 parent = v[index+1];
 44                 break;
 45 
 46             case V_Y:
 47                 x = v[index-1].x + 1;
 48                 y = v[index-1].y;
 49                 parent = v[index-1];
 50                 break;
 51 
 52             }
 53 
 54             while (((x < str1.length) && (y < str2.length))
 55                     && (str1.charAt(x) == str2.charAt(y))) {
 56                 x++;
 57                 y++;
 58             }
 59 
 60             v[index] = {x:x, y:y, parent:parent};
 61 
 62             if ((str1.length <= x) && (str2.length <= y)) {
 63                 return v[index];
 64             }
 65         }
 66     }
 67 }
 68

• 6〜17行目
  斜線kで、下の斜線上の点か、右の斜線上の点か、どちらから移動するかを決める関数です。より右にあるほうを採用します。
  
  
• 19〜67行目
  O(ND)アルゴリズム本体です。最後の右下の点を返します。点はそこに移動する前の点のポインタを保持しているので、それをたどって左上まで戻ることができます。
  
  
• 20行目
  配列vはそれぞれの斜線上の点の位置を表します。
  
  
• 23行目
  Dを1ずつ増やしてループします。
  
  
• 24、25行目
  斜線kをどこからどこまで調べる必要があるかを決めます。
  
  
• 27〜65行目
  斜線kそれぞれについてループします。最初d＝0のときはk＝0のみで、vは左上になります。d＝1のときはk＝-1とk＝1の斜線についてチェックします。
  
  
• 34〜38行目
  vに何も定義されていない場合は左上になります。
  
  
• 40〜44行目
  右の斜線上の点を採用する場合。下に移動します。
  
  
• 46〜50行目
  下の斜線上の点を採用する場合。右に移動します。
  
  
• 54〜58行目
  縦と横の文字が同じ場合は斜めに移動できます。移動できるだけ移動します。
  
  
• 60行目
  配列vにxとyと移動元の点（parent）を格納します。
  
  
• 62〜64行目
  右下にたどりついたらその点を返します。

●O(ND)アルゴリズムのソースコード（後半）

 69 function getDiffStringOND(str1, str2) {
 70     var point = getEndPoint(str1, str2);
 71     var diff_string = "";
 72     while (point.parent != null) {
 73         var parent = point.parent;
 74         var diff_x = point.x - parent.x
 75         var diff_y = point.y - parent.y
 76         var same_len = Math.min(diff_x, diff_y);
 77 
 78         for (var i = 0; i < same_len; i++) {
 79             diff_string = str1.charAt(point.x-i-1) + diff_string;
 80         }
 81 
 82         if (diff_y < diff_x) {
 83             diff_string = minus_ch(str1.charAt(parent.x)) + diff_string;
 84         } else  if (diff_x < diff_y) {
 85             diff_string = plus_ch(str2.charAt(parent.y)) + diff_string;
 86         }
 87 
 88         point = parent;
 89     }
 90 
 91     return diff_string;
 92 }
 93 
 94 function execDiffOND() {
 95     var text = getStringById('text');
 96     var area = getStringById('area');
 97     var diff_string = getDiffStringOND(text, area);
 98     document.getElementById('diff').innerHTML = diff_string;
 99 }
100 </script>
101 <input value="diff (O(ND))" type="button" onClick="execDiffOND()"></input><br><br>

• 70行目
  O(ND)アルゴリズムで右下までたどりついた点を取得します。
  
  
• 72〜89行目
  点を一歩ずつ元にたどりながら差分文字列を作成していきます。
  
  
• 78〜80行目
  斜めに進んだ分は変化のない文字列なので、そのまま結果の文字列に追加します。
  
  
• 82〜86行目
  縦に進んだか横に進んだかで増えた文字、消えた文字として結果の文字列に追加します。末尾からたどっているので最初のやり方と逆になっています。

連載の終わりに

　これまで10回にわたって、さまざまなアルゴリズムを紹介してきました。普段当たり前のように使っている処理でも実にさまざまなやり方があり、パフォーマンスや実装のスマートさに違いが出て奥が深いと思われたことでしょう。この連載によってコンピュータ的な発想のトレーニングに役立つことができれば幸いです。

著者紹介

山下 寛人

オイシックス株式会社

「コーディングに役立つ！ アルゴリズムの基本」バックナンバー

• レコメンデーションとエディットグラフ
• データを加工して圧縮率を高めよう
• データ量を操る圧縮／展開を究めよう
• 文字列の中から効率良くキーワードを探し出せ
• Firebugで探索アルゴリズムを見ていこう
• Internet Explorerよりも速くソートできたよ
• Internet Explorerよりも速くソートできるかな
• 再帰でハノイの塔を攻略せよ
• データ構造の選択次第で天国と地獄の差
• いまさらアルゴリズムを学ぶ意味