クライアント側の検索ツールの場合、他の何百万もの単語とのレーベンシュタイン距離を見つける必要があります。ユーザーは、約20語の短いテキストを本と比較できる必要があります。ユーザーは、本の中で最も特徴的なテキストの単語の場所を見つけることによってこれを行うことができます。「場所を見つける」とは、完全に一致するものを探すことを意味するのではなく、レーベンシュタインとほぼ一致することを意味します。私はすでに利用可能な実装から始めましたが、もっとスピードが必要でした。私はこれで終わった：
var rowA = new Uint16Array(1e6);
var rowB = new Uint16Array(1e6);
function levenshtein(s1, s2) {
var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0;
if (s1_len === 0)
return s2_len;
if (s2_len === 0)
return s1_len;
while (i < s1_len)
rowA[i] = ++i;
while (i2 < s2_len) {
c2 = s2[i2];
a = i2;
++i2;
b = i2;
for (i1 = 0; i1 < s1_len; ++i1) {
c = a + (s1[i1] !== c2 );
a = rowA[i1];
b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
rowB[i1] = b;
}
if (i2 === s2_len)
return b;
c2 = s2[i2];
a = i2;
++i2;
b = i2;
for (i1 = 0; i1 < s1_len; ++i1) {
c = a + (s1[i1] !== c2 );
a = rowB[i1];
b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
rowA[i1] = b;
}
}
return b;
}
ご覧のとおり、オブジェクトを再利用するために、関数からオブジェクトを配置するなどの手法を使用しました。また、ループをいくらか線形化することで、少し繰り返しました。もっと速くなるでしょうか？私はあなたのアドバイスに興味があります。
更新：Bergiからのヒントといくつかの考えの後、私はこの解決策に到達しました：
var row = new Uint16Array(1e6);
function levenshtein(s1, s2) {
var s1_len = s1.length, s2_len = s2.length, i2 = 1, a, b = 0, c, c2, i1 = 0;
if (s1_len === 0)
return s2_len;
if (s2_len === 0)
return s1_len;
c2 = s2[0];
if (s1[0] === c2) {
while (i1 < s1_len) {
row[i1] = i1++;
}
b = s1_len - 1;
} else {
row[0] = 1;
++b;
if (s1_len > 1)
for (i1 = 1; i1 < s1_len; ++i1) {
if (s1[i1] === c2) {
row[i1] = b;
for (++i1; i1 < s1_len; ++i1) {
row[i1] = ++b;
}
} else {
row[i1] = ++b;
}
}
}
if (s2_len > 1)
while (i2 < s2_len) {
c2 = s2[i2];
c = i2 + (s1[0] !== c2);
a = row[0];
++i2;
b = i2 < a ? (i2 < c ? i2 + 1 : c) : (a < c ? a + 1 : c);
row[0] = b;
if (s1_len > 1) {
for (i1 = 1; i1 < s1_len; ++i1) {
c = a + (s1[i1] !== c2);
a = row[i1];
b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
row[i1] = b;
}
}
}
return b;
}
これもはるかに高速です。私はそれからこれ以上搾り出すことはできません。私は他のアイデアを探し続けており、さらにいくつか試してみます。
同じ単語と何度も比較しているので、部分適用を使用してそこでキャッシュすることで、パフォーマンスを少し向上させることができます。
function levenshtein(s1) {
var row0 = [], row1 = [], s1_len = s1.length;
if (s1_len === 0)
return function(s2) {
return s2.length;
};
return function(s2) {
var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;
if (s2_len === 0)
return s1_len;
…
return b;
};
}
また、ループをいくらか線形化することで、少し繰り返しました。
はるかに高速になるかどうかはわかりませんが、配列の1つを省略できます。交互に読み取り/書き込みを行う必要はありません。
function levenshtein(s1) {
var s1_len = s1.length, row = new Array(s1_len);
if (s1_len === 0)
return function(s2) {
return s2.length;
};
return function(s2) {
var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;
if (s2_len === 0)
return s1_len;
while (i < s1_len)
row[i] = ++i;
while (s2_idx < s2_len) {
c2 = s2[s2_idx];
a = s2_idx;
++s2_idx;
b = s2_idx;
for (s1_idx = 0; s1_idx < s1_len; ++s1_idx) {
c = a + (s1[s1_idx] === c2 ? 0 : 1);
a = row[s1_idx];
b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
row[s1_idx] = b;
}
}
return b;
};
}
専用のデータ構造（プレフィックストライなど）に数百万の単語を入れずに、さらに最適化することはできないと思います。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加