Cel mai lung subșir comun (LCS)
Când comparați două versiuni ale unui fișier, liniile care nu s-au schimbat formează un subșir comun al ambelor. Găsirea celui mai lung vă spune exact ce a fost adăugat și ce a fost eliminat. Aceeași idee aliniază catene de ADN și sugerează corecturi ortografice, iar problema se rezolvă cu unul dintre cele mai elegante tabele din informatică.
Problema
Un subșir al unui cuvânt păstrează unele dintre literele lui în ordinea inițială: ACE este un subșir al lui ABCDE, dar EA nu este. Un subșir comun a două cuvinte este un subșir al amândurora, iar problema este găsirea celui mai lung. Un cuvânt de lungime n are 2ⁿ subșiruri, așa că încercarea tuturor este fără speranță dincolo de câteva litere.
Tabelul
Fie len[i][j] lungimea celui mai lung subșir comun al primelor i litere ale unui cuvânt și al primelor j litere ale celuilalt. Un cuvânt gol nu are nimic în comun cu nimic, deci primul rând și prima coloană sunt 0. Dacă litera i este egală cu litera j, len[i][j] = len[i − 1][j − 1] + 1: potrivirea prelungește ceea ce a fost înaintea ei. Altfel, len[i][j] este valoarea mai mare dintre len[i − 1][j] și len[i][j − 1]: se renunță la una dintre cele două litere și se păstrează rezultatul mai bun.
Un exemplu
Comparați ABCBDAB cu BDCABA. Prima literă a celui de-al doilea cuvânt, B, se potrivește cu B-ul de pe rândul 2; C-ul din a treia coloană se potrivește cu rândul 3 și așa mai departe, fiecare potrivire adăugând unu la celula din stânga sus. Celula din dreapta jos ajunge la 4. Citirea înapoi de acolo dă BCBA, dar BCAB și BDAB sunt la fel de lungi: un cel mai lung subșir comun nu trebuie să fie unic.
Citirea înapoi a răspunsului
Începeți din celula din dreapta jos. Dacă literele rândului și coloanei ei se potrivesc, acea literă face parte din răspuns: notați-o și mergeți în diagonală spre stânga sus. Altfel mergeți la vecina, de deasupra sau din stânga, cu valoarea mai mare, pentru că de acolo și-a luat celula valoarea. Opriți-vă la primul rând sau la prima coloană. Literele notate, în ordine inversă, formează subșirul.
Istorie și utilizări
Metoda tabelului a fost descoperită independent de mai multe persoane în jurul anului 1970, printre care Robert Wagner și Michael Fischer, al căror articol din 1974 a rezolvat problema strâns înrudită a distanței de editare. În 1975, Dan Hirschberg a arătat cum se poate găsi subșirul cu mult mai puțină memorie, iar în 1976 James Hunt și Douglas McIlroy au construit programul Unix diff pe baza celor mai lungi subșiruri comune de linii. Biologii folosesc aceeași idee, cu scoruri, pentru a alinia secvențe de ADN și de proteine.
Explorați
Deschideți aplicația și apăsați Pas. Cele două litere comparate se aprind în antete; la o potrivire se citește celula albastră din stânga sus, la o nepotrivire se citesc cele două celule albastre de deasupra și din stânga. Când tabelul este plin, drumul portocaliu urcă înapoi din colț, iar literele răspunsului apar sub tabel.
Întrebări frecvente
De cât timp și câtă memorie are nevoie algoritmul LCS?
Timp O(m·n) pentru cuvinte de lungimi m și n. Tabelul complet are nevoie și de memorie O(m·n) pentru a citi răspunsul înapoi; Dan Hirschberg a arătat în 1975 cum se găsește subșirul propriu-zis cu doar O(min(m, n)) memorie.
Cum folosește diff cel mai lung subșir comun?
Tratează fiecare linie a unui fișier ca pe un singur simbol și găsește un cel mai lung subșir comun al liniilor celor două fișiere. Liniile din acest subșir sunt neschimbate; celelalte linii ale fișierului vechi au fost șterse, iar celelalte linii ale fișierului nou au fost adăugate.
Dar pentru trei sau mai multe cuvinte?
Tabelul primește câte o dimensiune pentru fiecare cuvânt, deci trei cuvinte de lungime n au nevoie de n³ celule. Pentru un număr oarecare de cuvinte, problema este NP-dificilă.
Ce legătură are LCS cu distanța de editare?
Dacă sunt permise doar inserări și ștergeri, distanța de editare dintre două cuvinte este lungimea lor totală minus de două ori lungimea celui mai lung subșir comun al lor. Dacă se permit și înlocuiri, se obține distanța Levenshtein, calculată cu un tabel foarte asemănător.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați cel mai lung subșir comun