alle kombinationen von zeichen in einem string

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Samstag 8. November 2008, 19:07

DasIch hat geschrieben:Wie wäre es mit Kölner Phonetik oder Soundex?
ich glaube, wir reden aneinander vorbei. ich will keine aenlich klingenden woerter haben, sondern welche, die man aus einigen oder allen buchstaben des ursprungswortes bilden kann - egal in welcher reihenfolge die buchstaben verwendet werden.

lg
roschi
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!
BlackJack

Beitragvon BlackJack » Samstag 8. November 2008, 19:34

@roschi: Argh! Bist Du wahnsinnig!? Ums mal vorsichtig auszudrücken. ;-)

Da geht man besser den umgekehrten Weg und testet jedes Wort im Wörterbuch ob man es mit den vorhandenen Buchstaben bilden kann. Das durfte *deutlich* schneller sein als 81 GiB an Daten zu erzeugen von denen man im Vorfeld schon weiss, dass 99% davon nicht im Wörterbuch vorkommen werden.

Simpelste Methode zum finden von Anagrammen ist das sortieren der Buchstaben im Suchwort und allen Worten die untersucht werden. Wenn die dann gleich sind, hat man einen Treffer.

PS: Beispiel:

Code: Alles auswählen

In [301]: sorted('schaeuble')
Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']

In [302]: sorted('belausche')
Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']


Auf die Art kannst Du auch das komplette Wörterbuch mal vorverarbeiten und schauen welche Anagramme da enthalten sind.
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Samstag 8. November 2008, 20:40

@BlackJack:
es gibt eben doch noch leute, die mehr nachdenken als ich. :D
ich haette wohl gleich sagen sollen, was ich vorhabe.

vielen, vielen, lieben dank an alle, die versucht haben, mir zu helfen!

lg
roschi
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Sonntag 9. November 2008, 00:54

BlackJack hat geschrieben:

Code: Alles auswählen

In [301]: sorted('schaeuble')
Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']

In [302]: sorted('belausche')
Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']

Ich sehe, auch hier gibt es Leser von Fefes Blog :D
My god, it's full of CARs! | Leonidasvoice vs Modvoice
abgdf

Beitragvon abgdf » Sonntag 9. November 2008, 01:40

'belausche' ist ein Anagramm von 'schaeuble' ? Wie geil ist das denn :lol: ?

Es könnte sein, daß es schon genügt, nur die Anzahl der einzelnen Buchstaben zu vergleichen. "string.count()" ist da sehr hilfreich.

Gruß
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Sonntag 9. November 2008, 10:08

so, falls es nun jemanden interessieren sollte:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

import sys

def main(inputstring, dictfile="dict.txt"):
    fi = file(dictfile, "r")
    entries = fi.read().split()
    fi.close()

    inputstring = inputstring.lower()

    raw_chars = {}
    for char in inputstring:
        raw_chars[char] = inputstring.count(char)

    data = []
    for entrie in entries:
        entrie_show = entrie
        entrie = entrie.lower()
        chars_copy = {}
        for item in raw_chars:
            chars_copy[item] = raw_chars[item]
        is_okay = True
        for char in entrie:
            if char in chars_copy and chars_copy[char] > 0:
                chars_copy[char] -= 1
            else:
                is_okay = False
        if is_okay:
            data.append(entrie_show)

    fo = file("out.txt", "w")
    fo.write("\n".join(data + [""]))
    fo.close()

main(sys.argv[1])


das funktioniert einwandfrei und natuerlich bedeutend schneller ;-) ich hab ein 3,4 MB großes woerterbuch, werde mir aber bald ein deutlich groeßeres besorgen. naja, jedenfalls muss ich keine 81 GB daten erzeugen :)

ein riesengroßes dankeschoen nochmal !

lg
roschi
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!
BlackJack

Beitragvon BlackJack » Sonntag 9. November 2008, 11:04

Ist von der Laufzeit natürlich besser, aber immer noch fürchterlich kompliziert und verbrät immer noch eine Menge unnötiger Rechenzeit.

Die Berechnung von `raw_chars` hat quadratische Laufzeit, weil `count()` für jedes Zeichen jedes mal wieder `inputstring` von vorne bis hinten durchläuft.

Ein Dictionary kann man einfacher kopieren, in dem man das alte `dict()` als Argument gibt, also Zeile 20-22 wird zu ``chars_copy = dict(raw_chars)``.

Wenn `is_okay` auf `False` gesetzt wird, macht es keinen Sinn die Schleife noch weiter abzuarbeien. Wenn man den Test in eine Funktion auslagert, kann man sich `is_okay` komplett sparen und an der Stelle gleich ein ``return False`` schreiben.

Wobei ich mir nicht sicher bin, ob das Programm wirklich das macht, was es soll, weil auch Einträge in `data` kommen, die nicht alle Buchstaben des Eingabewortes verwenden. Ist das gewollt?

Man könnte ganz am Anfang auch noch eine Bedingung setzen, die die Längen überprüft. Wenn das Wort aus dem Wörterbuch länger als die Eingabe ist, kann man sich den restlichen Test sparen.

Ansonsten würde ich den Code so schreiben, dass das Wörterbuch nicht komplett auf einmal in den Speicher gelesen wird. Auch wenn ein paar Megabyte für heutige Rechner kein Problem mehr darstellen.

Die Funktion würde bei mir die Eingabe und ein "iterable" erhalten und selbst einen Iterator/Generator zurück geben. So ist sie am flexiblesten von der konkreten Ein- und Ausgabe getrennt.

PS: Kleines Beispiel wie ich einen Anagramm-Finder schreiben würde:

Code: Alles auswählen

import codecs
import sys

def normalize(word):
    return sorted(word.lower())

def iter_anagrams(word, words, normalize=normalize):
    key = normalize(word)
    return (w for w in words if len(key) == len(w) and normalize(w) == key)

def main():
    word_file = codecs.open('/usr/share/dict/ngerman', 'r', 'iso-8859-1')
    word = sys.argv[1].decode('utf-8')
    anagrams = iter_anagrams(word, (w.strip() for w in word_file))
    sys.stdout.writelines(a.encode('utf-8') + '\n' for a in anagrams)
    word_file.close()
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Freitag 14. November 2008, 21:06

hallo!

@BlackJack:
ja, es ist gewollt, das auch woerter gefunden werden, die nicht alle zeichen des inputstrings verwenden. vielen dank fuer die verbesserungsvorschlaege! es ist wirklich schneller - vor allem durch das pruefen der laenge am anfang. ich moechte ja nicht unbedingt anagramme finden, sondern, wie schon gesagt, auch woerter, die nicht alles aus dem inputstring nutzen.

ein riesengroßes dankeschoen und einen schoenen abend noch!

lg
roschi
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!

Wer ist online?

Mitglieder in diesem Forum: /me