Doc #36261 [Opn->Csd]: similar_text parameters aren't swappable

Edit report at https://bugs.php.net/bug.php?id=36261&edit=1 ID: 36261 Updated by: cmb@php.net Reported by: mac30 at narod dot ru Summary: similar_text parameters aren't swappable -Status: Open +Status: Closed Type: Documentation Problem Package: Strings related Operating System: * PHP Version: * -Assigned To: +Assigned To: cmb Block user comment: N Private report: N Previous Comments: ------------------------------------------------------------------------ [2018-02-22 17:42:22] cmb@php.net Automatic comment from SVN on behalf of cmb Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=344329 Log: Fix bug #36261: similar_text parameters aren't swappable ------------------------------------------------------------------------ [2015-04-12 19:45:43] cmb@php.net Related To: Bug #62648 ------------------------------------------------------------------------ [2015-04-12 19:38:01] cmb@php.net At first, it seems to be important to explain the algorithm. It is finding the longest common substring of two strings, and then doing this for the prefixes resp. the suffixes, recursively. The lengths of the found common substrings are added and returned as result. The percentage is calculated by multiplying the result with 200 and dividing by the sum of the lenghts of both input strings. Finding the longest common substring of two strings is accomplished by the following algorithm: function longest_common_substring($a, $b) { $max = 0; for ($i = 0; $i < strlen($a); $i++) { for ($j = 0; $j < strlen($b); $j++) { $l = 0; while ($i + $l < strlen($a) && $j + $l < strlen($b) && $a[$i + $l] == $b[$j + $l] ) { $l++; } if ($l > $max) { $max = $l; } } } return $max; } A noteworthy detail of the algorithm is that it always takes the first longest common substring in either of the strings. A simple example: similar_text('aabccc', 'aadccc') // => 5 The longest common substring is 'ccc' with a length of 3. None of the input strings has a suffix after 'ccc', so only the prefixes ('aab' and 'aad') are compared. Their longest common substring is 'aa' (length 2); both don't have a prefix, so the suffixes 'b' and 'd' are compared, resulting in no common substring (length 0). Adding up the lengths results in 5. Another example: similar_text('michaelski', 'pankanin') // => 1 The first longest common substring that is found is 'i' (length 1), so the prefixes are 'm' and 'pankan' and the suffixes are 'chaelski' and 'n'. The longest common substring of the prefixes is '' (length 0), the longest common substring of the suffixes is '' (length 0). So the result is 1. Swapping the arguments has a different result, though: similar_text('pankanin', 'michaelski') // => 3 That is because the first longest common substring is 'a' (length 1), with the prefixes 'p' and 'mich' and the suffixes 'nkanin' and 'elski'. The prefixes have no common substring, but the suffixes have 'k' (length 1), which has the prefixes 'n' and 'els' and the suffixes 'anin' and 'i'. The prefixes have no common substring, but the suffixes have 'i' (length 1). Therefore the result is 1. One might argue that the algorithm is imperfect, but at least the implementation is correct. It seems reasonable to document the behavior of similar_text more clearly, therefore I'm changing to "Documentation Problem". > I used PHP 4.4.0 and 5.0.5 and got exactly the same results on > both of them. According to <http://3v4l.org/N6j98> the results under PHP 4.4.0 and 5.0.5 are the same than under most recent versions. > Using LCS function (taken from comments on similar_text manual > page) This function does basically the same as longest_common_substring() above, which is only part of the more complex similar_text() algorithm. ------------------------------------------------------------------------ [2015-01-09 00:09:44] ajf@php.net Sounds like a bug, not a feature request, to me. ------------------------------------------------------------------------ [2011-07-11 12:15:27] dejaschinski at googlemail dot com I've running in the same problem. I'm using php-5.3.6 with opensuse11.3. <?php echo similar_text("test","wert"); echo "|"; echo similar_text("wert","test"); Expected result: 2|2 Current result: 1|2 ------------------------------------------------------------------------ The remainder of the comments for this report are too long. To view the rest of the comments, please view the bug report online at https://bugs.php.net/bug.php?id=36261 -- Edit this bug report at https://bugs.php.net/bug.php?id=36261&edit=1