Masek și Paterson [Masek, Paterson, 1980] utilizat pentru procedura de calcul a distanței dintre rândurile lui Wagner și abordarea Fischer patru rus (Arlazarova, Diniz, Kronrod și Faradzheva [Arlazarov, Dinic, Kronrod, Faradzev, 1970]) pentru a se obține algoritmul rulare în timp O (n 2 / log n). Este descris mai jos.
distanțele d matrice este împărțită într-o multitudine de submatricile pătrate cu suprapunere vectori marginale. Submatrice (i, j, p) este definit ca o submatrice de dimensiune (p + 1) * (p + 1), elementul din stânga sus este di, j. Din definiția (11) a intrărilor matricei d că valorile submatricea (i, j, p) sunt scoase din subșirurilor respective sale x (i + 1, i + p) și y (j + 1, j + p) și vectorii inițiali, adică rândul de sus (di, j. di, j + 1, ... di, j + p), iar coloana din stânga (di, j. di + 1, j. di + p, j).
În prima etapă a algoritmului sunt calculate valorile finale ale vectorilor, adică rândul de jos și o coloană din dreapta pentru fiecare submatricile posibile (i, j, p) pentru orice matrice d și valoarea datelor alfabet funcție. Acest lucru necesită listarea tuturor submatricile, ce doriți o listă cu toate combinațiile posibile ale subșirurilor și vectorilor inițiali. Pentru a lista toate posibilele siruri de lungime p, trebuie să presupunem că alfabetul este finit. Mai mult, încercările de a enumera toate posibile vector inițial poate fi interzisă. Cu toate acestea, editarea limitată a prețurilor, astfel încât acestea să devină multipli integrantă a unor numere reale va conduce la faptul că acestea vor fi doar un număr finit de diferențe între valorile succesive ale d pentru toate matrici la distanță folosind același alfabet și funcția de preț. Este mult mai practic să folosim aceste diferențe decât valorile absolute. Prin determinarea pas ca diferență între oricare două orizontal sau vertical elementele adiacente ale matricelor, obținem următoarele reguli de investigare (11) pentru calcul di, j:
Fiecare submatrice poate astfel deduce subșirurile respective x (i + 1, i + p) și y (j + 1, j + p), valoarea inițială a di, j. iar vectorii inițiali - un rând superior (di, j + 1. - di, j di, j + p - di, j + p-1) și prima coloană (di + 1, j - di, j ..., di + p. , j-di + p-1, j). Enumerarea tuturor submatricile posibile poate fi realizată prin enumerarea tuturor perechilor de rânduri de lungime p peste un alfabet finit C, și toate perechile de vectori de pași lungime p.
Algoritmul de calcul a tuturor submatricile prezentate în Figura 17. Rândurile de lungime p și lungimea etapelor p vector în ordine alfabetică, presupunând o ordonare fixă pe C și pe un set finit de valori posibile pas. pasul submatrice se calculează pentru fiecare pereche de linii u și v, și fiecare pereche de vectori inițial T pas și L, în conformitate cu (42). Pentru a facilita progresul ulterior, procedura de stocare stochează vectorii etapelor finale B și R, submatricul definit de u, v. T și L. În procedură se calculează matrice cu două trepte: V conține valorile pasului vertical și H - pasul orizontal.
Figura 17. Calcularea submatriculului în metoda Mashek-Paterson
Deoarece bucla interioară execută un timp constant și repetă exact p de 2 ori pentru fiecare pereche de șiruri și vectori de pas, fiecare submatrică este calculată în timp O (p 2). Numărul de perechi de linii de lungime p peste alfabet este de 2p. Dacă s este puterea acestui set de valori posibile ale treptei, pe care o vom presupune a fi finită, atunci există perechi de vectori pasi cu lungime p. Astfel, în toate (s *) 2p există submatricule diferite, care, în total, dau timpul de procesare O (p 2 (s * 2p).
Anterior, am anunțat că, cu restricții privind funcția de preț, setul de valori posibile posibile este finit. Să luăm în considerare această afirmație mai îndeaproape. Din regula pentru di, j și condițiile de graniță (11) - (12), putem observa că valorile pasului sunt limitate, indiferent de ce rânduri sunt luate în considerare:
Funcția de preț este numită rar. dacă fiecare membru al setului de ponderi de preț, și anume, este un multiplicator întreg al unor constante r. Pentru alfabetele finite, se poate arăta că dacă funcția de preț este redusă, atunci setul de valori pas obținute în matrice este finit, indiferent de rândurile specifice, ceea ce confirmă instrucțiunea anterioară.
Figura 18. Calculul distanței Masheka-Paterson
w (,) = w (a,) = w (a,) a w (, b) = w (, b)
Secvența actuală de editare a prețului minim poate fi obținută utilizând o metodă apropiată de căutare cu randamentele lui Wagner și Fisher. Editarea necesară pentru această distanță poate fi obținută fie prin recompunerea submatricilor prin care trece calea editării optime, fie prin stocarea submatricilor umplută în timpul calculărilor preliminare. Ultima abordare vă permite să definiți secvența de editare a matricelor umplută P și Q și submatricolele pre-calculate în timp liniar și necesită memorie O (n log 2 n) pentru stocarea submatricelor. Rețineți că matricile P și Q necesită fiecare câte unul (1 + m / p) * (1 + n / p) * p, care este O (n 2 / log n). Astfel, toată această metodă necesită memorie O (n 2 / log n).
Acest algoritm poate fi aplicat și problemei găsirii lcs (x, y) folosind funcția de preț dată de (15). Relația dintre d (x, y) și | l (x, y) |, definită prin expresia (16) permite apoi să se calculeze durata de timp lcs O (n 2 * log n). Lcs însuși poate fi obținut utilizând o metodă similară celei utilizate pentru obținerea secvenței de editare optimă.
S-a arătat că calculul distanțelor între linii folosind această metodă sunt asimptotic mai rapid decât pătratică metoda Wagner și Fischer. Cu toate acestea, în practică, câștigul real poate fi obținut numai pentru linii foarte lungi. Pentru a ilustra acest lucru, Masek și Paterson [Masek, Patterson, 1983] calculat că, pentru un alfabet și de stabilire a prețurilor funcții de editare distanță binară, cea mai bună eficiență este atins numai pentru liniile a căror lungime este mai mare decât 262418.
Trimiteți-le prietenilor: