note 19734 added to function.similar-text
| From: | georgesk at hotmail dot com | Date: | Sat, 09 Mar 2002 01:14:42 +0000 |
| Subject: | note 19734 added to function.similar-text | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-27540@lists.php.net to get a copy of this message | ||
Well, as mentioned above the speed is O(N^3), i've done a longest common subsequence way that
is O(m.n) where m and n are the length of str1 and str2, the result is a percentage and it seems to
be exactly the same as similar_text percentage but with better performance... here's the 3
functions i'm using..
function LCS_Length($s1, $s2)
{
$m = strlen($s1);
$n = strlen($s2);
//this table will be used to compute the LCS-Length, only 128 chars per string are considered
$LCS_Length_Table = array(array(128),array(128));
//reset the 2 cols in the table
for($i=1; $i < $m; $i++) $LCS_Length_Table[$i][0]=0;
for($j=0; $j < $n; $j++) $LCS_Length_Table[0][$j]=0;
for ($i=1; $i <= $m; $i++) {
for ($j=1; $j <= $n; $j++) {
if ($s1[$i-1]==$s2[$j-1])
$LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i-1][$j-1] + 1;
else if ($LCS_Length_Table[$i-1][$j] >= $LCS_Length_Table[$i][$j-1])
$LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i-1][$j];
else
$LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i][$j-1];
}
}
return $LCS_Length_Table[$m][$n];
}
function str_lcsfix($s)
{
$s = str_replace(" ","",$s);
$s = ereg_replace("[éèêëËÊÉÈ]","e", $s);
$s = ereg_replace("[àáâãäåÄÅÃÂÁÀ]","a", $s);
$s = ereg_replace("[ìíîïÏÎÍÌ]","i", $s);
$s = ereg_replace("[òóôõöÖÕÔÓ]","o", $s);
$s = ereg_replace("[ÜÛÚÙùúûü]","u", $s);
$s = ereg_replace("[Ç]","c", $s);
return $s;
}
function get_lcs($s1, $s2)
{
//ok, now replace all spaces with nothing
$s1 = strtolower(str_lcsfix($s1));
$s2 = strtolower(str_lcsfix($s2));
$lcs = LCS_Length($s1,$s2); //longest common sub sequence
$ms = (strlen($s1) + strlen($s2)) / 2;
return (($lcs*100)/$ms);
}
you can skip calling str_lcsfix if you don't worry about accentuated characters and things like
that or you can add up to it or modify it for faster performance, i think ereg is not the fastest
way?
hope this helps.
Georges
--
http://www.php.net/manual/en/function.similar-text.php
http://master.php.net/manage/user-notes.php?action=edit+19734
http://master.php.net/manage/user-notes.php?action=delete+19734
http://master.php.net/manage/user-notes.php?action=reject+19734