Jak wybrać pomiędzy tabelą Hash a Trie (drzewem prefiksów)?

Wszystko zależy od tego, jaki problem próbujesz rozwiązać. Jeśli wszystko, co musisz zrobić, to wstawić i wyszukać, przejdź z tabelą hash. Jeśli chcesz rozwiązać bardziej złożone problemy, takie jak zapytania związane z prefiksem, lepszym rozwiązaniem może być trie.

Każdy zna tabelę hash i jej zastosowania, ale nie jest to dokładnie stały czas wyszukiwania, zależy to od wielkości tabeli hash , złożoności obliczeniowej funkcji hash.

Tworzenie ogromnych tabel hashowych dla efektywnego wyszukiwania nie jest eleganckim rozwiązaniem w większości scenariuszy przemysłowych, w których nawet małe opóźnienia/skalowalność ma znaczenie (np.: high frequency trading). Musisz dbać o struktury danych, które mają być zoptymalizowane pod kątem miejsca zajmowanego w pamięci, aby zmniejszyć pamięć podręczną panienko.

Bardzo dobrym przykładem, gdzie trie lepiej odpowiada wymaganiom, jest messaging middleware . Masz milion subskrybentów i wydawców Wiadomości do różnych kategorii ( w Warunkach JMS-tematy lub wymiany), w takich przypadkach, jeśli chcesz odfiltrować wiadomości na podstawie tematów (które są w rzeczywistości ciągami) , zdecydowanie nie chcesz tworzyć tabeli hash dla milionów subskrypcji z milionem tematów . Lepszym podejściem jest przechowywanie tematów w trie, więc gdy filtrowanie odbywa się na podstawie dopasowanie 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ę, ponieważ można być kreatywnym z tej struktury danych w celu optymalizacji wymagań przestrzeni, a tym samym mają niższe miss pamięci podręcznej.

Użyj drzewa:

1. Jeśli potrzebujesz funkcji auto complete
2. Znajdź wszystkie słowa zaczynające się na' a 'lub' axe ' tak dalej.
Drzewo sufiksowe jest specjalną formą drzewa. Drzewa przyrostków mają całą listę zalet, których hash nie może pokryć.

Jest coś, o czym nikt nie wspomniał wyraźnie, że myślę, że jest ważne, aby pamiętać. Zarówno tabele skrótów, jak i próby różnego rodzaju zazwyczaj będą miały operacje O(k), gdzie k jest długością ciągu znaków w bitach (lub równoważnie w znakach).

Zakładając, że masz dobrą funkcję hashową. Jeśli nie chcesz, aby "farm" i "farm animals" były hashowane do tej samej wartości, wtedy funkcja hash będzie musiała użyć wszystkich bitów klucza, a więc hashowanie " farm animals" powinno to zająć około dwa razy więcej czasu niż "Farma" (chyba że jesteś w jakimś rolling hash scenario, ale istnieją nieco podobne scenariusze Oszczędzania operacji z próbami). A przy próbie waniliowej jasne jest, dlaczego wstawianie "zwierząt gospodarskich "zajmie około dwa razy więcej czasu niż tylko"Farma". Na dłuższą metę jest to prawdą również w przypadku skompresowanych prób.

Implementacja HashTable jest wydajna przestrzennie w porównaniu z implementacją basicTrie . Ale w przypadku ciągów, zamawianie jest konieczne w większości praktycznych zastosowań. Ale HashTable całkowicie zakłóca porządek leksykalny. Teraz, jeśli Twoja aplikacja wykonuje operacje oparte na kolejności leksykalnej (np. wyszukiwanie częściowe, wszystkie ciągi znaków z podanym prefiksem, wszystkie słowa w kolejności posortowanej), powinieneś użyć Tries. Dla only lookup, HashTable powinien być używany (jak zapewne, daje minimum czas wyszukiwania).

P. S.: inne niż te, Ternary search Trees (TTS) byłby doskonałym wyborem. Jego czas Wyszukiwania jest więcej niż HashTable, ale jest wydajny czas we wszystkich innych operacjach. Ponadto jest bardziej wydajny niż próbuje.

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

Hash da ci O(1) do wyszukiwania i wstawiania, ale najpierw musisz obliczyć hash na podstawie łańcucha wejściowego, który ponownie jest O(s).

Wnioskowanie, asymptotyczna złożoność czasu jest liniowa w obu przypadkach.

Trie ma trochę więcej narzutu z perspektywy danych, ale możesz wybrać skompresowany trie, który sprawi, że ponownie, mniej lub bardziej na remis z hash stolik.

Aby zerwać krawat zadaj sobie pytanie: Czy muszę szukać tylko pełnych słów? Czy muszę zwracać wszystkie słowa pasujące do prefiksu? (Jak w predykcyjnym systemie wprowadzania tekstu ). Dla pierwszego przypadku, idź na hash. Jest to prostszy i czystszy kod. Łatwiejsze do testowania i konserwacji. W przypadku bardziej ellaborated use case gdzie prefiksy lub sufiksy mają znaczenie, przejdź do trie.

I jeśli zrobisz to tylko dla Zabawy, wdrożenie trie dobrze wykorzysta niedzielne popołudnie.

Niektóre aplikacje (zazwyczaj wbudowane, w czasie rzeczywistym) wymagają, aby czas przetwarzania był niezależny od danych. W takim przypadku tabela hash może zagwarantować znany czas wykonania, podczas gdy trie różni się w zależności od danych.