search

yasar11732 / yasar11732.github.io

My Blog
0 stars 2 forks source link

LZ77 Sıkıştırma Algoritması | YSAR.NET #5

Open utterances-bot opened 4 years ago

utterances-bot commented 4 years ago

LZ77 Sıkıştırma Algoritması | YSAR.NET

http://ysar.net/algoritma/lz77.html

ozgurSULUM commented 4 years ago

Merhabalar [0,0,x] seklindeki tokenler tokenin boyutundan dolayı normalden daha çok yer kaplıyor yani kaynak metinde 1 byte'lık yer kaplarken sıkıştırılmış metinde 2byte'lık yer kaplıyor bunun için en optimal çözüm ne olabilir ?

yasar11732 commented 4 years ago

Merhaba,

Öncelikle tüm verilerin sıkıştırılmaya müsait olmadığını söylemek gerek. Kullandığın algoritma farketmeksizin, bazı girdilerin sıkıştırılmış hali, orjinal halinden büyük olacaktır.

Yukarıdaki önermeyi teyit etmenin daha teknik yolları var, ama basitçe şöyle düşünebilirsin; eğer her veriyi -kayıpsız- sıkıştırabilen bir algoritma olsaydı, algoritmayı tekrar tekrar sıkıştırılmış veriye uygulayarak, tüm verileri 1 bite kadar sıkıştırabilirdin. Bu da sadece 1 bit kullanarak sınırsız uzunlukta veri saklayabileceğin anlamına gelirdi ki, bunun mümkün olmayacağı aşikar.

Bununla birlikte, LZ algoritmasının bir çok varyasyonu var. Bu algoritmalardan bazıları değişken uzunluklu tokenler kullanarak, bahsettiğin sorunu minimize etmeye çalışıyorlar. Bunu şu şekilde yapabilirsin, eğer token [0,0,x] gibi tek bir karakterden oluşacaksa, ve x karakteri 0-127 arasında ise, x karakterini olduğu gibi bırakabilirsin. Diğer durumlar, 2 byte tokenin en üst bitini 1 olarak ayarlarsın. Böylece, en üst biti kontrol ederek, tokenin bir byte veya 2 byte olduğunu ayırt edebilirsin. 16 byte tokenin 1 bitini feda etmiş olacaksın ama, verinin durumuna göre, sıkıştırma oranını artırabilirsin.

Ayrıca LZW algoritmasını da incelemeni öneririm, orada kullanılan yöntem LZ77'ye nazaran daha başarılı diye düşünüyorum.

furkankaysudu commented 4 years ago

Daha once sikistirma algoritmalarini incelememistim ve henuz gordugum algoritmayi hizlica cozumleyamiyorum , fakat yorum satirlariniz sayesinde bu kodu tek seferde anladigimi dusunuyorum. Boyle bir Turkce kaynak buldugum icin ayrica mutluyum . Emegininz icin tesekkurler