Găsirea unui subșir într-un șir este una dintre cele mai simple sarcini de regăsire a informațiilor . Este folosit ca o funcție încorporată în editoarele de text , DBMS , motoarele de căutare , limbaje de programare etc.
În sarcinile de căutare, se obișnuiește în mod tradițional să se desemneze modelul de căutare ca ac (din engleză - „ac”) și șirul în care se efectuează căutarea ca un car de fân (din engleză - „ carul de fân ”). De asemenea, notăm cu Σ alfabetul pe care se efectuează căutarea.
Dacă presupunem că liniile sunt numerotate de la 1, cel mai simplu algoritm (algoritmul de forță brută engleză , algoritmul naiv ) arată așa.
pentru i=0...|car de fân|-|ac| pentru j=0...|ac| dacă carul de fân[i+j + 1]<>ac[j] apoi treci la 1 output("Găsit: ", i+1) unu:Cel mai simplu algoritm de căutare, chiar și în cel mai bun caz , efectuează | carul de fân |−| ac |+1 comparație; dacă sunt multe potriviri parțiale, viteza scade la O (| car de fân | · | ac |).
S-a dovedit că algoritmul primitiv completează în medie 2 ore comparații [1] .
Astăzi există o mare varietate de algoritmi de căutare subșiruri. Programatorul trebuie să aleagă pe cel potrivit în funcție de astfel de factori.
De regulă, într-un editor de text este suficient să luați cel mai simplu algoritm euristic precum Boyer - Moore - Horspool - chiar și un computer foarte lent va face față căutării într-o fracțiune de secundă. Dacă volumul de text este măsurat în gigaocteți, sau căutarea rulează pe un server care procesează multe solicitări, trebuie să alegeți cel mai de succes algoritm disponibil. De exemplu, programele de detectare a plagiatului efectuează verificări online folosind algoritmi de căutare subșirurilor într-un număr mare de documente stocate în propria lor bază de date.
Pentru concizie, notăm:
Complexitatea de calcul este determinată înainte de primul meci . Tipul aldine indică cei mai importanți algoritmi din punct de vedere practic.
În toți acești algoritmi, punctul în care „acul” nu a coincis cu „carul de fân” nu participă la decizie. Acest lucru vă permite să utilizați funcții standard pentru compararea zonelor de memorie , adesea optimizate la nivel de asamblare pentru un anumit procesor.
Din această categorie aparține și algoritmul de căutare primitivă.
| Nume | Preliminar tratament | Complexitate | Note | |
|---|---|---|---|---|
| tipic | Max. | |||
| Algoritmul primitiv | Nu | 2H _ | O ( Hn ) | |
| Algoritmul Boyer-Moore-Horspool | O ( n +σ) | ~ 2 H / σ [2] | O ( Hn ) | Algoritmul Boyer-Moore simplificat la limită; folosește doar o euristică modificată a simbolului de oprire - simbolul de oprire este întotdeauna luat drept simbolul carului de fân situat vizavi de ultimul simbol al acului . |
| Algoritm de căutare rapidă Algoritmul lui Sandy |
O ( n +σ) | < H | O ( Hn ) | De asemenea, folosește exclusiv euristica simbolului de oprire - dar simbolul de oprire este considerat simbolul carului de fân după ultimul simbol al acului . |
Această familie de algoritmi suferă de viteză scăzută pe datele „bune”, care este compensată de lipsa regresiei pe cele „rele”.
| Nume | Preliminar tratament | Complexitate | Note | |
|---|---|---|---|---|
| tipic | Max. | |||
| Algoritmul Rabin-Karp | O ( n ) | < H + n | O ( Hn ) | Hashingul poate reduce semnificativ complexitatea în medie |
| Algoritm automat Algoritmul Aho-Korasik |
O ( nσ ) | = H | Construiește o mașină de stări care recunoaște un limbaj format dintr-o singură linie. După o ușoară modificare, vă permite să găsiți o linie din mai multe într-o singură trecere cu carul de fân. | |
| Algoritmul Knuth-Morris-Pratt | O ( n ) | ≤ 2H | Unul dintre primii algoritmi cu estimare liniară în cel mai rău caz. O modificare a algoritmului Aho-Korasik care construiește un automat bazat implicit pe o funcție de prefix. | |
| Algoritmul lui Apostolico-Crochemore | O ( n ) | < H | ≤1,5H _ | |
| Algoritmul Shift-Sau Algoritmul Bitap Algoritmul binar |
O ( n +σ) | = H plafon ( n / w ) | Eficient dacă dimensiunea acului (în caractere) nu este mai mare decât dimensiunea cuvântului mașină (în biți, notat cu w ). Convertit cu ușurință în căutare aproximativă, căutare pe mai multe linii. | |
În această familie de algoritmi, acul se mișcă de-a lungul carului de fân de la stânga la dreapta, dar compararea acestor șiruri între ele se realizează de la dreapta la stânga. Comparația de la dreapta la stânga permite, în caz de nepotrivire, să se miște acul nu cu o poziție, ci cu mai multe.
| Nume | Preliminar tratament | Complexitate | Note | |
|---|---|---|---|---|
| tipic | Max. | |||
| Algoritmul Boyer-Moore | O ( n +σ) | < H | O ( Hn ) | Algoritmul standard pentru găsirea unui subșir într-un șir. Considerat cel mai eficient algoritm de uz general. [3] |
| Algoritmul Zhu-Takaoka | O ( n +σ²) | < H | O ( Hn ) | Algoritmul Boyer-Moore optimizat pentru alfabete scurte |
| Algoritmul lui Apostolico-Giancarlo | O ( n +σ) | < H | ≤1,5H _ | Una dintre primele încercări de a obține < H în cazul tipic și O ( H ) în cel mai rău caz. Foarte greu de implementat. |
| Algoritmul Turbo Boyer-Moore | O ( n +σ) | < H | ≤2H _ | Unul dintre cei mai eficienți algoritmi care nu dă regresie pe date „proaste”. |
| Nume | Preliminar tratament | Complexitate | Note | |
|---|---|---|---|---|
| tipic | Max. | |||
| Algoritm non-primitiv | const | < H | O ( Hn ) | Un algoritm simplu care compară al doilea caracter, începând apoi cu al treilea în modul cutie neagră și, în final, primul. Cu n [1]≠ n [2] [4] și nepotrivire la a doua sau a treia etapă - o deplasare cu 2 la dreapta. |
| Algoritmul lui Wright Algoritmul lui Boyer-Moore-Horspool-Wright |
O ( n +σ) | < H | O ( Hn ) | Un algoritm empiric optimizat pentru textele în limba engleză . Compară ultimul caracter, apoi primul, apoi mijlocul, apoi toate celelalte; în caz de nepotrivire, schimbarea Horspool. |
| Siruri de caractere | |
|---|---|
| Măsuri de similitudine a șirurilor | |
| Căutare subșir | |
| palindromuri | |
| Alinierea secvenței | |
| Structuri de sufix | |
| Alte | |