Jak wybrać między tabelą skrótów a Trie (drzewo prefiksów)?

Jeśli więc mam wybierać między tabelą skrótów a drzewem przedrostków, jakie czynniki dyskryminujące skłoniłyby mnie do wybrania jednego z nich. Z mojego własnego naiwnego punktu widzenia wydaje się, że używanie trie ma dodatkowe obciążenie, ponieważ nie jest przechowywane jako tablica, ale pod względem czasu wykonywania (zakładając, że najdłuższy klucz jest najdłuższym angielskim słowem) może zasadniczo być O (1) (w odniesieniu do górnej granicy). Może najdłuższe angielskie słowo ma 50 znaków?

Tabele z skrótami są natychmiastowo wyszukiwane po uzyskaniu indeksu . Wydaje się jednak, że haszowanie klucza w celu uzyskania indeksu może z łatwością zająć blisko 50 kroków.

Czy ktoś może podać mi bardziej doświadczoną perspektywę na ten temat? Dzięki!

Zalety prób:

Podstawy:

• Przewidywalny czas wyszukiwania O (k), gdzie k jest rozmiarem klucza
• Wyszukiwanie może zająć mniej niż k czasu, jeśli go tam nie ma
• Obsługuje uporządkowane przemierzanie
• Nie ma potrzeby funkcji skrótu
• Usunięcie jest proste

Nowe operacje:

• Możesz szybko wyszukać prefiksy kluczy, wyliczyć wszystkie wpisy z podanym prefiksem itp.

Zalety połączonej struktury:

• Jeśli istnieje wiele typowych prefiksów, wymagana przestrzeń jest współdzielona.
• Niezmienne próby mogą mieć wspólną strukturę. Zamiast aktualizować próbę na miejscu, możesz zbudować nową, która różni się tylko w jednej gałęzi, a gdzie indziej wskazuje na starą próbę. Może to być przydatne w przypadku współbieżności, wielu jednoczesnych wersji tabeli itp.
• Niezmienna trie jest kompresowalna. Oznacza to, że może również dzielić strukturę sufiksów dzięki funkcji mieszania.

Zalety tablic mieszających:

• Wszyscy znają tabele hash, prawda? Twój system będzie już miał ładną, dobrze zoptymalizowaną implementację, szybszą niż próby do większości zastosowań.
• Twoje klucze nie muszą mieć żadnej specjalnej struktury.
• Większa oszczędność miejsca niż oczywista połączona struktura trie ( patrz komentarze poniżej )

Wszystko zależy od tego, jaki problem próbujesz rozwiązać. Jeśli wszystko, co musisz zrobić, to wstawić i wyszukać, użyj tabeli skrótów. Jeśli chcesz rozwiązać bardziej złożone problemy, takie jak zapytania związane z prefiksami, lepszym rozwiązaniem może być próba.

Wszyscy znają tablicę skrótów i jej zastosowania, ale nie jest to dokładnie stały czas wyszukiwania, zależy to od wielkości tablicy skrótów, złożoności obliczeniowej funkcji skrótu.

Tworzenie ogromnych tablic mieszających w celu wydajnego wyszukiwania nie jest eleganckim rozwiązaniem w większości scenariuszy przemysłowych, w których nawet małe opóźnienia / skalowalność mają znaczenie (np. Handel z wysoką częstotliwością). Musisz zadbać o struktury danych, które mają być zoptymalizowane pod kątem miejsca, które zajmuje w pamięci, aby zmniejszyć brakujące w pamięci podręcznej.

Bardzo dobrym przykładem, gdzie trie lepiej odpowiada wymaganiom, jest oprogramowanie pośredniczące do przesyłania wiadomości. Masz milion subskrybentów i wydawców wiadomości do różnych kategorii (w kategoriach JMS - Tematy lub giełdy), w takich przypadkach, jeśli chcesz odfiltrować wiadomości na podstawie tematów (które w rzeczywistości są ciągami znaków), zdecydowanie nie chcesz tworzyć tablicy skrótów za milion subskrypcji z milionami tematów. Lepszym podejściem jest przechowywanie tematów w trie, więc gdy filtrowanie odbywa się na podstawie dopasowania tematu, jego złożoność jest niezależna od liczby tematów / subskrypcji / wydawców (zależy tylko od długości ciągu). Podoba mi się to, ponieważ możesz wykazać się kreatywnością dzięki tej strukturze danych, aby zoptymalizować wymagania dotyczące miejsca, a tym samym mieć mniejszy brak pamięci podręcznej.

Użyj drzewa:

1. Jeśli potrzebujesz funkcji automatycznego uzupełniania
2. Znajdź wszystkie słowa zaczynające się od „a” lub „ax” itd.
3. Drzewo przyrostków to specjalna forma drzewa. Drzewa sufiksowe mają całą listę zalet, których skrót nie obejmuje.

Jest coś, o czym nie widziałem, by ktoś wyraźnie wspomniał, o czym myślę, że należy o tym pamiętać. Zarówno tablice haszujące, jak i różnego rodzaju próby zwykle mają O(k)operacje, gdzie kjest długością łańcucha w bitach (lub równoważnie w znakach).

Zakłada się, że masz dobrą funkcję skrótu. Jeśli nie chcesz, aby „zwierzęta gospodarskie” i „zwierzęta hodowlane” miały tę samą wartość, funkcja skrótu będzie musiała wykorzystać wszystkie bity klucza, a więc haszowanie „zwierząt gospodarskich” powinno zająć około dwa razy dłużej niż „farma” (chyba że jesteś w jakimś scenariuszu kroczącego mieszania, ale są też podobne scenariusze oszczędzania operacji z próbami). W przypadku trie waniliowej jasne jest, dlaczego wstawienie słowa „zwierzęta hodowlane” zajmie około dwa razy dłużej niż wstawienie słowa „farma”. Na dłuższą metę jest to również prawdą w przypadku skompresowanych prób.

Wstawianie i wyszukiwanie w trie jest liniowe z długością łańcucha wejściowego O (s).

Skrót da ci O (1) do wyszukiwania i wstawiania, ale najpierw musisz obliczyć skrót na podstawie ciągu wejściowego, który ponownie jest O (s).

Podsumowując, asymptotyczna złożoność czasowa jest w obu przypadkach liniowa.

Trie ma trochę więcej narzutów z punktu widzenia danych, ale możesz wybrać skompresowaną próbę, która ponownie sprawi, że będziesz mniej więcej na równi z tabelą skrótów.

Aby zerwać z krawatem, zadaj sobie pytanie: Czy muszę wyszukiwać tylko pełne słowa? Czy muszę zwrócić wszystkie słowa pasujące do prefiksu? (Jak w systemie predykcyjnego wprowadzania tekstu). W pierwszym przypadku wybierz hash. Jest to prostszy i bardziej przejrzysty kod. Łatwiejsze w testowaniu i utrzymaniu. Aby uzyskać bardziej rozbudowany przypadek użycia, w którym liczą się przedrostki lub sufiksy, spróbuj.

A jeśli robisz to tylko dla przyjemności, wdrożenie trie może dobrze wykorzystać niedzielne popołudnie.

Implementacja HashTable zajmuje mniej miejsca w porównaniu z podstawową implementacją Trie . Ale w przypadku sznurków porządkowanie jest konieczne w większości praktycznych zastosowań. Ale HashTable całkowicie zaburza porządek leksograficzny. Teraz, jeśli Twoja aplikacja wykonuje operacje w oparciu o porządek leksograficzny (np. Wyszukiwanie częściowe, wszystkie ciągi znaków z podanym prefiksem, wszystkie słowa w kolejności posortowanej), powinieneś użyć Tries. Dla samego wyszukiwania należy użyć HashTable (ponieważ prawdopodobnie zapewnia minimalny czas wyszukiwania).

PS: Poza tym trójskładnikowe drzewa wyszukiwania (TST) byłyby doskonałym wyborem. Jego czas wyszukiwania jest dłuższy niż HashTable, ale oszczędza czas we wszystkich innych operacjach. Ponadto jest bardziej wydajna przestrzennie niż próbuje.

Niektóre aplikacje (zwykle osadzone, działające w czasie rzeczywistym) wymagają, aby czas przetwarzania był niezależny od danych. W takim przypadku tablica skrótów może zagwarantować znany czas wykonania, podczas gdy próba różni się w zależności od danych.