Algorithmus für generieren vertippten Wörter

Sirakov

Mitglied
Algorithmus zum generieren vertippten Wörter

hallo zusammen,
ich suche Algorithmus, der vertippte Wörter generiert. Ich habe mir folgendes gedacht:
1. Zuerst die nebeneinanderstehenden Buchstaben tauschen
2. Je eine Buchstabe zu entfernen.

Bsp:
gegeben: Das Wort "abcd", dann kann ich folgende Wörter generieren:

bacd
acbd
abdc
abc
abd
bcd

Hat jemand 'ne Idee, was ich noch anwenden kann, um solche Wörter zu generieren? (z.B. bestimmte Buchstaben zu wiederholen oder entfernen).

Danke im voraus,
AA
 
Zuletzt bearbeitet:

teppi

Erfahrenes Mitglied
oh stimmt .. für diesen Fall wäre eine Lösung bspw.:

PHP:
// Definition der Möglichkeiten
String letters[4] = {"a","b","c","d"};

// Durchlaufen aller Kombinationen
for ( int i = 0; i < 4; i++)
{
    for ( int j = 0; j < 4; j++)
    {
        for ( int k = 0; k < 4; k++)
        {
            for ( int l = 0; l < 4; l++)
            {
                 System.out.println( letters[i] + letters[j] + letters[k] + letters [l] );
            }
        } 
    }
}

Es gibt sicher noch eine elegantere rekursive Möglichkeit .. Aber ich bin nicht so der Meister der Rekursion :)

btw: in diesem Beispiel sieht man auch gut, wieso man 4^4 Möglichkeiten erhält, da die Schleifen 4*4*4*4-mal durchlaufen werden .. ;)

Es gilt die Formel: Grösse der Zeichenkette ^ Anzahl der Möglichkeiten pro Zeichen

Gruß Stefan
 
Zuletzt bearbeitet:

Thomas Darimont

Erfahrenes Mitglied
Hallo!

Wie du alle Permutationen einer Elementfolge bestimmst siehst du hier:
http://www.tutorials.de/forum/showthread.php?threadid=75639&highlight=permutation

Ein Problem ist jedoch, dass du ja im Prinzip alle Permutation für alle Teilmengen der "enthaltenen" Menge haben willst:

Bsp:

Menge M = {'A','B','C','D'}

Davon hättest du nun gerne die Permutationen von (je):
"Eingangspermutationen"
{} -> Leere Menge...
{ABCD}
{ABC}
{ABD}
{ACD}
{BCD} ... BCD, BDC, DBC, DCB, CDB,CBD ...
{AB}
{AC}
{AD}
{BC}
{BD} ...BD, DB
{CD} ...CD,DC
{A}
{B}
{C}
{D}

Bsp. 2:
Warum Fehlt beispielsweise die Variante BCA -> Ist von ABC schon abgedeckt... usw.
ABC gilt dann als Eingabe für die nächste Permutationssuche und bildet u.A. auch die Variante BCA.

Das ist IMHO ein wenig tricky, man könnte in seinem etwaigen Generator für die jede "Eingangspermutationen" mittels toCharArray() und Arrays.sort(...) in einem HashSet ablegen ... so würde man für etwaige "Eingangspermutationen" wie etwa BCA schon erkennen, das dies eine Variante von ABC darstellt usw... nicht ganz einfach aber machbar.

Ich glaube mich zu erinnern, dass die Anzahl der Menge einer Potenzmenge = 2^n ist (n = Anzahl der Elemente der "Eingangsmenge" -> ABCD -> 2^4 = 16...

Genauergesagt:
M = {A,B,C,D}

|M| = 4

|P(M)| = 2 ^ (|M|)

|P(M)| = 16

Gruß Tom
 
Zuletzt bearbeitet:

torsch2711

Erfahrenes Mitglied
Hmm, allerdings wäre deine lösung teppi leider nicht ganz die lösung der frage. Es steht ja explizit drin, das er "vertippte" varianten sucht, sprich abcd darf nicht drin vorkommen, da dies ja in der richtigen reihenfolge ist wenn man 4 buchstaben als maximum nimmt bei a, b, c, d.

Theoretisch ist dies ein automaten problem sprich auf die theoretische informatik zurückzuführen, was Thomas ansatz nicht ausschliesst.

Das Problem ist hierbei wirklich ein semantisches, du müsstest dem Rechner beibringen was "korrekte" wörter sind. Sprich so eine art lexikon mitführen. oder ansatzweise dem rechner rechtschreibung beibringen, was schwierig sein dürfte, da rechstschreibkorrekturen sich auf solche lexikalischen lösungen stützen.

Gruss

Torsten


Edit: obwohl wenn ich gerade über Tom's erklärung drüber gehe auch nicht ganz mit dessen mengenversuchslösung übereinstimme. Du willst doch auch eine Semantik waren: sprich in diesem fall wäre BCA nicht dasselbe wie ABC obwohl die Wortmenge gleich ist.

Wie gesagt ich denke du kommst nicht um eine lexikalische lösung drumherum....
 
Zuletzt bearbeitet:

teppi

Erfahrenes Mitglied
Hm .. und was hat man dann davon ? Das man aus dem vertippten Wort das "richtige" Wort ableiten kann, so ala Google ? :)

Dafür gibts doch sicherlich schon fertige Datenbanken .. nehm ich jetzt einfach mal an .. :D ..
 

Sirakov

Mitglied
Also....hier geht es nicht um Potenzmengen. Ich will z.B. das Wort "Krieg" eingeben, dass Programm muss von "Krieg" Wörter generieren, die ähnlich sind. Dafür brauche ich Regel, z.B.

1. ich kann je eine Buchstabe des Wortes entfernen - dann bekomme ich die Wörter "rieg", "Kieg", "Kreg", "Krie", aber nich mehr als eine Buchstabe muss ich entfernen, sonst ist das neue Wort zu unterschiedlich vom "Krieg"
2. Ich kan benachbarte Buchstaben tauschen, dann bekomme ich folgende Wörter - "rKieg", "Kireg", "Kreig", "Krige".

So...jetzt suche ich aber weitere Regeln, die solchen Wörter erzeugen, z.B. von "Krieg" kann ich "Krieeg" erstellen, also ich kann so ein Regel definieren, was "i" zu "ie" umgewandelt. Aber mir fällt nicht mehr ein, was ich noch anwenden kann, damit ich noch mehr Wörter generieren kann. Die generierte Wörter müssen nur 1 Zeichen länger oder kürzer sein.

Hoffentlich habe ich diesmal eine bessere Erklärung gemacht :)

Gruß,
Atanas
 

teppi

Erfahrenes Mitglied
Oh, schon ein bissel alt .. aber naja viell. hilfts ja noch was ..

Naja im Prinzip ist es schon ein Problem der Potenzmengen, denke ich .. Nur das es bei dir nicht um das Verdrehen von Buchstaben, sondern um das Verdrehen der Anwendung bestimmter Regeln geht ..

Ich denke, um das Programmieren der Regeln von Hand, kommst du nicht herum ..
 

takidoso

Erfahrenes Mitglied
Verstehe ich den Sinn Deines Programms richtig, dass Du Wörter wieder erkennen willst, die von einem Anwender vermutlich gemeint aber falsch getippt wurden? Als so eine Art Rechtschreibkorrekturprogramm?
naja ein Typischer Fehler beim Tippen wäre da noch wenn man auf der Tastatur benachbarte Tasten verwechselt. z.B. V mit B oder E mit R (sowas tu ich ganz gerne mal.

Takidoso