in Dictionary bestimmtes Wort enthalten

[BlackJack]

@Dingels: Noch mal kurz über die Definition geschaut und dann selbst implementiert. So kompliziert ist der letztendlich ja auch gar nicht. Zumindest die Knoten sind auch verbesserungswürdig, denn Blätter haben in dem Baum keine Kinder und innere Knoten keine Daten, also hätte man das in zwei Klassen mit jeweils nur den passenden Daten aufteilen können. Aber es funktionierte und hat weder Zeit noch den Laptopspeicher gesprengt, also habe ich es so gelassen.

[xeike]

Ist es so etwas hier?

Code: Alles auswählen

>>> d = {'Hose' : 1, 'Hosenbein' : 2, 'Handy' : 3 }
>>> l = [v for v in d.keys() if v.find('Hose') >= 0 ]
>>> for elem in l:
...   print(elem, d[elem])
... 
Hosenbein 2
Hose 1
>>> 

Xe

[BlackJack]

@xeike: Statt ``v.find('Hose') >= 0`` würde man besser den ``in``-Operator verwenden: ``'Hose' in v``. Das ist kürzer, weniger Code, und auch etwas verständlicher.

'Hose' ist aber nicht fest, sondern das was Du mit `Hose` gemacht hast, soll mit allen Schlüsseln gemacht werden. Und da ist so ein simpler Ansatz nicht effizient genug wenn die Wortmengen steigen. Wie gesagt, habe ich meinen Versuch mit cirka 300K Worten nach einer halben Stunde ergebnislos abgebrochen. Ist ja auch kein Wunder weil das ungefähr 90 Milliarden ``in``-Operationen sind, die da durchgeführt werden müssten. Wenn eine Operation nur 1µs dauern würde, dann währen das immer noch 25 Stunden Laufzeit.

[xeike]

@BlackJack: Danke.

Ist das hier besser:

Code: Alles auswählen

#!/usr/bin/env python3
import time
import datetime

def woerterbuch_laden():
  with open('/usr/share/dict/ngerman') as wbuch:
    return sorted(set(wort.strip().lower() for wort in wbuch))

if __name__ == '__main__' :
  start = datetime.datetime.now() 
  
  wortliste = woerterbuch_laden()
  
  while(len(wortliste)): 
    print(len(wortliste))
    suchwort = wortliste.pop();
    zusammengesetzt = [wort for wort in wortliste if suchwort in wort]
    if len(zusammengesetzt):
      print("Etwas gefunden: ", suchwort, " ist in ", len(zusammengesetzt), " anderen Worten enthalten")

  ende = datetime.datetime.now()
  print("Ende...", start, ende, ende - start )

Ich reduziere die Menge bei jedem Durchlauf, da "Hose" vor "Hosenbein" sortiert wird. Allerdings werden so mögliche Treffer wie "Handyvertrag" und "Vertrag" nicht gefunden, weil "Handyvertrag" zuvor aus der Liste genommen wird. Zu den Beispielen im ersten Posting passt aber eh "str.startswith()" besser. Das würde die Ausführungszeit auch nochmal etwas reduzieren. Mit diesem Programm hier bin ich in unter 1 Stunde durch.

Xe

[BlackJack]

@xeike: Es macht keinen Sinn Algorithmen nach Zeit zu vergleichen die nicht das gleiche Ergebnis liefern. Was Dein Algorithmus nicht findet hast Du ja selbst schon angemerkt. Das liefert also nicht nur ein anderes, weniger umfangreiches Ergebnis, sondern läuft trotzdem immer noch *deutlich* länger als der Suffix-Baum.

[BlackJack]

Ich habe den Suffixbaum noch einmal überarbeitet. Er verwendet jetzt kein Endsymbol mehr — das ist nun Implizit wenn ein Knoten Daten im `words`-Attribut hat. Dadurch werden weniger Knoten erzeugt und das Programm läuft bei mir 10 Sekunden weniger, also in knapp 40 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):
        self.root = Node()

    def __getitem__(self, word):
        node = self.root
        for character in word:
            node = node[character]
        return node.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):
        for suffix in iter_suffixes(word):
            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()