連載
レコメンデーションとエディットグラフ:コーディングに役立つ! アルゴリズムの基本(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回にわたって、さまざまなアルゴリズムを紹介してきました。普段当たり前のように使っている処理でも実にさまざまなやり方があり、パフォーマンスや実装のスマートさに違いが出て奥が深いと思われたことでしょう。この連載によってコンピュータ的な発想のトレーニングに役立つことができれば幸いです。
Copyright © ITmedia, Inc. All Rights Reserved.
関連記事
- いまさらアルゴリズムを学ぶ意味
コーディングに役立つ! アルゴリズムの基本(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の世界を体験してみよう