2
Ich habe einen Trie von Arten geschaffen, um alle Wörter (nicht Definitionen) im englischen Wörterbuch zu speichern. Der Sinn war es, dass ich alle Wörter, die nur Buchstaben enthalten, in einem bestimmten Bereich finden kann.Woher kommt der Größenunterschied?
Die Textdatei, die alle Wörter enthält, ist ungefähr 2.7 mb, aber nach dem Erstellen der Struktur und dem Schreiben in eine Datei mit Gurke ist die Datei> 33 mb.
Woher kommt dieser Größenunterschied? Ich dachte, ich würde Platz sparen, da ich nicht mehrere Kopien desselben Buchstabens für ein anderes Wort speichern müsste, zB für die Wörter app und apple würde ich nur 5 Knoten brauchen, für a -> p -> p -> l -> e .
Mein Code ist wie folgt:
import pickle
class WordTrieNode:
def __init__(self, nodeLetter='', parentNode=None, isWordEnding=False):
self.nodeLetter = nodeLetter
self.parentNode = parentNode
self.isWordEnding = isWordEnding
self.children = [None]*26 # One entry for each lowercase letter of the alphabet
def getWord(self):
if(self.parentNode is None):
return ''
return self.parentNode.getWord() + self.nodeLetter
def isEndOfWord(self):
return self.isWordEnding
def markEndOfWord():
self.isWordEnding = True
def insertWord(self, word):
if(len(word) == 0):
return
char = word[0]
idx = ord(char) - ord('a')
if(len(word) == 1):
if(self.children[idx] is None):
node = WordTrieNode(char, self, True)
self.children[idx] = node
else:
self.children[idx].markEndOfWord()
else:
if(self.children[idx] is None):
node = WordTrieNode(char, self, False)
self.children[idx] = node
self.children[idx].insertWord(word[1:])
else:
self.children[idx].insertWord(word[1:])
def getAllWords(self):
for node in self.children:
if node is not None:
if node.isEndOfWord():
print(node.getWord())
node.getAllWords()
def getAllWordsInRange(self, low='a', high='z'):
i = ord(low) - ord('a')
j = ord(high) - ord('a')
for node in self.children[i:j+1]:
if node is not None:
if node.isEndOfWord():
print(node.getWord())
node.getAllWordsInRange(low, high)
def main():
tree = WordTrieNode("", None, False)
with open('en.txt') as file:
for line in file:
tree.insertWord(line.strip('\n'))
with open("treeout", 'wb') as output:
pickle.dump(tree, output, pickle.HIGHEST_PROTOCOL)
#tree.getAllWordsInRange('a', 'l')
#tree.getAllWords()
if __name__ == "__main__":
main()
Die Größe eines Knotens ist _much_ größer als die Größe eines einzelnen Zeichens in einer Zeichenfolge. –
Wie kann ich das besser machen? Ich interessiere mich nicht unbedingt für den Raum, aber ich möchte ihn speichern, anstatt den Baum jedes Mal zu bauen. – p1g1n
Verwenden Sie ein Wörterbuch (die Python-Datenstruktur '{}', das nichts mit dem englischen Wörterbuch zu tun hat), indem Sie Buchstaben auf Knoten statt auf eine Liste abbilden. Es wird auch einfacher zu codieren sein: keine Notwendigkeit für 'ord' und so weiter. Wenn Sie nicht nur daran interessiert sind, es für sich selbst zu implementieren, dann googeln Sie "Python trie" und Sie werden Bibliotheken und solche finden, um zu sehen, wie andere es getan haben. –