Speicher Effiziente Datenstruktur für Trie Implementierung

Question

Ich implementiere eine Trie in Python. Bis jetzt über zwei ich verschiedene Methoden gekommen, um sie umzusetzen:

1. eine Klasse Knoten verwenden (ähnlich Knoten in C++ struct) mit Datenelementen -

char - zum Speichern von Zeichen

is_end - Ende des Wortes zu speichern (wahr oder falsch)

prefix_count - Öffnungs Anzahl der Worte mit dem aktuellen Präfix

Kind - Knotentyp dict (zum Speichern der anderen Knoten das heißt für 26 Alphabete)

class Node(object): 
    def __init__(self): 
     self.char = '' 
     self.word = '' 
     self.is_end = False 
     self.prefix_count = 0 
     self.child = {} 

2. ein Wörterbuch mit allen Daten zu speichern.

words = {'foo', 'bar', 'baz', 'barz'}

 {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
     'z': {'_end_': '_end_'}}}, 
     'f': {'o': {'o': {'_end_': '_end_'}}}} 

, die eine effiziente und Standard-Datenstruktur ist, die für Traversal und andere Trie-Operationen auf großen Datenmenge von Wörtern beide Speicher effizient und schnell ist?

Answer 1

Warum nicht beides? Gerade gestern habe ich eine ähnliche Datenstruktur zum Speichern und Abrufen einer Hierarchie von Objekten implementiert und diese genaue Situation in Betracht gezogen. Beendet mithilfe eines Node-Objekts mit einem Child-Dictionary. Der Hauptknoten ist ein Objekt können Sie benutzerdefinierte Methoden haben, um ihn zu drucken oder Sachen bekommen, und Sie können sogar eine verzögerte Initialisierung, wenn erforderlich (Sie große Datenmenge direkt erwähnt?)

class Node(object): 
    def __init__(self): 
     self.children = collections.defaultdict(lambda:self.__class__()) 
     self.stuff = ... 
    def __str__(self,depth=0): 
     if self.children: 
      return str(self.stuff)+'\n'+'\n'.join([' '*depth+k+' ' + v.__str__(depth+1) for k,v in self.children.items()]) 
     else: 
      return str(self.stuff) 
    def get_path(self,path): 
     node = self 
     while path: 
      node = node.children[path.pop(0)] 
     ... 

Answer 2

Ein direkter Ersatz wäre verschachtelte eine list;

Allerdings [mehr] Pythonic, kompakter im Speicher und damit schneller für die Suche wäre eine verschachtelte tuple.

Natürlich wird die Aktualisierung eines solchen Trie logN, da Sie jeden Vorgängerknoten neu erstellen müssen. Dennoch, wenn Ihre Lookups viel häufiger als Updates sind, kann es sich lohnen.

Answer 3

Trie ist ein Fehler, wenn es um Platzkomplexität geht. Trie neigt dazu, viel Speicher für die Verarbeitung und den Betrieb zu verwenden. Aber um dieses Problem zu vermeiden, gibt es eine Datenstruktur, die als prägnante Datenstruktur bekannt ist. Versuche das hier umzusetzen.

Weitere Informationen finden Sie unter here.