「iPodの残り容量が200MBを切った」と社内で発言してから「iPhoneを買おう！」としきりに言われるようになったbokkoです。そんな私は先月、ホコリをかぶっていたデスクトップPCを筐体ごと買い換えました。今ではMacBookからSSHでログインしてターミナル上で快適な生活を送っています。
今月、2TBのHDDを6本使ったサーバを立てる機会がありまして、今日はその時のお話です。
yukiです。ダイエットを始めて3kg減ったと思ったら、風邪を引いて見事に1kg増量。
運動しないと駄目ですね。あと残り20kg、道のりは遠いです。
さて今回は、「RDBで階層構造を扱うには？」です。
あるサイトを構築中に階層構造をもったカテゴリ構造にすることになり、DBでどのように扱うか悩みました。
DBはMySQLを採用していたので、この時点でぱっと頭に浮かんだ選択肢は以下のようなものでした。
(1)のXMLDBはオープンソースのeXistやXindice、Yggdrasillなど様々な選択肢がありましたが、カテゴリのみの利用な割にメンテナンスコストが高すぎるので見送りました。
(2)の親ID格納の実装は容易ですが、取り出し時のクエリが何回も行われるなど、負荷がかかるうえ、何よりエレガントさがありません。
(3)は一旦採用しかけたのですが、取り出しロジックの複雑さが増すので、できればやりたくありません。
(4)は柔軟な対応や検索など相当大変な気がしたので見送り。
すべての案がボツになったところで、いいアイデアはないかとグーグル先生に聞いてみたところ、以下のページが目からウロコだったのでさっそく採用してみました。
Storing Hierarchical Data in a Database
http://www.sitepoint.com/article/hierarchical-data-database/
英語ですが、PHPとMySQLのソースも掲載されているので、それほど難しくないと思います。
おおざっぱに説明すると、ルートを頂点として各ノードの左右に順にIDを振り、このIDを利用して範囲検索することで、柔軟な取得を可能にするというものでした。
例となる構造をここに示します。
+--------+
1|ジョージ|20
+--------+
|
+-------+-----------+
| |
+----------+ +------+
2|ジョナサン|15 16|ディオ|19
+----------+ +------+
| |
+-----------+ +--------+
3|ジョージ2世|14 17|ジョルノ|18
+-----------+ +--------+
|
+--------+
4|ジョセフ|13
+--------+
|
+------+-------+
| |
+------+ +--------+
5|ホリィ|10 11|東方仗助|12
+------+ +--------+
|
+----------+
6|空条承太郎|9
+----------+
|
+--------+
7|空条徐倫|8
+--------+
ルートにあたるジョージの左IDが1から始まり、左から順に子孫に番号を振りつつ、
末端の空条徐倫までたどり着くと右IDを振りつつ戻ります。
同様に、兄弟のディオの系列にも番号を振り、最終的にジョージへ戻ります。
テーブルにすると以下のようになります。
CREATE TABLE family (
"id" INTEGER NOT NULL AUTO_INCREMENT,
"left_id" INTEGER NOT NULL,
"right_id" INTEGER NOT NULL,
"name" VARCHAR(20) NOT NULL,
"gender" CAHR(1) DEFAULT "M" NOT NULL,
"stand" VARCHAR(100)
PRIMARY KEY ("id")
);
+--+-------+--------+-----------+------+--------------------------+
|id|left_id|right_id| name |gender| stand |
+--+-------+--------+-----------+------+--------------------------+
| 1| 1| 20|ジョージ | M | |
| 2| 2| 15|ジョナサン | M | |
| 3| 3| 14|ジョージ2世| M | |
| 4| 4| 13|ジョセフ | M |ハーミット・パープル |
| 5| 5| 10|ホリィ | F | |
| 6| 6| 9|空条承太郎 | M |スター・プラチナ |
| 7| 7| 8|空条徐倫 | F |ストーン・フリー |
| 8| 11| 12|東方仗助 | M |クレイジー・ダイヤモンド |
| 9| 16| 19|ディオ | M |ザ・ワールド |
|10| 17| 18|ジョルノ | M |ゴールド・エクスペリエンス|
+--+-------+--------+-----------+------+--------------------------+
親を含めて子孫を取得する場合、左右IDの数字を指定してやれば取得できます。
例としてジョセフとその子孫を取得する場合は以下のようになります。
SELECT left_id, right_id, name
FROM family
WHERE left_id BETWEEN 4 AND 13
ORDER BY left_id ASC
+-------+--------+-----------+
|left_id|right_id| name |
+-------+--------+-----------+
| 4| 13|ジョセフ |
| 5| 10|ホリィ |
| 6| 9|空条承太郎 |
| 7| 8|空条徐倫 |
| 11| 12|東方仗助 |
+-------+--------+-----------+
子孫から親をたどる場合、左IDが子ノードの左ID以下、右IDが子ノードの右以上のIDを探します。
例として東方仗助の親を探す場合は以下のようになります。
SELECT left_id, right_id, name
FROM family
WHERE left_id < 11
AND right_id > 12
ORDER BY left_id ASC
+-------+--------+-----------+
|left_id|right_id| name |
+-------+--------+-----------+
| 1| 20|ジョージ |
| 2| 15|ジョナサン |
| 3| 14|ジョージ2世|
| 4| 13|ジョセフ |
| 11| 12|東方仗助 |
+-------+--------+-----------+
あるノードから数えた子孫の数は、以下の計算式で算出します。
(ノード右ID - ノード左ID - 1) / 2ジョナサンを例にすると、
(15 - 2 - 1) / 2 = 6となり、子孫は6人となります。
また、新たにノードを増やす場合、あらかじめ左右のIDをずらしておきます。
たとえば空条徐倫に娘ができた場合は以下のようになります。
UPDATE family SET right_id = right_id + 2 WHERE right_id > 7 ORDER BY right_id DESC;
UPDATE family SET left_id = left_id + 2 WHERE left_id > 7 ORDER BY left_id DESC;
INSERT INTO family (left_id, right_id, name, gender) VALUES(8, 9, '徐倫の娘');これを実行すると以下のようなデータになります。
+--+-------+--------+-----------+------+--------------------------+
|id|left_id|right_id| name |gender| stand |
+--+-------+--------+-----------+------+--------------------------+
| 1| 1| 22|ジョージ | M | |
| 2| 2| 17|ジョナサン | M | |
| 3| 3| 16|ジョージ2世| M | |
| 4| 4| 15|ジョセフ | M |ハーミット・パープル |
| 5| 5| 12|ホリィ | F | |
| 6| 6| 11|空条承太郎 | M |スター・プラチナ |
| 7| 7| 10|空条徐倫 | F |ストーン・フリー |
| 8| 13| 14|東方仗助 | M |クレイジー・ダイヤモンド |
| 9| 18| 21|ディオ | M |ザ・ワールド |
|10| 19| 20|ジョルノ | M |ゴールド・エクスペリエンス|
|11| 8| 9|徐倫の娘 | F | |
+--+-------+--------+-----------+------+--------------------------+
-- 徐倫の娘の親をたどる
SELECT left_id, right_id, name
FROM family
WHERE left_id < 8
AND right_id > 9
ORDER BY left_id ASC
+-------+--------+-----------+
|left_id|right_id| name |
+-------+--------+-----------+
| 1| 22|ジョージ |
| 2| 17|ジョナサン |
| 3| 16|ジョージ2世|
| 4| 15|ジョセフ |
| 5| 12|ホリィ |
| 6| 11|空条承太郎 |
| 7| 10|空条徐倫 |
| 8| 9|徐倫の娘 |
+-------+--------+-----------+
この更新方法にはパフォーマンス上の様々な意見があるので、
このモデルをさらに推し進めた方法も存在するようです。
今回はleft_idとright_idに整数値を利用しましたが、ノード追加時に更新が発生するのを防ぐため小数値を利用する方法もあります。
具体的には左IDを8,右IDを9ではなく、左IDを7.3、右IDを7.6にすることで、他レコードへの更新を防ぎINSERT文1度で済むようにする、という方法です。
この方法であれば、親子関係は維持したまま、だいぶパフォーマンスでは有利になります。
私の場合はそれほど頻繁に更新しないのと、小数だと全体の見渡しがよくなくなると考えたため、この方法は採用しませんでした。
私は上記サイトでこの設計を知ったのですが、後になってWEB+DB PRESSを見直した所
同様の記事を見つました。(Vol49, 50の『SQLアタマアカデミー』著：ミック)
英語が苦手な方は是非こちらをお勧めします。
また筆者の方のWEBサイトにはより詳細に網羅的に記載があります。
SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル
http://www.geocities.jp/mickindex/database/db_tree_ns.html
概念自体は古くからあるようなのでご存知の方は多いと思いますが、
今回の自分のように目からウロコがボロボロ落ちる方がいるかもしれないと思い
エントリーを書き起こしました。
よいSQLライフを！
[23:52] 「徐倫の娘」(ノード追加) についての実行結果と、小数を利用した方法を追記しました。
yamaokaです。
Opera Uniteが話題になっていますね。 Operaを使うことが多いので、こうして話題になると少しだけうれしいです。 Operaは単なるwebブラウザーではありません。 Opera Uniteはともかく、メーラーにも、IRCのクライアントにも、 BitTorrentのクライアントにもなることができます。 そして、ウィジェットが動くプラットフォームでもあるのです。
Operaのウィジェットにはいろいろな種類があって、 例えばTwitterクライアントのTwipperaなど便利なものから、 ちょっとしたツールやゲームまで揃っています。 ウィジェットの開発はHTMLとJavaScript、CSSを使って行います。普通のwebサイト制作と同じですね。 開発者向けのドキュメントはまだ整備段階の感じもしますが、一通りの情報は揃っています。
というわけで（？）、試しにフォト蔵の写真をスライドショー表示するウィジェットを作ってみました。 ウィジェットは次のファイルで構成されている必要があります。
もちろん、画像やJavaScriptをディレクトリに分けておくことも可能です。 それら全てを、1つのディレクトリに保存します。
まず「config.xml」を用意します。
<?xml version="1.0" encoding="UTF-8" ?>
<widget>
<widgetname>フォト蔵スライドショー</widgetname>
<description>フォト蔵で人気の写真を表示します</description>
<id>
<host>photozou.jp</host>
<name>photozou-slideshow</name>
<revised>2009-06-17</revised>
</id>
<width>150</width>
<height>150</height>
<author>
<name>YAMAOKA Hiroyuki</name>
<organization>Unoh Inc.</organization>
</author>
</widget>
そして、「index.html」を用意します。
<!DOCTYPE html>
<html>
<head>
<script type="text/javascript" src="http://www.google.com/jsapi"></script>
<script type="text/javascript">google.load("jquery", "1.3");</script>
<style type="text/css">
ul#photos {
position:relative;
width:120px;
height:120px;
margin:0;
padding:0;
list-style:none;
}
ul#photos li {
position:absolute;
top:0;
left:0;
z-index:8;
}
ul#photos li.active {
z-index:10;
}
ul#photos li.last-active {
z-index:9;
}
</style>
</head>
<body>
<ul id="photos"></ul>
<script type="text/javascript">
$(function(){
$.ajax({
type: "GET",
url: "http://api.photozou.jp/rest/photo_list_public",
data: { type: "popular", limit: "30" },
dataType: "xml",
success: function(data, dataType) {
if (data !== undefined) {
var photosFirstChild = $("#photos li:first-child");
var photos = $(data).find("photo").each(function() {
var thumbnailURL = $(this).find("thumbnail_image_url").text();
var url = $(this).find("url").text();
var content = "<a href=\""+ url +"\"><img src=\"" + thumbnailURL + "\"></a>";
if (photosFirstChild.length == 0) {
$("#photos").append($("<li>").html(content));
} else {
photosFirstChild.before($("<li>").html(content));
}
});
}
},
error: function() { opera.postError("Photozou API error"); },
complete: function(xmlHttpRequest, textStatus) {
if (textStatus != "success") {
return;
}
setInterval(function() {
var activePhoto = $("#photos li.active");
if (activePhoto.length == 0) {
activePhoto = $("#photos li:last");
}
var nextPhoto = activePhoto.next().length ?
activePhoto.next() : $("#photos li:first");
activePhoto.addClass("last-active");
nextPhoto.css({ opacity: 0.0 })
.addClass("active")
.animate({ opacity: 1.0 }, 1000, function() {
activePhoto.removeClass("active last-active");
});
}, 5000);
}
});
});
</script>
</body>
</html>
JavaScriptを使うにあたって、jQueryをライブラリとして利用しています。 今回はGoogleのAJAX Libraries APIを利用しましたが、ウィジェットとして配布するのであればパッケージに同梱することになるでしょう。 スライドショーとして写真を順々に表示する部分は、 A Simple jQuery Slideshowを参考にしました。
Operaのウィジェットでは、通信はXMLHttpRequestを使って行います。 通常Ajaxなどで使う場合は同一のドメイン内にしかリクエストを発行できませんが、 ウィジェットの中で使う場合は何の制限もなく使うことができます。 今回はフォト蔵のAPIにリクエストを投げています。
この2つのファイルを同じディレクトリに保存して、 「config.xml」をOperaのウィンドウにドラッグ＆ドロップすると、 ウィジェットが起動します。簡単ですね。 まだ閉じるボタンも設定画面もありませんが、ウィジェットが1つできました。 実際にウィジェットとして配布する場合は、 zipでディレクトリをアーカイブして拡張子をwgtに変更すればいいようです。
非常に簡単に作れるので、個人的なツールをささっと作るといった用途にも使えそうです。 また、HTMLとJavaScriptで作成するので、JavaScriptの豊富なライブラリを利用できるのも大きなポイントです。 ちょっといろいろ作ってみるのもいいかもしれませんね。
$ctl[] = array('regex' => '#^/hello$#',
'base' => '/index.php',
'model' => 'Unoh_Views',
'method' => 'hello');
class Unoh_Views
{
public function hello($req, $arg)
{
return new Pluf_HTTP_Response('Hello Pluf!');
}
}
$ctl[] = array('regex' => '#^/sample/(\d+)/$#',
'base' => '/index.php',
'model' => 'Unoh_Views',
'method' => 'year');
class Unoh_Views
{
public function hello($req, $arg)
{
return new Pluf_HTTP_Response($arg['year']);
}
}
$ctl[] = array('regex' => '#^/template/$#',
'base' => '/index.php',
'model' => 'Unoh_Views',
'method' => 'template');
Views
public function template($req, $arg)
{
return Pluf_Shortcuts_RenderToResponse('unoh/template.html',
array('data' => 'data')
);
}
<html>
<head>
<title>{block title}{/block}</title>
</head>
<a href="{url 'Unoh_Views::date', array('2009', '06')}">2009/06</a>
{block body}{/block}
</html>
{extends 'unoh/base.html'}
{block title}test{/block}
{block body}<span style="color:red">ボディ</span>{/block}
またテンプレート関数のurlはディスパッチャの設定の指定を見てURLを生成してくれます。
こんにちは！やまもと＠テスト番長です。
最近、15年住み続けた築40年以上になる木造アパートから、築2年の駅近マンションに引越しました。
あまりの住環境の落差に、今までは何だったんだろうと呟いていたりします。
変化することを面倒臭がらずに、日々快適な暮らしを目指すべきだったんでしょうね。
さて、テスターが快適に仕事をするに当たって、保障されるべきこととは何でしょうか？
「テスターの権利章典」というものを考えた方がいるのをご存知ですか？
昨年秋に訳されたもので旬は逃しておりますが、最近ふと思い出したのでご紹介してみます。
テスターの権利章典
Tom Gilb & Kai Gilb : Testers Bill of Rights
こちらのページの下のほうに、大西建児さん訳の日本語版があります。
これはテスターの方のみならず、むしろプログラマの方に見ていただきたいなと思います。
お互いを尊重し協業していく上で、相手にとって何が大事なのかを知っておくのは、とても重要なことだからです。
人権というとちょっと大袈裟かもしれませんが、大事にしたいことばかりですね。
先日、まちつく！が正式リリースになりました。よろしければ是非携帯でアクセスして遊んでみてください。
こんにちは、ryosukeです。
ラボブログの前々回のエントリーで ruby で実装された web application framework の Sinatra が紹介されていたのですが、私もあまりのお手頃感に触発されて少しさわってみました。
その時にふとモデルやビューにいつもは使わない物を使ってみようと思い立ち、 Sequel と Haml を選んでみたのですが、 Haml の構文が見た目に反して(?)思いの他わかりやすかったので、今更感もありますが私同様 erb 以外使おうとも思わなかった人も少なくないのでは無いかと思いご紹介させて頂こうと思います。
Haml は XHTML Abstraction Markup Language の略で...という所から説明するのが筋なのですが、あっという間に5分経過してしまいそうなので、要点をかいつまんで進めて行こうと思います。
!!! XML
!!!
%html
%head
%meta{ 'http-equiv' => 'content', :content => 'text/html; charset=utf-8'}
%body
%div#container
%a welcome to |
labs.unoh.net |
<?xml version='1.0' encoding='utf-8' ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<meta content='text/html; charset=utf-8' http-equiv='content' />
</head>
<body>
<div id='container'>
<a>welcome to labs.unoh.net</a>
</div>
</body>
</html>
!!! XML
<?xml version='1.0' encoding='utf-8' ?>MEMO: 第二引数に文字コードを指定できる。デフォルトはUTF-8。
!!! XML euc-jp
<?xml version='1.0' encoding='euc-jp' ?>
!!!
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">MEMO: デフォルトでは XHTML 1.0 Transitional になります。他にもいくつか例示すると以下のように記述できます。
!!! Strict
!!! Frameset
!!! 1.1
%a labs.unoh.net
<a>labs.unoh.net</a>MEMO: 要素名を省略できる場面では DIV がデフォルトになる。
%a{:href => 'http://labs.unoh.net/'} labs.unoh.net
<a href="http://labs.unoh.net/">labs.unoh.net</a>MEMO: %aと{}の間にスペースを空けない。シンボルに使えない文字を含めたい場合(http-equivの-等)は文字列にする。
%div
%a{:href => 'http://labs.unoh.net/'} labs.unoh.net
<div> <a href='http://labs.unoh.net/'>labs.unoh.net</a> </div>MEMO: ネストはインデントで表現する。 1インデントは2つのスペースで表現する。
%span この行は長過ぎるので行分割したい | パイプで行分割できるんです。 |
<span>この行は長過ぎるので行分割したい パイプで行分割できるんです。</span>これはテキストだけでなく、構文中に含める事が出来ます。
%script{ :type => "textjavascript", |
:src => "/js/jquery.js" } |
MEMO: |の前にスペースが必須。最終行の |を忘れないように。
/ HTMLのコメント
<!-- HTMLのコメント -->
-# haml のコメント
出力ドキュメントとしては表示されません
¥%a が <a>になります
%a が <a>になります
%div#container body
<div id='container'>body</div>
%div.navi menu
<div class='navi'>menu</div>
%head
:javascript
var string = 'hello';
window.alert(string);
<head>
<script type='text/javascript'>
//<![CDATA[
var string = 'hello';
window.alert(string);
//]]>
</script>
</head>
%div
:escaped
<html>
<head>
<title>title</title>
</head>
<body>
<h1>h1</h1>
</body>
</html>
<div> <html> <head> <title>title</title> </head> <body> <h1>H1</h1> </body> </html> </div>
%div= "現在の時刻は" + Time.now.to_s + "です"
<div>現在の時刻はTue May 26 17:28:15 +0900 2009です</div>
- (1..10).each do |i|
%p= "値は#{i}です。"
- if i >= 5
%span.big 5以上
<p>値は1です。</p>
<p>値は2です。</p>
<p>値は3です。</p>
<p>値は4です。</p>
<p>値は5です。</p>
<span class='big'>5以上</span>
<p>値は6です。</p>
<span class='big'>5以上</span>
<p>値は7です。</p>
<span class='big'>5以上</span>
<p>値は8です。</p>
<span class='big'>5以上</span>
<p>値は9です。</p>
<span class='big'>5以上</span>
<p>値は10です。</p>
<span class='big'>5以上</span>
いかがでしょうか？5分だと少しきついかもしれませんが、これを見ただけでもすぐ書けそうな気がしませんか？
ここまで Haml の基本的な構文をかいつまんでみてきましたが、できるだけ出力に近い方が何かと便利というのは正直な所で、プロダクションレベルや共同作業が必要になる場合に採用するかというとちょっと...と考えてしまうかも知れません。とはいえ HTML を理解していればとても簡単に Haml も覚える事ができるので、どんな物かを知る為にちょっと触ってみるのも良いのではないでしょうか。
また、 Haml には Sass という CSS テンプレートがあり、簡潔に記述したり、変数を使ったり、コードを再利用したり、出力されるCSSを圧縮したりと erb等のテンプレートシステム を使って CSS をメンテナンスした事がある人にとっては恐らく Haml 以上に魅力的なおすすめツールだと思います。今回 Sass は扱いませんでしたが、機会があれば Sass にも触れられればと思います。
最近、「何故、君はマウスを2つ同時に使っているんだい？」と聞かれることが多くなったbokkoです。VX Revolution RXは右手用ですが、左手で使うならMicrosoftのArcがオススメです。近頃はフットマウスを買うかどうか真剣に悩んでいます。
Software Designには去年にも「ソースを読み，パッチを作成してみよう～GNU GLOBAL，diff，patchの使い方～」という記事を執筆する機会を頂いたので、本誌に執筆するのはこれが二度目になります。
今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているO(NP)差分アルゴリズムについて解説しています。
O(NP)や、それによく似たO(ND)をはじめとするエディットグラフを使って差分を求めるアルゴリズムは普段何気なく使っているdiffコマンドや各種バージョン管理システムで使われていることからもわかるようにとても有用であり、アルゴリズム自体の美しさやスマートさにも目を見張るものがあります。興味がある方はぜひ手にとって読んでみてください。本記事を通してdiffのアルゴリズムのおもしろさが伝われば幸いです。
本記事には訂正箇所が3箇所ほどあります。うち2つは本記事で使用しているdtlのバージョンが執筆後に0.05から0.06に上がったことによるもので、もう一つはO(NP)のアルゴリズムの計算量に対する私の勘違いによるものです。詳しい内容についてはSoftware Design 2009年6月号：サポートページ｜gihyo.jp ... 技術評論社をご覧下さい。
関係者や読者の方にはご迷惑をおかけしました。すみません。以後、気を付けます。
本記事にはサンプルコードとしてO(NP)を使って2つの文字列間の編集距離を求めるC++のプログラムが載っているのですが、ふと思い立って、同じことをするプログラムおよびLCSとSESも計算するプログラムをLuaで書いてみました。だからどうというわけでもないのですが、何か新しいプログラミング言語を触る際に、こんな風に自分にとってなじみのあるアルゴリズムを記述してみるのはその言語を勉強する上で、とてもいい方法だと再確認した次第です。
実際に書いていてハマったのですが、Luaではほかの大多数の言語と違って配列や文字列のインデックスが0からではなく1から始まるので、別の言語で記述されたアルゴリズムとかのコードを写経する際は注意しましょう。
しかし、この間、プログラマの友達とそんなLuaの独特の挙動について話をしていると、
まあ、(アルゴリズムの)論文に載っているような擬似コードは配列のインデックスが1から始まってるから、論文の擬似コードを写経する分にはちょうどいいんじゃね？
という感じのことを言われて「ああ、言われてみればそうだなあ」と妙に納得した次第です。とりあえず、今後、論文に載ってる疑似コードを実際のコードに落とす際はまずLuaで書いてそれからCとかC++に書き直すということを実践してみようと思います。
話が逸れました。以下にLuaによるO(NP)アルゴリズムの実装を2種類示します。その1が編集距離のみを計算するバージョン、その2が編集距離に加えてLCS、SESを計算するバージョンになります。なお、dtlと違ってワーストケース(LCSが極端に短くなる場合)への対応は行っていません。
-- editDistance.lua
-- Lua5.1.4で動作確認
ONP = {}
function ONP.new (a, b) -- ONPクラスのコンストラクタ
local self = { -- メンバ変数
A = a,
B = b,
M = string.len(a),
N = string.len(b),
}
function self.editDistance () -- 編集距離を計算する
offset = self.M + 1
delta = self.N - self.M
size = self.M + self.N + 3
fp = {}
for i = 0, size-1 do
fp[i] = -1
end
p = -1
repeat
p = p + 1
for k=-p, delta-1, 1 do
fp[k+offset] = self.snake(k, math.max(fp[k-1+offset]+1, fp[k+1+offset]))
end
for k=delta+p,delta+1, -1 do
fp[k+offset] = self.snake(k, math.max(fp[k-1+offset]+1, fp[k+1+offset]))
end
fp[delta+offset] = self.snake(delta, math.max(fp[delta-1+offset]+1, fp[delta+1+offset]))
until fp[delta+offset] >= self.N
return delta + 2 * p
end
function self.snake (k, y) -- 最遠点のy座標を計算する
x = y - k
while (x < self.M and y < self.N and
string.sub(self.A, x+1, x+1) == string.sub(self.B, y+1, y+1))
do
x = x + 1
y = y + 1
end
return y
end
if self.M >= self.N then -- N >= Mになるように調整
self.A, self.B = self.B, self.A
self.M, self.N = self.N, self.M
end
return self
end
if #arg < 2 then
error("few argument")
end
a = arg[1]
b = arg[2]
d = ONP.new(a, b)
print("editDistance:" .. d:editDistance())
narazuya@bokkko% lua editDistance.lua abcdef dacfea 6 narazuya@bokkko% lua e.editDistancelua abc abd 2 narazuya@bokkko%
-- onp.lua
-- Lua5.1.4で動作確認
ONP = {}
SES_DELETE = -1
SES_COMMON = 0
SES_ADD = 1
function ONP.new (a, b) -- ONPクラスのコンストラクタ
local self = { -- メンバ変数
A = a,
B = b,
M = string.len(a),
N = string.len(b),
path = {},
pathposi = {},
P = {},
ses = {},
seselem = {},
lcs = "",
editdis = 0,
reverse = false,
}
-- getter
function self.geteditdistance ()
return self.editdis
end
function self.getlcs ()
return self.lcs
end
function self.getses ()
return self.ses
end
-- constructor
function self.P.new (x_, y_, k_)
local self = { x=x_, y=y_, k=k_ }
return self
end
function self.seselem.new (elem_, type_)
local self = { elem=elem_, type=type_}
return self
end
-- 差分構築
function self.compose ()
offset = self.M + 1
delta = self.N - self.M
size = self.M + self.N + 3
fp = {}
for i = 0, size-1 do
fp[i] = -1
self.path[i] = -1
end
p = -1
repeat
p = p + 1
for k=-p, delta-1, 1 do
fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
end
for k=delta+p,delta+1, -1 do
fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
end
fp[delta+offset] = self.snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset])
until fp[delta+offset] >= self.N
self.editdis = delta + 2 * p
r = self.path[delta+offset]
epc = {}
while r ~= -1 do
epc[#epc+1] = self.P.new(self.pathposi[r+1].x, self.pathposi[r+1].y, nil)
r = self.pathposi[r+1].k
end
self.recordseq(epc)
end
function self.snake (k, p, pp) -- 最遠点のy座標を計算する
r = 0;
if p > pp then
r = self.path[k-1+offset];
else
r = self.path[k+1+offset];
end
y = math.max(p, pp);
x = y - k
while (x < self.M and y < self.N and
string.sub(self.A, x+1, x+1) == string.sub(self.B, y+1, y+1))
do
x = x + 1
y = y + 1
end
self.path[k+offset] = #self.pathposi
p = self.P.new(x, y, r)
self.pathposi[#self.pathposi+1] = p
return y
end
function self.recordseq (epc) -- LCS、SESを記録する
x_idx, y_idx = 1, 1
px_idx, py_idx = 0, 0
for i=#epc, 1, -1 do
while (px_idx < epc[i].x or py_idx < epc[i].y) do
if (epc[i].y - epc[i].x) > (py_idx - px_idx) then
elem = string.sub(self.B, y_idx, y_idx)
if self.reverse then
type = SES_DELETE
else
type = SES_ADD
end
self.ses[#self.ses+1] = self.seselem.new(elem, type)
y_idx = y_idx + 1
py_idx = py_idx + 1
elseif epc[i].y - epc[i].x < py_idx - px_idx then
elem = string.sub(self.A, x_idx, x_idx)
if self.reverse then
type = SES_ADD
else
type = SES_DELETE
end
self.ses[#self.ses+1] = self.seselem.new(elem, type)
x_idx = x_idx + 1
px_idx = px_idx + 1
else
elem = string.sub(self.A, x_idx, x_idx)
type = SES_COMMON
self.lcs = self.lcs .. elem
self.ses[#self.ses+1] = self.seselem.new(elem, type)
x_idx = x_idx + 1
y_idx = y_idx + 1
px_idx = px_idx + 1
py_idx = py_idx + 1
end
end
end
end
if self.M >= self.N then -- N >= Mになるように調整
self.A, self.B = self.B, self.A
self.M, self.N = self.N, self.M
self.reverse = true
end
return self
end
if #arg < 2 then
error("few argument")
end
a = arg[1]
b = arg[2]
d = ONP.new(a, b)
d:compose()
print("editDistance:" .. d:geteditdistance()) -- 編集距離
print("LCS:" .. d:getlcs()) -- Longest Common Subsequence
print("SES")
ses = d:getses() -- Shortest Edit Script
for i=1, #ses do
if ses[i].type == SES_COMMON then
print(" " .. ses[i].elem)
elseif ses[i].type == SES_DELETE then
print("- " .. ses[i].elem)
elseif ses[i].type == SES_ADD then
print("+ " .. ses[i].elem)
end
end
narazuya@bokkko% lua onp.lua abcdef dacfea editDistance:6 LCS:acf SES + d a - b c - d - e f + e + a narazuya@bokkko% lua a.lua abc abd editDistance:2 LCS:ab SES a b - c + d narazuya@bokkko%
