Piekło,Najlepszy sposób w php, aby znaleźć najbardziej podobne ciągi?
PHP ma wiele funkcji łańcuchowych, takich jak levenshtein, similar_text i soundex, które mogą porównywać ciągi podobieństwa. http://www.php.net/manual/en/function.levenshtein.php
Który jest najlepszy dla dokładności i wydajności?
similar_text ma złożoność O (max (n, m) ** 3) i niweluje złożoność O (m * n), gdzie n i m są długością łańcuchów, więc levenshtein powinien być znacznie szybszy. Oba są w 100% dokładne, ponieważ dają takie samo wyjście dla tego samego wejścia, ale wyjścia dla każdej funkcji będą się różnić. Jeśli używasz innej miary dokładności, musisz utworzyć własną funkcję porównania.
W rzeczywistości, po prostu sprawdzane na php i ich złożoność jest inna: "Złożoność algorytmu (levenshtein) to O (m * n), gdzie n i m są długością str1 i str2 (raczej dobre w porównaniu do similar_text() , która jest O (max (n, m) ** 3), ale nadal droga). " – giorgio79
To zależy w dużej mierze od tego, co jest dla ciebie inne. Znalazłem "podobny_tekst", aby lepiej pasował do mojej sprawy. 'levenshtein' zwróci więcej podobieństwa, jeśli łańcuchy mają tę samą długość. Na przykład: "marco blabla" w porównaniu do "rob blabla" dało 81,8% (similar_text) i 4 (levenshtein). Natomiast "jan blabla" w porównaniu z "rob blabla" dał 70% (podobny_tekst) i 3 (levenshtein). Tak więc "levenshtein" uważa, że te ostatnie są bardziej podobne, a "similar_text" uważa, że te pierwsze są bardziej podobne. – Lode
Wydaje mi się, że byłoby lepiej przystosowane jako społeczność Wiki –
Nie wiedząc zbyt wiele o szczegółach implementacji różnych funkcji, mam przeczucie, że nie można celować w dokładność i wydajność. Są one prawdopodobnie trochę odwrotnie proporcjonalne. –
@ András Możliwe, że będziesz w stanie odpowiedzieć, która jest lepsza dla wydajności, a która jest lepsza pod względem dokładności. – Adam