Specific Dynamic Nested Dictionaries, Autovivification Implementation

I'm trying to implement a nested dictionary structure in a specific manner. I'm reading in a long list of words. These words are eventually going to need to be searched through of

Solution 1:

Here's a short example on how to implement trie with autovivification built on defaultdict. For every node that terminates a word it stores extra key term to indicate it.

from collections import defaultdict

trie = lambda: defaultdict(trie)

defadd_word(root, s):
    node = root
    for c in s:
        node = node[c]
    node['term'] = Truedeflist_words(root, length, prefix=''):
    ifnot length:
        if'term'in root:
            yield prefix
        returnfor k, v in root.items(): 
        if k != 'term':
            yieldfrom 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)))

Output:

Length 3
joe
can
car
Length 4
cars

Solution 2:

Not being sure what your purpose of this structure is, here's a solution using recursion to generate the structure that you describe:

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


defnest(d, word):
    if word == "":
        return d
    d = {word[-1:]: word if d isNoneelse d}
    return nest(d, word[:-1])


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

print(d)

Solution 3:

Here's a way to do it without using collections.defaultdict or creating your own custom subclass of dict—so the resulting dictionary is just a ordinary dict object:

import pprint

def_build_dict(wholeword, chars, val, dic):
    iflen(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)

defbuild_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)

Output:

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

It's based on a recursive algorithm illustrated in a message in a python.org Python-list Archives thread titled Building and Transvering multi-level dictionaries.