Algorytm Raity
W informatyce algorytm Raita to algorytm wyszukiwania ciągów , który poprawia wydajność algorytmu Boyera – Moore’a – Horspoola . Algorytm ten wstępnie przetwarza szukany ciąg znaków pod kątem wzorca, co jest podobne do algorytmu wyszukiwania ciągów Boyera-Moore'a . Schemat wyszukiwania konkretnego podciągu w danym ciągu różni się od algorytmu Boyera – Moore’a – Horspoola. Algorytm ten został opublikowany przez Timo Raitę w 1991 roku.
Opis
Algorytm Raita wyszukuje wzorzec „P” w danym tekście „T” porównując każdy znak wzorca w podanym tekście. Wyszukiwanie zostanie przeprowadzone w następujący sposób. Okno na tekst „T” definiuje się jako długość „P”.
- Najpierw porównywany jest ostatni znak wzorca z skrajnym prawym znakiem okna.
- Jeśli występuje dopasowanie, pierwszy znak wzorca jest porównywany z skrajnym lewym znakiem okna.
- Jeśli ponownie się zgadzają, porównuje środkowy znak wzorca ze środkowym znakiem okna.
Jeśli wszystko podczas wstępnej kontroli przebiegło pomyślnie, oryginalne porównanie rozpoczyna się od drugiego znaku do przedostatniego. Jeśli na którymkolwiek etapie algorytmu wystąpi niezgodność, wykonywana jest funkcja przesunięcia nieprawidłowego znaku, która została obliczona w fazie wstępnego przetwarzania. Zła funkcja przesunięcia znaku jest identyczna z proponowaną w algorytmie Boyera – Moore’a – Horspoola.
Nowoczesne sformułowanie podobnej kontroli wstępnej można znaleźć w std::string::find , liniowym/kwadratowym mechanizmie dopasowującym ciągi, w bibliotekach libc++ i libstdc++. Zakładając, że wersja memcmp jest dobrze zoptymalizowana , niepomijanie znaków w „oryginalnym porównaniu” jest zwykle bardziej wydajne, ponieważ prawdopodobnie wzorzec zostanie wyrównany.
Kod C dla algorytmu Raita
0 #include <limits.h> #include <stddef.h> #define ALPHABET_SIZE (1 << CHAR_BITS) /* zazwyczaj 256 */ /* Przetwarzanie wstępne: tabela złego dopasowania BMH. */ static inline void preBmBc ( char * pat , size_t lpat , ptrdiff_t bmBc []) { size_t i ; for ( i = ; i < ROZMIAR_ALFABETU ; ++ i
0
) bmBc [ i ] = lpat ; for ( i = ; i < lpat - 1 ; ++ i ) bmBc [ pat [ i ]] = lpat - i - 1 ; } void RAITA ( char * pat , size_t lpat , char * s ,
0
size_t n ) { ptrdiff_t bmBc [ ALPHABET_SIZE ]; /* Obudowy Quick Edge. */ if ( lpat == || lpat > n ) return ; if ( lpat == 1 ) { char * match_ptr = s ; podczas gdy ( match_ptr < s + n ) { match_ptr = 0
memchr ( match_ptr , pat [ ], n - ( match_ptr - s )); if ( match_ptr != NULL ) { WYJŚCIE ( match_ptr - s ); mecz_ptr ++ ; } inaczej zwróć ; } } preBmBc ( pat , lpat , bmBc ); /* Okno przedmeczowe. */
0
0
char FirstCh = pat [ ]; char środkowyCh = pat [ lpat / 2 ]; char lastCh = pat [ lpat - 1 ]; /* Wyszukiwanie */ ptrdiff_t j = ; podczas gdy ( jot <= n - m ) { char c = s [ jot + lpat -
1 ]; /* Może to zaszkodzić lokalizacji danych w przypadku długich wzorców. W tym przypadku należy rozważyć zmniejszenie * liczby testów wstępnych lub użycie większej liczby wskaźników klastrowych. */ if ( lastCh == c && środkowyCh == s [ j + lpat / 2 ] && pierwszyCh == s [ j ] && memcmp ( & pat [ 1 ], & s 0
[ j + 1 ], lpat - 2 ) == ) WYJŚCIE ( j ); j += bmBc [ do ]; } }
Przykład
Wzór: abdb
Tekst:abbaabaabddbabadbb
Etap wstępnego przetwarzania:
abd 4 3 1
Próba 1: abbaabaabddbabadbb ....b Przesunięcie o 4 (bmBc[a])
Porównanie ostatniego znaku wzorca ze znakiem znajdującym się najbardziej na prawo w oknie. Jest to niedopasowanie i zostało przesunięte o 4 zgodnie z wartością na etapie wstępnego przetwarzania.
Próba 2: abbaabaabddbabadbb Przesunięcie AdB o 3 (bmBc[b])
Tutaj ostatni i pierwszy znak wzorca są dopasowane, ale środkowy znak jest niezgodny. Zatem wzór jest przesuwany w zależności od etapu wstępnego przetwarzania.
Próba 3: abbaabaabddbabadbb ABDDB Przesunięcie o 3 (bmBc[b])
Znaleźliśmy tutaj dokładne dopasowanie, ale algorytm kontynuuje działanie, dopóki nie będzie mógł przejść dalej.
Próba 4: abbaabaABDDBabadbb ....b Przesunięcie o 4 (bmBc[a])
Na tym etapie musimy przesunąć wzór o 4, a nie możemy przesunąć wzoru o 4. Zatem algorytm się kończy. Litery pisane wielką literą są dokładnie zgodne ze wzorem w tekście.
Złożoność
- Etap wstępnego przetwarzania zajmuje czas O(m), gdzie „m” to długość wzoru „P”.
- Etap wyszukiwania zajmuje złożoność czasową O(mn), gdzie „n” to długość tekstu „T”.