使用trie在python中建立目录结构

Question

我有一个文件名列表：

filenames = ["111", "112", "1341", "2213", "2131", "22222", "11111"]

应该以目录结构进行组织，并且一个目录中的最大文件数不应大于2。因此，如果子树中的文件数量不超过最大值，则我将前缀树（trie，下面的代码）存储在字典中，并以前缀作为键和'end'作为前缀。

trie = make_trie(filenames, max_freq=2)

trie
{'1': {'1': {'1': 'end', '2': 'end'}, '3': 'end'},'2': {'1': 'end', '2': 'end'}}
然后为每个文件名在特里进行查找（下面的代码）并相应地构建路径：

for f in filenames:
    print("Filename: ", f, "\tPath:", get_path(f, trie))

Filename:  111  Path: 1/1/1/
Filename:  112  Path: 1/1/2/
Filename:  1341         Path: 1/3/
Filename:  2213         Path: 2/2/
Filename:  2131         Path: 2/1/
Filename:  22222        Path: 2/2/
Filename:  11111        Path: 1/1/1/
这很好用，但是对于我的特里（make_trie）和查找（get_path）的简单实现，这变得令人望而却步。我的猜测是我应该采用一种有效的现有Trie实现，例如pytrie和datrie，但我真的不知道如何使后缀数量的阈值设为2的Trie，所以我在如何使用软件包方面有些困难，例如：

import datrie
tr = datrie.Trie(string.digits) # make trie with digits
for f in filenames:
    tr[f] = "some value" # insert into trie, but what should be the values??

tr.prefixes('111211321') # I can look up prefixes now, but then what?
如何使用现有的快速Trie实现来建立目录结构？

[我天真的尝试和查找：

def make_trie(words, max_freq):
    root = dict()
    for word in words:
        current_dict = root
        for i in range(len(word)):
            letter = word[i]
            current_prefix = word[:i+1]
            prefix_freq = sum(list(map(lambda x: x[:i+1]==current_prefix, words)))
            if prefix_freq > max_freq:
                current_dict = current_dict.setdefault(letter, {})
            else:
                current_dict = current_dict.setdefault(letter, "end")
                break
    return root

def get_path(image_id, trie):
    result = ""
    current_dict = trie
    for i in range(len(image_id)):
        letter = image_id[i]
        if letter in current_dict:
            result += letter + "/"
            if current_dict[letter] == "end":
                break
            current_dict = current_dict[letter]
    return result

我有一个文件名列表：filenames = [“ 111”，“ 112”，“ 1341”，“ 2213”，“ 2131”，“ 22222”，“ 11111”]，应按目录结构进行组织，并且一个目录中的最大文件数...

Answer 1

这可以使用os.makedirs。