Struktura danych do wyszukiwania nazw plików i uzyskania ścieżki

Question

Będę wstawiał nazwy plików w sposób dynamiczny, w przybliżeniu do 1 miliarda nazw. Poza tym, chcę również zapisać ścieżkę, w której znajdują się pliki, aby wykonać następujące zapytania:

• Wyszukiwanie, w którym nazwa pliku jest przechowywana, aby uzyskać jego ścieżkę.
• Wyszukiwanie nazwy wszystkich plików, które pasują do podciągu, rodzaj podobnego zapytania (np. Jeśli wyszukiwanie * o *, zwróci mi joel, hola, ola, oso, osea, algo, jeśli szukaj aa *, zwróci mi aaab i jeśli przeszukuję *, to zwróci oso).
• Usuń nazwę pliku.

Tak, staram się zrobić coś w rodzaju struktury danych trie w następujący sposób:

mam 26 węzłów (angielski alfabet AZ, ja nie zamierzam umieścić wszystkie węzły na obrazie ponieważ przestrzeń) tak, że jeśli wstawię słowo "hola", to utworzę krawędź od węzła z literą "h" do węzła z literą "o" i której krawędź ma dane 1, ponieważ ta liczba reprezentuje poziom głębokości . Co więcej, w węźle, w którym przechowywane jest "a", będę miał strukturę mapy w celu przechowywania ścieżki pliku, ponieważ na pewno będę miał wiele ścieżek przechowywanych w węźle, który zawiera literę "a" .

Powiedziawszy to, wstawiłem następujące słowa: joel, hola, ola, oso, osea, algo, aaab.

Zrobiłem tak, bo nie chcą mieć wiele węzłów z tych Lettres sama (np a, b, etc), ale problemem jest to, że mam dużo krawędziach i sctructure potrzebuje

bajtów pamięci (I 'm programowania w C++), gdzie w jest ciągiem wielkości .

Jak widać, jeśli szukam nazwy pliku "jola" (który nie został wstawiony), nie zostanie zwrócona żadna ścieżka, a to oznacza, że ​​taki plik nie jest przechowywany.

Jak mogę to poprawić? Czy to sposób na zmniejszenie liczby krawędzi? czy istnieje lepsza struktura i sposób na zrobienie tego? Jestem bardzo otwarty na wszelkie sugestie.

Answer 1

można albo użyć DAG (skierowany graf acykliczny) lub można również użyć rozłącznych technik operacyjnych zestaw (techniki szybkiego znalezienia (* jako głównym celem jest znaleźć))