damerau-levenshtein.php
Gesponsorde koppelingen
PHP script bestanden
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
<?php
/**
* Damerau-Levenshtein afstand
* @param string $s Bron
* @param string $t Doel
* @return int
*/
function dl_afstand(string $s, string $t) : int
{
$d = []; // 2D matrix
$n = grapheme_strlen($s); // Stap 1
$m = grapheme_strlen($t);
if (0 === $n) {return $m;}
if (0 === $m) {return $n;}
for ($i = $n; $i >= 0; $i--) {$d[$i] = [];} // Maak array van arrays aan
for ($i = $n; $i >= 0; $i--) {$d[$i][0] = $i;} // Stap 2
for ($j = $m; $j >= 0; $j--) {$d[0][$j] = $j;}
for ($i = 1; $i <= $n; $i++) { // Stap 3
$s_i = grapheme_substr($s, $i - 1, 1);
for ($j = 1; $j <= $m; $j++) { // Stap 4
// Controleer de kartelige Lehvenstein-afstand totaal tot nu toe
if ($i === $j and isset($d[$i][$j]) && $d[$i][$j] > 4) {return $n;}
$t_j = grapheme_substr($t, $j - 1, 1);
$cost = ($s_i === $t_j) ? 0 : 1; // Stap 5
$mi = $d[$i - 1][$j] + 1; // Bereken het minimum
$b = $d[$i][$j - 1] + 1;
$c = $d[$i - 1][$j - 1] + $cost;
if ($b < $mi) {$mi = $b;}
if ($c < $mi) {$mi = $c;}
$d[$i][$j] = $mi; // Stap 6
// Damerau transpositie
if ($i > 1 and $j > 1 && $s_i == grapheme_substr($t, $j - 2, 1)
and grapheme_substr($s, $i - 2, 1) == $t_j)
{
$d[$i][$j] = min([$d[$i][$j], $d[$i - 2][$j - 2] + $cost]);
}
}
}
// Stap 7
return $d[$n][$m];
}
/**
* Damerau-Levenshtein afstand
* @param string $s Bron
* @param string $t Doel
* @return int
*/
function dl_afstand(string $s, string $t) : int
{
$d = []; // 2D matrix
$n = grapheme_strlen($s); // Stap 1
$m = grapheme_strlen($t);
if (0 === $n) {return $m;}
if (0 === $m) {return $n;}
for ($i = $n; $i >= 0; $i--) {$d[$i] = [];} // Maak array van arrays aan
for ($i = $n; $i >= 0; $i--) {$d[$i][0] = $i;} // Stap 2
for ($j = $m; $j >= 0; $j--) {$d[0][$j] = $j;}
for ($i = 1; $i <= $n; $i++) { // Stap 3
$s_i = grapheme_substr($s, $i - 1, 1);
for ($j = 1; $j <= $m; $j++) { // Stap 4
// Controleer de kartelige Lehvenstein-afstand totaal tot nu toe
if ($i === $j and isset($d[$i][$j]) && $d[$i][$j] > 4) {return $n;}
$t_j = grapheme_substr($t, $j - 1, 1);
$cost = ($s_i === $t_j) ? 0 : 1; // Stap 5
$mi = $d[$i - 1][$j] + 1; // Bereken het minimum
$b = $d[$i][$j - 1] + 1;
$c = $d[$i - 1][$j - 1] + $cost;
if ($b < $mi) {$mi = $b;}
if ($c < $mi) {$mi = $c;}
$d[$i][$j] = $mi; // Stap 6
// Damerau transpositie
if ($i > 1 and $j > 1 && $s_i == grapheme_substr($t, $j - 2, 1)
and grapheme_substr($s, $i - 2, 1) == $t_j)
{
$d[$i][$j] = min([$d[$i][$j], $d[$i - 2][$j - 2] + $cost]);
}
}
}
// Stap 7
return $d[$n][$m];
}