Transformarea Burrows-Wheeler
Transformarea Burrows-Wheeler (prescurtată BWT ) este un algoritm utilizat în programele de compresie a datelor precum bzip2 . A fost inventat de Michael Burrows și David Wheeler. [1]
Când un șir de caractere este trimis către BWT, niciunul dintre ele nu se schimbă în valoare, deoarece transformarea permite doar ordinea caracterelor. Dacă șirul original conține multe repetări ale anumitor șiruri de caractere, atunci în șirul transformat vom găsi mai multe puncte în care același caracter se repetă de multe ori. Acest lucru este util pentru compresie, deoarece devine ușor să comprimați un șir în care apar secvențe lungi de caractere care sunt la fel.
De exemplu, șirul:
TRINZECI. TRENTINIANI.
s-ar transforma în următoarele:
OIIEEAEO..LDTTNN.RRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAAO .... OU.T
Transformatul
Transformarea se face prin ordonarea tuturor rotațiilor textului și apoi luând doar ultima coloană. De exemplu, textul „^ BANANA @ ” este transformat în „BNN ^ AA @ A” prin acești pași (caracterele roșii ^ și @ indică începutul indicatorului șir și, respectiv, sfârșitul indicatorului șir sau „EOF”):
| Transformat | ||||
|---|---|---|---|---|
| Intrare | Toate rotații | Linii în ordine lexicografic | Ia ultimul coloană | Ieșire |
^ BANANA @ | ^ BANANA @ @ ^ BANANA A @ ^ BANAN NA @ ^ BANA ANA @ ^ BAN NANA @ ^ BA ANANA @ ^ B BANANA @ ^ | A NANA @ ^ B A NA @ ^ BAN A @ ^ BANAN B ANANA @ ^ N ANA @ ^ BA N A @ ^ BANA ^ BANANA @ @ ^ BANANA | ANANA @ ^ B ANA @ ^ BA N A @ ^ BANA N BANANA @ ^ NANA @ ^ B A NA @ ^ BAN A ^ BANANA @ @ ^ BANAN A | BNN ^ AA @ A |
Următorul pseudocod arată o metodă ineficientă pentru a calcula BWT și inversul acestuia. Se presupune că șirul de intrare s conține un caracter special „EOF” care este întotdeauna ultimul caracter și nu apare niciodată în text și, prin urmare, este ignorat la sortare.
Funcția BWT ( șiruri )
creează o listă cu toate rotațiile posibile ale lui s
puneți fiecare rotație pe un rând de masă pătrată mare
sortează rândurile tabelelor în ordine alfabetică, tratând fiecare rând ca un șir
afișează coloana din dreapta a tabelului
funcția BWTinversa ( șiruri )
creează un tabel gol, fără rânduri sau coloane
repetă lungimea_de (de) ori
introduceți s ca o nouă coloană în partea stângă a tabelului
sortează rândurile tabelului în ordine alfabetică
returnează linia care se termină cu caracterul „EOF”
Transformarea inversă
Cel mai interesant lucru despre BWT nu este că generează o ieșire care este mai ușor de comprimat decât originalul, ci și pentru că acest lucru ar putea fi realizat prin simpla plasare a caracterelor în ordine alfabetică, ci este reversibilitatea sa: documentul original este reconstruit începând doar din caracterele ultimei coloane.
Inversul poate fi înțeles în acest fel. Luați tabelul final al algoritmului BWT și ștergeți totul, cu excepția ultimei coloane. Având în vedere doar aceste informații, puteți reconstrui cu ușurință prima coloană. Ultima coloană vă spune care sunt toate caracterele textului, trebuie doar să le sortați pentru a obține prima coloană. Acum sunt cunoscute prima și ultima coloană și împreună vă oferă toate perechile succesive de caractere din document, unde perechile dau, ciclic, întotdeauna mai întâi ultimul și apoi primul caracter al perechii din documentul original. Sortând lista de perechi veți obține prima și a doua coloană. Continuând în acest fel, puteți reconstitui întreaga listă, prin urmare, linia cu caracterul „EOF” la sfârșit este textul original. Transformarea inversă a exemplului de mai sus arată astfel:
| Transformarea inversă | |||
|---|---|---|---|
| Intrare | |||
BNN ^ AA @ A
| |||
| adăuga | Fel | adăuga | Fel |
B.
Nu.
Nu.
^
LA
LA
@
LA
| LA
LA
LA
B.
Nu.
Nu.
^
@
| BA N / A N / A ^ B UN UN @ ^ A @ | UN UN A @ BA N / A N / A ^ B @ ^ |
| adăuga | Fel | adăuga | Fel |
INTERZICE NAN NA @ ^ BA ANA ANA @ ^ B A @ ^ | ANA ANA A @ ^ INTERZICE NAN NA @ ^ BA @ ^ B | BANA NANA NA @ ^ ^ BAN ANAN ANA @ @ ^ BA A @ ^ B | ANAN ANA @ A @ ^ B BANA NANA NA @ ^ ^ BAN @ ^ BA |
| adăuga | Fel | adăuga | Fel |
BANAN NANA @ NA @ ^ B ^ BANA ANANA ANA @ ^ @ ^ BAN A @ ^ BA | ANANA ANA @ ^ A @ ^ BA BANAN NANA @ NA @ ^ B ^ BANA @ ^ BAN | BANANĂ NANA @ ^ NA @ ^ BA ^ BANAN ANANA @ ANA @ ^ B @ ^ BANA A @ ^ BAN | ANANA @ ANA @ ^ B A @ ^ BAN BANANĂ NANA @ ^ NA @ ^ BA ^ BANAN @ ^ BANA |
| adăuga | Fel | adăuga | Fel |
BANANA @ NANA @ ^ B NA @ ^ BAN ^ BANANĂ ANANA @ ^ ANA @ ^ BA @ ^ BANAN A @ ^ BANA | ANANA @ ^ ANA @ ^ BA A @ ^ BANA BANANA @ NANA @ ^ B NA @ ^ BAN ^ BANANĂ @ ^ BANAN | BANANA @ ^ NANA @ ^ BA NA @ ^ BANA ^ BANANA @ ANANA @ ^ B ANA @ ^ BAN @ ^ BANANA A @ ^ BANAN | ANANA @ ^ B ANA @ ^ BAN A @ ^ BANAN BANANA @ ^ NANA @ ^ BA NA @ ^ BANA ^ BANANA @ @ ^ BANANA |
| Ieșire | |||
^ BANANA @
| |||
Anumite optimizări pot face ca acești algoritmi să ruleze mai eficient fără a modifica rezultatul; nu este nevoie să păstrați întregul tabel în memorie, cu atât mai puțin pe disc și nu este necesar să repetați ordinea continuă a exemplului. Fiecare rând al tabelului este reprezentat în memorie cu un pointer simplu către caracterul său de început.
Exemplu de implementare
Notă: Scris în C
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
octet de caractere nesemnat typedef ;
octet * rotlexcmp_buf = NULL ;
int rotexcmp_bufsize = 0 ;
int rotlexcmp ( const void * l , const void * r )
{
int li = * ( const int * ) l , ri = * ( const int * ) r , ac = rottexcmp_bufsize ;
if ( li == ri ) returnează 0 ;
while ( rotlexcmp_buf [ li ] == rotlexcmp_buf [ ri ])
{
if ( ++ li == routesxcmp_bufsize )
li = 0 ;
if ( ++ ri == rottexcmp_bufsize )
ri = 0 ;
dacă ( ! - ac )
retur 0 ;
}
if ( rotlexcmp_buf [ li ] > rotlexcmp_buf [ ri ])
retur 1 ;
altceva
retur -1 ;
}
bwt_encode void (byte * buf_in, octet * buf_out, int size, int * primary_index)
{
indici int [ dimensiune ];
int i ;
pentru ( i = 0 ; i < dimensiune ; i ++ )
indici [ i ] = i ;
rotlexcmp_buf = buf_in ;
rottexcmp_bufsize = dimensiune ;
qsort ( indici , dimensiune , sizeof ( int ), rotlexcmp );
pentru ( i = 0 ; i < dimensiune ; i ++ )
buf_out [ i ] = buf_in [( indici [ i ] + mărime -1 ) % mărime ];
pentru ( i = 0 ; i < dimensiune ; i ++ )
{
if ( indicii [ i ] == 1 ) {
* primar_index = i ;
întoarcere ;
}
}
afirmă ( 0 );
}
void bwt_decode (octet * buf_in, octet * buf_out, dimensiune int primary_index)
{
octet F [ mărime ];
găleți int [ 256 ];
int i , j , k ;
indici int [ dimensiune ];
pentru ( i = 0 ; i < 256 ; i ++ )
găleți [ i ] = 0 ;
pentru ( i = 0 ; i < dimensiune ; i ++ )
găleți [ buf_in [ i ]] ++ ;
pentru ( i = 0 , k = 0 ; i < 256 ; i ++ )
pentru ( j = 0 ; j < găleți [ i ]; j ++ )
F [ k ++ ] = i ;
afirmă ( dimensiunea k == );
pentru ( i = 0 , j = 0 ; i < 256 ; i ++ )
{
while ( i > F [ j ] && j < dimensiune )
j ++ ;
cupe [ i ] = j ; // va primi valori false dacă nu există i în F, dar
// asta nu ne va aduce probleme
}
pentru ( i = 0 ; i < dimensiune ; i ++ )
indici [ găleți [ buf_in [ i ]] ++ ] = i ;
pentru ( i = 0 , j = index_primar ; i < dimensiune ; i ++ )
{
buf_out [ i ] = buf_in [ j ];
j = indici [ j ];
}
}
int main ()
{
byte buf1 [] = "Polska Wikipedia" ;
int size = strlen (( const char * ) buf1 );
octet buf2 [ dimensiune ];
octet buf3 [ dimensiune ];
int primar_index ;
bwt_encode ( buf1 , buf2 , size , & primary_index );
bwt_decode ( buf2 , buf3 , size , primary_index );
afirmă ( ! memcmp ( buf1 , buf3 , dimensiune ));
printf ( "Rezultatul este același cu intrarea, adică: <%. * s> \ n " , dimensiune , buf3 );
// Imprimați codificarea / decodarea rezultatelor:
printf ( "Intrare: <%. * s> \ n " , dimensiune , buf1 );
printf ( "Ieșire: <%. * s> \ n " , dimensiune , buf2 );
retur 0 ;
}
Implementare Perl:
#! / usr / bin / perl
# o implementare Oromis92
while ( $ text = <> ) {
chomp $ text ;
@text = split // , $ text ;
$ lungime = lungime ( $ text );
@array = ( $ text );
pentru ( $ j = 0 ; $ j < $ lungime ; $ j ++ ) {
pentru ( $ i = 0 ; $ i < $ lungime ; $ i ++ ) {
$ string . = $ text [ ( $ i - ( $ j + 1 ) ) ]];
}
$ array [ $ j + 1 ] = $ șir ;
$ string = "" ;
}
pop ( @array );
@array = sort ( @array );
$ text = "" ;
pentru ( $ k = 0 ; $ k <= $ # matrice ; $ k ++ ) {
$ text . = substr ( $ array [ $ k ], ( $ length ) - 1 , 1 );
}
tipăriți „$ text \ n” ;
}
Notă
- ^ Burrows M și Wheeler D, Un bloc de sortare a algoritmului de compresie a datelor fără pierderi , Raport tehnic 124, Digital Equipment Corporation, 1994.
