[Dresden-pm] Wortgleichheit

[Helmut Wollmersdorfer]

Thomas Rittsche wrote:

> wir wollen Usereingaben auf Wortähnlichkeit, um bei falschen
> Schreibweisen trotzdem richtig reagieren zu können.

[...]

> Text::Levenshtein
> Text::LevenshteinXS
> Text::WagnerFischer
> Text::PhraseDistance

Eventuell auch interessant:
String::Approx
Algorithm::Diff
Text::Soundex

Zu Levenshtein:

Hab ich mal vor längerer Zeit runtergeladen, zum Laufen gebracht 
und in ein 'sub' verpackt.

Der originale Levenshtein-Algorithmus permutiert alle Kombinationen 
durch und gibt dann die Edit-Distance zurück.
Doppelt lange Strings brauchen viermal so lange. Das ist das Hauptproblem. 
Daran ändert die XS-Variante vermutlich auch nicht viel (nicht probiert).

Wagner-Fischer erweitert noch um Gewichte, was vermutlich noch etwas 
langsamer sein wird.

Üblicherweise genügt für obige Problemeatik eine Edit-Distance von 1 oder 2, 
wofür man den Algorithmus modifizieren kann, sodass bei Erreichen oder 
Überschreiten einer maximalen Distanz abgebrochen wird. 
Sowas (und noch andere schnelle Matching-Algorithmen) hat ein Herr Ukkonen entwickelt.
Die zurückgebene Edit-Distance stimmt dann für 0 .. $max_distance, 
darüber nicht unbedingt, ist aber grösser als $max_distance.
Ich hab das mal nach Perl portiert (Quelle des Pseudocodes vergessen):

sub ukkonen {
    my (
        $string1,
        $string2,
        $max_distance,
        ) = @_;

    if ($string1 eq $string2 ) {
        return (0); # edit distance = 0
    }

    my ($length1, $length2) = (length $string1, length $string2);
    my $length_difference = abs ($length1 - $length2);

    if ($length_difference > $max_distance) {
        return ($length_difference);
    }

    my $i = 0;
    my $j = 0;

    my $error_count = 0;

    TRY:
    while ( ($error_count <= $max_distance)
        and ($i < $length1)
        and ($j < $length2) ) {
        # The current characters match.
        #   Advance to next character in both strings.
        if ( substr($string1,$i,1) eq substr($string2,$j,1) ) {
            $i++;
            $j++;
            next TRY;
        }
        # The current character matches the next in the other string.
        #   Advance to next character in other string, error++.
        elsif ( (($j + 1) < $length2)
            and substr($string1,$i,1) eq substr($string2,$j + 1,1) ) {
                $error_count++;
                $j++;
                next TRY;
        }
        elsif ( (($i + 1) < $length1)
            and (substr($string1,$i+1,1) eq substr($string2,$j,1)) ) {
                $error_count++;
                $i++;
                next TRY;
        }
        # Else: Advance in both strings; error++.
        $error_count++;
        $i++;
        $j++;
        next TRY;
    }

    if ($error_count <= $max_distance) {
        if ($i < $length1) {
            $error_count = $error_count + ($length1 - ($i + 1));
        }
        if ($j < $length2) {
            $error_count = $error_count + ($length2 - ($i + 1));
        }
    }
    return ($error_count);
}

Dazu ein Benchmark auf meinem Athlon XP 2500:

use Benchmark qw(:all) ;

cmpthese(50000, {
    'lev1' => sub { levenshtein('meier','maier'); },
    'ukk1' => sub { ukkonen('meier','maier',2); },
    'lev2' => sub { levenshtein('wollmersdorfer','wollnerstorfer'); },
    'ukk2' => sub { ukkonen('wollmersdorfer','wollnerstorfer',2); },
});
        Rate   lev2   lev1   ukk2   ukk1
lev2   442/s     --   -86%   -99%  -100%
lev1  3069/s   595%     --   -93%   -97%
ukk2 45872/s 10280%  1394%     --   -50%
ukk1 90909/s 20471%  2862%    98%     --

Einen Eingabestring mit allen Elementen eines Array oder Hash zu vergleichen,
sollte also bei zehntausend Elementen noch vernünftige Antwortzeiten erlauben.

Die Menge kann man natürlich reduzieren, indem man den Eingabestring und die 
Schlüssel der Vergleichstabelle 'normalisiert', z.B. durch lc(), 
Entfernen der Punktation und der Umlaute:

my %mapping = (
        'grungasse' => [
            'Grüngasse',
            'Grun-Gasse',
        ]);

Soundex bringt auch gute Ergebnisse und eignet sich auf für sehr grosse Datenmengen,
wenn man einen Soundex-Index (auf Platte, Datenbank) anlegt.

Dann gibt es noch jede Menge Möglichkeiten, wie Suffix-Trees, Patricia-Trees, 
Bloom-Filter oder auf Matching optimierte Datenbanken, die je nach 
Einsatzcharakteristik mehr oder weniger gut passen.

Helmut Wollmersdorfer
-- 
Psssst! Schon vom neuen GMX MultiMessenger gehört?
Der kanns mit allen: http://www.gmx.net/de/go/multimessenger