Scripts

Damerau-Levenshtein

-08-07-2020 21:20 -14.206 views

Deze functie berekent de Damerau-Levenshteinafstand tussen twee strings, dat is het minimumaantal bewerkingen (invoegen, vervangen of verwijderen) per teken om van de ene string de andere string te maken. Het aantal bewerkingen kan gezien worden als de mate van gelijkenis tussen twee woorden, als beide strings één byte per karakter hebben. Toepassingen: - wachtwoorden afkeuren die te veel lijken op de accountnaam - andere woorden voorstellen bij spelfouten - ... Afhankelijkheden: - Intl-extentie voor Unicode support Zie: - https://nl.wikipedia.org/wiki/Levenshteinafstand - https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

Download alle bestanden als ZIP

damerau-levenshtein.php

<?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];
}