Jaki jest najszybszy algorytm wyszukiwania podciągów?

OK, więc nie brzmię jak idiota, mam zamiar określić problem / wymagania dokładniej:

• Igła (wzór) i stóg siana (tekst do wyszukania) to ciągi zakończone znakiem C w stylu C. Brak informacji o długości; w razie potrzeby należy ją obliczyć.
• Funkcja powinna zwrócić wskaźnik do pierwszego dopasowania lub NULLjeśli nie zostanie znalezione żadne dopasowanie.
• Przypadki niepowodzenia są niedozwolone. Oznacza to, że każdy algorytm z niestałymi (lub dużymi stałymi) wymaganiami dotyczącymi pamięci masowej będzie musiał mieć przypadek rezerwowy dla błędu alokacji (a wydajność w opiece rezerwowej przyczynia się w ten sposób do wydajności w najgorszym przypadku).
• Implementacja ma być w C, chociaż dobry opis algorytmu (lub link do takiego algorytmu) bez kodu też jest w porządku.

... a także to, co mam na myśli przez „najszybszy”:

• Deterministyczne O(n)gdzie n= długość stogu siana. (Ale może być możliwe użycie pomysłów z algorytmów, które są normalnie O(nm)(na przykład toczący się hash), jeśli są połączone z bardziej niezawodnym algorytmem, aby dać deterministyczne O(n)wyniki).
• Nigdy nie działa (wymiernie; kilka zegarów if (!needle[1])itp. Jest w porządku) gorzej niż naiwny algorytm brutalnej siły, szczególnie na bardzo krótkich igłach, które są prawdopodobnie najczęstszym przypadkiem. (Bezwarunkowe, duże obciążenie wstępne przetwarzania jest złe, podobnie jak próba poprawy współczynnika liniowego dla patologicznych igieł kosztem prawdopodobnych igieł).
• Biorąc pod uwagę dowolną igłę i stóg siana, porównywalna lub lepsza wydajność (nie gorsza niż 50% dłuższy czas wyszukiwania) w porównaniu z jakimkolwiek innym szeroko stosowanym algorytmem.
• Poza tymi warunkami zostawiam definicję „najszybszego” otwartego. Dobra odpowiedź powinna wyjaśniać, dlaczego uważasz proponowane podejście za „najszybsze”.

Moja obecna implementacja działa mniej więcej od 10% wolniej do 8 razy szybciej (w zależności od danych wejściowych) niż implementacja dwukierunkowa glibc.

Aktualizacja: mój aktualny optymalny algorytm jest następujący:

• W przypadku igieł o długości 1 użyj strchr.
• W przypadku igieł o długości 2-4 użyj słów maszynowych, aby porównać 2-4 bajty naraz w następujący sposób: Wstępnie załaduj igłę 16- lub 32-bitową liczbą całkowitą z przesunięciami bitów i przełączaj stary bajt / nowe bajty ze stosu siana w każdej iteracji . Każdy bajt stogu siana jest odczytywany dokładnie raz i podlega sprawdzeniu względem 0 (koniec ciągu) i jednym 16- lub 32-bitowym porównaniem.
• W przypadku igieł o długości> 4 użyj algorytmu dwukierunkowego ze złą tabelą zmian (np. Boyer-Moore), która jest stosowana tylko do ostatniego bajtu okna. Aby uniknąć narzutu inicjalizacji tabeli 1kb, co byłoby stratą netto dla wielu igieł o średniej długości, zachowuję tablicę bitową (32 bajty) oznaczającą, które wpisy w tabeli przesunięć są inicjalizowane. Bity, które nie są ustawione, odpowiadają wartościom bajtów, które nigdy nie pojawiają się w igle, dla których możliwe jest przesunięcie o pełną długość igły.

Najważniejsze pytania, jakie mam w głowie, to:

• Czy istnieje sposób na lepsze wykorzystanie złego stołu zmiany biegów? Boyer-Moore najlepiej go wykorzystuje, skanując do tyłu (od prawej do lewej), ale dwukierunkowy wymaga skanowania od lewej do prawej.
• Jedyne dwa realne algorytmy kandydatów, które znalazłem dla ogólnego przypadku (brak warunków braku pamięci lub kwadratowych wydajności), to dwukierunkowe i dopasowywanie ciągów w uporządkowanych alfabetach . Ale czy istnieją łatwe do wykrycia przypadki, w których różne algorytmy byłyby optymalne? Z pewnością wiele z algorytmów kosmicznych O(m)(gdzie mjest długość igły) można by użyć do m<100lub czegoś podobnego. Byłoby również możliwe użycie algorytmów, które są w najgorszym przypadku kwadratowe, jeśli istnieje łatwy test dla igieł, który, jak można udowodnić, wymaga tylko czasu liniowego.

Punkty bonusowe za:

• Czy możesz poprawić wydajność, zakładając, że zarówno igła, jak i stóg siana są dobrze uformowane w UTF-8? (Przy znakach o różnych długościach bajtów, dobrze uformowana struktura narzuca pewne wymagania dotyczące wyrównania łańcucha między igłą a stogiem siana i umożliwia automatyczne przesunięcie o 2-4 bajty w przypadku napotkania niedopasowania bajtu głowy. Ale czy te ograniczenia kupują wiele / cokolwiek poza tym, co maksymalne obliczenia sufiksów, dobre przesunięcia sufiksów itp. już dają Ci różne algorytmy?)

Uwaga: dobrze znam większość dostępnych algorytmów, ale nie wiem, jak dobrze działają w praktyce. Oto dobre odniesienie, aby ludzie nie podawali mi referencji na temat algorytmów jako komentarzy / odpowiedzi: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Zbuduj bibliotekę testową prawdopodobnych igieł i stogów siana. Profiluj testy kilku algorytmów wyszukiwania, w tym brutalnej siły. Wybierz ten, który najlepiej sprawdza się z Twoimi danymi.

Boyer-Moore używa złej tabeli znaków z dobrą tabelą sufiksów.

Boyer-Moore-Horspool używa złej tabeli znaków.

Knuth-Morris-Pratt używa częściowej tabeli odpowiedników.

Rabin-Karp używa uruchomionych skrótów.

Wszyscy oni zamieniają się na mniejsze porównania w różnym stopniu, więc rzeczywiste wyniki będą zależeć od średniej długości igły i stogu siana. Im więcej początkowych narzutów, tym lepiej przy dłuższych wejściach. Przy bardzo krótkich igłach może wygrać brutalna siła.

Edytować:

Do znajdowania par zasad, wyrażeń angielskich lub pojedynczych słów może być najlepszy inny algorytm. Gdyby istniał jeden najlepszy algorytm dla wszystkich danych wejściowych, zostałby opublikowany.

Pomyśl o poniższej małej tabeli. Każdy znak zapytania może mieć inny najlepszy algorytm wyszukiwania.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

To naprawdę powinien być wykres z zakresem krótszych lub dłuższych danych wejściowych na każdej osi. Gdybyś wykreślił każdy algorytm na takim wykresie, każdy miałby inną sygnaturę. Niektóre algorytmy cierpią z powodu dużej liczby powtórzeń we wzorcu, co może wpływać na zastosowania takie jak wyszukiwanie genów. Niektóre inne czynniki, które wpływają na ogólną wydajność, obejmują wyszukiwanie tego samego wzorca więcej niż jeden raz i jednoczesne wyszukiwanie różnych wzorców.

Gdybym potrzebował przykładowego zestawu, myślę, że zeskrobałbym witrynę taką jak Google lub Wikipedia, a następnie usunąłbym kod HTML ze wszystkich stron wyników. W przypadku witryny wyszukiwania wpisz słowo, a następnie użyj jednego z sugerowanych wyszukiwanych słów. W razie potrzeby wybierz kilka różnych języków. Korzystając ze stron internetowych, wszystkie teksty byłyby krótkie lub średnie, więc połącz wystarczającą liczbę stron, aby uzyskać dłuższe teksty. Możesz również znaleźć książki należące do domeny publicznej, dokumenty prawne i inne duże zbiory tekstów. Lub po prostu generuj losową treść, wybierając słowa ze słownika. Ale celem profilowania jest sprawdzenie pod kątem rodzaju treści, które będziesz przeszukiwać, więc jeśli to możliwe, używaj próbek ze świata rzeczywistego.

Zostawiłem krótko i długo niejasne. Jeśli chodzi o igłę, myślę, że krótka ma mniej niż 8 znaków, średnia to mniej niż 64 znaki, a długość poniżej 1 tys. Jeśli chodzi o stóg siana, myślę, że krótki to mniej niż 2 ^ 10, średni - mniej niż 2 ^ 20, a długi - maksymalnie 2 ^ 30 znaków.

Wydany w 2011 roku wydaje mi się, że może to być algorytm „Prostego dopasowania ciągów w przestrzeni stałej w czasie rzeczywistym” autorstwa Dany'ego Breslauera, Roberto Grossiego i Filippo Mignosi.

Aktualizacja:

W 2014 roku autorzy opublikowali następujące ulepszenie: W kierunku optymalnego dopasowania upakowanych ciągów .

http://www-igm.univ-mlv.fr/~lecroq/string/index.html odwołuje wskazaniu jest doskonałym źródłem i podsumowanie niektóre z najbardziej znanych i badanych algorytmów dopasowywania smyczkowych.

Rozwiązania większości problemów związanych z wyszukiwaniem obejmują kompromisy związane z narzutem wstępnego przetwarzania, wymaganiami czasowymi i przestrzennymi. Żaden pojedynczy algorytm nie będzie optymalny ani praktyczny we wszystkich przypadkach.

Jeśli Twoim celem jest zaprojektowanie określonego algorytmu wyszukiwania ciągów, zignoruj ​​resztę tego, co mam do powiedzenia, jeśli chcesz opracować uogólnioną procedurę wyszukiwania ciągów znaków, spróbuj wykonać następujące czynności:

Poświęć trochę czasu na przejrzenie konkretnych mocnych i słabych stron algorytmów, do których już się odnosisz. Przeprowadź przegląd w celu znalezienia zestawu algorytmów obejmujących zakres i zakres wyszukiwań ciągów, które Cię interesują. Następnie zbuduj selektor wyszukiwania interfejsu użytkownika w oparciu o funkcję klasyfikatora, aby wskazać najlepszy algorytm dla danych wejściowych. W ten sposób możesz zastosować najbardziej wydajny algorytm do wykonania zadania. Jest to szczególnie skuteczne, gdy algorytm jest bardzo dobry w przypadku niektórych wyszukiwań, ale słabo się psuje. Na przykład brutalna siła jest prawdopodobnie najlepsza w przypadku igieł o długości 1, ale szybko ulega degradacji wraz ze wzrostem długości igły, po czym algoritim sustik-mooremogą stać się bardziej wydajne (w przypadku małych alfabetów), wtedy dla dłuższych igieł i większych alfabetów algorytmy KMP lub Boyer-Moore mogą być lepsze. To tylko przykłady ilustrujące możliwą strategię.

Podejście oparte na wielu algorytmach nie jest nowym pomysłem. Wydaje mi się, że był używany przez kilka komercyjnych pakietów Sort / Search (np. SYNCSORT powszechnie używany na komputerach mainframe implementuje kilka algorytmów sortowania i używa heurystyki, aby wybrać „najlepszy” dla danych wejściowych)

Każdy algorytm wyszukiwania występuje w kilku odmianach, które mogą znacząco różnić się jego wydajnością, jak na przykład w tym artykule ilustruje .

Porównaj swoją usługę, aby skategoryzować obszary, w których potrzebne są dodatkowe strategie wyszukiwania, lub aby bardziej efektywnie dostroić funkcję selektora. To podejście nie jest szybkie ani łatwe, ale jeśli zostanie wykonane dobrze, może przynieść bardzo dobre wyniki.

Byłem zaskoczony, widząc nasz raport techniczny cytowany w tej dyskusji; Jestem jednym z autorów algorytmu, który powyżej nazwano Sustik-Moore. (Nie używaliśmy tego terminu w naszym artykule).

Chciałem tutaj podkreślić, że dla mnie najbardziej interesującą cechą algorytmu jest to, że dość łatwo jest udowodnić, że każda litera jest badana najwyżej raz. W przypadku wcześniejszych wersji Boyer-Moore udowodnili, że każdy list jest badany najwyżej 3, a później najwyżej 2 razy, a dowody te były bardziej skomplikowane (patrz cytaty w artykule). Dlatego też dostrzegam wartość dydaktyczną w przedstawianiu / studiowaniu tego wariantu.

W artykule opisujemy również dalsze warianty, które są ukierunkowane na efektywność, jednocześnie zmniejszając gwarancje teoretyczne. Jest to krótka praca, a materiał moim zdaniem powinien być zrozumiały dla przeciętnego maturzysty.

Naszym głównym celem było zwrócenie uwagi na tę wersję innym, którzy mogą ją dalej ulepszać. Przeszukiwanie ciągów znaków ma tak wiele odmian i sami nie jesteśmy w stanie wymyślić wszystkich, w których ten pomysł mógłby przynieść korzyści. (Stały tekst i zmieniający się wzorzec, stały wzorzec inny tekst, przetwarzanie wstępne możliwe / niemożliwe, wykonywanie równoległe, znajdowanie pasujących podzbiorów w dużych tekstach, zezwalanie na błędy, bliskie dopasowania itp.)

Najszybszy algorytm wyszukiwania podciągów będzie zależał od kontekstu:

1. wielkość alfabetu (np. DNA vs angielski)
2. długość igły

Artykuł z 2010 r. „The Exact String Matching Problem: a Comprehensive Experimental Evaluation” podaje tabele z czasem wykonywania dla 51 algorytmów (z różnymi rozmiarami alfabetu i długościami igieł), dzięki czemu można wybrać najlepszy algorytm do swojego kontekstu.

Wszystkie te algorytmy mają implementacje C, a także zestaw testów, tutaj:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Naprawdę dobre pytanie. Po prostu dodaj małe kawałki ...

1. Ktoś mówił o dopasowywaniu sekwencji DNA. Ale w przypadku sekwencji DNA zwykle budujemy strukturę danych (np. Tablicę sufiksów, drzewo sufiksów lub indeks FM) dla stogu siana i dopasowujemy do niej wiele igieł. To jest inne pytanie.

2. Byłoby naprawdę świetnie, gdyby ktoś chciał porównać różne algorytmy. Istnieją bardzo dobre testy porównawcze dotyczące kompresji i konstrukcji tablic przyrostków, ale nie widziałem testu porównawczego dopasowywania ciągów. Potencjalni kandydaci na stóg siana mogą pochodzić z testu porównawczego SACA .

3. Kilka dni temu testowałem implementację Boyer-Moore ze strony, którą poleciłeś (EDYCJA: potrzebuję wywołania funkcji jak memmem (), ale nie jest to funkcja standardowa, więc zdecydowałem się ją zaimplementować). Mój program do testów porównawczych wykorzystuje losowy stóg siana. Wygląda na to, że implementacja Boyer-Moore na tej stronie jest razy szybsza niż memmem () glibc i strnstr () Maca. Jeśli jesteś zainteresowany, implementacja jest tutaj, a kod do testów porównawczych jest tutaj . To zdecydowanie nie jest realistyczny punkt odniesienia, ale to początek.

Wiem, że to stare pytanie, ale większość złych tabel zmian to pojedynczy znak. Jeśli ma to sens dla twojego zbioru danych (np. Szczególnie jeśli jest to napisane słowa) i jeśli masz dostępne miejsce, możesz uzyskać dramatyczne przyspieszenie, używając złej tabeli zmiany biegów złożonej z n-gramów, a nie pojedynczych znaków.

Użyj stdlib strstr:

char *foundit = strstr(haystack, needle);

Było bardzo szybkie, pisanie zajęło mi tylko około 5 sekund.

Oto implementacja wyszukiwania w Pythonie , używana w całym rdzeniu. Komentarze wskazują, że używa skompresowanej tabeli boyer-moore delta 1 .

Sam przeprowadziłem dość obszerne eksperymenty z wyszukiwaniem ciągów, ale dotyczyło to wielu ciągów wyszukiwania. Implementacje asemblacyjne Horspool i Bitap często radzą sobie z algorytmami takimi jak Aho-Corasick o małą liczbę wzorców.

Szybszy strchralgorytm „Wyszukaj jeden pasujący znak” (ala ).

Ważne notatki:

• Te funkcje używają gcckompilatora wewnętrznego „liczba / liczba (wiodących | końcowych) zer” kompilatora __builtin_ctz. Te funkcje będą prawdopodobnie działać szybko tylko na maszynach, które mają instrukcje, które wykonują tę operację (np. X86, ppc, arm).

• Te funkcje zakładają, że architektura docelowa może wykonywać niewyrównane obciążenia 32- i 64-bitowe. Jeśli twoja docelowa architektura tego nie obsługuje, będziesz musiał dodać trochę logiki startowej, aby odpowiednio wyrównać odczyty.

• Te funkcje są niezależne od procesora. Jeśli docelowy procesor ma instrukcje wektorowe, możesz zrobić (znacznie) lepiej. Na przykład strlenponiższa funkcja używa SSE3 i może być w prosty sposób zmodyfikowana do XOR skanowanych bajtów w celu wyszukania bajtu innego niż 0. Testy porównawcze przeprowadzone na laptopie 2,66 GHz Core 2 z systemem Mac OS X 10.6 (x86_64):

  • 843,433 MB / s dla strchr
  • 2656,742 MB / s dla findFirstByte64
  • 13094,479 MB / s dla strlen

... wersja 32-bitowa:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... i wersja 64-bitowa:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Edycja 2011/06/04 OP zwraca uwagę w komentarzach, że to rozwiązanie ma „błąd nie do przezwyciężenia”:

może czytać poza poszukiwanym bajtem lub zakończeniem zerowym, który mógłby uzyskać dostęp do niezamapowanej strony lub strony bez prawa odczytu. Po prostu nie możesz używać dużych odczytów w funkcjach łańcuchowych, chyba że są wyrównane.

Jest to technicznie prawda, ale dotyczy praktycznie każdego algorytmu, który działa na fragmentach większych niż jeden bajt, w tym metody sugerowanej przez OP w komentarzach:

Typowa strchrimplementacja nie jest naiwna, ale trochę wydajniejsza niż to, co podałeś. Zobacz koniec tego, aby zapoznać się z najczęściej używanym algorytmem: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

To też naprawdę nie ma nic wspólnego z wyrównaniem jako takim . To prawda, może to potencjalnie spowodować zachowanie omówione na większości powszechnie używanych architektur, ale ma to więcej wspólnego ze szczegółami implementacji mikroarchitektury - jeśli niewyrównany odczyt przekracza granicę 4K (znowu, typowo), to odczyt spowoduje program przerywanie błędu, jeśli następna granica strony 4K nie jest odwzorowana.

Ale to nie jest „błąd” w algorytmie podanym w odpowiedzi - takie zachowanie jest spowodowane tym, że funkcje lubią strchri strlennie akceptują lengthargumentu ograniczającego rozmiar wyszukiwania. Wyszukiwanie char bytes[1] = {0x55};, które dla celów naszej dyskusji tak się składa, że ​​znajduje się na samym końcu granicy strony maszyny wirtualnej 4K, a następna strona nie jest odwzorowana, z strchr(bytes, 0xAA)(gdzie strchrjest implementacja bajt po czasie), zakończy się dokładnie ta sama droga. To samo dotyczy strchrpokrewnego kuzynastrlen .

Bez lengthargumentu nie ma sposobu, aby stwierdzić, kiedy należy wyłączyć szybki algorytm i wrócić do algorytmu bajt po bajcie. O wiele bardziej prawdopodobnym „błędem” byłoby odczytanie „przekraczającego rozmiar alokacji”, co technicznie skutkuje undefined behaviorzgodnie z różnymi standardami języka C i zostałby oznaczony jako błąd przez coś podobnego valgrind.

Podsumowując, wszystko, co działa na fragmentach większych niż bajty, działa szybciej, jak ten kod odpowiada i kod wskazany przez OP, ale musi mieć semantykę odczytu z dokładnością do bajtów, prawdopodobnie będzie „błędne”, jeśli nie ma lengthargumentu kontrolować narożne przypadki „ostatniego odczytu”.

Kod w tej odpowiedzi jest jądrem umożliwiającym szybkie znalezienie pierwszego bajtu w porcji o naturalnym rozmiarze słowa procesora, jeśli docelowy procesor ma ctzinstrukcje podobne do szybkich . Dodanie takich rzeczy, jak upewnienie się, że działa tylko na prawidłowo wyrównanych granicach naturalnych lub jakiejś formie lengthograniczenia, które pozwoliłoby na wyjście z szybkiego jądra do wolniejszego sprawdzania bajt po bajcie, jest trywialne .

PO stwierdza również w komentarzach:

Jeśli chodzi o optymalizację ctz, ma to znaczenie tylko dla operacji ogona O (1). Mogłoby to poprawić wydajność przy małych strunach (np. strchr("abc", 'a');Ale na pewno nie przy strunach o dowolnym większym rozmiarze.

To, czy to stwierdzenie jest prawdziwe, zależy w dużej mierze od danej mikroarchitektury. Używając kanonicznego 4-stopniowego modelu potoku RISC, jest to prawie na pewno prawda. Jednak niezwykle trudno jest stwierdzić, czy jest to prawdą w przypadku współczesnego niesprawnego superskalarnego procesora, w którym prędkość rdzenia może całkowicie przyćmić szybkość przesyłania strumieniowego pamięci. W tym przypadku jest nie tylko prawdopodobne, ale dość powszechne, że istnieje duża luka w „liczbie instrukcji, które można wycofać” w stosunku do „liczby bajtów, które mogą być przesyłane strumieniowo”, tak że masz „ liczba instrukcji, które można wycofać dla każdego bajtu, który może być przesyłany strumieniowo ”. Jeśli jest wystarczająco duży, instrukcję ctz+ shift można wykonać „za darmo”.

Po prostu wyszukaj „najszybszy strstr”, a jeśli zobaczysz coś interesującego, zapytaj mnie.

Moim zdaniem nakładasz na siebie zbyt wiele ograniczeń (tak, wszyscy chcemy subliniowej liniowości w wyszukiwarce max), jednak potrzeba prawdziwego programisty, aby wkroczyć, do tego czasu myślę, że podejście hash jest po prostu sprytnym rozwiązaniem ( dobrze wzmocniony przez BNDM dla krótszych wzorów 2..16).

Tylko krótki przykład:

Przeprowadzenie wyszukiwania wzorca (32bytes) do STRING (206908949bytes) AS-jednej linii ... Skip-Performance (większy-the-lepiej): 3.041% 6801754 przeskakuje / iteracji Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade wydajność: 3483KB / zegar

Przeprowadzenie wyszukiwania wzorca (32bytes) do STRING (206908949bytes) AS-jednego wiersza ... Pomiń wydajność (większa-the-lepsze): 1554%, 13307181 przeskakuje / iteracji Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg Osiągi: 2434KB / zegar

Wykonywanie wyszukiwania wzorca (32 bajty) w łańcuch (206908949 bajtów) jako jeden wiersz ... Pomiń wydajność (większy tym lepszy): 129%, 160239051 pomija / iteracje Dwukierunkowe_hits / Dwukierunkowe_ zegary: 0/816 Dwa -Way wydajność: 247KB / zegar

Sanmayce,
Pozdrawiam

Algorytm dwukierunkowy, o którym wspominasz w swoim pytaniu (który, nawiasem mówiąc, jest niesamowity!) Został niedawno ulepszony, aby wydajnie działał na wielobajtowych słowach naraz: Optymalne dopasowywanie upakowanych ciągów .

Nie przeczytałem całego artykułu, ale wygląda na to, że polegają na kilku nowych, specjalnych instrukcjach procesora (zawartych np. W SSE 4.2), które są O (1) dla ich złożoności czasowej, chociaż jeśli nie są dostępne, mogą symuluj je w czasie O (log log w) dla słów w-bitowych, które nie brzmią zbyt źle.

Możesz zaimplementować, powiedzmy, 4 różne algorytmy. Co M minut (do ustalenia empirycznie) uruchom wszystkie 4 na bieżących rzeczywistych danych. Gromadzenie statystyk dotyczących N przebiegów (również do ustalenia). Następnie wykorzystaj tylko zwycięzcę przez następne M minut.

Loguj statystyki wygranych, aby móc zastąpić algorytmy, które nigdy nie wygrywają, nowymi. Skoncentruj wysiłki optymalizacyjne na najlepszej rutynie. Zwróć szczególną uwagę na statystyki po wszelkich zmianach w sprzęcie, bazie danych lub źródle danych. Jeśli to możliwe, uwzględnij te informacje w dzienniku statystyk, dzięki czemu nie będziesz musiał ich odczytywać na podstawie daty / sygnatury czasowej dziennika.

Niedawno odkryłem fajne narzędzie do pomiaru wydajności różnych dostępnych alg: http://www.dmi.unict.it/~faro/smart/index.php

Może ci się to przydać. Ponadto, gdybym musiał szybko wywołać algorytm wyszukiwania podciągów, wybrałbym Knuth-Morris-Pratt.

Możesz również chcieć mieć różne testy porównawcze z kilkoma typami ciągów, ponieważ może to mieć duży wpływ na wydajność. Algosy będą wykazywać różnicę w oparciu o wyszukiwanie w języku naturalnym (i nawet tutaj nadal mogą istnieć drobnoziarniste rozróżnienia ze względu na różne morfologie), ciągi DNA lub przypadkowe ciągi itp.

Rozmiar alfabetu będzie odgrywał rolę w wielu algach, podobnie jak rozmiar igły. Na przykład Horspool radzi sobie dobrze z tekstem w języku angielskim, ale źle z DNA z powodu różnej wielkości alfabetu, co utrudnia życie dla zasady złych znaków. Wprowadzenie przyrostka good-suix znacznie to ułatwia.

Nie wiem, czy to absolutnie najlepsze, ale mam dobre doświadczenia z Boyer-Moore .

To nie odpowiada bezpośrednio na pytanie, ale jeśli tekst jest bardzo duży, co powiesz na podzielenie go na zachodzące na siebie sekcje (nakładanie się na długość wzoru), a następnie przeszukiwanie sekcji za pomocą wątków. Jeśli chodzi o najszybszy algorytm, myślę, że Boyer-Moore-Horspool jest jednym z najszybszych, jeśli nie najszybszym spośród wariantów Boyer-Moore. W tym temacie zamieściłem kilka wariantów Boyer-Moore (nie znam ich nazwy) Algorytm szybszy niż wyszukiwanie BMH (Boyer – Moore – Horspool) .

Najszybszy jest obecnie EPSM autorstwa S. Faro i OM Kulekciego. Zobacz http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

„Dokładne dopasowanie spakowanych ciągów” zoptymalizowane pod kątem SIMD SSE4.2 (x86_64 i aarch64). Działa stabilnie i najlepiej we wszystkich rozmiarach.

Witryna, z którą się połączyłem, porównuje 199 algorytmów szybkiego wyszukiwania ciągów znaków, przy czym te zwykłe (BM, KMP, BMH) działają dość wolno. EPSM przewyższa wszystkie inne wymienione tutaj na tych platformach. To także najnowsze.