Уменьшение размера Trie всех английских слов

Question

Я реализую функцию автозаполнения, используя Trie. Используя список слов в этой ссылке, я вставляю каждое слово в свой Trie. Я хочу уменьшить объем памяти, используемой Trie, не используя что-то слишком причудливое, например, ориентированный ациклический граф слов.

Trie основан на словаре, что позволяет хранить его в файле JSON. Это мой текущий сценарий:

import json 

#Make a trie of english words
# The words file can be found at https://github.com/dwyl/english-words
with open('words_dictionary.json', 'r') as file:
    words = json.load(file)

_end = '_end_'
trie = {}

def make_trie(words):
    root = trie 
    for word in words:
        current = root
        for char in word:
            if char not in current:
                current[char] = {}
            current = current[char]
        current[_end] = _end 

make_trie(words)

with open('word_trie.json', 'w') as outfile:
    json.dump(trie, outfile)

Если это можно сделать, пожалуйста, помогите мне с фрагментами кода.

Answer 1

Если ваш файл статичен, то есть вам не нужно время от времени вставлять в него слова, но вы можете создавать его «все сразу», тогда вам нужна структура DAFSA , что означает «Направленный ациклический конечный государственный автомат». В случае, если ваша задача динамична, то есть вам нужно будет вставить в нее новые слова, DAFSA по-прежнему ответит, но алгоритмы намного сложнее.

Это в основном сжатая версия дерева, она имеет такую ​​же скорость доступа, но в общем случае требует гораздо меньше места.

Алгоритмы преобразования дерева в DAFSA (иногда называемые DAWG для направленного ациклического графа слов) не так просты, как алгоритмы, которые просто строят дерево, но они понятны. Вы должны найти все, что вам нужно здесь .