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!
źródło
00110010może być bajtem wejściowym, ale chcesz uwzględnić dopasowanie,00111010które jest usuwane tylko o jeden bit.Odpowiedzi:
Zalety prób:
Podstawy:
Nowe operacje:
Zalety połączonej struktury:
Zalety tablic mieszających:
źródło
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.
źródło
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.
źródło
Użyj drzewa:
źródło
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, gdziekjest 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.
źródło
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.
źródło
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.
źródło
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.
źródło