in Dictionary bestimmtes Wort enthalten

[pitty]

Hallo,

ich habe eine Frage bezüglich Dictionaries:
Ich habe ein Dictionary wo verschiedene Keys gespeichert sind. Jetzt möchte ich gerne überprüfen, ob Keys in dem Dictionary sind und auf diese zugreifen, falls sie ein bestimmtes Wort enthalten. Zum Beispiel möchte ich wenn ich das Wort "Hose" habe, dass der Key "Hosenbein" gefunden und ausgeben wird. Das selbe z.B. für "Handy" und "Handytasche".
Ich habe keine Idee, wie ich das anstellen soll. Hat dazu jemand eine Idee?
Vielen Dank für die Hilfe

MfG

[webspider]

Code: Alles auswählen

>>> dictionary = {'a': 1, 'b': 2, 'c': 3}
>>> 'a' in dictionary
True
>>> dictionary['a']
1

Aber Moment. Du suchst wohl nach dictionary.keys() und willst durch jeden Key gehen um die gefundenen zu verwenden, richtig?

[BlackJack]

Code: Alles auswählen

    for key in dictionary.iterkeys():
        if 'Hose' in key:
            print key

[pitty]

Vielen Dank für eure schnellen Antworten,

der Code von BlackJack ist in etwa das was ich suche. Allerdings soll er in dem Dictionary verschiedene keys gleichzeitig finden. Also z.B. sowohl "Hosenbein" als auch "Handytasche". Je nachdem, welchen key man gerade über die for-schleife bekommen hat, soll es dann im Dictionary überprüfen, ob das Wort nochmal in einem anderen Wort vorkommt.
Habe jetzt mit deinem Beispiel mal das ausprobiert:

Code: Alles auswählen

dictionary = {'a': 1, 'b': 2, 'c': 3, 'ab':4}
for key in dictionary.iterkeys():
        if key in dictionary.keys():
            print key

Das macht aber keinen Sinn, weil dann viel zu viel ausgegeben wird. Nämlich in dem Beispiel "a,c,b,ab" Das ist aber viel zu viel, da ich lediglich von "a" auf "ab" schließen möchte.
Ich hoffe ihr versteht, was mein Problem ist.

[Sirius3]

@pitty: Wenn Du Deine und BlackJacks Zeilen anschaust, fallen Dir bestimmt zwei Unterschiede auf, die den Unterschied zwischen gewünschtem und nicht-gewünschtem Ergebnis ausmachen.

[pitty]

@Sirius3
Klar fällt mir auf was ich anders gemacht habe, aber so wie BlackJack das gemacht hat, funktioniert es ja nur für das Wort "Hose" und ich möchte es halt für verschiedene Wörter in dem Dictionary jeweils machen und habe mir deswegen überlegt das ich das aktuelle Wort(Variable key) dann auf ein vorkommen in einem anderen Wort durch dictionary.keys() suche, was aber ja nicht klappt. Ich habe aber keine Idee, wie ich das gewünschte anstellen kann, ohne eine verschachtelte for-Schleife zu benutzen, die aber zu lange dauert, weil sie dann zweimal über das komplette Dictionary iteriert und das je nach Dictionary-Größe zu lange dauern wird.

[BlackJack]

@pitty: Du prüfst zum einen nicht das richtige, also im Code nicht das was Du im Beitrag formuliert hast. Und zum anderen: Wenn Du für zwei (Teil)Begriffe nicht das Dictionary zweimal durchlaufen möchtest, dann musst Du das einmal durchlaufen und für jeden Schlüssel die beiden Teilbegriffe testen. Das ändert an der Gesamtzahl der Tests (fast) nichts, aber das ist nun mal die Natur von dem was Du wissen willst.

[Dingels]

Schau dir mal die Funktion `itertools.combinations` an. Ein Beispiel:

Code: Alles auswählen

>>> from itertools import combinations

>>> def search_for_substrings(wordlist):
...    for word1, word2 in combinations(wordlist, 2):
...        if word1 in word2:
...            print '"{}" steckt in "{}"'.format(word1, word2)
...        elif word2 in word1:
...            print '"{}" steckt in "{}"'.format(word2, word1)

>>> search_for_substrings([u'Hose', u'Hosen', u'Hosenträger', u'Hosenbund', u'Handytasche', u'Handy', u'Handydisplay'])

Dann erhältst Du:

"Hose" steckt in "Hosen"
"Hose" steckt in "Hosenträger"
"Hose" steckt in "Hosenbund"
"Hosen" steckt in "Hosenträger"
"Hosen" steckt in "Hosenbund"
"Handy" steckt in "Handytasche"
"Handy" steckt in "Handydisplay"

Alternativ kann man auch die Funktion `itertools.permutations` verwenden, die automatisch über alle Rückrichtungen iteriert und nach meinen Tests tatsächlich genau so schnell arbeitet wie `itertools.combinations`. Dann benötigt man nur eine if-Abfrage.

Code: Alles auswählen

>>> from itertools import permutations

>>> def search_for_substrings(wordlist):
...    for word1, word2 in permutations(wordlist, 2):
...        if word1 in word2:
...            print '"{}" steckt in "{}"'.format(word1, word2)

[BlackJack]

@Dingels: Das hat ja ein noch „schlechteres” Laufzeitverhalten, setzt aber auch etwas um was gar nicht gefragt ist. Jedenfalls so wie ich die Fragestellung verstanden habe.

[Dingels]

@Dingels: Das hat ja ein noch „schlechteres” Laufzeitverhalten, setzt aber auch etwas um was gar nicht gefragt ist. Jedenfalls so wie ich die Fragestellung verstanden habe.

Ja, die Laufzeit kann bei großem Input natürlich lang werden, das ist wahr. Es geht doch hier einfach nur um das Finden von Substrings, oder nicht? Oder hab ich was nicht mitbekommen? :K

[BlackJack]

@Dingels: Soweit ich das verstanden habe gibt es eine Wortliste und eine vorgegebene Anzahl von Suchbegriffen die nicht der ganzen Wortliste entsprechen. Der OP spricht von zwei Eingaben, du aber nur von einer, nämlich der Wortliste selbst. Soweit ich das verstanden habe sieht die API für die Suchfunktion so aus:

Code: Alles auswählen

def search_many(needles, haystack):
    # ...

Und für `needles` wird ``['Hose', 'Handy']`` übergeben, wobei die Begriffe selbst auch nicht zwangsläufig in `haystack` vorkommen müssen.

Das Du beide Richtungen prüfst ist übrigens überflüssig, denn die jeweiligen Rückrichtung ergibt sich ja dadurch, dass die Kombinationen auch den anderen Fall enthalten.

[Dingels]

Das Du beide Richtungen prüfst ist übrigens überflüssig, denn die jeweiligen Rückrichtung ergibt sich ja dadurch, dass die Kombinationen auch den anderen Fall enthalten.

Du verwechselst `combinations` mit `permutations`. Letztere Funktion erzeugt auch sämtliche Rückrichtungen, erstere nicht, daher meine beiden if-Abfragen. Man kann natürlich auch `permutations` verwenden, aber dann erhöht sich die Anzahl der Iterationen beträchtlich, was eine noch schlechtere Laufzeit zur Folge hat. Eine weitere if-Abfrage stattdessen sollte eigentlich performanter sein.

[BlackJack]

@Dingels: Ups, stimmt.

Hier mein Verständnis von der Problemstellung als Einzeiler:

Code: Alles auswählen

def search_many(needles, haystack):
    return (item for item in haystack if any(n in item for n in needles))

[pitty]

Vielen Dank für die ganzen Antworten =)

Prinzipiell ist das was Dingels gemacht hat in etwa so wie ich es haben möchte. Ich habe keine vorgegebene Anzahl von Suchbegriffen die ich übergebe, sondern möchte aus dem Dictionary die einzelnen Wörter vergleichen, ob sie nochmal in einem anderen Wort in dem Dictionary auftauschen.
Wie BlackJack gesagt hat dauert der Code von Dingels so aber wirklich sehr lange. Habe es gerade mal ausprobiert.
Gibt es da vielleicht eine schnellere Lösung für?

[BlackJack]

@pitty: Jain. Es gibt theoretisch schnellere Lösungen, allerdings auf Kosten von Komplexität der Algorithmen und zusätzlichem Speicherverbrauch. Dabei entsteht erst einmal zusätzlicher Aufwand um eine geeignete Datenstruktur aufzubauen. Das lohnt sich also erst ab einer bestimmten Datenmenge, ab der die komplexere Lösung schneller wird als die ”Naive”. Diesen Punkt schiebt Python als dynamische Sprache gegenüber einer statisch typisierten noch ein wenig hinaus. Man sollte sich also IMHO gut überlegen ob die einfache, funktionierende Lösung nicht doch schnell genug ist, bevor man Zeit in etwas Komplexes investiert und das am Ende vielleicht noch nach C portiert um Geschwindigkeit zu gewinnen und Speicher zu sparen. Falls es was Komplexers werden soll, dann würde ich wohl in Richtung Suffix-Bäume recherchieren.

Das Du ein Wörterbuch hast, hat mit dem ganzen Problem hier ja übrigens überhaupt nichts zu tun. Eigentlich geht es um eine Sequenz von Wörtern.

Mir ist auch noch nicht klar welches Ergebnis die Suchfunktion denn nun genau liefern soll!? Wie sollte das Ergebnis hier aussehen:

Code: Alles auswählen

def search_substrings(words):
    # ...
    return result

Von was für erwarteten Daten reden wir? Wieviele Worte? Wie lang im Schnitt? Welche Abweichung bei der Länge? Wie sieht die Treffer/Substring-Verteilung aus?

Edit: Welches Problem soll da überhaupt gelöst werden, also was sind das für Daten und warum brauchst Du die Substrings? Nicht das wir hier an etwas basteln für das es schon eine fertige Lösung gibt.

[pitty]

@BlackJack
Ich suche im Endeffekt alle Wörter die aus 2 oder mehrern Wörtern zusammengesetzt sind. Die Abweichung der Länge und Länge im Allgemeinen kann ich nicht einschätzen, weil der Quellcode auf x-beliebige Dictionarys funktionieren soll, wo immer unterschiedliche und unterschiedlich viele Wörter drin vorkommen.

[BlackJack]

@pitty: Dann müsstest Du den bisherigen, einfachen Algorithmus mit quadratischer Laufzeit einfach mal auf die grösste zu erwartende Wortmenge loslassen und dann entscheiden ob das von der Laufzeit her noch akzeptabel ist. Am besten als Funktion separiert, die man mit anderen Implementierungen austauschen kann. Zum einen weil man dann etwas Komplexeres versuchen kann, und zum anderen weil man dann eine Referenz hat, mit der man andere Algorithmen testen kann.

Und wie gesagt, suchst Du keinen Algorithmus für Wörterbücher. Das die Wörter aus so einer Datenstruktur kommen, ist ja für die Suche die Du brauchst unerheblich. Einzig das es keine Doubletten in der Eingabe für die Suche geben kann, wird vom Wörterbuch garantiert, aber das kann man bei der Funktion auch einfach als Vorbedingung angeben.

Wie sieht denn nun das Ergebnis aus was die Funktion ausspucken soll?

[BlackJack]

@pitty: Ich habe das mal mit der ``/usr/share/dict/ngerman``-Wortliste auf meinem Laptop ausprobiert und die naive Variante nach einer halben Stunde abgebrochen. Dafür eignet sie sich also nicht. In Kleinbuchstaben umgewandelt und von Doubletten befreit sind das 332.258 Wörter. Also habe ich's mal mit einem Suffix-Baum probiert. Der verbraucht zwar ordentlich zusätzlichen Speicher, aber das Programm lief in cirka 50 Sekunden durch.

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
import json

WORDS_FILENAME = '/usr/share/dict/ngerman'


def load_words(filename):
    with open(filename) as lines:
        return sorted(set(s.strip().lower() for s in lines))


def iter_suffixes(word):
    for i in xrange(len(word)):
        yield word[i:]


class Node(object):
    def __init__(self):
        self.children = dict()
        self.words = list()

    def __getitem__(self, character):
        return self.children[character]

    def __setitem__(self, character, child_node):
        self.children[character] = child_node

    def get(self, character):
        try:
            return self[character]
        except KeyError:
            result = Node()
            self[character] = result
            return result

        
class SuffixTree(object):
    def __init__(self, end_symbol='\0'):
        self.end_symbol = end_symbol
        self.root = Node()

    def __getitem__(self, word):
        if self.end_symbol in word:
            raise ValueError('word must not contain the end symbol')
        node = self.root
        for character in word:
            node = node[character]
        return node[self.end_symbol].words

    def _add_suffix(self, word, suffix):
        node = self.root
        for character in suffix:
            node = node.get(character)
        node.words.append(word)

    def add(self, word):
        if self.end_symbol in word:
            raise ValueError('word must not contain the end end symbol')
        for suffix in iter_suffixes(word + self.end_symbol):
            self._add_suffix(word, suffix)


def iter_search_substrings(words):
    tree = SuffixTree()
    for word in words:
        tree.add(word)
    for word in words:
        contained_in = [w for w in tree[word] if w != word]
        if contained_in:
            yield (word, contained_in)


def save_result(mapping, filename):
    for value in mapping.itervalues():
        value.sort()
    with open(filename, 'w') as result_file:
        json.dump(mapping, result_file)


def main():
    words = load_words(WORDS_FILENAME)
    print len(words)
    result = dict(iter_search_substrings(words))
    print len(result)
    save_result(result, 'test.json')


if __name__ == '__main__':
    main()

[pitty]

@BlackJack Vielen Dank für deine riesige Hilfe =) werde mir das mal anschauen und versuchen zu verstehen =)
Nochmal danke für die Hilfe =)

[Dingels]

@BlackJack: Hast Du diesen Suffix-Baum selbst implementiert oder woher hast Du den?