Lz77 Lz88 Sıkıştırma Algoritması

 Lz77 Lz88 Sıkıştırma Algoritması
Okunuyor Lz77 Lz88 Sıkıştırma Algoritması

Selamun Aleyküm  Lz77 Lz88 Sıkıştırma Algoritması LZ77 ve LZ78, 1977 ve 1978’de Abraham Lempel ve Jacob Ziv tarafından yayınlanan makalelerde yayınlanan iki kayıpsız veri sıkıştırma algoritmasıdır. Ayrıca sırasıyla LZ1 ve LZ2 olarak bilinir. Bu iki algoritma, LZW, LZSS, LZMA ve diğerleri dahil olmak üzere birçok varyasyonun temelini oluşturur.

Lz77 Lz88 Sıkıştırma Algoritması

Örnek LZ77:  Sıkıştıracağımız kelime (encoding İşlemi  ):        sir_srd_eastman

Metin belgelerinde, kendini tekrar eden kısımlar olur. Özellikle bağlaç ve zamirler ile, diğer

ARAMA TAMPON İLERİ TAMPON 3 Parametremiz ( uzaklık, benzerlik, takip tekrarı) –>Output
  sir_srd_eastman (0,0,”s”) Burada benzersiz bir şey ekledik.
s ir_srd_eastman (0,0,”s”),(0,0,”i”)
si r_srd_eastman (0,0,”s”),(0,0,”i”),(0,0,”r”)
sir _srd_eastman (0,0,”s”),(0,0,”i”),(0,0,”r”),(0,0,”_”)
sir_ srd_eastman (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”)
sir_srd _eastman (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”),(4,1,”e”)
sir_srd_e astman (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”),(4,1,”e”),(0,0,”a”)
sir_srd_ea stman (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”),(4,1,”e”),(0,0,”a”),(10,1,”t”)
sir_srd_east man (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”),(4,1,”e”),(0,0,”a”),(10,1,”t”),(0,0,”m”)
sir_srd_eastm an (0,0,”s”),(0,0,”i”),(0,0″,”r”),(0,0,”_”),(4,2,”d”),(4,1,”e”),(0,0,”a”),(10,1,”t”),(0,0,”m”),(4,1,n)

Lz77 Lz88 Sıkıştırma Algoritması

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, yukarıdaki örneği inceleyelim:

LZ77 3 Parametreli bir sıkıştırma algoritmasıdır.Bu parametreler uzaklık ,benzerlik ve takip tekrarıdır.

Buradaki örneğimizde sir_srd_eastman LZ77 algoritması sonucunu almış bulunmaktayız. Benzersiz bir veri girişinde (0,0,”veri”) şeklinde giriş yapılmıştır. Yukarıdaki ilk 4 adım buna örnek niteliktedir. Sonraki adımda ise “s” karakteri daha önceden giriş yapıldığı için arama tamponundaki kendine olan uzaklığı alınmış ve yazılmıştır. Daha sonra kendinden sonra gelen karaktere bakılmıştır.”i” karakteri de arama tamponunda bulunmaktadır. Yani benzerliğimiz ikiye çıkmıştır. Sonra bir sonraki karaktere geçilmiştir. Bu benzersizdir. Sonucumuz (4,2,”d”) halini almıştır. Bundan sonraki işlemler bu mantıkta devam etmiştir.

Lz77 Lz88 Sıkıştırma Algoritması

Örnek LZ78:  Sıkıştıracağımız kelime(encoding işlemi): ABBCBCABABCAABCAAB

 

Dictionary  
İndex string output
1 A (0,A)
2 B (0,B)
3 BC (2,C)
4 BCA (3,A)
5 BA (2,A)
6 BCAA (4,A)
7 BCAAB (6,B)
Mesajın Toplamı : (0,A),(0,B),(2,C),(3,A),(2,A),(4,A),(6,B)

Lempel ve Ziv, LZ77’de yer alan tampon büyüklüğünün sınırlı olmasının yarattığı sıkıntıları ortadan kaldırmak için, tampon kullanmayan çok farklı bir yöntem geliştirerek 1978’in Eylül ayında yayınlanan “Compression of Individual Sequences via Variable-Rate Coding” isimli makalelerinde bu algoritmalarına. LZ77’den çok farklı bir yapıda olması nedeniyle, bu algoritma ve geliştirilmiş biçimleri, LZ78 (veya LZ2) ailesi olarak adlandırılmıştır. LZ77’den farklı olarak, sadece metin tabanlı sıkıştırmada değil, bitmap gibi farklı sayısal veriler üzerinde de başarıyla uygulanabilmiştir.

Lz77 Lz88 Sıkıştırma Algoritması

Genel olarak mantığa bakacak olursak ;

  1. Metinden bir harf al
  2. Sözlükte harfi ara
  3. Metindeki sıradaki harfi aldığında sözlükteki bir kayda karşılık geliyorsa metinden harf almaya devam et
  4. Şimdiye kadar uyan sözlük değerini sonuca bas
  5. Uyumu bozan yeni harfle birlikte şimdiye kadar uyan sözlük kaydını, yeni sözlük kaydı olarak ekle
  6. Metin bitmediyse 2. Adımdan uymayan bu yeni harf ile devam et.

ÖRNEK KODLAR

 

Örnek Kodumuz LZ77:

#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);

Lz77 Lz88 Sıkıştırma Algoritması

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.

Lz77 Lz88 Sıkıştırma Algoritması

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)

Lz77 Lz88 Sıkıştırma Algoritması

{
                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)
{

Lz77 Lz88 Sıkıştırma Algoritması

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;
}

Lz77 Lz88 Sıkıştırma Algoritması

LZ78 Örnek Kodları

 

using System;
using System.Collections.Generic;

public class Program
{
	public static void Main()
	{
		List<int> indices = new List<int>();


foreach (KeyValuePair<int, string> kvp in Compressor("LZWLZ78LZ77LZCLZMWLZAP", ref indices))
		{
			Console.WriteLine(kvp.Key + ": " + kvp.Value);
		}

		foreach (int index in indices)
		{
			Console.WriteLine(index);
		}
	}

 

Yapılan Yorumlar

Bir Cevap Yazın

This site uses Akismet to reduce spam. Learn how your comment data is processed.