b'\n_START_ARTICLE_\nTransformata Burrowsa-Wheelera\n_START_PARAGRAPH_\nTransformata Burrowsa-Wheelera \xe2\x80\x93 algorytm u\xc5\xbcyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu t\xc4\x85 transformacj\xc4\x85 daj\xc4\x85 si\xc4\x99 znacznie lepiej skompresowa\xc4\x87 za pomoc\xc4\x85 klasycznych algorytm\xc3\xb3w kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te s\xc4\x85 wi\xc4\x99ksze. Zazwyczaj u\xc5\xbcywa si\xc4\x99 blok\xc3\xb3w o rozmiarach kilkuset kilobajt\xc3\xb3w._NEWLINE_Transformata Burrowsa-Wheelera jest podstaw\xc4\x85 algorytmu BZIP2._NEWLINE_Dla potrzeb kompresji, zwykle po transformacie Burrowsa-Wheelera u\xc5\xbcywa si\xc4\x99 algorytmu Move To Front, po czym kompresuje si\xc4\x99 dowoln\xc4\x85 metod\xc4\x85 kompresji bezstratnej, np. algorytmem Huffmana.\n_START_SECTION_\nPrzyk\xc5\x82adowy kod w C\n_START_PARAGRAPH_\n#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){_NEWLINE_    int li = *(const int*)l, ri = *(const int*)r, ac=rottexcmp_bufsize;_NEWLINE_    while (rotlexcmp_buf[li] == rotlexcmp_buf[ri])_NEWLINE_    {_NEWLINE_        if (++li == rottexcmp_bufsize)_NEWLINE_            li = 0;_NEWLINE_        if (++ri == rottexcmp_bufsize)_NEWLINE_            ri = 0;_NEWLINE_        if (!--ac)_NEWLINE_            return 0;_NEWLINE_    }_NEWLINE_    if (rotlexcmp_buf[li] > rotlexcmp_buf[ri])_NEWLINE_        return 1;_NEWLINE_    else_NEWLINE_        return -1;}void bwt_encode(byte *buf_in, byte *buf_out, int size, int *primary_index){_NEWLINE_    int indices[size];_NEWLINE_    int i;_NEWLINE__NEWLINE_    for(i=0; i<size; ++i)_NEWLINE_        indices[i] = i;_NEWLINE_    rotlexcmp_buf = buf_in;_NEWLINE_    rottexcmp_bufsize = size;_NEWLINE_    qsort (indices, size, sizeof(int), rotlexcmp);_NEWLINE__NEWLINE_    for (i=0; i<size; ++i)_NEWLINE_        buf_out[i] = buf_in[(indices[i]+size-1)%size];_NEWLINE_    for (i=0; i<size; ++i)_NEWLINE_    {_NEWLINE_        if (indices[i] == 1) {_NEWLINE_            *primary_index = i;_NEWLINE_            return;_NEWLINE_        }_NEWLINE_    }_NEWLINE_    assert (0);}void bwt_decode(byte *buf_in, byte *buf_out, int size, int primary_index){_NEWLINE_    byte F[size];_NEWLINE_    int buckets[256];_NEWLINE_    int i,j,k;_NEWLINE_    int indices[size];_NEWLINE__NEWLINE_    for (i=0; i<256; ++i)_NEWLINE_        buckets[i] = 0;_NEWLINE_    for (i=0; i<size; ++i)_NEWLINE_        buckets[buf_in[i]] ++;_NEWLINE_    for (i=0,k=0; i<256; i++)_NEWLINE_        for (j=0; j<buckets[i]; ++j)_NEWLINE_            F[k++] = i;_NEWLINE_    assert (k==size);_NEWLINE_    for (i=0,j=0; i<256; ++i)_NEWLINE_    {_NEWLINE_        buckets[i] = j; // it will get fake values if there is no i in F, but_NEWLINE_                        // that won\'t bring us any problems_NEWLINE_        while (i>=F[j] && j<size)_NEWLINE_            ++j;_NEWLINE_    }_NEWLINE_    for(i=0; i<size; ++i)_NEWLINE_        indices[buckets[buf_in[i]]++] = i;_NEWLINE_    for(i=0,j=primary_index; i<size; ++i)_NEWLINE_    {_NEWLINE_        buf_out[i] = buf_in[j];_NEWLINE_        j=indices[j];_NEWLINE_    }}int main(){_NEWLINE_    byte buf1[] = "Polska Wikipedia";_NEWLINE_    int size = strlen(buf1);_NEWLINE_    byte buf2[size];_NEWLINE_    byte buf3[size];_NEWLINE_    int primary_index;_NEWLINE__NEWLINE_    bwt_encode (buf1, buf2, size, &primary_index);_NEWLINE_    bwt_decode (buf2, buf3, size, primary_index);_NEWLINE__NEWLINE_    assert (!memcmp (buf1, buf3, size));_NEWLINE_    printf ("Result is the same as input, that is: <%.*s>\\n", size, buf3);_NEWLINE_    return 0;}'