2009年07月13日

PHP の levenshtein を JavaScript に移植

海外にも JavaScript でレーベンシュタイン距離を計算するソースコードはいくつか見つかったんだけど、挿入、置換、削除のコストをそれぞれ指定できるようになっているソースは見つからなかったのでこれもPHPのソースコードを参照してそのまま移植。

function levenshtein(s1, s2, cost_ins, cost_rep, cost_del)
{
if (typeof cost_ins == "undefined") cost_ins = 1;
if (typeof cost_rep == "undefined") cost_rep = 1;
if (typeof cost_del == "undefined") cost_del = 1;

var l1 = s1.length, l2 = s2.length;
var p1, p2, tmp, i1, i2, j1, j2, cp1, cp2, c0, c1, c2, ch1, ch2;

if (l1 == 0) {
return l2 * cost_ins;
}
if (l2 == 0) {
return l1 * cost_del;
}

p1 = new Array(l2 + 1);
p2 = new Array(l2 + 1);

for (i2 = 0; i2 <= l2; i2++) {
p1[i2] = i2 * cost_ins;
}
for (i1 = 0, j1 = 0; i1 < l1; i1++) {
p2[0] = p1[0] + cost_del;
for (i2 = 0, j2 = 0; i2 < l2; i2++) {
c0 = p1[i2] + (s1.charAt(i1) == s2.charAt(i2) ? 0 : cost_rep);

c1 = p1[i2 + 1] + cost_del;
if (c1 < c0) {
c0 = c1;
}
c2 = p2[i2] + cost_ins;
if (c2 < c0) {
c0 = c2;
}
p2[i2 + 1] = c0;
}
tmp = p1;
p1 = p2;
p2 = tmp;
}
c0 = p1[l2];

return c0;
}
posted by oov at 23:49| Comment(0) | TrackBack(0) | プログラム | このブログの読者になる | 更新情報をチェックする
この記事へのコメント

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。