2007-11-08

for 文を setTimeout に変換する（継続風）

for 文を setTimeout に変換する - IT戦記が楽しそうだったので、久しぶりにJavaScriptを書いてみた。
継続風に書くと、通常のforループとsetTimeout付きforループが同じようになります。
JavaScriptも楽しいなぁ。また、書きたい。

// 通常版
forloop(0, 3, 1)(function(i, cont){
    forloop(0, 7 ,1)(function(j, cont){
	console.log('a' + i + "-" + j);
	cont();
    }, cont);
}, function(){});

// timeout版
to_forloop(0, 3, 1)(function(i, cont){
    to_forloop(0, 7 ,1)(function(j, cont){
	console.log('a' + i + "-" + j);
	cont();
    }, cont);
}, function(){});

forloopとto_forloopはこんな感じです。

// from http://d.hatena.ne.jp/amachang/20071108/1194501306
var to = function() {
  var f = Array.prototype.shift.apply(arguments);
  args = arguments;
  return setTimeout(function() { f.apply(null, args) }, 10);
};

function forloop(i, j, k){
   var l = i;
   var a = function a(f, cont){
       if (l >= j) {
           return cont();
       }
       f(l, function(){
           l += k;
           a(f, cont);
       });
   }
   return a;
}

function to_forloop(i, j, k){
   var l = i;
   var a = function a(f, cont){
       if (l >= j) {
           return cont();
       }
       to(f, l, function(){
           l += k;
           a(f, cont);
       });
   }
   return a;
}

2007-03-18

ニコニコ動画は動画検索におけるGoogleになり得るか？

ニコニコ動画は動画検索におけるGoogleになり得ると思う。GoogleがWebページ検索において革命的であったのは、重要なのはページそのもの内容ではなく、Webページに対するアノテーション、つまり、リンクであることに気が付いた点である。そして、ニコニコ動画のコメントは、Webページのリンクと同じ性質を持っている。

ニコニコ動画のコメントとWebページのリンクで類似している点は次の3点である。

アノテーションの内容は不定形のテキスト（リンクの場合はアンカーテキスト）である。その為、キーワード検索で利用出来る。
人気のあるコンテンツに対してはアノテーションの数が多い。その為、アノテーション数を人気度の指標に出来る。
アノテーションを作成する動機は自分の楽しみ・利益の為である。その為、アノテーションの数はほっておいても自然に増大する。

これらの3つの特徴をリンクが持つため、Web検索ではページそのもの内容よりも、リンク（アンカーテキスト）の方が重要視される。同様に、ニコニコ動画のコメントが、動画検索においても最も重要なデータになる可能性はあると思う

門外漢ではあるが、従来の動画検索手法では、動画そのものを解析する手法が主流なように思える。例えば、動画の色・カメラ操作・音声などの情報を解析して、盛り上がっているシーンを検出するなどである。しかし、ニコニコ動画ならば、高度な動画処理技術を使わなくても、コメントの多いシーンを抽出することで、盛り上がりシーンを高精度に検出できるだろう。また、野球の動画からホームランのシーンを探し出すのは、動画そのものの解析では困難であろうが、ニコニコ動画のコメントを使えば、このような技術を簡単に実現できそうである。単に、「ホームラン」のコメントが大量に付与されたシーンを提示するだけで十分そうである。

まだ多くの課題が存在すると思うが、ニコニコ動画のアプローチは動画検索に革命を起こし得ると思う。そして、動画検索に革命を起こせれば、検索結果に広告を付けることで、投稿動画の問題点の1つであるビジネスモデルも解決できるかもしれない。つまり、サービス提供者は、動画を投稿し、閲覧者が各シーンにコメントできる場を提供する。そして、投稿されたコメントを利用して、高精度な動画検索サービスを構築する。さらに、この検索サービスで検索連動型広告を展開することで運営費を回収する。ただ、動画検索で検索連動型広告を打って、どれだけクリックされるかについては疑問点が残るところだが。

2007-02-20

継続を使ってSjaxをAjaxに簡単に変換する方法

JavaScriptによる全文検索エンジンの最初のバージョンはAjaxではなく、Sjaxであった。その為、サーバへのリクエストが発生する毎にブラウザが固まってしまい、応答性が悪かった。なぜ、Sjaxで記述したかというと、連続してサーバへリクエストを送り、しかも、サーバからのレスポンスに応じてリクエストを変更するようなAjaxプログラミングが面倒だった為である。このようなSjaxのコード例を次に示す（prototype.jsを使用）。

// (Sjax)サーバからpathのデータをoffsetの位置からlengthバイト取得
function fetch(path, length, offset){
    var range = ["bytes=" + offset + "-" + (offset + length - 1)].join("");
    var options = {
	method: "get",
	asynchronous: false,
	requestHeaders: ["Range", range]
    }
    var request = new Ajax.Request(path, options);
    return request.transport.responseText;
}
function fetch_data(){
    var path = "/data.txt";
    // 先頭4byteからoffsetを取得
    var offset = parseInt(fetch(path, 4, 0));
    // 先頭4byteからlengthを取得
    var length = parseInt(fetch(path, 4, 4));
    // 取得したoffset, lengthのデータを取得し返却
    return fetch(path, length, offset);
}
alert(fetch_data);

このようなSjaxによる処理をAjaxに変更する際、どうすれば簡単に書けるかしばらく考えていた。Stateパターンやイベントキューを検討してみたが、コーディングが面倒そうだし、コードも読み難くなりそうだった。そこで、継続を使ってみたところ、簡単にSjaxをAjaxに変換できた。

先ほどの例を、継続を使ってAjax化すると次のようになる。

// (Ajax)サーバからpathのデータをoffsetの位置からlengthバイト取得し、取得後contを実行。
function fetch(path, length, offset, cont){
    var range = ["bytes=" + offset + "-" + (offset + length - 1)].join("");
    var options = {
	method: "get",
	onComplete: function(request){cont(request.responseText);},
	requestHeaders: ["Range", range]
    }
    new Ajax.Request(path, options);
}
function fetch_data(cont){
    var path = "/data.txt";
    fetch(path, 4, 0, function(offset){
	offset = parseInt(offset);
	fetch(path, 4, 4, function(length){
	    length = parseInt(length);
	    fetch(path, length, offset, function(data){
		cont(data);
	    });
	});
    });
}
fecth_data(alert);

継続を使う方法のメリットには次の3点がある。

処理の流れとコードの流れが一致する。
単純作業でコードが変換できる。
apiの変更が少ない。

関数呼び出しのネストが深くなるのが少々難点だが、たいしたデメリットではないと思う。実際に、継続を使って名古屋市で賢い借金返済方法を教えます！をAjax化してみたが、予想より短時間で実装できた。

なお、継続でループを書く場合には、再帰呼び出しになる。例えば、次のSjaxコード

function loop_fetch(l){
    var data = "";
    for(var i = 0; i < l; i ++){
	data += fetch("/data.txt", 4, 4 * i);
    }
    return data;
}

を継続を使ってAjaxにすると、次のようになる。

function loop_fetch(l, cont){
    var data = "";
    var f = function(i){
	if(i < l){
	    fetch("/data.txt", 4, 4 * i, function(rv){
		data += rv;
		f(i + 1);
	    });
	}else{
	    cont(data);
	}
    }
    f(0);
}

継続を始めて知った時には、あまり役に立つ概念とは思えなかったけれど、やはり有名な概念は学んでおいて損はないと思った。

2007-02-18

UTF-8文字列を圧縮されたUTF-8文字列に変換するライブラリ u-lzss

UTF-8文字列の圧縮ライブラリを作っている。いまさら圧縮ライブラリをなぜ作るのかというと、JavaScriptによる全文検索エンジンで、インデックスの圧縮を行いたいからである。検索結果に概要文を出すには、インデックスが元テキスト全てを含む必要がある。従って、インデックスサイズの肥大化を避けるには、圧縮が必要不可欠である。ところが、次の条件を満たすライブラリを見つけられなかった。

圧縮後のデータがUTF-8文字列
JavaScriptで復元可能

前者の条件が必要なのは、JavaScriptでバイナリが扱えない為、圧縮後のデータがUTF-8文字列である必要がある為である。後者の条件は当たり前であるが、意外に該当するライブラリは少なかった。JavaScriptによるzipの解凍ライブラリは公開されているが、ライセンスが不明であった。

しょうがないので、LZSS符号をベースに、自分でライブラリを作ってみた。最低限のテストは通ったようなので、とりあえず、公開してみます。現在のところ、JavaScriptとRubyで符号・復号が出来ます。なお、符号化仕様はまだまだ流動的ですし、圧縮効率はあまり高くありません。

圧縮ライブラリを作ったので、日本語wikipediaの全文検索デモを作りたいのだけど、wiki記法からプレーンテキストにするのが面倒くさい。

2007-01-23

JavaScriptによる全文検索エンジン

JavaScriptでインデックス型の全文検索エンジンを作ってみた。全文検索エンジンを作る際に問題となるのは、インデックスデータを部分的に読み込む方法である。通常はmmapやpreadなどを使ってファイルの一部を部分的に読み込むのだが、もちろん、ブラウザには使えない。ブラウザでファイルの一部分を読み込むには2通りの方法がある。1つは、ファイルを多数のファイルに分割する方法であり、もう1つはHTTPリクエストのRangeヘッダを利用して、ファイルの一部を取得する方法である。前者の利点は、ブラウザのキャッシュが効くことや、対応ブラウザが多いことである。後者の利点は、ファイル数が少なくなるので、インデックスの管理が容易になることである。今回はRangeヘッダの実用性にも興味があったので、後者の方法を用いた。

参考ページ：最速インターフェース研究会 :: Ajaxを使ったシンプルなチャット

転置インデックスの構成は単純な 1gram + 連接情報にした。1gramだと検索速度が遅いが、インデックスサイズが大きいので今回は妥協した。2gramに対応するには、データ構造の洗練が必要である。インデックスサイズがまだまだ大きすぎる。なお、インデックス生成プログラムはRubyで書いた。最初はこちらもJavaScriptにしようと思ったのだが、色々と問題があって断念した。

苦労したのはJavaScriptではバイナリデータを扱えない点。その為、インデックス中の数値は全て文字列に変換する必要がある。例えば、数値の0はスペース(\u0020)に変換した。また、文字列のn-byte目の文字にアクセスする手段がないのも不便であった。JavaScriptではn文字目にアクセスする手段しかない。そのため、例えば、文字列のn-byteからm-byteを抜き出す（遅い）コードは次のようになる。

String.prototype.substr2 = function(offset, length){
    var out = "";
    var idx = 0;
    for(var i = 0; i < this.length; i++){
	if(offset <= idx && idx < offset + length){
	    out += this.charAt(i);
	}
	var code = this.charCodeAt(i);
	if(code < 0x80){
	    idx += 1;
	}else if(code > 0x7FF){
	    idx += 3;
	}else{
	    idx += 2;
	}
    }
    return out;
}

ただ、全文検索エンジンの作成自体は結構楽しかった。多分、チューニング作業が好きなのだと思う。削れる余地はまだまだいくらでもあるので、しばらく遊べるかも。

デモとして、はてなブックマークの過去の人気エントリー25000件のタイトルの検索サービスを公開してみます。デモページはJavaScriptプログラムやインデックスデータなどの静的なファイルのみから構成されています。

デモページ：名古屋市で賢い借金返済方法を教えます！

AND検索も出来ないし、バグだらけですが、よかったら試してみてください。1gramなので、ひらがなやカタカナの検索は結構遅いかもしれません。

2007-01-11

Wiki小話/Vol.7

Wiki小話/Vol.7に行ってきました。学習技術とRuby on RailsとJavaScriptが好きな自分には、とても楽しいイベントでした。特に印象深かったのは、音声認識技術の強みと弱みを一般の人にもっと知って欲しいというメッセージとid:brazilさんのとってもポップなプレゼンテーションでした。

昔の日記で次のように書いたことがあります。

「深い技術」が重要視されない原因の一つは、「深い技術」がブラック・ボックスになっている為である。「深い技術」で何が出来るのか、そして、何が出来ないのかが認知されない限り、「深い技術」が適切に評価される日はこないと思う。自分でプログラミングはしない人でも、プログラミングで何が出来るのかを知っている人は多いだろう。それと同じように、自分で「深い技術」を開発はしない人でも、「深い技術」で何が出来るのかを知っている人が増えればと思う。
「Googleの作り方」を書くことの難しさ、そして期待 - llameradaの日記

Podcastleのアプローチで「深い技術」の認知度を上げられないか考えてみよう。

懇親会は参加できず、ちょっと残念。

2006-12-25

複数の単語を似た意味に分類するサービス

単語をクラスタリングするサービスを作りました。

http://llamerada.sakura.ne.jp/clustord/cluster.cgi

入力された単語を似た意味のグループの分割します。例えば、「トマト」「りんご」「みかん」「なす」を入力した場合、「トマト　なす」と「りんご　みかん」に分類します。

検索キーワードなどは多種多様で、そのまま眺めても全体を把握しづらいことがありますが、単語をクラスタリングすることで概要がつかみやすくなります。また、私のdel.icio.usのタグを分類してみたところ次のようになりました。なんとなく合っているようです。
http://llamerada.sakura.ne.jp/clustord/cluster.cgi?id=5

精度はそれなりですが、使いどころはあるのかなと思います。向上の余地はまだまだあるので、少しずつ手を入れていきたいと思います。