Jak mogę utworzyć przyrostowy skierowany acykliczny wykres słowo do przechowywania i wyszukiwania ciągów?

Question

Próbuję przechowywać dużą listę ciągów w zwięzły sposób, aby mogły one być bardzo szybko analizowane/przeszukiwane.

Skierowany acykliczny wykres słowo (DAWG) doskonale pasuje do tego celu. Jednak nie mam listy ciągów do uwzględnienia, więc musi ona być przyrostowo budowana. Dodatkowo, gdy przeszukuję go w poszukiwaniu ciągu znaków, muszę przywrócić dane powiązane z wynikiem (nie tylko boolowskie stwierdzenie, czy było obecne).

Znalazłem informacje na temat modyfikacji DAWG do śledzenia danych ciągowych tutaj: http://www.pathcom.com/~vadco/adtdawg.html Wygląda niezwykle, bardzo skomplikowane i nie jestem pewien, czy jestem w stanie go napisać.

Znalazłem również kilka prac badawczych opisujących algorytmy budowania przyrostowego, chociaż odkryłem, że prace badawcze w ogóle nie są bardzo pomocne.

Nie sądzę, że jestem na tyle zaawansowany, aby móc połączyć oba te algorytmy osobiście. Czy istnieje dokumentacja algorytmu, który już je zawiera, lub alternatywny algorytm o dobrej szybkości wykorzystania pamięci?

Answer 1

Napisałem stronę internetową ADTDAWG. Dodawanie słów po zakończeniu budowy nie jest opcją. Struktura jest niczym więcej niż 4 tablice niepodpisanych typów całkowitych. Zaprojektowano go tak, aby był niezmienny dla całkowitej integracji pamięci podręcznej procesora i minimalnej złożoności dostępu wielowątkowego.

Struktura jest automatem, który stanowi minimalną i idealną funkcję skrótu. Został zbudowany z myślą o szybkości podczas ruchu rekursywnego za pomocą jawnego stosu.

Opublikowane, obsługuje do 18 znaków. W tym wszystkie 26 znaków angielskich będzie wymagać dalszego powiększenia.

Moja rada to użycie standardowego Trie z indeksem tablicy przechowywanym w każdym węźle. Tak, to będzie wyglądało jak infantylne, ale każdy węzeł END_OF_WORD reprezentuje tylko jedno słowo. ADTDAWG jest rozwiązaniem dla każdego węzła END_OF_WORD w tradycyjnym DAWG reprezentującym wiele, wiele słów.

Minimalne i doskonałe stoły hash nie jest coś takiego, że można po prostu umieścić razem w locie.

szukam czegoś innego, aby pracować, czy pracy, więc ze mną skontaktować, a zrobię co mogę. Na razie wszystko, co mogę powiedzieć, to to, że nierealistyczne jest stosowanie ciężkiej optymalizacji struktury, która często ulega częstym zmianom.

Answer 2

Możesz również zajrzeć do struktury trie (potencjalnie budując radix-tree). Wygląda na przyzwoitą "prostą" alternatywną strukturę.

ja sugeruję to z kilku powodów:

1. ja naprawdę nie mam pełne zrozumienie swojego wyniku.
2. Zdecydowanie przyrostowy w budowie.
3. Węzły liści mogą zawierać dowolne dane.
4. Subiektywnie, prosty algorytm.

Answer 3

Java

Na wykresie problemów, które wymagają wytrwałości, chciałbym przyjrzeć projektu Neo4j graph DB. Neo4j jest przeznaczony do przechowywania dużych wykresów i umożliwia przyrostowe tworzenie i modyfikowanie danych, co wydaje się spełniać kryteria, które opisujesz.

Mają dobre przykłady, abyś mógł szybko zacząć działać, a zazwyczaj masz przykład kodu, który pomoże Ci zacząć od większości problemów.

Mają one DAG example z łączem na dole do full source code.

C++

Jeśli używasz C++, wspólne rozwiązanie na wykresie budynek/analiza jest użycie Boost graph library. Aby utrwalić swój wykres, można zachować wersję graficzną opartą na plikach w GraphML (na przykład) i odczytać i zapisać do tego pliku w miarę zmiany wykresu.