Trie oszczędza miejsce, ale jak?

Question

Nie mam pojęcia, w jaki sposób implementacja Trie pozwala zaoszczędzić miejsce & przechowuje dane w najbardziej kompaktowej formie!

Jeśli spojrzeć na drzewo poniżej. Gdy przechowujesz znak w dowolnym węźle, musisz również zapisać odniesienie do tego &, tak aby dla każdego znaku ciągu trzeba było zachować jego odniesienie. OK, zaoszczędziliśmy trochę miejsca, gdy pojawiła się zwykła postać, ale straciliśmy więcej miejsca na przechowywanie odniesienia do tego węzła postaci.

A więc czy nie ma zbyt wiele strukturalnych kosztów utrzymania tego drzewa? Zamiast tego, gdyby zamiast tego została użyta TreeMap, powiedzmy, aby zaimplementować słownik, mogłoby to zaoszczędzić dużo więcej miejsca, ponieważ ciąg byłby przechowywany w jednym kawałku, a więc nie zmarnowałoby się miejsca na przechowywanie odniesień, prawda?

Answer 1

Można wywnioskować, że oszczędza miejsce na idealnej maszynie, gdzie każdy bajt jest przydzielany wydajnie. Jednak prawdziwe maszyny przydzielają wyrównane bloki pamięci (8 bajtów na Javę i 16 bajtów na niektórych C++), więc może nie zapisać żadnej przestrzeni.

Java Struny i kolekcje dodają stosunkowo dużą ilość nad głową, więc różnica procentowa może być bardzo mała.

O ile twoja struktura nie jest bardzo duża, o tyle, o ile chodzi o wagę czasu, koszt pamięci, który przy użyciu najprostszej, najbardziej standardowej i najłatwiejszej do utrzymania kolekcji jest o wiele ważniejszy. na przykład twój czas może bardzo łatwo być wart 1000x lub więcej wartości pamięci, którą próbujesz zapisać.

np. powiedzmy, że masz 10000 nazw, które można zapisać 16 bajtów każdy za pomocą trie. (Zakładając, że można to udowodnić, nie zabierając więcej czasu) To równa się 16 KB, która przy dzisiejszych cenach jest warta 0,1 centa. Jeśli Twój czas kosztuje firmę 30 USD za godzinę, koszt napisania jednej linii testowanego kodu może wynosić 1 USD.

Jeśli zastanawiasz się nad tym dłużej, by zaoszczędzić 16 KB, prawdopodobnie nie będzie to warte komputera. (Urządzenia mobilne są już inna historia, ale ten sam argument dotyczy IMHO)

EDIT: Ty zainspirowały mnie do dodania aktualizacji http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html

Answer 2

Przestrzeń jest zapisywany gdy masz wiele słów, aby być reprezentowana przez drzewa. Ponieważ wiele słów ma tę samą ścieżkę na drzewie; im więcej masz słów, tym więcej miejsca zaoszczędzisz.

Ale istnieje lepsza struktura danych, jeśli chcesz zaoszczędzić miejsce. Trie nie oszczędza tak dużo miejsca, jak directed acyclic word graph (DAWG), ponieważ dzieli wspólny węzeł w całej strukturze, podczas gdy trie nie współdzieli węzłów. The wiki entry wyjaśnia tak wiele szczegółów, więc spójrz na to.

tym polega różnica (graficznie) pomiędzy Trie i psie:

struny "dotknij", "zawory", "góra" i "wierzchołki" przechowywane w Trie (po lewej) i DAWG (po prawej), EOW oznacza Koniec słowa.

Drzewo po lewej stronie to Trie, a drzewo po prawej to DAWG. Porównaj je i zobacz, jak DAWG oszczędza przestrzeń. Trie ma zduplikowane węzły, które reprezentują tę samą literę/podrzędne, podczas gdy DAWG ma dokładnie jeden węzeł dla każdej litery/podword.

Answer 3

Aby zaoszczędzić miejsce podczas używania Trie, można użyć compressed trie (znany również jako trie patricia lub drzewa radix), dla których jeden węzeł może reprezentować wiele znaków:

w informatyce, przelicznika drzewo (również patricia trie lub radix trie) jest strukturą danych zoptymalizowaną pod kątem przestrzeni, w której każdy węzeł z jednym dzieckiem zostaje połączony z dzieckiem. W rezultacie każdy węzeł wewnętrzny ma co najmniej dwoje dzieci. W przeciwieństwie do zwykłych prób, krawędzie mogą być oznaczone ciągami znaków, jak również pojedynczymi znakami. Dzięki temu są znacznie wydajniejsze w przypadku małych zestawów (szczególnie, jeśli ciągi są długie) oraz w zestawach ciągów, które mają wspólne długie prefiksy.

Przykład drzewa Patricia:

Uwaga że trie jest zwykle stosowany jako skuteczny struktury danych do dopasowywania przedrostka na zestaw strun. Trie może być również używane jako tablica asocjacyjna (jak tablica asocjacyjna), gdzie klucz jest ciągiem znaków.

Answer 4

Nie chodzi o tanią przestrzeń w pamięci, chodzi o cenną przestrzeń w pliku lub łącze komunikacyjne. Z algorytmem, który buduje ten trik, możemy wysłać "dziesięć" w trzech bitach, w lewo-prawo-prawo. W porównaniu do 24 bitów "dziesięć" zajmowałoby nieskompresowane, to jest ogromna oszczędność cennego miejsca na dysku lub przepustowości transferu.

Answer 5

Guava rzeczywiście mogą przechowywać klucz na każdym poziomie, ale punkt do realizacji jest to, że Klucz tak naprawdę nie musi być przechowywany, ponieważ ścieżka do węzła całkowicie definiuje klucz dla tego węzła. Wszystko, co faktycznie musi być przechowywane w każdym węźle, to pojedyncza wartość logiczna wskazująca, czy jest to węzeł liścia, czy też nie.

Próby, podobnie jak inne struktury, sprawdzają się w przechowywaniu określonych typów danych. W szczególności, najlepiej jest przechowywać ciągi, które mają wspólny katalog główny. Zastanów się, na przykład, przechowując pełne katalogi katalogów.