検索
連載

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

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか(編集部)

PC用表示 関連情報
Share
Tweet
LINE
Hatena
前のページへ |       

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

著者紹介

山下 寛人

オイシックス株式会社


Copyright © ITmedia, Inc. All Rights Reserved.

前のページへ |       
ページトップに戻る