Anagramm-Generator

[ms4py]

So, noch jemand verbesserungsvorschläge ?

Du solltest das Dictionary auf jeden Fall nur einmal laden, ist ja das selbe für jedes Anagram...

[Xynon1]

Ja, habe ich schon erledigt, trotzdem danke.

Noch iwelche Ideen ?
Ich denke die Flaschenhälse hängen in der "text_for_anagram"-Funktion und der "combine_words"-Funktion bei den Kombinationen, fällt dort jemanden noch eine Optimierung ein.

Wenn ihr eine kleine Dokumentation dazu braucht, um zu verstehen was ich dort umsetzen wollte, müsst ihr es nur sagen.

[EyDu]

Hallo.

Raten wo der Flaschenhals ist bringt in den meisten Fällen nichts. Du solltest einfach messen, welcher Teil deines Codes wie lange braucht und dann optimieren.

Sebastian

[Xynon1]

Ich habe ja nicht direkt geraten, sondern dadurch das ich print anweisungen dazwischen gesetzt hatte, gesehen wo es länger dauert.
Aber ja ich kann nochmal genau nachmessen.

Dennoch sind ca. 80% oder mehr der Ausführungszeit bei den Kombinationen der einzelnen Wörter.
Dies geht ja auch schon aus dem Algorithmus heraus. Hat hier jemand noch eine Idee, wie man diese Kombination etwas besser handhaben kann ?

Edit: So habe es jetzt auch nochmal gemessen, bei "anagram("Ich sollte ein Anagram sein.", 2)" brauche ich für die ganze Funktion ca. 102 s.
Davon beträgt die "text_for_anagram" Funktion ca 5 s.
Fast der gesamte Rest geht an die "combine_words"-Funktion verloren mit ca. 97 s.

Edit2: Ich prüf jetzt nochmal extra auf die Länge, wie ich das zuvor schon gemacht hatte,
damit liegt die "combine_words"-Funktion nun bei 11s.
Trotzdem wäre ich noch an Verbesserungsvorschlägen interessiert.

So sieht es aktuell aus, ist jetzt auch schon etwas schneller

Code: Alles auswählen

from collections import defaultdict
import string
import itertools

SOURCE = "../dict/ngerman"
WORDS = defaultdict(list)

_dummy_table = string.maketrans("", "")
_delete_chars = string.punctuation + string.whitespace

def sort_word(word):
    return "".join(sorted(word.translate(_dummy_table, _delete_chars).lower()))

def text_for_anagram(anagram):   
    for word in WORDS:
        chars = list(word)
        for char in anagram:
            if char in chars:
                del chars[chars.index(char)]
                    
        if len(chars) == 0:
            yield word

def combine_words(anagram, combinations, max_words):
    #Edit
    length = len(anagram)
    #
    for combination in itertools.combinations(combinations, max_words):
        #Edit2
        word_combination = "".join(combination)
        if len(word_combination) != length:
            continue
        #
        if anagram == "".join(sorted("".join(word_combination))):
            words = itertools.product(*[x for x in (WORDS.get(word) for word in 
                                        combination)])
            for word in words:
                yield " ".join(word)
                
def anagram(anagram="Fr. Inge C. Sonst, Rheine", max_words=1):
    sorted_anagram = sort_word(anagram)
        
    if max_words > 1:
        combinations = list(text_for_anagram(anagram)) 
        cw = combine_words(sorted_anagram, combinations, max_words)
        result = "\n".join(cw)
    else:
        result = WORDS.get(sorted_anagram, "No anagram found.")
       
    return "{0}: {1}".format(anagram, result)
        

if __name__ == "__main__":
    with open(SOURCE) as lines:
        for line in lines:
            word = line.strip()
            WORDS[sort_word(word)].append(word)
                
    print(anagram("Antigone"))
    print(anagram("Fr. Inge C. Sonst, Rheine"))
    print(anagram("Ich sollte ein Anagram sein.", 2))

[ms4py]

Deine `text_for_anagram` Funktion ist mir noch unklar, was genau gibt die zurück?

IMO ist das das gleiche wie `WORDS[sort_word(anagram)]`

[Xynon1]

Nein, nicht ganz.

Ich will das Wort/Satzt/Buchstabensalat teilen und sehen, ob andere Wörter rein passen.
Die Funktion soll nun nichts weiter machen als zu prüfen welche Wörter alle in meinen Buschstabensalat passen.

zB. bei dem Wort "Autogramm" würde es mir etwas in der Art ausgeben:
["Auto", "Amor", "Armut", "Gramm", "Ort", ...]
Dann natürlich dann aber klein und sortiert.

Bei der ".get(...)" Methode würde ich nur Wörter bekommen, die exakt die selben Buchstaben haben wie das Anagram.
Hier bekomm ich halt alle die "reinpassen".

[EyDu]

Noch zu "text_for_anagram":

Code: Alles auswählen

def text_for_anagram(anagram):
    test = set(anagram).issuperset
    for word in WORDS:
        if test(set(word)):
            yield word

Elemente aus einer Liste zu löschen, über welche du gerade iterierst, ist übrigens keine gute Idee

[Xynon1]

Da musst du dich verguckt haben, oder ich.
Denn ich lösche aus "chars", iterieren tue ich aber über "WORDS" und "anagram".

Bei deiner Lösung sehe ich auch ein Problem, werden bei "set"s nicht alle doppelten/dreifachen/... Buchstaben entfernt ?
Denn wenn dem so ist, gibt es das Problem, das zB in das Wort "an", "anna" reinpassen würde.
Umgekehrt kein Problem, aber so wäre das ein Fehler.

[EyDu]

Da habe ganz offensichtlich nicht richtig gelesen. Als Kur verschreibe ich mir mal mehr schlaf

[derdon]

Ich finds cool, dass dieser Thread so eine starke Resonanz hervorgerufen hat. Mit so vielen Antworten habe ich gar nicht gerechnet, finde sie alle sehr interessant!

[Xynon1]

Keiner eine Idee, wie man das Kombinieren noch optimieren kann ?

Denn wenn man 3 Wörter sucht, dauert das eine Ewigkeit, bei 2 Wörtern ist das Tempo in Ordnung, aber 4 sind schon fast unmöglich.

[snafu]

Das Kombinieren läuft bei mir bestimmt 20 Sekunden. Möchte mal behaupten, in dieser Form ist es eigentlich unverwendbar. Zudem sollten IMHO nur grammatisch sinnvolle Kombinationen ausgespuckt werden. Ich poste zur Veranschaulichung mal die Ausgabe:

Code: Alles auswählen

urx@murx:~$ python test.py
Antigone: ['Negation']
Fr. Inge C. Sonst, Rheine: ['Schornsteinfegerin']
Ich sollte ein Anagram sein.: Maschinerien Analogteils
allegorischem Asiatinnen
Samoainseln nachteiliger
Eismaschinen Alligatoren
allergisches Animationen
Italieners angolanischem
Anachronismen allseitige

Was hier beispielsweise ginge, wären Kombinationen aus "allseitige" und einer der Pluralformen. Nur muss man dabei natürlich wieder darauf achten, dass es mit den übriggebliebenen Buchstaben auch noch passt. Und ich möchte nicht wissen, was das alles an zusätzlicher Rechenzeit kosten wird...

[Xynon1]

Bei mir sind es ziemlich genau 16 Sekunden.

Aber ja, das mit der "grammatisch sinnvolle Kombinationen", ist mir auch schon aufgefallen.
Es erinnert mich an ein lehrnfähiges Sprachprogramm welches ich vor ein paar Monaten ausprobiert habe.
Dafür wurde ein BOMP verwendet, welches ein Wörterbuch Text-Ausprache ist und eine weiteres Wörterbuch, welches zur Zuordnung des Wortes in einer Satztstrucktur genutzt wurde.
Dann konnte man eine Liste an Satzstruckturen bilden und diese dann aus den Wörtern die einem Satztstruckturelement bestücken.

Was ich damit sagen will ist, das man für eine solche Komplexität eigentlich "nur" noch ein Wörterbuch braucht, welches ein Übersetzung Wort zu Satztstruckturelement macht, dann könnte man die Wörter auch in eine solche Strucktur pressen.
Die ja dann imho etwas weniger Rechenzeit erordern, weil ja nicht mehr Wahllos kombiniert werden muss.

Problem nur, ich habe kein Wörterbuch Wort-zu-Satztstruckturelemen, dieses musste man in dem Sprachprogramm auch selbst definieren.
Und für alle Wörter in dem "ngerman"-Wörterbuch, halte ich leider etwas zu aufwendig.

Kennt jemand zufällig ein Dictionary für solche Zwecke ?