Vertipper in DB suchen

MaxMara · 05.07.06, 10:13

Hallo!

Ich bin auf der Suche nach einem Weg wie man nach Schreibfehlern in einer DB (oder Text,...) suchen kann.
ein Beispiel:

Suchbegriff: Häuser
Ergebnis: Höuser, Häusre, Hüuer,....

Hat vielleicht jemand eine Idee wie man das umsetzen könnte?

Vielen Dank!

Grüße
Christian

***Dr Dau*** · 05.07.06, 22:19

Hallo!

Meiner Meinung nach dürfte es unmöglich sein.
Du müsstest eine Referenz festlegen (alternativ dynamisch generieren lassen), die alle nur erdenklichen Kombinationen durchläuft.
Was ist aber wenn z.b. äährseur (anstatt Häuser) im Text steht?
Genauso gut könnte äährseur aber ja z.b. auch für "Auto" im Text stehen.
Du weisst also nicht was für ein Wort im Text steht und auch nicht wofür es steht.
Demnach könnte also jede erdenkliche Kombination auf jedes erdenkliche Wort passen.
Du würdes also in einer unendlichen Suche landen.

Statt dessen solltest Du lieber darauf achten, ob irgend jemand sich nicht an die Rechtschreibung gehalten hat und es ggf. korrigieren.
Nicht ohne Grund gibt es hier im Forum den Punkt "Rechtschreibung" in der Netiquette.

Gruss Dr Dau

MaxMara · 06.07.06, 20:36

Danke für deine Antwort!
Ich hab mir schon gedacht, dass es nicht leicht wird.

Hab heute (in der Arbeit

) ein wenig ge

t und folgendes gefunden:
vertipp.de - Schnäppchen durch Tippfehler bei eBay finden!
Das ist genau das, was ich suche - nur wie machen die das?

Danke fürs Mitgrübeln

#Edit: Hab grad mitbekommen, dass diese Seite Geld durchs eBay-Klicken reinbringt. Soll keine Werbung für die Seite sein, sondern mir geht es lediglich um die Technik dahinter.

nikwithk · 06.07.06, 21:03

Ich denke dass die aus der orginalen Eingabe mögliche andere Buchstabenkombinationen generieren und hängen diese in den SearchString rein --> Beispiel Adidas

            
                    Code:
                  
                   	http://search.ebay.de/(didas,aidas,addas,adias,adids,adida,daidas,aiddas,addias,adiads,adidsa,sdidas,aadidas,asidas,afidas,addidas,addas,adisas,adifas,adiddas,adidss,adidaas,adidaa,adidad,adidass

***Matthias Reitinger*** · 06.07.06, 21:09

Hallo,

hier scheint es sich um einen recht simplen Algorithmus zu handeln. Zuerst wird jeweils ein Buchstabe weggelassen. Dann werden jeweils zwei aufeinander folgende Zeichen ausgetauscht (Buchstabendreher). Schlussendlich werden noch alle Möglichkeiten durchprobiert, die dadurch entstehen, dass man jeweils einen Buchstaben durch einen auf der Tastatur daneben liegenden austauscht.

edit: Ganz übersehen: auch versehentlich gedoppelte Buchstaben werden in die Vertipperliste aufgenommen.

Beispielimplementation:

            
            
              
                
                  
                    PHP-Code:
                  
                

                  
			
<?php

function vertipper($wort) {
    $len = strlen($wort);
    $liste = array();

    // 1. Weggelassene oder doppelte Buchstaben
    for ($i = 0; $i < $len; ++$i) {
        $liste[] = substr($wort, 0, $i) .
            substr($wort, $i+1);
        $liste[] = substr($wort, 0, $i+1) .
            substr($wort, $i);
    }

    // 2. Buchstabendreher
    for ($i = 0; $i < $len-1; ++$i) {
        $liste[] = substr($wort, 0, $i) .
            $wort{$i+1} . $wort{$i} .
            substr($wort, $i+2);
    }

    // 3. Auf der Tastatur nahe liegende Buchstaben
    $tastaturzeilen = array(
        '1234567890ß',
        'qwertzuiopü',
        'asdfghjklöä',
        'yxcvbnm',
    );

    for ($i = 0; $i < $len; ++$i) {
        $buchst = $wort{$i};
        $daneben = array();
        foreach ($tastaturzeilen as $zeile) {
            if (($pos = strpos($zeile, $buchst)) !== false) {
                if ($pos-1 >= 0) {
                    $daneben[] = $zeile{$pos-1};
                }
                if ($pos+1 < strlen($zeile)) {
                    $daneben[] = $zeile{$pos+1};
                }
            }
        }
        foreach ($daneben as $ersatz) {
            $vertipper = $wort;
            $vertipper{$i} = $ersatz;
            $liste[] = $vertipper;
        }
    }

    return array_values(array_unique($liste));
}

print_r(vertipper('tutorials'));

?>


		

                

              
            
          

Grüße,
Matthias

***Dr Dau*** · 06.07.06, 21:10

Habe ich nicht ausprobiert..... die sollen ja kein Geld durch uns einnehmen.

Ich vermute allerdings dass sie lediglich die "typischen" Vertipper in einer Datenbank hinterlegt haben.
Denkbar währe z.b. "Heuser" für "Häuser"..... oder Buchstabenverdreher wie z.b. "Häusre".
Mein Beispiel "äährseur" wird also wohl kaum gefunden werden wenn ich nach "Häuser" suche.

Ähnlich macht es Google ja auch..... nur halt umgekehrt.
Wenn ich nach "Häusre" suche, fragt mich Google "Meinten Sie: Häuser".

[edit]
@Matthias, das währe natürlich auch eine Möglichkeit..... ich würde es mal als "logischen Fehler" bezeichen, also z.b. die von Dir angesprochenen Nachbartasten oder fehlende Buchstaben.
Solche Dinge passieren ja recht schnell mal.
[/edit]

Christian Fein · 06.07.06, 21:39

Mann macht ihr das alle kompliziert

MySQL 4.0 Referenzhandbuch :: 7.3.2 Zeichenketten-Funktionen

Zitat:

SOUNDEX(zeichenkette)

Gibt eine Soundex-Zeichenkette von zeichenkette zurück. Zwei Zeichenketten, die fast gleich klingen, sollten identische Soundex-Zeichenketten haben. Eine Standard-Soundex-Zeichenkette ist 4 Zeichen lang, aber die SOUNDEX()-Funktion gibt eine beliebig lange Zeichenkette zurück. Sie können SUBSTRING() auf das Ergebnis anwenden, um eine Standard-Soundex-Zeichenkette zu erhalten. Alle nicht alphanumerischen Zeichen in der angegebenen Zeichenkette werden ignoriert. Alle internationalen alphabetischen Zeichen ausserhalb des Wertebereichs A bis Z werden als Vokale behandelt:

Sprich "select name from bloedetabelle where SOUNDEX(name) = SOUNDEX("Heuser")

SELECT *
FROM meine_tabelle
WHERE soundex( username ) = soundex( "Christian Vein" )

findet Christian Fein

MaxMara · 06.07.06, 21:47

Zitat:

Zitat von Matthias Reitinger

Hallo,

hier scheint es sich um einen recht simplen Algorithmus zu handeln. Zuerst wird jeweils ein Buchstabe weggelassen. Dann werden jeweils zwei aufeinander folgende Zeichen ausgetauscht (Buchstabendreher). Schlussendlich werden noch alle Möglichkeiten durchprobiert, die dadurch entstehen, dass man jeweils einen Buchstaben durch einen auf der Tastatur daneben liegenden austauscht.

edit: Ganz übersehen: auch versehentlich gedoppelte Buchstaben werden in die Vertipperliste aufgenommen.
[...]

Danke Matthias, genau das hab ich gesucht.

Zitat:

Zitat von Christian Fein

Sprich "select name from bloedetabelle where SOUNDEX(name) = SOUNDEX("Heuser")

Funktioniert auch gut für mein Problem, aber mir gefallen die Vertipper besser, die man "reproduzieren" kann

***Matthias Reitinger*** · 06.07.06, 22:39

Hallo,

Zitat:

Zitat von Christian Fein

Mann macht ihr das alle kompliziert

SOUNDEX() versagt nur leider, wenn es um Vertipper geht, die phonetisch unähnliche Wörter erzeugen.

Lustiges Detail am Rande: SOUNDEX('spears') == SOUNDEX('superzicke')

Grüße,
Matthias

***Dr Dau*** · 07.07.06, 00:19

@Matthias, perfekt ist Dein Script aber dann doch nicht.
Was ist wenn man einen Buchstaben zu weit oben oder unten getippt hat?
Also beim beim z.b. "t" könnte man ja z.b. auch das "g" oder evtl. das "f" getroffen haben.

***Matthias Reitinger*** · 07.07.06, 00:31

Hallo,

Zitat:

Zitat von Dr Dau

@Matthias, perfekt ist Dein Script aber dann doch nicht.

Hab ich auch nie behauptet

Ich hab mit meinem Skript nur die Funktionalität der verlinkten Seite imitiert, nicht mehr und nicht weniger.

Schon allein die Tatsache, dass bei einem längeren Wort durchaus auch mal zwei Vertipper passieren können, bringt diese Implementierung in's straucheln.

Grüße,
Matthias

***Dr Dau*** · 07.07.06, 01:11

@Matthias, ich wollte ja nur drauf aufmerksam machen..... ich weiss ja schliesslich nicht wie weit Du das Script getestet hast.