Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
Заголовки (включая s/Алгоритм Левенштейна на языке //); →К переименованию: использован шаблон. |
|||
Строка 1:
{{К переименованию | 2014-05-02 | Реализации алгоритмов/Расстояние Левенштейна}}
Здесь приведены реализации [[w:Алгоритм Левенштейна|алгоритма Левенштейна]] на разных языках программирования.
== [[w:Visual Basic 6.0 (VB)]] ==
<source lang="vb">
Строка 8 ⟶ 11 :
Dim l1 As Long: l1 = VBA.Len(s1) + 1
Dim l2 As Long: l2 = VBA.Len(s2) + 1
If l1 = 1 Then Err.Raise 449
If l2 = 1 Then Err.Raise 449
Dim diff As Byte
Dim m() As Long
Строка 18 ⟶ 21 :
Dim b1() As Byte: b1 = VBA.StrConv(s1, VBA.VbStrConv.vbUnicode)
Dim b2() As Byte: b2 = VBA.StrConv(s2, VBA.VbStrConv.vbUnicode)
For i = 0 To l1
m(i, 1) = i
Next
For j = 0 To l2
m(1, j) = j
Next
For i = 1 To l1
For j = 1 To l2
Строка 33 ⟶ 36 :
Next
Next
LevenshteinDistance = m(l1, l2) - 1
End Function
Строка 49 ⟶ 52 :
</source>
==
<source lang="php">
<?PHP
Строка 90 ⟶ 93 :
// Serg Lifinsky
?>
</source>
==
<source lang="javascript">
/**
Строка 147 ⟶ 150 :
</source>
==
<source lang="python">
import Data.List
levenshtein s1 s2 = last $ foldl (transform s1) [0..length s1] s2 where
transform str xs@(x:xs') c = res where
Строка 158 ⟶ 161 :
</source>
==
нумерация элементов массивов начинается с единицы
Строка 174 ⟶ 177 :
l_nlength_vsource = len(a_vsource)
l_nlength_vtarget = len(a_vtarget)
if l_nlength_vsource = 0 then
return l_nlength_vtarget
Строка 183 ⟶ 186 :
column_to_left[j] = j
next
FOR i = 1 to l_nlength_vsource
current_column[1] = i
FOR j = 2 to (l_nlength_vtarget + 1)
IF mid(a_vsource, i, 1) = mid(a_vtarget, j - 1, 1) THEN
v_cost = 0
Строка 201 ⟶ 204 :
FOR j = 1 to (l_nlength_vtarget + 1)
column_to_left[j] = current_column[j]
next
next
end if
return current_column[l_nlength_vtarget + 1] - 1
end function
</source>
== [[w:Java]] ==
Линейное потребление памяти
Строка 221 ⟶ 224 :
int[] D1;
int[] D2 = new int[n + 1];
for(int i = 0; i <= n; i ++)
D2[i] = i;
Строка 246 ⟶ 249 :
</source>
==
<source lang="python">
Строка 257 ⟶ 260 :
a, b = b, a
n, m = m, n
current_row = range(n+1) # Keep current and previous row, not entire matrix
for i in range(1, m+1):
Строка 266 ⟶ 269 :
change += 1
current_row[j] = min(add, delete, change)
return current_row[n]
</source>
==
<!--
Зависимости: System
Строка 280 ⟶ 283 :
<source lang="Pascal">
program LeveDist; {
{ реализация функции в принципе соответствует описанию с одной оговоркой:
Строка 354 ⟶ 357 :
</source>
==
<!--
Зависимости: System
Строка 453 ⟶ 456 :
</source>
== [[w:Perl]] ==
<source lang="perl">
sub levenshtein($$){
Строка 487 ⟶ 490 :
== [[w:C++]] ==
<!--
Зависимости: Нет. Стандартный Си++.
Строка 530 ⟶ 533 :
}
}
return matrix[m][n];
}
Строка 546 ⟶ 549 :
</source>
== [[w:C sharp]] ==
<!--
Зависимости: System
Строка 558 ⟶ 561 :
if (string1==null) throw new ArgumentNullException("string1");
if (string2==null) throw new ArgumentNullException("string2");
int diff;
int [,] m = new int[string1.Length+1,string2.Length+1];
for (int i=0;i<=string1.Length;i++) m[i,0]=i;
for (int j=0;j<=string2.Length;j++) m[0,j]=j;
for (int i=1;i<=string1.Length;i++)
for (int j=1;j<=string2.Length;j++)
{
diff=(string1[i-1]==string2[j-1])?0:1;
m[i,j]=Math.Min(Math.Min(m[i-1,j]+1,
m[i,j-1]+1),
m[i-1,j-1]+diff);
}
return m[string1.Length,string2.Length];
}
</source>
Строка 585 ⟶ 588 :
</source>
==
''Примечание: Данная процедура может использоваться только в качестве примера, или для тестирования в силу плохой производительности.''
Строка 597 ⟶ 600 :
if (@string1 is null) Raiserror ('Строка 1 не должна быть пустой', 16, 1);
if (@string2 is null) Raiserror ('Строка 2 не должна быть пустой', 16, 1);
declare @diff int
declare @len1 int
declare @len2 int
set @len1 = len(@string1)
set @len2 = len(@string2)
Строка 610 ⟶ 613 :
set @i = 0
while (@i <= @len1)
begin
delete @m where i=@i and j=0
Строка 639 ⟶ 642 :
else
set @diff = 1
declare @minval int
select @minval = min(val)
from (
select isnull(val, 0) + 1 as val
from @m
where i = @i-1 and j = @j
union
select isnull(val, 0) + 1 as val
from @m
where i = @i and j = @j-1
union
select isnull(val, 0) + @diff as val
from @m
Строка 667 ⟶ 670 :
values (@i, @j, isnull(@minval, 0))
set @j = @j + 1
end
set @i = @i + 1
Строка 673 ⟶ 676 :
declare @retval int
select @retval = isnull(val, 0)
from @m
where i = @len1 and j = @len2
Строка 688 ⟶ 691 :
</source>
==
<source lang="maxscript">
fn LevenshteinDistance s1 s2 =
| |||