Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
|||
Строка 96:
== Алгоритм Левенштейна на языке [[JavaScript|JavaScript]] ==
<source lang="javascript">
var cuthalf = 150;
var buf = new Array((cuthalf * 2) - 1);
function min3(a, b, c) { // вспомогательная функция
}
// s, t - строки преобразования
function LeveDist(s, t) {▼
// cd, ci, cs - стоимость удаления, вставки и замены
var i, j, m, n, cost, flip, result;
s = s.substr(0,cuthalf);
Строка 109 ⟶ 111 :
m = s.length;
n = t.length;
if (m === 0)
result = n;
else if (n === 0)
result = m;
else {
cd = cd || 1;
ci = ci || 1;
cs = cs || 1;
var minCost = min3(cd, ci, cs);
var minD = Math.max( minCost, (m - n) * cd );
var minI = Math.max( minCost, (n - m) * ci );
flip = false;
for (i = 0; i <= n; i++)
buf[i] = i * minD;
for (i = 1; i <= m; i++) {
if (flip)
buf[0] = i * minI;
else
buf[cuthalf] = i * minI;
for (j = 1; j <= n; j++) {
if (s.charAt(i-1) == t.charAt(j-1))
cost = 0;
else
cost =
if (flip)
buf[j] = min3((buf[cuthalf + j] +
(buf[j - 1] +
(buf[cuthalf + j - 1] + cost)); // substitute
else
buf[cuthalf + j] = min3((buf[j] +
(buf[cuthalf + j - 1] +
(buf[j - 1] + cost)); // substitute
}
flip = !flip;
Строка 146 ⟶ 154 :
}
</source>
== Алгоритм Левенштейна на языке [[Haskell|Haskell]] ==
<source lang="python">
| |||