Специальные динамические вложенные словари, реализация автовивификации

Question

Я пытаюсь реализовать вложенную структуру словаря определенным образом. Я читаю в длинном списке слов. Эти слова в конечном итоге нужно будет часто и эффективно искать, поэтому я хочу, чтобы мой словарь был настроен:

Я пытаюсь создать вложенную словарную структуру, в которой первое значение ключа - это длина слова, значение - это dict, ключ - первая буква слова, а значение - dict, ключ - вторая буква. слова и значение, являющееся диктатом с ключом в качестве третьей буквы слова и т. д.

так что если я читаю в "машине" "можно" и "джо"

я получил

{3: {c: {a: {r: car, n: can}}},j: {o: {e: joe}}}

Мне нужно сделать это примерно для 100000 слов, и они варьируются по длине от 2 до 27 букв.

Я просмотрел Каков наилучший способ реализации вложенных словарей? и динамические вложенные словари.

но не повезло выяснить это.

Я, конечно, могу получить мои слова из моего текстового файла, используя

for word in text_file.read().split()

и я могу взломать каждого персонажа, используя

for char in word

или же

for i in range(len(word)):
    word[i]

Я просто не могу понять, как разрушить эту структуру. Любая помощь будет принята с благодарностью.

Answer 1

Вот краткий пример того, как реализовать три с помощью автовивификации, построенной на defaultdict, Для каждого узла, заканчивающего слово, он хранит дополнительный ключ term чтобы указать это.

from collections import defaultdict

trie = lambda: defaultdict(trie)

def add_word(root, s):
    node = root
    for c in s:
        node = node[c]
    node['term'] = True

def list_words(root, length, prefix=''):
    if not length:
        if 'term' in root:
            yield prefix
        return

    for k, v in root.items(): 
        if k != 'term':
            yield from list_words(v, length - 1, prefix + k)

WORDS = ['cars', 'car', 'can', 'joe']
root = trie()
for word in WORDS:
    add_word(root, word)

print('Length {}'.format(3))
print('\n'.join(list_words(root, 3)))
print('Length {}'.format(4))
print('\n'.join(list_words(root, 4)))

Выход:

Length 3
joe
can
car
Length 4
cars

Answer 2

Не будучи уверенным, какова ваша цель этой структуры, вот решение, использующее рекурсию для создания структуры, которую вы описываете:

from collections import defaultdict
d = defaultdict(list)
words = ['hello', 'world', 'hi']


def nest(d, word):
    if word == "":
        return d
    d = {word[-1:]: word if d is None else d}
    return nest(d, word[:-1])


for word in words:
    l = len(word)
    d[l].append(nest(None, word))

print(d)

Answer 3

Вот способ сделать это без использования collections.defaultdict или создать свой собственный подкласс dict- итоговый словарь - обычный dict объект:

import pprint

def _build_dict(wholeword, chars, val, dic):
    if len(chars) == 1:
        dic[chars[0]] = wholeword
        return
    new_dict = dic.get(chars[0], {})
    dic[chars[0]] = new_dict
    _build_dict(wholeword, chars[1:], val, new_dict)

def build_dict(words):
    dic = {}
    for word in words:
        root = dic.setdefault(len(word), {})
        _build_dict(word, list(word), word[1:], root)
    return dic

words = ['a', 'ox', 'car', 'can', 'joe']
data_dict = build_dict(words)
pprint.pprint(data_dict)

Выход:

{1: {'a': 'a'},
 2: {'o': {'x': 'ox'}},
 3: {'c': {'a': {'n': 'can', 'r': 'car'}}, 'j': {'o': {'e': 'joe'}}}}

Он основан на рекурсивном алгоритме, проиллюстрированном в сообщении в потоке Python.org Archives, под названием Создание и преобразование многоуровневых словарей.