frank
Goto Top

Schnelle Stringvergleichsfunktion für PHP

article-picture
Hallo User,

als Entwickler stand ich vor einer Herausforderung: Ich brauchte eine schnelle Stringvergleichsfunktion für unsere Website. Meine Reise begann mit den PHP-Funktionen similar_text() und später levenshtein(). Doch selbst diese nativen Funktionen brauchten bei längeren Texten über 30 Sekunden – viel zu lang für unsere Webseite.

Die Suche nach einer effizienteren Lösung führte mich zu einer einfachen, aber äußerst effektiven Methode. Statt komplexer Algorithmen nutze ich nun grundlegende Textverarbeitungsmethoden wie Längenvergleich und Wortzählung. Das Ergebnis? Eine beeindruckende Performancesteigerung von 80% bis 90% gegenüber similar_text() und levenshtein() face-smile

Meine neue stringCompare()-Funktion vergleicht zwei Texte ($str1, $str2) und gibt den Unterschied in Prozent aus. Sie ist nicht nur schnell, sondern auch leicht zu verstehen und zu implementieren. Hundertprozentig genau ist sie jedoch nicht (je nach Länge des Textes sind Abweichungen im einstelligen Bereich möglich). Die Funktion konzentriert sich mehr auf quantitative Aspekte (Länge, Worthäufigkeit) als auf qualitative Aspekte (Bedeutung, Kontext). Sie ist effektiv darin, strukturelle Ähnlichkeiten und wörtliche Übereinstimmungen zu erkennen, aber sie kann subtilere inhaltliche Unterschiede oder Ähnlichkeiten übersehen.

Ich möchte diese Lösung mit der Entwickler-Community teilen, in der Hoffnung, dass sie bei ähnlichen Performance-Problemen helfen kann.

class TextComparison {
    public static function stringCompare($str1, $str2): float {
        // Frühe Rückkehr für identische Strings
        if ($str1 === $str2) {
            return 0.0;
        }

        // Normalisierung, reinige die Strings (optional)
        $str1 = self::cleanString($str1);
        $str2 = self::cleanString($str2);

        // Prüfe auf leere Strings nach der Reinigung
        if ($str1 === '' && $str2 === '') {  
            return 0.0;
        }
        if ($str1 === '' || $str2 === '') {  
            return 100.0;
        }

        // Berechne Längenänderung
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        $lengthChange = abs($len2 - $len1) / max($len1, $len2);

        // Berechne Wortübereinstimmung
        $words1 = str_word_count(mb_strtolower($str1), 1);
        $words2 = str_word_count(mb_strtolower($str2), 1);
        $uniqueWords = array_unique(array_merge($words1, $words2));
        $matchingWords = 0;

        foreach ($uniqueWords as $word) {
            $count1 = array_count_values($words1)[$word] ?? 0;
            $count2 = array_count_values($words2)[$word] ?? 0;
            $matchingWords += min($count1, $count2);
        }

        $totalWords = max(count($words1), count($words2));
        $wordChange = 1 - ($matchingWords / $totalWords);

        // Kombiniere Längen- und Wortänderung
        $overallChange = ($lengthChange + $wordChange) / 2;

        // Ausgabe in Prozent 
        return round($overallChange * 100, 2);
    }
    
    private static function cleanString($string): string {
        // Entferne Satzzeichen und sonstige nicht-alphanumerische Zeichen (optional)
        return preg_replace('/[^a-zA-Z0-9\s]/u', '', $string);  
    }
}

// Beispielaufrufe
$str1 = "Dies ist ein Beispieltext für den Vergleich.";  
$str2 = "Dies ist ein Beispieltext für den Vergleich. Dies ist ein Beispieltext für den Vergleich.";  
$str3 = "Dies ist ein völlig anderer Text.";  

echo "Änderungsprozentsatz (verdoppelter Text): " . TextComparison::stringCompare($str1, $str2) . "%\n";  
echo "Änderungsprozentsatz (unterschiedlicher Text): " . TextComparison::stringCompare($str1, $str3) . "%\n";  
echo "Änderungsprozentsatz (identischer Text): " . TextComparison::stringCompare($str1, $str1) . "%\n";  

UPDATE: Es gibt mehrere verbesserte Versionen des Codes weiter unten. "cleanString" und die "Beispielaufrufe" sind jedoch identisch.

Gruß
Frank

Content-ID: 668057

Url: https://administrator.de/contentid/668057

Printed on: October 15, 2024 at 05:10 o'clock

14260433693
14260433693 Sep 11, 2024 updated at 15:24:54 (UTC)
Goto Top
Moin.
👍 . Kommt darauf an wie man hier die "Menge an Änderung" definiert, wenn ich etwa beispielsweise alle Zeichen durch "x" ersetze, Länge lasse ich gleich, habe ich eigentlich nach meiner Definition alles abgeändert (außer der Leerzeichen) der Prozentsatz beträgt dann aber nur 52,27 %
$str1 = "Dies ist ein Beispieltext für den Vergleich.";  
$str2 = "xxxx xxx xxx xxxxxxxxxxxx xxx xxx xxxxxxxxxx";  
echo "Änderungsprozentsatz " . TextComparison::stringCompare($str1, $str2) . "%";    
https://tio.run/##jVXbTttAEH3PV4wiCk5JSPBbkyJEafvSqqqgKhKXRhtnHK9Yr93dNV ...

Noch als Verbesserungsvorschlag
array_count_values($words1)
array_count_values($words2)
Die Ergebnisse der zwei Funktionsaufrufe könnte man vor der Schleife noch zwischenspeichern so das sie nicht für jeden Schleifenaufruf erneut berechnet werden müssen, das täte der Performance auch noch gut.

Gruß
Lochkartenstanzer
Lochkartenstanzer Sep 11, 2024 at 15:25:15 (UTC)
Goto Top
Sorry, daß ich Mehrarbeit verursacht habe. face-smile

lks
Frank
Frank Sep 11, 2024 updated at 19:21:42 (UTC)
Goto Top
@Lochkartenstanzer
Nein, das hatte nur indirekt mit deiner Anfrage zu tun. Es gab zur gleichen Zeit ein Problem mit einem sehr langen Tutorial, das erst nach über 30 Sekunden gespeichert wurde. Ich habe mir das dann genauer angesehen.

@14260433693:
Moin.
👍 . Kommt darauf an wie man hier die "Menge an Änderung" definiert, wenn ich etwa beispielsweise alle Zeichen durch "x" ersetze, Länge lasse ich gleich, habe ich eigentlich nach meiner Definition alles abgeändert (außer der Leerzeichen) der Prozentsatz beträgt dann aber nur 52,27 %
$str1 = "Dies ist ein Beispieltext für den Vergleich.";  
$str2 = "xxxx xxx xxx xxxxxxxxxxxx xxx xxx xxxxxxxxxx";  
echo "Änderungsprozentsatz " . TextComparison::stringCompare($str1, $str2) . "%";    

Ja, einen genauen inhaltlichen Abgleich macht er nicht. Aber dass ein Benutzer seinen Text komplett mit anderen Zeichen füllt, ist eher unwahrscheinlich und wurde daher von mir ignoriert. Der eigentliche Grund für die Funktion findet man hier.

Noch als Verbesserungsvorschlag
array_count_values($words1)
array_count_values($words2)
Die Ergebnisse der zwei Funktionsaufrufe könnte man vor der Schleife noch zwischenspeichern so das sie nicht für jeden Schleifenaufruf erneut berechnet werden müssen, das täte der Performance auch noch gut.

Ja, du hast verdammt Recht. Hier ist die verbesserte Version, die noch einmal 5-10% schneller ist:

public static function stringCompare($str1, $str2): float {
    // Frühe Rückkehr für identische Strings
    if ($str1 === $str2) {
        return 0.0;
    }

    // Reinige die Strings
    $str1 = self::cleanString($str1);
    $str2 = self::cleanString($str2);

    // Prüfe auf leere Strings nach der Reinigung
    if ($str1 === '' && $str2 === '') {  
        return 0.0;
    }
    if ($str1 === '' || $str2 === '') {  
        return 100.0;
    }

    // Berechne Längenänderung
    $len1 = strlen($str1);
    $len2 = strlen($str2);
    $lengthChange = abs($len2 - $len1) / max($len1, $len2);

    // Berechne Wortübereinstimmung
    $words1 = str_word_count(mb_strtolower($str1), 1);
    $words2 = str_word_count(mb_strtolower($str2), 1);
    
    // Optimierung: Vorberechnung der Wort-Häufigkeiten
    $wordCount1 = array_count_values($words1);
    $wordCount2 = array_count_values($words2);
    
    $uniqueWords = array_unique(array_merge($words1, $words2));
    $matchingWords = 0;

    foreach ($uniqueWords as $word) {
        $count1 = $wordCount1[$word] ?? 0;
        $count2 = $wordCount2[$word] ?? 0;
        $matchingWords += min($count1, $count2);
    }

    $totalWords = max(count($words1), count($words2));
    $wordChange = 1 - ($matchingWords / $totalWords);

    // Kombiniere Längen- und Wortänderung
    $overallChange = ($lengthChange + $wordChange) / 2;

    return round($overallChange * 100, 2);
}

Gruß
Frank
Pjordorf
Pjordorf Sep 11, 2024 at 17:48:53 (UTC)
Goto Top
Zitat von @Frank:
verbesserte Version, die noch einmal 5-10% schneller ist:
Noch 30 Versuche dann ist die schneller als das Licht face-smile bzw. kommt die Antwort schon vor der Frage face-smileface-smileface-smile

Gruss,
Peter
Frank
Frank Sep 11, 2024, updated at Sep 13, 2024 at 12:42:24 (UTC)
Goto Top
@14260433693
Kommt darauf an wie man hier die "Menge an Änderung" definiert ..

Da in der Programmierung alles möglich ist, konnte ich das nicht einfach so stehen lassen. Hier ist eine verbesserte Version, die dein Szenario berücksichtigt und auch rudimentär auf den Inhalt eingeht (nein, sie ist nicht schneller, aber gleich schnell face-smile ):

$str1 = "Dies ist ein Beispieltext für den Vergleich.";  
$str2 = "xxxx xxx xxx xxxxxxxxxxxx xxx xxx xxxxxxxxxx";  
echo "Änderungsprozentsatz (mit gleicher Position, Zeichen durch x ersetzt) " . TextComparison::stringCompare($str1, $str2) . "%\n";  

Ergebnis:
Änderungsprozentsatz (mit gleicher Position, Zeichen durch x ersetzt) 93.59%

Hier der Code dazu:

 public static function stringCompare($str1, $str2): float {
        if ($str1 === $str2) return 0.0;

        $str1 = self::cleanString($str1);
        $str2 = self::cleanString($str2);

        if ($str1 === '' && $str2 === '') return 0.0;  
        if ($str1 === '' || $str2 === '') return 100.0;  

        $len1 = strlen($str1);
        $len2 = strlen($str2);

        // Längenänderung
        $lenChange = abs($len1 - $len2) / max($len1, $len2);

        // Verbesserte Erkennung von Textwiederholungen
        $repetitionFactor = 0;
        if (str_contains($str2, $str1) || str_contains($str1, $str2)) {
            $repetitions = max($len1, $len2) / min($len1, $len2);
            $repetitionFactor = 1 - (1 / $repetitions);
        }

        // Zeichenvergleich
        $chars1 = count_chars($str1, 1);
        $chars2 = count_chars($str2, 1);
        $charDiff = 0;
        foreach (array_keys($chars1 + $chars2) as $i) {
            $charDiff += abs(($chars1[$i] ?? 0) / $len1 - ($chars2[$i] ?? 0) / $len2);
        }
        $charChange = $charDiff / 2;  // Normalisierung

        // Wortvergleich
        $words1 = str_word_count(mb_strtolower($str1), 1);
        $words2 = str_word_count(mb_strtolower($str2), 1);
        $wordCount1 = array_count_values($words1);
        $wordCount2 = array_count_values($words2);
        $wordDiff = 0;
        $allWords = array_unique(array_merge(array_keys($wordCount1), array_keys($wordCount2)));
        
        $count1 = count($words1);
        $count2 = count($words2);

        if ($count1 > 0 || $count2 > 0) {
            foreach ($allWords as $word) {
                $freq1 = $count1 > 0 ? ($wordCount1[$word] ?? 0) / $count1 : 0;
                $freq2 = $count2 > 0 ? ($wordCount2[$word] ?? 0) / $count2 : 0;
                $wordDiff += abs($freq1 - $freq2);
            }
            $wordChange = $wordDiff / 2;  // Normalisierung
        } else {
            // Wenn keine Wörter erkannt wurden, verwenden wir nur den Zeichenvergleich
            $wordChange = $charChange;
        }

        // Gewichtete Gesamtänderung
        $overallChange = max(
            $lenChange,
            $repetitionFactor,
            ($charChange * 0.4 + $wordChange * 0.6)
        );

        return round(min($overallChange, 1.0) * 100, 2);
    }

Update: Es gab einen Fehler hinter $allWords (Zeile 40), wenn es nur ein Wort war (Division durch 0). Ich habe den Fehler behoben und den Code oben aktualisiert.

Hat Spaß gemacht face-smile

Gruß
Frank
Michi91
Michi91 Sep 12, 2024 at 13:31:00 (UTC)
Goto Top
Rein theoretisch könntest du nun deinen Code noch in C umschreiben und ein eigenes PHP-Modul kompilieren. Da ließen sich vermutlich nochmal ein paar Prozente rausholen.

Grüße