jaka jest najszybsza struktura/algorytm zbierania ciągów dla startswith i/lub zawiera wyszukiwania

Question

Mam następującą sytuację: Mam dużą kolekcję ciągów (powiedzmy 250.000+) o średniej długości może 30 lat. Co muszę zrobić zrobić, to zrobić wiele przeszukiwań w ramach tych .. głównie te będą z StartsWith i Contains rodzaju.

Kolekcja jest statyczna w czasie wykonywania. Co oznacza, że ​​pierwsze czytanie i wypełnianie wybranego zbioru odbywa się tylko raz. Dlatego wydajność budowania danych nie jest absolutnie ważna. Pamięć również nie stanowi problemu: co oznacza, że ​​nie mam nic przeciwko posiadaniu dwóch kolekcji z tymi samymi danymi w każdym z nich, jeśli jest to potrzebne (np. Dla startwith i innego dla zawiera). Jedyne, co ma znaczenie, to skuteczność wyszukiwań, które powinny zwracać wszystkie elementy pasujące do wyszukiwanego hasła.

Na początku natrafiłem na Trie lub Radix-tree .. ale może są jeszcze lepsze wybory?

Dla zawiera .. Nie mam jeszcze żadnego dobrego pomysłu (poza uruchomieniem kwerendy linq na liście, która nie będzie bardzo szybka z taką ilością danych).

Z góry dziękuję wszystkim!

zmiana: zapomniałem ważną rolę: Zawiera mam na myśli żadnych dokładnych dopasowań w kolekcji .. ale chcę znaleźć wszystkie sznurki w kolekcji zawierających daną searchstring

Answer 1

budowania suffix tree pozwoli Ci wykonaj wyszukiwanie podciągu na wszystkich ciągach równolegle w O(1). Pedantyczny we mnie nie może nie zauważyć, że to naprawdę O(n + m), gdzie n to liczba ciągów pasujących do podłańcucha, a m to rozmiar podciąganego podciągu.

Co to jest drzewo przyrostków? W swojej najprostszej implementacji jest to trie z fantazyjną metodą insertowania: oprócz dodawania ciągu dodaje on także każdy możliwy sufiks tego napisu do tria. W tej strukturze danych wyszukiwanie podłańcowe staje się przedrostkowym wyszukiwaniem wszystkich możliwych przyrostków. Ponieważ chcesz także wyszukiwać prefiksy, będziesz chciał dodać znak specjalny przed każdym wstawionym ciągiem i podciągami zapytania. Znak specjalny pozwoli ci rozróżnić sufiks od pełnego łańcucha.

Chociaż ta implementacja drzewa sufiksu jest niezwykle prosta, jest również bardzo nieefektywna (O(n^2) czas i czas kompilacji). Na szczęście istnieją inne, bardziej wydajne implementacje, które mogą znacznie zmniejszyć czas i przestrzeń. Jeden z nich, algorytm Ukkonena, jest bardzo dobrze wyjaśniony w this SO answer i przenosi spację do O(n). Możesz również zajrzeć do suffix arrays, które są równoważne, ale bardziej wydajne reprezentacja drzew sufiksów.

O ile wiem, istnieje wiele znacznie więcej implementacji drzewek przyrostowych (jeden z nich prawdopodobnie trafi w słodkie miejsce na twój przypadek użycia) Po prostu ich nie znam. Zalecam wykonanie pewnych badań na ten temat, zanim zdecydujesz się na wdrożenie.