note 31935 added to function.levenshtein
| From: | asseg at ukl dot uni-feiburg dot de | Date: | Fri, 09 May 2003 11:05:21 +0000 |
| Subject: | note 31935 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-47735@lists.php.net to get a copy of this message | ||
for the unserious guys how might do dna sequence analysis
with php. Here's the function that can handle long strings.
to get an output of the matrix uncomment the
printf-section. handle with care iteration are approximately
2x2^strlen ;)
------------------------------------------------------------
function levdis($s,$t){
$n=strlen($s);
$m=strlen($t);
$matrix=array(range(0,$n+1),range(0,$m+1));
$ret=0;
if ($n==0){
return $m;
}
elseif ($m==0){
return $n;
}
for ($i=0;$i<=$n;$i++) {
$matrix[$i][0]=$i;
}
for ($j=0;$j<=$m;$j++) {
$matrix[0][$j]=$j;
}
for ($i=1;$i<=$n;$i++) {
for ($j=1;$j<=$m;$j++) {
if ($s[$i-1]==$t[$j-1]) {
$cost=0;
}else{
$cost=1;
}
$matrix[$i][$j]=min($matrix[$i-1][$j]+1,
$matrix[$i][$j-1]+1,
$matrix[$i-1][$j-1]+$cost);
}
}
/* for ($j=0;$j<=$m;$j++) {
for ($i=0;$i<=$n;$i++) {
printf(" %02d",$matrix[$i][$j]);
}
echo "\n";
}*/
return $matrix[$n][$m];
}
----------------------------------------------
--
http://www.php.net/manual/en/function.levenshtein.php
http://master.php.net/manage/user-notes.php?action=edit+31935
http://master.php.net/manage/user-notes.php?action=delete+31935
http://master.php.net/manage/user-notes.php?action=reject+31935