Algoritm de potrivire a modelelor pe șiruri
În informatică , algoritmii de potrivire a modelelor pe șiruri , numiți uneori algoritmi de comparație a șirurilor sau algoritmi de căutare a șirurilor , sunt o clasă importantă de algoritmi de șiruri care încearcă să localizeze o poziție într-un șir mai mare sau într-un text, în care unul sau mai multe șiruri de obicei mai mici ( numite și tipare ) se găsesc.
Fie Σ un alfabet (format din elemente aparținând unui set finit ). În mod formal, atât modelul căutat, cât și textul căutat sunt vectori elementari ai lui Σ. Σ poate fi un alfabet uman comun (de exemplu, literele de la A la Z din alfabetul latin). Alte aplicații pot utiliza un alfabet binar (Σ = {0,1}) sau un alfabet ADN (Σ = {A, C, G, T}) în bioinformatică .
În practică, modul în care sunt codate șirurile poate afecta fezabilitatea algoritmilor de căutare a șirurilor. În special, dacă folosim o codificare cu lungime variabilă, atunci algoritmul va fi lent (în termeni de timp proporțional cu N) pentru a găsi caracterul N. Acest lucru va încetini semnificativ mulți dintre algoritmii de căutare mai avansați. O soluție posibilă este, în schimb, să căutăm secvența unităților de cod ( cuvânt de cod ): acest lucru ar putea produce totuși accesări false dacă codificarea nu a fost special concepută pentru a le evita.
Clasificări de bază
Diferitele algoritmi pot fi clasificate în funcție de numărul de modele pe care le folosesc.
Algoritmi care utilizează un singur model
Fie m lungimea modelului și n lungimea textului care trebuie căutat.
| Algoritm | Timpul de preprocesare | Timp de meci 1 |
|---|---|---|
| Algoritm naiv de căutare a șirurilor | 0 (fără preprocesare) | Θ ((n-m + 1) m) |
| Algoritm de căutare șir Rabin-Karp | Θ (m) | medie Θ (n + m), foarte rău Θ ((n-m + 1) m) |
| Cercetări bazate pe automat cu stare finită | Θ (m | Σ |) | Θ (n) |
| Algoritm Knuth-Morris-Pratt | Θ (m) | Θ (n) |
| Algoritm de căutare a șirurilor Boyer-Moore | Θ (m + | Σ |) | Ω (n / m), O (n) |
| Algoritm Bitap ( shift-or , shift-and , Baeza - Yates - Gonnet ) | Θ (m + | Σ |) | O (mn) |
1 Notarea asimptotică a timpilor este exprimată folosind notația O, Ω și Θ
Algoritmul Boyer-Moore de căutare a șirurilor a fost referința standard în literatură ca aplicație practică a căutării șirurilor. [1]
Algoritmi care utilizează un set de modele
Algoritmi care utilizează un număr infinit de tipare
Evident, tiparele nu pot fi cuantificate numeric în acest caz. Ele sunt de obicei reprezentate printr-o gramatică obișnuită sau o expresie regulată .
Alte clasificări
Sunt posibile și alte abordări de clasificare. Una dintre cele mai frecvente utilizări preprocesare ca principal criteriu.
| Text neprelucrat | Text preprocesat | |
|---|---|---|
| Tipare neprelucrate | Algoritmi elementari | Metode cu indici |
| Modele preprocesate | Motoare de căutare construite | Metode de semnătură |
Căutați corzi Naïve
Cel mai simplu și cel mai puțin eficient mod de a găsi aparițiile unui șir în altul este să verificați dacă pentru fiecare poziție, una câte una, apare apariția tuturor caracterelor. Deci, în primul rând, să vedem dacă există o apariție a primului caracter al modelului în primul caracter al textului, altfel îl căutăm în al doilea caracter al textului, altfel în al treilea și așa mai departe; odată ce a fost găsită apariția primului caracter al modelului în text, apariția celorlalte caractere ale modelului trebuie să apară și secvențial, altfel este posibil să căutați aparițiile caracterelor modelului din primul, în caracterul textului următor. În mod normal, va fi suficient să vă uitați la unul sau două caractere înainte de a determina o poziție din text ca fiind greșită, deci în cazul de mijloc algoritmul Naïve folosește pași O ( n + m ), unde n este dimensiunea textului și m lungimea modelului; dar, în cel mai rău caz, de exemplu, căutarea unui model precum „aaaab” într-un text precum „aaaaaaaaaaab” va face pași O ( nm ) (complexitate subcadrată).
Cercetări bazate pe un automat cu stare finită
În această abordare, evităm să verificăm același caracter de mai multe ori, o operație care ar pierde timpul, prin construirea unui automat deterministic de stare finită (DFA) care recunoaște șirurile care conțin șirul dorit de căutat. Automatele sunt complexe de construit - de obicei sunt create folosind construcția de subseturi - dar invers sunt foarte rapide de utilizat. De exemplu, automatul din dreapta recunoaște cuvântul „MOMIE”. Această abordare este frecvent generalizată în practică pentru a căuta expresii regulate arbitrare.
Căutare trunchiată
Knuth-Morris-Pratt calculează un DFA care recunoaște șirul care trebuie căutat ca sufix ca intrare, Boyer-Moore începe căutarea derulând textul și modelul în sens invers, de la dreapta la stânga, astfel încât, de obicei, reușește să sară întreaga dimensiune a modelului.fiecare pas dacă acest lucru nu se potrivește cu textul. Baeza-Yates înregistrează dacă caracterele j anterioare erau un prefix al șirului căutat și, prin urmare, este adaptabil algoritmilor de căutare fuzzy . Algoritmul Bitap este o aplicație a abordării Baeza-Yates.
Metode cu indici
Cei mai rapizi algoritmi de căutare se bazează pe preprocesarea textului. După construirea unei structuri de date numită index de sub șir , cum ar fi un arbore de sufixe sau o matrice de sufixe , aparițiile modelului pot fi găsite rapid. De exemplu, un arbore de sufix poate fi construit în timp Θ ( n ) și toate aparițiile Ζ ale modelului pot fi găsite în timp O ( m + Ζ ) (dacă considerăm dimensiunea alfabetului ca o constantă).
Căutați în texte comprimate
Algoritmii de căutare a șirurilor din fișierele comprimate se numesc algoritmi de potrivire a modelelor pe șirurile comprimate (în engleză Compressed pattern matching ).
Problemă de aliniere a cuvintelor cod
Dacă fișierul este comprimat cu o codificare cu lungime variabilă, există o problemă legată de alinierea unităților de codificare, numită cuvinte de cod (problemă cunoscută în limba engleză sub numele de „ trecerea limitelor cuvintelor de cod ”): apare atunci când există cuvinte de cod care sunt, de asemenea, conținute în interiorul celorlalte cuvinte de cod (sau „încrucișate” între mai multe cuvinte de cod consecutive); să presupunem, de exemplu, că caracterul a are codarea "100" și că caracterul b are codarea "110100", în acest caz codificarea lui a este un sufix al codificării lui b . Acest lucru dă naștere la așa-numitele potriviri false : atunci când algoritmul de căutare a șirurilor caută o apariție a , ar putea de fapt să returneze o poziție corespunzătoare codificării lui b . Este întotdeauna posibilă decodarea (și apoi decomprimarea) întregului text comprimat pentru a verifica dacă apariția modelului comprimat corespunde de fapt cu o apariție a modelului decomprimat, dar această practică trebuie evitată întrucât necesită spațiu și timp suplimentar pentru decompresie, pretenție excesivă, în special având în vedere fișierele comprimate disponibile online. Există diverse strategii care pot fi adoptate pentru a identifica cu încredere limitele cuvintelor de cod și a evita decompresia totală, de exemplu:
- Lista indexului inițial al fiecărei cuvinte de cod, căutabilă prin căutare binară;
- Lista inițială a indexului fiecărei cuvinte de cod cu codificare diferențială, pentru a ocupa mai puțin spațiu în interiorul fișierului;
- Mască de biți, unde bitul 1 indică bitul de pornire al fiecărei cuvinte de cod;
- Subdivizarea în blocuri pentru decompresia vizată parțială ulterioară.
Alte variante
Unele metode de cercetare, cum ar fi căutarea trigramelor , sunt concepute pentru a găsi răspunsul (potrivirea) „cel mai bun”, cel mai apropiat de potrivirea exactă dintre model și text, în loc să returneze doar rezultatul „potrivire / nu se potrivește” . Acestea sunt de obicei numite căutări neclare .
Notă
- ^(EN) Hume and Sunday (1991) [Căutare rapidă a șirurilor] SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 21 (11), 1221-1248 (NOIEMBRIE 1991)
Bibliografie
- ( EN ) RS Boyer și JS Moore, Un algoritm de căutare rapidă a șirurilor , Carom. ACM 20, (10), 262-272 (1977).
- (EN) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein .Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capitolul 32: Corelarea corzilor, pp. 906-932.
- ( EN ) Shmuel T. Klein și Dana Shapira PATTERN MATCHING IN HUFFMAN ENCODED TEXTTS (2003)
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe algoritmul de potrivire a modelelor pe șiruri
linkuri externe
- ( EN ) Listă imensă (menținută) de legături de potrivire a modelelor , pe cs.ucr.edu .
- ( EN ) StringSearch - algoritmi de potrivire a modelelor de înaltă performanță în Java - Implementări ale multor algoritmi de potrivire a șirurilor în Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
- ( EN )Algoritmi de potrivire a șirurilor exacte - animație în Java, descriere detaliată și implementare C a multor algoritmi.
- (EN) Boyer-Moore-Raita-Thomas , de la concentric.net. Adus la 17 decembrie 2012 (arhivat din original la 30 iunie 2007) .
- ( EN ) (PDF) Îmbunătățirea potrivirii unice și multiple a șirurilor aproximative ( PDF ), su cs.ucr.edu .
- (EN) Kalign2: aliniere multiplă de înaltă performanță a secvențelor de proteine și nucleotide Permițând caracteristici externe pe ncbi.nlm.nih.gov.
