Transformarea Burrows -Wheeler [1] ( transformarea Burrows-Wheeler , BWT , numită istoric și compresie prin sortare bloc , deși nu este o compresie) este un algoritm utilizat în tehnicile de compresie a datelor pentru a transforma datele originale. BWT este folosit în arhivatorul bzip2 . Algoritmul a fost inventat de Michael Burrows și David Wheeler .
Termenul BWT este folosit și pentru a se referi la algoritmi completi de compresie care folosesc BWT ca unul dintre pași.
Schimbă ordinea caracterelor din șirul de intrare, astfel încât subșirurile repetate să formeze secvențe consecutive de caractere identice în ieșire. Astfel, combinația dintre BWT și RLE realizează sarcina de compresie de eliminare a subșirurilor repetate, o sarcină similară cu algoritmii LZ .
În plus, subșiruri ale textului de intrare care sunt aproape exact repetate (cu diferențe minore) produc secvențe ale acelorași caractere în ieșire, rareori intercalate cu alte caractere. Dacă după aceea efectuăm pasul de înlocuire a fiecărui caracter cu distanța până la întâlnirea anterioară (așa-numitul algoritm de mutare în față , MTF), atunci setul de numere rezultat va avea o distribuție statistică extrem de bună pentru aplicarea compresiei entropiei, cum ar fi Huffman sau aritmetica .
În practică, algoritmul de compresie BWT → MTF/RLE → Huffman utilizat în arhivatorul bzip2 depășește ușor cele mai bune implementări LZH în ceea ce privește calitatea compresiei la aceeași viteză.
Cea mai importantă problemă care trebuie rezolvată pentru a obține un algoritm BWT rapid este problema sortării șirurilor. În același timp, trebuie avut în vedere că unii algoritmi de sortare a șirurilor sunt extrem de dependenți de „succesul” datelor de intrare, funcționează rapid în majoritatea cazurilor, dar se degradează extrem de puternic în cazurile nereușite.
De exemplu, aceasta este în general o combinație destul de reușită „sortare găleată + qsort Sedgwick în fiecare găleată” pe textul de intrare ca o secvență lungă ABABABAB - sortarea găleților va crea 2 găleți pentru A și B, umplând fiecare cu șiruri aproape complet identice, după care qsort pe un astfel de set se va trage aproape pentru totdeauna.
În astfel de cazuri, este necesar să se întrerupă execuția algoritmului „prelungit” și să se treacă la un alt algoritm (sortare pe bază), care este mai rău în cazuri de succes, dar nu este supus degradării alunecării de teren.
Consumul de memorie al compresorului BWT se reduce în principal la alocarea unui buffer pentru porțiunea sortată în prezent a datelor de intrare, pentru o calitate bună a compresiei (profunzime bună de analiză) este de câțiva megaocteți, ceea ce depășește consumul de memorie al tuturor celorlalți părți ale compresorului.
Compresorul LZH (gzip în modul maxim) este puțin mai prost ca calitate a compresiei și aproximativ aceeași ca viteză, dar consumă mult mai puțină memorie.
Decompresorul BWT este mult mai rapid (viteză liniară) și nu consumă cantități semnificative de memorie, ceea ce îl deosebește de algoritmii PPM .
Să existe un text de intrare cu linii repetate (sau aproape repetate):
….VANYA…..VANYA….TANYA….MANYA…VANYA…
Când completați matricea BWT, aceasta va conține cu siguranță rânduri:
Când sortați o matrice, rândurile care încep cu același prefix ANYA vor fi grupate într-un grup strâns. Ultimele lor simboluri vor da o secvență de V, intercalate ocazional cu T și M.
După aplicarea MTF, obținem o secvență de zerouri, intercalate ocazional cu numere mici pentru T și M.
Când un șir de caractere este transformat folosind BWT, niciunul dintre caracterele acestuia nu este schimbat. Schimbă doar ordinea personajelor. Dacă șirul original are subșiruri care apar frecvent, atunci șirul transformat va avea câteva locuri în care un singur caracter este repetat de mai multe ori la rând. Acest lucru este util pentru compresie, deoarece facilitează comprimarea unui șir care constă din caractere repetate utilizând tehnici precum codificarea lungimii de rulare .
De exemplu, linia:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.CUTIIse transformă în acest șir, care se comprimă mai ușor deoarece conține o mulțime de caractere repetate:
TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIITTransformarea se face prin sortarea tuturor permutărilor ciclice ale rândului, apoi selectând ultima coloană din matricea rezultată. De exemplu, textul „.BANANA”. este transformat în „BNN.AA.A” utilizând acești pași (punctul roșu indică caracterul de final de linie ):
| Transformare | |||
|---|---|---|---|
| Intrare | Toate permutările |
Sortarea șirurilor |
Ieșire |
| .BANANA . | .BANANA . . .BANANĂ A. _ .BANANĂ NA . .BANA ANA . .INTERZICE N.A.N.A. _ .BA ANANA . .B banana . . | ANANA . .B ANA . .INTERZICE A. _ .BANANĂ banana . . N.A.N.A. _ .BA NA . .BANA .BANANA . . .BANANĂ | BNN.AA._ _ A |
Următorul pseudocod oferă o modalitate simplă, dar ineficientă de a calcula BWT și de a-l inversa. Se presupune că caracterul special de final de linie (EOL) nu apare în altă parte în text și este ignorat în timpul sortării.
funcția BWT ( șir de caractere ) creați o listă cu toate rotațiile posibile ale s fie fiecare rotație să fie un rând într-o masă mare, pătrată sortați rândurile tabelului în ordine alfabetică, tratând fiecare rând ca pe un șir returnează ultima coloană (din dreapta) a tabelului funcția inverseBWT( șir de caractere ) creați un tabel gol fără rânduri sau coloane repeta lungimi de ori inserați s ca o nouă coloană în partea stângă a tabelului sortați rândurile tabelului în ordine alfabetică returnează rândul care se termină cu caracterul „EOL”.Caracteristica distinctivă a BWT nu este că produce o ieșire mai ușor de codificat - multe operațiuni banale vă permit să faceți acest lucru - ci că este reversibilă , permițându-vă să restaurați documentul original din datele ultimei coloane.
Transformarea inversă poate fi ușor de înțeles după cum urmează. Luați ultimul tabel și ștergeți toate coloanele, cu excepția ultimei. Doar cu aceste informații, puteți restabili cu ușurință prima coloană. Ultima coloană conține toate caracterele textului, așa că prin sortarea lor, obținem prima coloană.
Apoi, prima și ultima coloană împreună vă oferă toate perechile de caractere din șir. Sortând lista de perechi, obținem prima și a doua coloană. Continuând în acest fel, puteți restabili lista completă. Apoi, linia cu „terminator” la sfârșit este linia originală. Inversând exemplul dat mai sus, obținem ceva de genul acesta:
| Transformare inversă | |||
|---|---|---|---|
| Intrare | |||
| BNN.AA._ _ A | |||
| Anexa 1 | Sortare 1 | Anexa 2 | Sortare 2 |
| B N N . A A . A | A A A B N N . . | BA N / A N / A .B UN UN . . A. _ | UN UN A. _ BA N / A N / A .B . . |
| Anexa 3 | Sortare 3 | Anexa 4 | Sortare 4 |
| INTERZICE NAN NA . .BA ANA ANA . .B A. _ . | ANA ANA A. _ . INTERZICE NAN NA . .BA . .B | BANA NANA NA . . .INTERZICE ANAN ANA . . .BA A. _ .B | ANAN ANA . A. _ .B BANA NANA NA . . .INTERZICE . .BA |
| Anexa 5 | Sortare 5 | Anexa 6 | Sortare 6 |
| banană N.A.N.A. _ NA . .B .BANA ANANA ANA . . . .INTERZICE A. _ .BA | ANANA ANA . . A. _ .BA banană N.A.N.A. _ NA . .B .BANA . .INTERZICE | Banană N.A.N.A. _ . NA . .BA .BANANĂ ANANA . ANA . .B _ .BANA A. _ .INTERZICE | ANANA . ANA . .B A. _ .INTERZICE Banană N.A.N.A. _ . NA . .BA .BANANĂ . .BANA |
| Anexa 7 | Sortare 7 | Anexa 8 | Sortare 8 |
| banana . N.A.N.A. _ .B NA . .INTERZICE .BANANĂ ANANA . . ANA . .B.A . .BANANĂ A. _ .BANA | ANANA . . ANA . .BA A. _ .BANA banana . N.A.N.A. _ .B NA . .INTERZICE .BANANĂ . .BANANĂ | banana . . N.A.N.A. _ .BA NA . .BANA .BANANA . ANANA . .B ANA . .BAN . .BANANĂ A. _ .BANANĂ | ANANA . .B ANA . .INTERZICE A. _ .BANANĂ banana . . N.A.N.A. _ .BA NA . .BANA .BANANA . . .BANANĂ |
| Rezultat | |||
| .BANANA . | |||
O serie de optimizări pot face acești algoritmi mai eficienți fără a modifica rezultatul. În BWT, nu este necesar să stocați întregul tabel în memorie, deoarece fiecare rând de tabel poate fi reprezentat printr-un pointer către o anumită poziție din rândul original. În BWT invers, nu este nevoie să stocați o masă sau să faceți mai multe feluri. Este suficient să sortați șirul o dată, folosind o sortare stabilă și să vă amintiți unde s-a mutat fiecare caracter. Acest lucru ne oferă o permutare circulară, care este suficientă pentru a obține rezultatul. Un „caracter” dintr-un algoritm poate fi un octet sau un bit, sau orice altă dimensiune adecvată.
De asemenea, nu este necesar să aveți un caracter de final de linie. În schimb, indicatorul care conține „EOL” poate fi folosit ca și cum ar exista. În această abordare, ieșirea BWT trebuie să includă atât șirul transformat, cât și valoarea finală a acestui pointer. Aceasta înseamnă că BWT crește ușor dimensiunea datelor. Transformarea inversă le reduce apoi la dimensiunea lor originală: având în vedere un șir și un indicator, returnează doar un șir.
O descriere completă a algoritmilor poate fi găsită în articolul lui Burroughs și Wheeler sau într-o serie de surse disponibile online.
Dacă sortați un șir folosind POSIX comparison , obțineți un șir de ieșire ușor diferit:
TEXYDST.E.IXIXIXXSSMPPS.B..ESEUSFXDIIOIIITîn loc de
TEXYDST.E.XIIXIXXSMPPSS.B..S.EEUSFXDIOIIIITISO 8859 are reguli complicate de comparare, dar punctele sunt ignorate în acest caz. Comparația POSIX tratează punctele ca caractere.
| Metode de compresie | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Fara pierderi |
| ||||||
| Audio |
| ||||||
| Imagini |
| ||||||
| Video |
| ||||||