2009年07月18日

プチ業務連絡

過去ログ倉庫を621スレ分まで配置しました。

検索もこれから621スレ分まで対応させるつもりですが、
個人的な趣味で色々やりたいことがあるので作り直しします。

2009年07月14日

Jaro-Winkler Distance

レーベンシュタイン距離と似たような用途で使える Jaro-Winkler 距離を JavaScript で使えるように。今回は Apache ライセンスで提供されている Lucene に含まれる Java のソースを適当に移植。

function jarowinkler(s1, s2)
{
var threshold = 0.7;

var max, min;
if (s1.length > s2.length)
{
max = s1;
min = s2;
}
else
{
max = s2;
min = s1;
}

var range = Math.max(max.length / 2 - 1, 0);
var matchIndexes = new Array(min.length);
for (var i = 0; i < matchIndexes.length; ++i){ matchIndexes[i] = -1; }
var matchFlags = new Array(max.length);
var matches = 0;

for(var mi = 0; mi < min.length; mi++)
{
var c1 = min.charAt(mi);
for(var xi = Math.max(mi - range, 0),
xn = Math.min(mi + range + 1, max.length); xi < xn; xi++)
{
if ((!matchFlags[xi])&&(c1 == max.charAt(xi)))
{
matchIndexes[mi] = xi;
matchFlags[xi] = true;
matches++;
break;
}
}
}
var ms1 = new Array(matches);
var ms2 = new Array(matches);
for (var i = 0, si = 0; i < min.length; ++i)
{
if (matchIndexes[i] != -1)
{
ms1[si] = min.charAt(i);
++si;
}
}
for (var i = 0, si = 0; i < max.length; ++i)
{
if (matchFlags[i])
{
ms2[si] = max.charAt(i);
++si;
}
}
var transpositions = 0;
for (var mi = 0; mi < ms1.length; ++mi)
{
if (ms1[mi] != ms2[mi])
{
++transpositions;
}
}
var prefix = 0;
for (var mi = 0; mi < min.length; ++mi)
{
if(s1.charAt(mi) == s2.charAt(mi))
{
++prefix;
}
else
{
break;
}
}

if (matches == 0)
{
return 0;
}

var m = matches;
var j = ((m / s1.length + m / s2.length +
(m - (transpositions / 2)) / m)) / 3;

return j < threshold ? j :
j + Math.min(0.1, 1.0/max.length) * prefix * (1 - j);
}
posted by oov at 22:01| Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする

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) | プログラム | このブログの読者になる | 更新情報をチェックする

PHP の similar_text を JavaScript に移植

PHPのソースコードを参照してそのまま移植したコード。
サーバサイドでやらなくてもいいようなケースに遭遇したら、
この負荷をクライアント側にやらせられるのはわりと意味があると思う。

function similar_text(text1, text2)
{
function similar_char(text1, len1, text2, len2)
{
function similar_str(text1, len1, text2, len2)
{
var pos1 = 0, pos2 = 0, max = 0, i, j, l;

for (i = 0; i < len1; ++i)
{
for (j = 0; j < len2; ++j)
{
for (l = 0; (i + l < len1)&&(j + l < len2)&&
(text1.charAt(i+l) == text2.charAt(j+l)); ++l);
if (l > max)
{
max = l;
pos1 = i;
pos2 = j;
}
}
}

return {
'pos1': pos1,
'pos2': pos2,
'max': max
};
}

var r = similar_str(text1, len1, text2, len2);
var sum = r.max;
if (sum)
{
if (r.pos1 && r.pos2)
{
sum += similar_char(text1, r.pos1, text2, r.pos2);
}
if((r.pos1 + r.max < len1)&&(r.pos2 + r.max < len2))
{
sum += similar_char(
text1.substr(r.pos1 + r.max),
len1 - r.pos1 - r.max,
text2.substr(r.pos2 + r.max),
len2 - r.pos2 - r.max);
}
}
return sum;
}

var sim = similar_char(text1, text1.length, text2, text2.length);
return {
'similar': sim,
'percent': sim * 200.0 / (text1.length + text2.length)
};
}
posted by oov at 23:43| Comment(0) | TrackBack(0) | プログラム | このブログの読者になる | 更新情報をチェックする
×

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