Mam listę nazw plików:

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

Który powinien być zorganizowany w strukturę katalogów, a maksymalna liczba plików w jednym katalogu nie powinna być większa niż powiedzmy 2. Dlatego tworzę drzewo prefiksów (trie, kod poniżej) przechowywane w słowniku z prefiksami jako kluczami i 'end', jeśli liczba plików w poddrzewie nie przekroczy maksymalnej:

trie = make_trie(filenames, max_freq=2)

trie
{'1': {'1': {'1': 'end', '2': 'end'}, '3': 'end'},'2': {'1': 'end', '2': 'end'}}

Następnie dla każdej nazwy pliku wyszukuję (kod poniżej) w trie i odpowiednio buduję ścieżkę:

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/

Działa to dobrze, ale z moimi naiwnymi implementacjami trie (make_trie) i lookup (get_path) staje się to zaporowe. Domyślam się, że powinienem skorzystać z wydajnej istniejącej implementacji trie, takiej jak pytrie i datrie, ale tak naprawdę nie wiem, jak utworzyć próbę, która ma wartość progową 2 dla liczby sufiksów, więc trochę utknąłem w używaniu pakietów, np:

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?

Jak mogę użyć istniejącej, szybkiej implementacji trie, aby utworzyć strukturę katalogów?

Moja naiwna implementacja trie i lookup:

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
1
user1981275 19 grudzień 2019, 14:27
Czy naprawdę potrzebujesz spróbować, czy Twoim celem jest po prostu stworzenie struktury katalogów?
 – 
m.raynal
19 grudzień 2019, 17:38
Naprawdę nie potrzebuję próby
 – 
user1981275
19 grudzień 2019, 17:45

1 odpowiedź

To może zadziałać, używając os.makedirs.

import os

def create_dir_structure(filenames):
    for filename in filenames:
        os.makedirs(
            '/'.join(e for e in str(filename))
        )


create_dir_structure(
    ['1111', '1123']
)

Powiedz mi w komentarzach, jeśli chcesz zobaczyć inne zachowanie

0
m.raynal 19 grudzień 2019, 18:27
Nie uwzględnia to ograniczenia maksymalnej liczby katalogów.
 – 
user1981275
19 grudzień 2019, 18:41
Działałoby to, gdyby tylko jeden plik (i dalsze katalogi) były dozwolone na katalog
 – 
user1981275
19 grudzień 2019, 18:42
Ale jak możesz dodać ['1', '2', '3', '4', '5'], jeśli limit podkatalogów na katalog wynosi 2, a limit plików na katalog to 2 ? Aby problem był wykonalny, musi być więcej założeń (o wielkości alfabetu w stosunku do stałych max).
 – 
m.raynal
19 grudzień 2019, 22:03