0

我正在尝试以特定方式实现嵌套字典结构。我正在阅读一长串单词。这些词最终需要经常有效地搜索，所以这就是我希望我的字典设置的方式：

我正在尝试制作一个嵌套字典结构，其中第一个键值是单词的长度，值是一个字典，键是单词的第一个字母，值是一个字典，键是第二个字母的单词和值是一个字典，键是单词的第三个字母等。

所以如果我读到“car”“can”和“joe”

我明白了

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

我需要为大约 100,000 个单词执行此操作，它们的长度从 2 到 27 个字母不等。

我已经浏览了实现嵌套字典的最佳方法是什么？ 和 动态嵌套字典。

但没有任何运气弄清楚这一点。

我当然可以使用

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

我可以使用

for char in word

或者

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

我只是不知道如何让这个结构下来。任何帮助将不胜感激。

4

3 回答 3

3

这是一个简短的示例，介绍如何使用基于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
于 2016-12-07T01:54:51.463 回答
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)
于 2016-12-07T01:36:00.820 回答
1

这是一种无需使用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 Python-list Archives 线程中标题为Building and Transvering multi-level dictionaries的消息中说明的递归算法。

于 2016-12-07T03:21:04.240 回答