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

134

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!

Justin Bozonier
źródło
1
Warto zauważyć, że drzewo redix jest bardziej wydajne niż zwykłe trie, ponieważ nie potrzebujesz nowej gałęzi dla każdego bajtu ciągu. Ponadto drzewa redix zapewniają lepszą obsługę wyszukiwania „rozmytego” niż tabele skrótów, ponieważ podczas pracy nad ścieżką patrzysz na poszczególne bity. Na przykład 00110010może być bajtem wejściowym, ale chcesz uwzględnić dopasowanie, 00111010które jest usuwane tylko o jeden bit.
Xeoncross

Odpowiedzi:

116

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 )
Darius Bacon
źródło
26
nie może się do końca zgodzić z „Bardziej wydajnym przestrzennie niż oczywista połączona struktura trie” - w ogólnej implementacji tablicy mieszającej zajmuje znacznie większą przestrzeń na klucze, podczas gdy w próbach każdy węzeł reprezentuje słowo. W tym sensie próby są bardziej wydajne przestrzennie.
galactica
1
co powiesz na dostęp do danych z jednej struktury w porównaniu z drugą? Myślę o pamięci podręcznej i lokalizacji
Horia Toma
8
@galactica, to jest sprzeczne z moim doświadczeniem: na przykład w tej odpowiedzi na wszystkie struktury, które zmierzyłem dla przestrzeni, próba wypadła najgorzej. Ma to sens, ponieważ wskaźnik jest znacznie większy niż bajt. Tak, dzielenie się prefiksami pomaga, ale musi pokonać wiele narzutów, aby osiągnąć parytet. Bardziej wydajna przestrzennie reprezentacja może bardzo pomóc, ale wtedy nie mówimy już o oczywistej połączonej strukturze.
Darius Bacon
1
@DariusBacon obsługujący plany numeracji telefonów wydaje się rozsądnym scenariuszem prób. Przykładowy scenariusz: dopasowanie numeru telefonu do operatora, w tym numery przenoszone od jednego przewoźnika do drugiego. W przypadku zwykłych słowników może to zależeć od języka (mandaryński czy angielski), potrzebujesz n-gramów i / lub innych danych statystycznych. W przypadku książki z rymowankami drzewo z przyrostkami również wydaje się dobrym rozwiązaniem.
mbx
Różnorodność danych do wyszukania ma duże znaczenie. Jeśli duży procent wartości danych jest unikalnych, złożoność przestrzeni wzrośnie wraz z mieszaniem z powodu użycia dodatkowych wskaźników zerowych.
Statystyki uczenia się na przykładzie
45

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.

Adam Rosenfield
źródło
8
jeśli tablica skrótów i trie mają taką samą złożoność zapytania, O (k) dla łańcucha długości k, dlaczego mielibyśmy wybierać hash? czy mógłbyś wyjaśnić?
Sazzad Hissain Khan
29

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.

user179156
źródło
10

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.
Dr Sai
źródło
4

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.

user3391564
źródło
3

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.

Visiedo
źródło
„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)”. Dzięki za wyjaśnienie!
abadawi
2

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.

Jay Jodiwal
źródło
-2

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.

Adam Liss
źródło
6
Większość tablic haszujących nie gwarantuje znanego czasu wykonania - najgorszym przypadkiem jest O (n), jeśli każdy element zderzy się i zostanie powiązany
Adam Rosenfield
2
Dla dowolnego zestawu danych można obliczyć idealną funkcję skrótu, która zagwarantuje wyszukiwania O (1) dla tych danych. Oczywiście obliczenie idealnego skrótu nie jest darmowe.
George V. Reilly
5
Ponadto tworzenie łańcuchów nie jest jedynym sposobem radzenia sobie z kolizjami; istnieje wiele interesujących, sprytnych sposobów radzenia sobie z tym - na przykład haszowanie z kukułką ( en.wikipedia.org/wiki/Cuckoo_hashing ) - a najlepszy wybór zależy od potrzeb kodu klienta.
Hank Gay
nie wiedziałem o haszowaniu kukułki i jego związku z filtrem bloom, będzie ciekawą lekturą, dzięki!
Horia Toma
Nie zapomnij o haszowaniu Robin-hood, które jest lepsze w przypadku pamięci podręcznej i wariancji. sebastiansylvan.com/2013/05/08/… codecapsule.com/2013/11/11/robin-hood-hashing
Nicholls