Transformata Burrowsa-Wheelera

Ten artykuł od 2021-04 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do wiarygodnych źródeł. (Dodanie listy źródeł bibliograficznych lub linków zewnętrznych nie jest wystarczające). Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Transformata Burrowsa-Wheelera – algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów.

Transformata Burrowsa-Wheelera jest podstawą algorytmu BZIP2.

Dla potrzeb kompresji, zwykle po transformacie Burrowsa-Wheelera używa się algorytmu Move To Front, po czym kompresuje się dowolną metodą kompresji bezstratnej, np. algorytmem Huffmana.

Algorytm transformaty

Na początku mamy blok danych o rozmiarze N bajtów, np.:

Generujemy wszystkie N rotacji kompresowanego bloku. Wymaga to jedynie O(N) pamięci, nie zaś O(N²), ponieważ generujemy indeksy, a nie kopiujemy.

Sortujemy łańcuchy leksykograficznie, czyli najpierw według wartości pierwszego bajta, następnie drugiego itd.

Zachowujemy ostatni bajt każdej rotacji, w kolejności ich leksykograficznego wystąpienia (kolumna L), oraz pozycję, na której w L znajduje się pierwszy znak kompresowanego bloku danych (indeks P), czyli po prostu pozycję, na której jest łańcuch S1. W tym przypadku indeksem P jest numer 13 oraz blok:

Z bloku oraz indeksu P można odtworzyć pierwotne dane.

Algorytm transformaty odwrotnej

Mamy indeks P = 13 i blok L.

Należy w tym momencie zauważyć, że sortując bajty w L uzyskamy F, czyli pierwszą kolumnę posortowanej macierzy łańcuchów.

Ponieważ bajt przyjmuje 256 możliwych wartości, a bajtów zwykle jest kilkaset tysięcy, najłatwiej zrobić to za pomocą sortowania kubełkowego lub podobnego algorytmu o liniowym czasie wykonywania.

Następnie konstruujemy wektor sąsiedztw T, który posłuży nam do odzyskania pierwotnego ciągu. Wektor T jest to tablica przejść taka, że L[i] i L[T[i]] są kolejnymi znakami pierwotnego ciągu. Dla przykładu:

Posiadając wektor T, L, oraz index P, możemy odtworzyć ciąg:

• i = P

• dopóki nie odzyskamy całej długości ciągu:
  • wypisz L[i]
  • i = T[i]

Przykład:

• i = P → 13
• L[i] = L[13] → 'P'
• i = T[i]= T[13] → 12
• L[12] → 'o'
• i = T[12] → 15
• L[15] → 'l'
• ...

Aby wygenerować wektor T z L, należy poprzez sortowanie utworzyć również wektor F. Następnie dla każdego kolejnego elementu F wyznaczyć pozycję elementu odpowiadającego w L. Wówczas index elementu F będzie indeksem T, a index wyznaczonego elementu L jego wartością. Wyznaczony element z L zaznaczamy jako użyty.
Najlepiej zobrazować to na przykładzie pięciu kroków algorytmu (kropką • zaznaczone użyte elementy):

Z tak otrzymanego wektora T i indeksu P, z łatwością uzyskujemy pierwotny blok danych.

Przykładowy kod w C

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

typedef unsigned char byte;

byte *rotlexcmp_buf = NULL;
int rottexcmp_bufsize = 0;

int rotlexcmp(const void *l, const void *r)
{
    int li = *(const int*)l, ri = *(const int*)r, ac=rottexcmp_bufsize;
    while (rotlexcmp_buf[li] == rotlexcmp_buf[ri])
    {
        if (++li == rottexcmp_bufsize)
            li = 0;
        if (++ri == rottexcmp_bufsize)
            ri = 0;
        if (!--ac)
            return 0;
    }
    if (rotlexcmp_buf[li] > rotlexcmp_buf[ri])
        return 1;
    else
        return -1;
}

void bwt_encode(byte *buf_in, byte *buf_out, int size, int *primary_index)
{
    int indices[size];
    int i;

    for(i=0; i<size; ++i)
        indices[i] = i;
    rotlexcmp_buf = buf_in;
    rottexcmp_bufsize = size;
    qsort (indices, size, sizeof(int), rotlexcmp);

    for (i=0; i<size; ++i)
        buf_out[i] = buf_in[(indices[i]+size-1)%size];
    for (i=0; i<size; ++i)
    {
        if (indices[i] == 1) {
            *primary_index = i;
            return;
        }
    }
    assert (0);
}

void bwt_decode(byte *buf_in, byte *buf_out, int size, int primary_index)
{
    byte F[size];
    int buckets[256];
    int i,j,k;
    int indices[size];

    for (i=0; i<256; ++i)
        buckets[i] = 0;
    for (i=0; i<size; ++i)
        buckets[buf_in[i]] ++;
    for (i=0,k=0; i<256; i++)
        for (j=0; j<buckets[i]; ++j)
            F[k++] = i;
    assert (k==size);
    for (i=0,j=0; i<256; ++i)
    {
        buckets[i] = j; // it will get fake values if there is no i in F, but
                        // that won't bring us any problems
        while (i>=F[j] && j<size)
            ++j;
    }
    for(i=0; i<size; ++i)
        indices[buckets[buf_in[i]]++] = i;
    for(i=0,j=primary_index; i<size; ++i)
    {
        buf_out[i] = buf_in[j];
        j=indices[j];
    }
}

int main()
{
    byte buf1[] = "Polska Wikipedia";
    int size = strlen(buf1);
    byte buf2[size];
    byte buf3[size];
    int primary_index;

    bwt_encode (buf1, buf2, size, &primary_index);
    bwt_decode (buf2, buf3, size, primary_index);

    assert (!memcmp (buf1, buf3, size));
    printf ("Result is the same as input, that is: <%.*s>\n", size, buf3);
    return 0;
}

Zobacz też

• Kompresja danych (informatyka)
• Program do kompresji plików
• Kompresja bezstratna oraz kompresja stratna
• Kodowanie arytmetyczne
• Kodowanie Huffmana
• Słowo Lyndona

Linki zewnętrzne

• M. Burrows and D.J. Wheeler: A Block-sorting Lossless Data Compression Algorithm (ang.)