Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does the function levenshtein in PHP have a 255-character limit?

Does anybody know why the function levenshtein in PHP has a 255-character limit?

like image 452
marco.ciotoli Avatar asked Sep 06 '18 09:09

marco.ciotoli


1 Answers

This is the PHP full implementation for the function. As you can see there are nested loop based on string characters length:

function lev($s,$t) {
  $m = strlen($s);
  $n = strlen($t);

  for($i=0;$i<=$m;$i++) $d[$i][0] = $i;
  for($j=0;$j<=$n;$j++) $d[0][$j] = $j;

  for($i=1;$i<=$m;$i++) {
    for($j=1;$j<=$n;$j++) {
      $c = ($s[$i-1] == $t[$j-1])?0:1;
      $d[$i][$j] = min($d[$i-1][$j]+1,$d[$i][$j-1]+1,$d[$i-1][$j-1]+$c);
    }
  }

  return $d[$m][$n];
}

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#PHP

the version for PHP named levenshtein() in PHP starting from version 4.0.1 to 255 chars length.

I think the limitation is introduced to maintain performance and duration in a most acceptable range.

If you need string comparison for lengths > 255, you could use the implementation above.

like image 164
ScaisEdge Avatar answered Sep 23 '22 01:09

ScaisEdge