LZ77 Sıkıştırma Algoritması

Bu aralar sıkıştırma algoritmalarına merak sardım. Geçen yazıda, Huffman Kodlaması üzerine birşeyler yazmıştım. Bu yazıda, bir diğer efsane sıkıştırma algoritması olan LZ77'den bahsedeceğim. LZ77 algoritması, Abraham Lembel ve Jacob Ziv tarafından 1977 yılında yazdıkları A Universal Algorithm for Sequential Data Compression başlıklı makale ile ortaya atılmıştır. Daha sonra, LZ78, LZSS, BTLZ, LZW, LZMA gibi çeşitli türevleri ortaya çıkmış, ayrıca, DEFLATE sıkıştırma metodunda, LZ77 ve Huffman kodlaması bir arada kullanılmıştır.

Metin belgelerinde, kendini tekrar eden kısımlar olur. Özellikle bağlaç ve zamirler ile, diğer kelimelerin başına ve sonuna gelen ekler, metinlerin içinde sık sık tekrar edebilirler. LZ77 algoritması, metin belgelerindeki tekrar eden bölümleri ortadan kaldırarak, sıkıştırma yapmayı amaçlar. Bunu nasıl yaptığını anlamaya çalışmak için, aşağıdaki örneği inceleyelim:

Bu köşe yaz köşesi, bu köşe kış köşesi, ortada su şişesi.

Bu metinde, köşe kelimesinin 4 defa kullanıldığını hemen dikkat çekiyor. İlk bakışta dikkat çekmeyen başka tekrarlar da var. Mesela, 7 karakterden oluşan "u köşe " metin parçası 2 kez tekrar ediyor. 9 karakterden oluşan " köşesi, " metin parçası yine 2 kere tekrar ediyor vs. Eğer bu tekrarları göstermek için kendimize yeni bir notasyon geliştirirsek, yukarıdaki metni aşağıdaki şekilde de ifade edebiliriz.

Bu köşe yaz<-9,5>si, b<-20,7>kış<-20,9>ortada su şi<-18,4>.

Yukarıdaki örnekte, tekrar eden kısımları "<" ve ">" işaretleri arasında gösterdim. Bu işaretler arasında virgülle ayrılmış iki sayı var. Bunlardan ilki, tekrar eden kısmın, metnin neresinde olduğunu gösteriyor. Bu sayı, metnin içindeki o anki pozisyonu 0 pozisyonu sayıyor. Mesela, <-9,5> notasyonundaki -9, buraya kopyalanacak karakteri bulmak için, 9 karakter geri gitmemiz gerektiğini belirtiyor. Orjinal terminolojiye bağlı kalmak için, bu sayıya offset diyeceğiz. Virgülden sonra gelen sayı ise, ilk sayı ile gösterilen pozisyondan kaç karakter kopyalamamız gerektiğine işaret ediyor. Yani, <-9,5> notasyonunu kullandığımızda, 9 karakter geriden 5 karakter kopyalamamız gerektiğini anlıyoruz. Yine orjinal terminolojiye sadık kalmak adına, bu ikinci sayıya length diyeceğiz. <-9,5> şeklinde gösterimin tamamına ise token diyeceğiz.

Yukarıdaki örnekte, yöntemin temelini daha rahat ifade edebilmek adına, karakterleri ve tokenleri iç içe kullandık. Ancak, algoritmanın aslında, sıkıştırılmış veriyi sadece tokenler kullanarak ifade ediyoruz. Bir diğer deyişle, örneğin şu şekilde verilmiş olması aslına daha uygun olur.

<0,0,B><0,0,u><0,0, ><0,0,k><0,0,ö> ...

Bu yeni gösterimde, offset ve length her zaman belirtilmek zorunda. Eğer, herhangi bir eşleşme yoksa, offset ve length'in ikisini de 0 olarak gösteriyoruz. Offset ve length'in arkasında, eşleşmenin ardından gelen ilk karakteri de, tokenin içine dahil etmemiz gerekiyor.

Programlama dilinde tokenleri nasıl ifade etmemiz gerektiği konusunda, herhangi bir standart yok. Bu tokenler sabit genişlikli olabildiği gibi, bazen sıkıştırma oranını artırmak için, değişken genişlikli de tasarlanabiliyor. Ben kolay uygulanabilir olacağı için, sabit genişlikli tokenler kullanacağım.

#define OFFSETBITS 5
#define LENGTHBITS (8-OFFSETBITS)
#define OFFSETMASK ((1 << (OFFSETBITS)) - 1)
#define LENGTHMASK ((1 << (LENGTHBITS)) - 1)
#define GETOFFSET(x) (x >> LENGTHBITS)
#define GETLENGTH(x) (x & LENGTHMASK)
#define OFFSETLENGTH(x,y) (x << LENGTHBITS | y)
struct token {
    uint8_t offset_len;
    char c;
};

Her bir tokenim 5 offset biti, 3 length biti ve 8 karakter biti olmak üzere toplam 16bit (2 byte) genişliğinde olacak. Dolayısıyla, offset maksimum 31, length ise maksimum 7 olabilecek. Yukarıda bazı yardımcı makrolar da tanımladım.

Tokenleri oluşturmak için, metni iki parça olarak düşüneceğiz. Bu parçalardan biri, metnin henüz işlenmemiş kısmı olacak. Bu kısma, lookahead buffer diyeceğiz. Bu parçalardan diğeri ise, search buffer. Search buffer içerisinde eşleşme arayacağız. Örneğin:

|Bu köşe yaz köşesi, bu köşe |kış köşesi, ortada su şişesi.
|^                           |^
|Search Buffer               |Lookahead Buffer

Yukarıdaki tabloda, sıkıştırma algoritması, kış kelimesinin başına kadar ilerlediğinde, lookahead ve search buffer'larının olabileceği durumu görüyoruz. Böyle bir durumda algoritma, search buffer'ın içinde lookahead buffer'in önü ile eşleşen en uzun parçayı arayıp, oluşacak token'nin offset ve length değerlerini tespit edecek. Token tespit edildikten sonra, lookahead ve search buffer'ları ileriye doğru kaydırılacak.

Bu iki buffer'ın genişliği, tokenime uygun olarak, search buffer için 31 karakter, lookahead buffer için 7 karakter olarak seçilecek. Aşağıda, tokenleri oluşturmak için kullandığım fonksiyonu inceleyebilirsiniz.

/*
* LZ77 ile sıkıştırılacak bir metin alır.
* token array'i döndürür.
* Eğer numTokens NULL değilse, token sayısını
* numTokens ile gösterilen yere kaydeder.
* char *text => sıkıştırılacak metin
* int limit  => Kaç karakter sıkıştıracağımız.
* int *numTokens => Kullanılan token sayısının yerini gösterir pointer
*
*/
struct token *encode(char *text, int limit, int *numTokens)
{
    // cap (kapasite) hafızada kaç tokenlik yer ayırdığımız.
    int cap = 1 << 3;
    // kaç token oluşturduğumuz.
    int _numTokens = 0;
    // oluşturulacak token
    struct token t;
    // lookahead ve search buffer'larının başlangıç pozisyonları
    char *lookahead, *search;
    // tokenler için yer ayır.
    struct token *encoded = malloc(cap * sizeof(struct token));
    // token oluşturma döngüsü
    for (lookahead = text; lookahead < text + limit; lookahead++)
    {
        // search buffer'ı lookahead buffer'ın 31 (OFFSETMASK) karakter
        // gerisine koyuyoruz.
        search = lookahead - OFFSETMASK;
        // search buffer'ın metnin dışına çıkmasına engel ol.
        if (search < text)
            search = text;
        // search bufferda bulunan en uzun eşleşmenin
        // boyutu
        int max_len = 0;
        // search bufferda bulunan en uzun eşleşmenin
        // pozisyonu
        char *max_match = lookahead;
        // search buffer içinde arama yap.
        for (; search < lookahead; search++)
        {
            int len = prefix_match_length(search, lookahead, LENGTHMASK);
            if (len > max_len)
            {
                max_len = len;
                max_match = search;
            }
        }
        /*
        * ! ÖNEMLİ !
        * Eğer eşleşmenin içine metnin son karakteri de dahil olmuşsa,
        * tokenin içine bir karakter koyabilmek için, eşleşmeyi kısaltmamız
        * gerekiyor.
        */
        if (lookahead + max_len >= text + limit)
        {
            max_len = text + limit - lookahead - 1;
        }
        // bulunan eşleşmeye göre token oluştur.
        t.offset_len = OFFSETLENGTH(lookahead - max_match, max_len);
        lookahead += max_len;
        t.c = *lookahead;
        // gerekirse, hafızada yer aç
        if (_numTokens + 1 > cap)
        {
            cap = cap << 1;
            encoded = realloc(encoded, cap * sizeof(struct token));
        }
        // oluşturulan tokeni, array'e kaydet.
        encoded[_numTokens++] = t;
    }
    if (numTokens)
        *numTokens = _numTokens;
    return encoded;
}

Gerekli açıklamaları yorum satırlarında yaptım. Burada kullandığım prefix_match_length fonksiyonu, iki metnin başından kaç karakter eşleştiğini hesaplıyor. Onu da şu şekilde yazdım.

/*
* iki string'in ilk kaç karakteri özdeş?
* en fazla limit'e kadar kontrol yapar.
*/
inline int prefix_match_length(char *s1, char *s2, int limit)
{
    int len = 0;
    while (*s1++ == *s2++ && len < limit)
        len++;
    return len;
}

Sıkıştırma işleminin hepsi bu. Oluşturulan token array'ini depolama veya transfer amacıyla kullanbilirsiniz. Sıkıştırılan metni eski haline döndürmek, sıkıştırmaya nazaran daha basit.

/*
* token array'ini, karakter array'ine dönüştürür.
*/
char *decode(struct token *tokens, int numTokens, int *pcbDecoded)
{
    // hafızada ayırdığımız kapasite
    int cap = 1 << 3;
    // kullanılan byte sayısı
    *pcbDecoded = 0;
    // hafızada yer ayır
    char *decoded = malloc(cap);
    int i;
    for (i = 0; i < numTokens; i++)
    {
        // token'in içinden offset, length ve char
        // değerlerini oku
        int offset = GETOFFSET(tokens[i].offset_len);
        int len = GETLENGTH(tokens[i].offset_len);
        char c = tokens[i].c;
        // gerekirse kapasite artır.
        if (*pcbDecoded + len + 1 > cap)
        {
            cap = cap << 1;
            decoded = realloc(decoded, cap);
        }
        // eğer length 0 değilse, gösterilen karakteleri
        // kopyala
        if (len > 0)
        {
            lz77memcpy(&decoded[*pcbDecoded], &decoded[*pcbDecoded - offset], len);
        }
        // kopyalanan karakter kadar ileri sar
        *pcbDecoded += len;
        // tokenin içindeki karateri ekle.
        decoded[*pcbDecoded] = c;
        // 1 adım daha ileri sar.
        *pcbDecoded = *pcbDecoded + 1;
    }
    return decoded;
}

Gerekli açıklamalar, yorum satırlarında mevcut. Burada tek ilginç olan nokta lz77memcpy fonksiyonu. Buna neden gerek duyulduğuna geçmeden önce, aşağıdaki tokenlerin nasıl bir metin oluşturması gerektiğine bakalım.

<0,0,a><-1,7,a>

İkinci tokene dikkat ederseniz, 1 karakter geri gidip, 7 karakter kopyalamamız gerekiyor, ancak, gösterilen yerde 7 karakter yok. LZ77 algoritmasında bu şekilde henüz olmayan metne referans verebiliyoruz. Aşağıdaki tabloda ikinci token oluşturulmaya başlamadan önceki metnin haline bakalım.

|1|2|3|4|5|6|7|8|
|a|?|?|?|?|?|?|?|

Bu noktada kopyalamanın hedefi ikinci karakter, kaynağı ise birinci karakter. Bu aşamada, 1 karakter kopyalarsak, aşağıdaki duruma geçiyoruz.

|1|2|3|4|5|6|7|8|
|a|a|?|?|?|?|?|?|

Bu aşamada, kopyalamanın hedefi üçüncü karakter, kaynağı ise ikinci karakter. Örnek tabloda gördüğünüz gibi, ilk karakteri kopyaladıktan sonra, kopyalanacak ikinci karakter oluşmuş oldu. Bu şekilde devam ederek, gerekli 7 karakteri kopyalayabiliriz. lz77memcpy fonksiyonu da bu işe yarıyor.

/*
* memcpy fonksiyonu ile benzer. Byte düzeyinde
* kopyalama yapma garantisi olduğu için, bu
* versiyonu kullanıyoruz.
*/
inline void lz77memcpy(char *s1, char *s2, int size)
{
    while (size--)
        *s1++ = *s2++;
}

Kaynak ve hedefin örtüştüğü durumlarda, standart memcpy fonksiyonu her zaman doğru çalışmayacaktır. Bunun için, kendi versiyonumuzu yazmamız gerekti.

Programın tamamı aşağıdaki şekilde. Farklı özellikteki metinlerle ve parametleri değiştirerek denemenizi tavsiye ederim. offset ve length değişkenlerini tutmak için daha büyük bir veri yapısı (uint16_t gibi) deneyerek, daha iyi sıkıştırma oranları elde etmeniz mümkün. offset için ayırdığınız yerin, length'den büyük olması çoğu zaman daha avantajlı olur.

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define OFFSETBITS 5
#define LENGTHBITS (8-OFFSETBITS)
#define OFFSETMASK ((1 << (OFFSETBITS)) - 1)
#define LENGTHMASK ((1 << (LENGTHBITS)) - 1)
#define GETOFFSET(x) (x >> LENGTHBITS)
#define GETLENGTH(x) (x & LENGTHMASK)
#define OFFSETLENGTH(x,y) (x << LENGTHBITS | y)
struct token {
    uint8_t offset_len;
    char c;
};
/*
* iki string'in ilk kaç karakteri özdeş?
* maksimum limit sayısı kadar kontrol yapar.
*/
inline int prefix_match_length(char *s1, char *s2, int limit)
{
    int len = 0;
    while (*s1++ == *s2++ && len < limit)
        len++;
    return len;
}
/*
* memcpy fonksiyonu ile benzer. Byte düzeyinde
* kopyalama yapma garantisi olduğu için, bu
* versiyonu kullanıyoruz.
*/
inline void lz77memcpy(char *s1, char *s2, int size)
{
    while (size--)
        *s1++ = *s2++;
}
/*
* token array'ini, karakter array'ine dönüştürür.
*/
char *decode(struct token *tokens, int numTokens, int *pcbDecoded)
{
    // hafızada ayırdığımız kapasite
    int cap = 1 << 3;
    // kullanılan byte sayısı
    *pcbDecoded = 0;
    // hafızada yer ayır
    char *decoded = malloc(cap);
    int i;
    for (i = 0; i < numTokens; i++)
    {
        // token'in içinden offset, length ve char
        // değerlerini oku
        int offset = GETOFFSET(tokens[i].offset_len);
        int len = GETLENGTH(tokens[i].offset_len);
        char c = tokens[i].c;
        // gerekirse kapasite artır.
        if (*pcbDecoded + len + 1 > cap)
        {
            cap = cap << 1;
            decoded = realloc(decoded, cap);
        }
        // eğer length 0 değilse, gösterilen karakteleri
        // kopyala
        if (len > 0)
        {
            lz77memcpy(&decoded[*pcbDecoded], &decoded[*pcbDecoded - offset], len);
        }
        // kopyalanan karakter kadar ileri sar
        *pcbDecoded += len;
        // tokenin içindeki karateri ekle.
        decoded[*pcbDecoded] = c;
        // 1 adım daha ileri sar.
        *pcbDecoded = *pcbDecoded + 1;
    }
    return decoded;
}
/*
* LZ77 ile sıkıştırılacak bir metin alır.
* token array'i döndürür.
* Eğer numTokens NULL değilse, token sayısını
* numTokens ile gösterilen yere kaydeder.
*/
struct token *encode(char *text, int limit, int *numTokens)
{
    // cap (kapasite) hafızada kaç tokenlik yer ayırdığımız.
    int cap = 1 << 3;
    // kaç token oluşturduğumuz.
    int _numTokens = 0;
    // oluşturulacak token
    struct token t;
    // lookahead ve search buffer'larının başlangıç pozisyonları
    char *lookahead, *search;
    // tokenler için yer ayır.
    struct token *encoded = malloc(cap * sizeof(struct token));
    // token oluşturma döngüsü
    for (lookahead = text; lookahead < text + limit; lookahead++)
    {
        // search buffer'ı lookahead buffer'ın 31 (OFFSETMASK) karakter
        // gerisine koyuyoruz.
        search = lookahead - OFFSETMASK;
        // search buffer'ın metnin dışına çıkmasına engel ol.
        if (search < text)
            search = text;
        // search bufferda bulunan en uzun eşleşmenin
        // boyutu
        int max_len = 0;
        // search bufferda bulunan en uzun eşleşmenin
        // pozisyonu
        char *max_match = lookahead;
        // search buffer içinde arama yap.
        for (; search < lookahead; search++)
        {
            int len = prefix_match_length(search, lookahead, LENGTHMASK);
            if (len > max_len)
            {
                max_len = len;
                max_match = search;
            }
        }
        /*
        * ! ÖNEMLİ !
        * Eğer eşleşmenin içine metnin son karakteri de dahil olmuşsa,
        * tokenin içine bir karakter koyabilmek için, eşleşmeyi kısaltmamız
        * gerekiyor.
        */
        if (lookahead + max_len >= text + limit)
        {
            max_len = text + limit - lookahead - 1;
        }
        // bulunan eşleşmeye göre token oluştur.
        t.offset_len = OFFSETLENGTH(lookahead - max_match, max_len);
        lookahead += max_len;
        t.c = *lookahead;
        // gerekirse, hafızada yer aç
        if (_numTokens + 1 > cap)
        {
            cap = cap << 1;
            encoded = realloc(encoded, cap * sizeof(struct token));
        }
        // oluşturulan tokeni, array'e kaydet.
        encoded[_numTokens++] = t;
    }
    if (numTokens)
        *numTokens = _numTokens;
    return encoded;
}
// bir dosyanın tamamını tek seferde
// okur. Büyük dosyaları okumak için uygun
// değildir.
char *file_read(FILE *f, int *size)
{
    char *content;
    fseek(f, 0, SEEK_END);
    *size = ftell(f);
    content = malloc(*size);
    fseek(f, 0, SEEK_SET);
    fread(content, 1, *size, f);
    return content;
}
int main(void)
{
    FILE *f;
    int metin_boyutu = 8, token_sayisi, decode_boyutu;
    char *kaynak_metin = "aaaaaaaa", *decoded_metin = "";
    struct token *encoded_metin;
    if (f = fopen("source.txt", "rb"))
    {
        kaynak_metin = file_read(f, &metin_boyutu);
        fclose(f);
    }
    encoded_metin = encode(kaynak_metin, metin_boyutu, &token_sayisi);
    if (f = fopen("encoded.txt", "wb"))
    {
        fwrite(encoded_metin, sizeof(struct token), token_sayisi, f);
        fclose(f);
    }
    decoded_metin = decode(encoded_metin, token_sayisi, &decode_boyutu);
    if (f = fopen("decoded.txt", "wb"))
    {
        fwrite(decoded_metin, 1, decode_boyutu, f);
        fclose(f);
    }
    printf("Orjinal Boyut: %d, Encode Boyutu: %d, Decode Boyutu: %d", metin_boyutu, token_sayisi * sizeof(struct token), decode_boyutu);
    return 0;
}