特定動態嵌套字典，自動實現實現

我試圖以特定方式實現嵌套字典結構。我正在閱讀一長串單詞。這些詞最終將需要通過經常有效的搜索，所以這是我想如何設置我的字典：特定動態嵌套字典，自動實現實現

我想做一個嵌套的字典結構，其中第一個鍵值是該詞是一個字典，其中鍵是該詞的第一個字母，該值是一個詞典，該鍵是該詞的第二個字母，該值是該詞作爲該詞的第三個字母的詞典等。 ..

所以如果我讀了「汽車」，「可以」和「喬」

我得到

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

雖然我需要爲此處理大約100,000個字，並且它們的長度從2到27個字母不等。

我已經通過What is the best way to implement nested dictionaries? 和 Dynamic nested dictionaries看去。

但沒有任何運氣搞清楚這一點。

我肯定能得到我的話了使用

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

我的文本文件的，我可以用

for char in word

或

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

我只是」打入每個字符弄清楚如何讓這個結構下來。任何幫助將不勝感激。

來源

2016-12-07 J. Smith

在你的例子中長度不應該是3嗎？那麼喬詞典的關鍵是什麼？ – Iluvatar

@Ivvatar是的！編輯顯示3，謝謝。喬字典的關鍵是3，因爲它是一個3個字母的單詞。 –

你不能有兩個相同的鍵。另外，你的目標是什麼？像詞建議？ – Iluvatar

並非是確保您的這種結構的目的是什麼，這是一個使用遞歸來生成你描述的結構的解決方案：

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-07 01:36:00 antonagestam

這建立了字典列表的字典，不只是嵌套字典 - 這是什麼OP想要。 – martineau

@martineau這個問題被編輯了，在這個問題上有一個列表。 – antonagestam

也許你應該[編輯]你的答案，並指出你正在回答問題的早期版本（並顯示產生的字典/輸出）。 – martineau

下面是關於如何實現與建立在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-07 01:54:51 niemmi

這裏有一個辦法做到這一點不使用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列表標題爲Building and Transvering multi-level dictionaries的歸檔主題。

來源

2016-12-07 03:21:04 martineau

特定動態嵌套字典，自動實現實現

回答

相關問題