Kodlama yöntemleri. Seri kodlama yöntemiyle sıkıştırma: RLE algoritması

Tersinir sıkıştırma algoritmalarının temel sınıflandırması

birçok farklı var pratik yöntemler kural olarak farklı verime sahip bilgi kaybı olmadan sıkıştırma farklı şekiller veri ve farklı hacimler. Bununla birlikte, bu yöntemler üç ana klasik sıkıştırma şemasına dayanmaktadır:

Dizi serisi kodlaması (RLE);

İstatistiksel sıkıştırma yöntemleri;

Sözlük (sezgisel) sıkıştırma yöntemleri.

Seri kodlama yöntemiyle sıkıştırma: RLE algoritması

En iyi bilinen basit yaklaşım ve tersine çevrilebilir sıkıştırma algoritması, Çalışma Uzunluğu Kodlamasıdır (RLE). Bu yaklaşımın yöntemlerinin özü, zincirleri veya yinelenen bayt dizilerini veya bunların dizilerini bir kodlama baytı ve tekrarlarının sayısı için bir sayaçla değiştirmektir. Tüm benzer yöntemlerle ilgili sorun, sıkıştırmayı açma algoritmasının, elde edilen bayt akışında kodlanmış dizileri diğer kodlanmamış bayt dizilerinden nasıl ayırt edebileceğini belirlemektir. Sorunun çözümü genellikle kodlanmış zincirlerin başına etiketlerin yerleştirilmesiyle sağlanır. Bu tür işaretler, örneğin, bir kodlanmış çalıştırmanın ilk baytındaki karakteristik bit değerleri, bir kodlanmış çalıştırmanın ilk baytının değerleri ve benzerleri olabilir. Bu yöntemler genellikle bitmap sıkıştırma için oldukça verimlidir. grafik görüntüler(BMP, PCX, TIF, GIF), çünkü ikincisi, birkaç uzun yinelenen bayt dizisi dizisi içerir. RLE yönteminin dezavantajı, oldukça düşük bir sıkıştırma oranı veya az sayıda seriye sahip ve daha da kötüsü, seri olarak az sayıda tekrarlanan bayt içeren dosyaları kodlama maliyetidir.

RLE algoritması, tekrarlanan veri dizilerini tanımlama ve bunları bir veri kodu ve tekrarlama faktörü belirten daha basit bir yapıyla değiştirme fikrine dayanır. Örneğin, sıkıştırmaya tabi olan böyle bir veri dizisi verilsin: 1 1 1 1 2 2 3 4 4 4 . RLE algoritmasında, aşağıdaki yapıyla değiştirilmesi önerilir: 1 4 2 2 3 1 4 3 , burada her sayı çiftinin ilk sayısı veri kodudur ve ikincisi tekrar faktörüdür. Giriş dizisinin her bir veri öğesini depolamak için 1 bayt tahsis edilirse, tüm dizi 10 bayt bellek kaplarken, çıkış dizisi (sıkıştırılmış sürüm) 8 bayt bellek kaplar. RLE algoritmasının vereceği açıktır. en iyi etki yinelenen bir veri dizisinin daha büyük bir uzunluğunda sıkıştırma. Yukarıdaki örnekte, giriş sırası şöyle görünüyorsa: 1 1 1 1 1 1 3 4 4 4, sıkıştırma oranı %60 olacaktır. Bu bağlamda, RLE algoritmasının daha yüksek verimliliği, grafik verileri sıkıştırarak elde edilir (özellikle tek tonlu görüntüler için).

Sezgisel (sözlük) algoritmalar sıkıştırma (LZ, LZW), dosyada tekrarlanan satırları arar ve daha önce karşılaşılmış olan tümceciklerin bir sözlüğünü oluşturur. Tipik olarak, bu tür algoritmalar, seçimi çalışmanın yazarının deneyimine bağlı olan bir dizi özel parametreye (arabellek boyutu, maksimum ifade uzunluğu vb.) sahiptir ve bu parametreler, elde edilecek şekilde seçilir. algoritmanın çalışma süresinin optimal oranı, sıkıştırma oranı ve iyi sıkıştırılan dosya listesi.

İstatistiksel Algoritmalar(Huffman, Shannon-Fano, aritmetik) İstatistiksel algoritmalar istatistiksel bir veri modeli kullanır ve bilgi sıkıştırmanın kalitesi doğrudan bu modelin ne kadar iyi olduğuna bağlıdır. Muhasebe istatistiksel özellikler en basit durumda veri, kodlama için tekdüze olmayan kodların kullanılması anlamına gelir - sıklıkla ortaya çıkan karakterler kısa kodlarda ve nadiren uzun kodlarda kodlanır. Yani, bu tür algoritmaların, basit durumda giriş verilerinde karakterlerin görülme sıklığı ile tahmin edilebilecek olan, görüntüdeki karakterlerin ortaya çıkma olasılıklarını bilmesi gerekir. Kural olarak, bu olasılıklar bilinmemektedir. Kodlamanın amacı, giriş akışını minimum uzunlukta bir bit akışına dönüştürmektir, bu da giriş akışının entropisini (kaotik) simge frekanslarını dikkate alarak azaltarak elde edilir.

Akış alfabesindeki karakterleri temsil eden kodun uzunluğu, giriş akışındaki bilgi miktarıyla orantılı olmalıdır ve akış karakterlerinin bit cinsinden uzunluğu, 8'in katı veya değişken bile olamaz. Girdi akışının alfabesindeki karakterlerin oluşum sıklıklarının olasılık dağılımı biliniyorsa, optimal bir kodlama modeli oluşturmak mümkündür. Ancak, çok sayıda varlığı nedeniyle çeşitli formatlar dosyalar, çünkü görev çok daha karmaşıktır. veri sembolü frekans dağılımı önceden bilinmemektedir. Bu durumda iki yaklaşım kullanılır.

Birinci giriş akışını görüntülemeyi ve toplanan istatistiklere dayalı bir kodlama oluşturmayı içerir (bu, dosyadan iki geçiş gerektirir - biri görüntüleme ve toplama için) istatistiki bilgi, ikincisi - bu tür algoritmaların kapsamını bir şekilde sınırlayan kodlama için, çünkü bu nedenle, veri miktarının bazen bilinmediği telekomünikasyon sistemlerinde kullanılan "anında" tek geçişli kodlama olasılığı ve bunların yeniden iletim veya ayrıştırma makul olmayan bir şekilde uzun sürebilir). Böyle bir durumda kullanılan kodlamanın entropi şeması çıkış akımına yazılır. Bu method statik Huffman kodlaması olarak bilinir. Sembol tablosu, sıkıştırılmış dosya ile birlikte aktarılır. Bu tür algoritmalar çoğu dosyayı oldukça iyi sıkıştırır, ancak sembol frekans tablosunun ek iletimi ve ayrıca istatistik toplamak ve sıkıştırma için kaynak dosyanın iki geçişine ihtiyaç vardır.

ikinci yöntem- uyarlanabilir kodlama yöntemi. İlkesi, giriş akışındaki değişikliklerin doğasına bağlı olarak kodlama şemasını değiştirmektir. Uyarlanabilir - sabit bir ilk karakter sıklık tablosuyla çalışmaya başlayın (genellikle tüm karakterler ilk başta eşit derecede olasıdır) ve çalışma sürecinde bu tablo dosyada bulunan karakterlere bağlı olarak değişir. Avantajları: tek geçişli algoritma, sembol frekans tablosunu aktarmaya gerek yoktur, geniş bir dosya sınıfını oldukça verimli bir şekilde sıkıştırır. Bu yaklaşımın tek geçişli bir algoritması vardır ve kullanılan kodlama hakkında açık bilgi depolaması gerektirmez. Uyarlanabilir kodlama verebilir daha yüksek derece giriş akışının frekanslarındaki değişiklikler daha tam olarak dikkate alındığından, statik ile karşılaştırıldığında sıkıştırma. Bu teknik, dinamik Huffman kodlaması olarak bilinir.

Bunu akılda tutarak, istatistiksel algoritmalar üç sınıfa ayrılabilir:

1. Uyarlanamaz - sabit, önceden belirlenmiş sembol olasılıklarını kullanın. Sembol olasılık tablosu önceden bilindiği için dosyayla birlikte aktarılmaz. Dezavantaj: Kabul edilebilir bir sıkıştırma oranının elde edildiği belirli bir frekans tablosu için dar kullanım alanı.

2. Yarı uyarlanabilir - her dosya için bir karakter frekans tablosu oluşturulur ve dosya buna göre sıkıştırılır. Sembol tablosu, sıkıştırılmış dosya ile birlikte aktarılır. Bu tür algoritmalar çoğu dosyayı oldukça iyi sıkıştırır, ancak sembol frekans tablosunun ek iletimi ve ayrıca istatistik toplamak ve sıkıştırma için kaynak dosyanın iki geçişine ihtiyaç vardır.

3. Uyarlanabilir - sabit bir ilk karakter sıklık tablosuyla çalışmaya başlayın (genellikle tüm karakterler ilk başta eşit derecede olasıdır) ve çalışma sürecinde bu tablo dosyada bulunan karakterlere bağlı olarak değişir. Avantajları: tek geçişli algoritma, sembol frekans tablosunu aktarmaya gerek yoktur, geniş bir dosya sınıfını oldukça verimli bir şekilde sıkıştırır.

Huffman algoritması, bit gruplarına göre kodlama fikrine dayanmaktadır. İlk gerçekleştirilen frekans analizi giriş veri dizisi, yani içinde meydana gelen her karakterin oluşum sıklığı belirlenir. Bundan sonra, karakterler azalan oluşum sıklığına göre sıralanır.

Temel fikir, bir karakter ne kadar yaygınsa, o kadar az bit kodlar. Kodlama sonucu, kod çözme için gerekli sözlüğe girilir. Huffman algoritmasının işleyişini gösteren basit bir örneği ele alalım.

Statik Huffman kodlamasında, giriş karakterlerine (çeşitli uzunluklardaki bit dizileri), yine değişken uzunluktaki bit dizileri - kodları - atanır. Her karakterin kodunun uzunluğu, frekansının ters işaretle alınan ikili logaritması ile orantılı olarak alınır. Ve karşılaşılan tüm farklı karakterlerin toplam seti, akışın alfabesidir. Bu kodlama, ortaya çıkan akışa kodunun çözülmesini kolaylaştıran önektir, çünkü önek kodlamada herhangi bir karakterin kodu, başka herhangi bir karakterin kodunun öneki değildir - alfabe benzersizdir.

Algoritmanın ilk versiyonu

Bu algoritmanın uygulanması son derece kolaydır. İngiliz Çalışma Uzunluğu Kodlamasından (RLE) grup kodlaması, en eski ve en basit grafik arşivleme algoritmalarından biridir. İçindeki görüntü (aşağıda açıklanan birkaç algoritmada olduğu gibi), tarama çizgileri boyunca bir bayt zincirine çekilir. RLE'de sıkıştırmanın kendisi gerçekleşir orijinal görüntüde aynı bayt zincirlerinin olması nedeniyle. Onları çiftlerle değiştirmek<счетчик повторений, значение>veri fazlalığını azaltır.

algoritma baskıyı azaltmaşuna benziyor:

başlatma(...);
Yapmak(
if(sayaçtır(bayt)) (
sayaç = Düşük6bit(bayt)+1;
for(i=1 karşı koymak için)
De
}
başka(
DecompressedFile.WriteByte(bayt)
) while(ImageFile.EOF());

Bu algoritmada sayacın (counter) işareti, okunan dosyanın ilk iki bitindekilerdir:

Buna göre kalan 6 bit, 1 ile 64 arasında değer alabilen sayaçta harcanır. 64 tekrarlı baytlık bir diziyi iki bayta dönüştürürüz, yani. 32 kez sıkıştırın.

Egzersiz yapmak: Algoritma yap sıkıştırma RLE algoritmasının ilk versiyonu için.

Otokontrol için soru: RLE algoritması için iki veya üç "kötü" görüntü örneği önerin. Neden sıkıştırılmış dosya boyutunu açıklayın büyük boy Kaynak dosyası.

Algoritmanın ikinci versiyonu

Bu algoritmanın ikinci varyantı daha büyük bir maksimum arşivleme oranına sahiptir ve kaynak dosyanın boyutunu daha az artırır.

Bunun için dekompresyon algoritması şöyle görünür:

başlatma(...);
Yapmak(
bayt = ImageFile.ReadNextByte();
sayaç = Düşük7bit(bayt)+1;
if(eğer tekrar işareti(bayt)) (
değer = ImageFile.ReadNextByte();
için (i=1 karşı koymak için)
CompressedFile.WriteByte(değer)
}
başka(
for(i=1 karşı saymak için)(
değer = ImageFile.ReadNextByte();
CompressedFile.WriteByte(değer)
}
CompressedFile.WriteByte(bayt)
) while(ImageFile.EOF());

Bu algoritmadaki bir tekrar işareti, karşılık gelen baytın yüksek sırasındaki bir birimdir:

Kolayca hesaplanabileceği gibi, en iyi senaryo bu algoritma dosyayı 64 kez sıkıştırır (önceki sürümde olduğu gibi 32 kez yerine), en kötü ihtimalle 1/128 oranında artar. Ortalama sıkıştırma oranları bu algoritma birinci varyantın göstergeleri düzeyindedir.

Egzersiz yapmak: RLE algoritmasının ikinci versiyonu için bir sıkıştırma algoritması yazın.

RLE algoritmasının özellikleri:

Sıkıştırma oranları:İlk seçenek: 32, 2, 0.5. İkinci seçenek: 64, 3, 128/129.(en iyi, ortalama, en kötü oranlar)

Görüntü sınıfı: Algoritma, az sayıda renge sahip görüntülere odaklanır: ticari ve bilimsel grafikler.

Simetri: Yaklaşık bir.

Karakteristik özellikler: Algoritmanın belki de tek olumlu yönü, yalnızca gerektirmediği gerçeğine atfedilebilir. ek bellek arşivlerken ve açarken de hızlı çalışır. İlginç özellik grup kodlaması, bazı görüntülerin arşivlenme derecesinin yalnızca görüntü paletindeki renklerin sırası değiştirilerek önemli ölçüde artırılabilmesidir.

Algoritmanın adı, geliştiricilerinin adlarının ilk harfleriyle verildi - Lempel, Ziv ve Welch. İçindeki sıkıştırma, RLE'den farklı olarak, aynı bayt zincirleri nedeniyle zaten gerçekleştirilir.

Algoritma LZ

Örneğin, tekrarlanan zincirleri arama yönteminde farklılık gösteren oldukça geniş bir LZ benzeri algoritma ailesi vardır. yeterli bir tane basit seçenekler bu algoritma, örneğin, giriş akışının bir çift içerdiğini varsayar.<счетчик, смещение относительно текущей позиции>, ya da sadece<счетчик>"atlanan" baytlar ve bayt değerleri kendileridir (RLE algoritmasının ikinci versiyonunda olduğu gibi). Bir çift için fermuarı açarken<счетчик, смещение>kopyalanmış<счетчик>açma işleminden kaynaklanan çıktı dizisinden bayt<смещение>önce bayt ve<счетчик>(yani, sayaca eşit bir sayı) "atlanan" baytların değerleri, giriş akışından çıktı dizisine basitçe kopyalanır. Bu algoritma, aynı alt dizileri ararken tamponun tam olarak aranmasını gerektirdiğinden, zaman açısından asimetriktir. Sonuç olarak, sıkıştırma süresindeki keskin artış nedeniyle büyük bir arabellek ayarlamamız zor. Bununla birlikte, potansiyel olarak bir algoritmanın inşası<счетчик>ve üzerinde<смещение>2 bayt tahsis edilecek (sayacın yüksek baytının yüksek biti, dize tekrarı / akış kopyalamanın bir işaretidir), bize 64Kb'lik bir arabellekte 32Kb'ye kadar tüm tekrarlanan alt dizileri sıkıştırma fırsatı verecektir.

Bu durumda, dosya boyutunda en kötü durumda 32770/32768 oranında bir artış elde edeceğiz (iki baytta, sonraki 2 15 baytın çıkış akışına yeniden yazılması gerektiği yazılır), ki bu hiç de fena değil. Maksimum sıkıştırma oranı 8192 kat sınırında olacaktır. Limitte, 32Kb'lik bir tamponu 4 bayta çevirerek maksimum sıkıştırmayı elde ettiğimiz için ve bu boyutta bir tamponu hemen biriktirmeyeceğiz. Ancak sıkıştırmamızın faydalı olacağı minimum alt dizi genellikle en az 5 bayttan oluşmalıdır ki bu algoritmanın düşük değerini belirler. LZ'nin avantajları, açma algoritmasının aşırı basitliğini içerir.

Egzersiz yapmak:Çiftin bulunduğu LZ algoritmasının başka bir varyantını önerin.<счетчик, смещение>3 bayt tahsis edilecek ve algoritmanızın ana özelliklerini hesaplayacaktır.

Aşağıda ele alınan algoritmanın varyantı, zincirleri temsil etmek ve depolamak için bir ağaç kullanacaktır. Açıkçası, bu, zincir tipi üzerinde oldukça güçlü bir kısıtlamadır ve sıkıştırma sırasında görüntümüzdeki özdeş alt zincirlerin tümü kullanılmayacaktır. Ancak önerilen algoritmada 2 bayttan oluşan çift zincirleri sıkıştırmak avantajlıdır.

Sıkıştırma işlemi oldukça basit görünüyor. Girdi akımının karakterlerini sırayla okuyoruz ve oluşturduğumuz string tablosunda böyle bir string olup olmadığını kontrol ediyoruz. Bir satır varsa bir sonraki karakteri okuruz ve satır yoksa önceki bulunan satırın kodunu akışa girip satırı tabloya koyar ve tekrar aramaya başlarız.

InitTable() işlevi tabloyu temizler ve tüm tek uzunluktaki satırları tabloya koyar.

Başlatma Tablosu();
CompressedFile.WriteCode(ClearCode);
CurStr=boş dizi;
while(not ImageFile.EOF())( //Dosya sonuna kadar
C=ImageFile.ReadNextByte();
if(CurStr+C tabloda ise)
CurStr=CurStr+C;//Bir karakter dizisini yapıştırın
başka(
code=CodeForString(CurStr);//code-byte değil!
AddStringToTable(CurStr+C);
CurStr=C; // Tek karakter dizisi
}
}
kod=CodeForString(CurStr);
CompressedFile.WriteCode(kod);
CompressedFile.WriteCode(CodeEndOfInformation);

Yukarıda bahsedildiği gibi, InitTable() işlevi, tüm olası tek karakterli dizeleri içermesi için dize tablosunu başlatır. Örneğin, bayt verilerini sıkıştırırsak, tabloda bu tür 256 satır olacaktır (“0”, “1”, ..., “255”). 256 ve 257 değerleri açık kod (ClearCode) ve bilgi sonu kodu (CodeEndOfInformation) için ayrılmıştır Algoritmanın ele alınan versiyonunda 12 bitlik bir kod ve buna göre değerler kullanılır ​​258'den 4095'e kadar satırların kodları kalır.Eklenen satırlar tabloya sırayla yazılır ve tablodaki satır dizini onun kodu olur.

ReadNextByte() işlevi, bir dosyadan bir karakter okur. WriteCode() işlevi, çıktı dosyasına bir kod (boyut olarak bir bayta eşit olmayan) yazar. AddStringToTable() işlevi ekler Yeni hat tabloya bir kod atfederek. Ek olarak, bu fonksiyon tablo taşma durumunu yönetir. Bu durumda, önceki bulunan satırın kodu ve temizleme kodu akışa yazılır, ardından tablo InitTable() işlevi tarafından temizlenir. CodeForString() işlevi, bir tabloda bir dize bulur ve bu dizenin kodunu döndürür.

Örnek:

45, 55, 55, 151, 55, 55, 55 sırasını sıkıştıralım. Ardından, yukarıda açıklanan algoritmaya göre, önce temizleme kodunu çıkış akışına yerleştireceğiz<256>, ardından başlangıçta boş olan dizeye "45" ekleyin ve tabloda "45" dizisi olup olmadığını kontrol edin. Başlatma sırasında bir karakterin tüm satırlarını tabloya girdiğimiz için, “45” dizisi tablodadır. Ardından, giriş akışından sonraki karakter 55'i okuruz ve "45, 55" dizisinin tabloda olup olmadığını kontrol ederiz. Tabloda henüz böyle bir satır yok. Tabloya “45, 55” dizisini giriyoruz (ilk serbest kod 258 ile) ve kodu akışa yazıyoruz<45>. Arşivlemeyi kısaca şöyle hayal edebilirsiniz:

• "45" - tabloda;
• "45, 55" - hayır. tabloya ekle<258>"45, 55". Akış için:<45>;
• "55, 55" - hayır. Masaya:<259>"55, 55". Akış için:<55>;
• "55, 151" - hayır. Masaya:<260>"55, 151". Akış için:<55>;
• "151, 55" - hayır. Masaya:<261>"151, 55". Akış için:<151>;
• "55, 55" - tablodadır;
• "55, 55, 55" - hayır. Tabloya: “55, 55, 55”<262>. Akış için:<259>;

LZW'nin özelliği, dekompresyon için string tablosunu dekompresyon için bir dosyaya kaydetmemize gerek olmamasıdır. Algoritma, dizi tablosunu yalnızca kod akışını kullanarak geri yükleyebileceğimiz şekilde oluşturulmuştur.

Biliyoruz ki, her kod için tabloya, orada zaten mevcut olan satırdan ve akıştaki bir sonraki satırın başladığı karakterden oluşan bir satır eklememiz gerekiyor.

Bu işlemi gerçekleştiren dekompresyon algoritması aşağıdaki gibidir:

code=File.ReadCode();
while(kod != CodeEndOfInformation)(
if(kod = ClearCode) (
Başlatma Tablosu();
code=File.ReadCode();
if(kod = CodeEndOfInformation)
(işi bitirmek);
ImageFile.WriteString(StrFromTable(kod));
eski_kod=kod;
}
başka(
if(InTable(kod)) (
ImageFile.WriteString(Tablodan(kod));
AddStringToTable(StrFromTable(eski_kod)+
FirstChar(StrFromTable(kod));
eski_kod=kod;
}
başka(
OutString= StrFromTable(eski_kod)+
FirstChar(StrFromTable(eski_kod));
ImageFile.WriteString(OutString);
AddStringToTable(OutString);
eski_kod=kod;
}
}
}

Burada ReadCode() işlevi, sıkıştırılmış dosyadan bir sonraki kodu okur. InitTable() işlevi, sıkıştırma sırasındaki eylemlerin aynısını gerçekleştirir, örn. tabloyu temizler ve bir karakterin tüm satırlarını tabloya koyar. FirstChar() işlevi bize bir dizgenin ilk karakterini verir. StrFromTable() işlevi, bir tablodan koda göre bir satır döndürür. AddStringToTable() işlevi tabloya yeni bir satır ekler (buna ilk serbest kodu atayarak). WriteString() işlevi, bir dosyaya bir dize yazar.

1. açıklama Gördüğünüz gibi akışa yazılan kodlar giderek artıyor. Tabloda 512 kodu, örneğin ilk kez görünene kadar, tüm kodlar 512'den küçük olacaktır. Ayrıca, sıkıştırma ve açma sırasında, aynı sembol işlenirken tablodaki kodlar eklenir, yani. "senkronize" olur. Sıkıştırma oranını artırmak için algoritmanın bu özelliğini kullanabiliriz. Tabloya 512 karakteri eklenene kadar, çıkış bit akışına 9 bitlik kodlar yazacağız ve 512 eklerken hemen 10 bitlik kodlar yazacağız. Buna göre, açıcı da tabloya 512 kodu eklenene kadar giriş akışının tüm kodlarını 9 bit olarak kabul etmek zorunda kalacak, ardından tüm giriş kodlarını 10 bit olarak algılayacaktır. Tabloya 1024 ve 2048 kodlarını eklerken de aynısını yapacağız.Bu teknik, sıkıştırma oranını yaklaşık %15 artırmanıza olanak tanır:

Not 2. Bir görüntüyü sıkıştırırken tablodaki satırları arama hızını sağlamak bizim için önemlidir. Her bir sonraki alt dizenin bir öncekinden bir karakter daha uzun olması gerçeğinden yararlanabiliriz, ayrıca bir önceki satır bizim tarafımızdan tabloda zaten bulunmuştur. Bu nedenle, belirli bir alt dize ile başlayan dizelere referansların bir listesini oluşturmak yeterlidir ve tablodaki tüm arama işlemi, önceki dize için listede yer alan dizeleri aramaya indirgenecektir. Böyle bir operasyonun çok hızlı bir şekilde gerçekleştirilebileceği açıktır.

Ayrıca, gerçekte tabloda yalnızca birkaçını saklamamızın yeterli olduğuna dikkat edin.<код предыдущей подстроки, добавленный символ>. Bu bilgi algoritmanın çalışması için oldukça yeterli. Yani 0'dan 4095'e kadar elemanları olan bir dizi<код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки>arama sorununu çok yavaş da olsa çözer.

Uygulamada, bir tabloyu depolamak için listelerde olduğu kadar hızlı, ancak bellekte daha kompakt bir karma tablo kullanılır. Tablo 8192 (2 13) öğeden oluşmaktadır. Her eleman içerir<код предыдущей подстроки; добавленный символ; код этой строки>. 20 bitlik arama anahtarı, tabloda tek bir sayı (anahtar) olarak saklanan ilk iki öğe kullanılarak oluşturulur. Bu sayının alt 12 biti kod için, sonraki 8 biti sembol değeri için verilir.

İşte bir hash işlevi olarak kullanılır:

Index(key)= ((key >> 12) ^ key) & 8191;

Nerede >> - bitsel olarak sağa kaydırma (tuş >> 12 - karakter değerini alırız), ^ - mantıksal işlem bitsel XOR, & mantıksal bitsel AND.

Böylece, sayılan sayıda karşılaştırma için, istenen kodu veya tabloda böyle bir kod olmadığına dair bir mesaj alırız.

Bu algoritma için en iyi ve en kötü sıkıştırma oranlarını hesaplayalım. Açıktır ki en iyi katsayı, büyük uzunlukta özdeş baytlardan oluşan bir zincir için elde edilecektir (yani, tüm noktaları kesinlik için 0 rengine sahip olan 8 bitlik bir görüntü için). Aynı zamanda, tablonun 258. satırına “0, 0”, 259. satırına - “0, 0, 0”, ... 4095. satırına - 3839 dizisi (=4095-256) yazacağız. ) sıfırlar. Bu durumda, temizleme kodu da dahil olmak üzere 3840 kod akışa girecektir (algoritmaya göre kontrol edin!). Bu nedenle, 2'den 3839'a (yani sıkıştırılmış zincirin uzunluğu) aritmetik ilerlemenin toplamını hesaplayıp 3840*12/8'e (12 bit kodlar akışa yazılır) bölerek en iyi sıkıştırma oranını elde ederiz. .

Egzersiz yapmak: En iyi sıkıştırma oranının tam değerini hesaplayın. Daha zor bir görev: 1. notu dikkate alarak aynı katsayıyı hesaplayın.

Egzersiz yapmak: Bu tür zincirleri oluşturmak için bir algoritma yazın. Bu şekilde elde edilen dosyayı standart arşivleyicilerle (zip, arj, gz) sıkıştırmaya çalışın. Sıkıştırma alırsanız, oluşturma algoritması yanlış yazılır.

LZW uygulandı GIF formatları ve TIFF.

Algoritma Özellikleri LZW:

Sıkıştırma oranları: Yaklaşık 1000, 4, 5/7 (en iyi, ortalama, en kötü oranlar). 1000 kez sıkıştırma, yalnızca yaklaşık 7 MB'ın katı olan tek renkli görüntülerde elde edilir.

Görüntü sınıfı: LZW, bir bilgisayarda oluşturulan 8 bitlik görüntülere odaklanır. Akıştaki aynı alt zincirler nedeniyle sıkıştırır.

Simetri: Neredeyse simetrik, tablodaki satır arama işleminin en uygun şekilde uygulanmasına tabidir.

Özellikler: Algoritmanın görüntüyü büyüttüğü durum oldukça nadirdir. LZW evrenseldir - geleneksel arşivleyicilerde kullanılan çeşitleridir.

Klasik Huffman Algoritması

60'lardan beri bilinen klasik algoritmalardan biri. Görüntüde yalnızca aynı baytların oluşma sıklığını kullanır. Oluşan giriş akışındaki karakterleri eşleştirir Daha kez, daha kısa uzunluktaki bitlerden oluşan bir zincir. Ve aksine, nadir - daha uzun bir zincir. İstatistik toplamak için görüntünün üzerinden iki kez geçiş yapılması gerekir.

İlk olarak, bazı tanımları tanıtalım.

Tanım. Y harfi olsun =( A 1 , ..., bir r ) sonlu sayıda harften oluşur. Y'den sonlu bir karakter dizisi

arayacağız kelime Y alfabesinde ve sayı N - kelime uzunluğu A. Bir kelimenin uzunluğu şu şekilde gösterilir: l(A).

W harfi verilsin, W =( B 1 , ..., B Q ). Başından sonuna kadar B W ve aracılığıyla alfabedeki kelimeyi belirtin S (K)W alfabesindeki tüm boş olmayan sözcüklerin kümesidir.

İzin vermek S =S(Y ) -Y alfabesindeki boş olmayan tüm kelimelerin kümesi ve S"- kümenin bazı alt kümeleri S. eşleme de olsun F, hangi her kelime A, A? S(Y), kelimeyle eşleşir

B=F(A), B ? S(B) .

Kelime İÇİNDE arayacağız mesaj kodu A ve kelimeden geçiş A onun koduna - kodlama.

Tanım. Y alfabesinin harfleri ile W alfabesinin bazı kelimeleri arasındaki yazışmayı düşünün:

A 1 - B 1 ,
A 2 - B 2 ,
. . .
A R- B R

Bu yazışma denir plan ve S ile gösterilir. Kodlamayı şu şekilde tanımlar: S" (K)=S (K)adlı bir kelime ile eşleşir. kelime kodu A.Kelimeler B 1 ... B R isminde temel kodlar. Bu tip kodlama denir alfabetik kodlama

Tanım. bırak kelime İÇİNDE forma sahip

B=B"B"

sonra kelime B" isminde başlangıç veya kelime öneki B, bir B" - bir kelimenin sonu B. Bu durumda, boş L kelimesi ve kelimenin kendisi B bir kelimenin başlangıçları ve bitişleri olarak kabul edilir B .

Tanım . S düzeni önek özelliğine sahiptir, eğer herhangi biri içinBen Ve J(1? Ben , J? ri? J) kelime B Benbir kelime öneki değildir B J .

teorem 1.Şema S ise önek özelliğine sahipse, alfabetik kodlama bire bir olacaktır.

Diyelim ki bize Y alfabesi verildi =( A 1 ,..., A R} (R >1 ) ve bir dizi olasılık P 1 , . . . , P R sembollerin görünümü A 1 ,..., A R. Ayrıca, W alfabesi verilsin, W =( B 1 , ..., B Q} (Q >1 ). O zaman bir dizi S alfabetik kodlama şeması oluşturmak mümkündür.

bir 1 - B 1 ,
. . .
A R- B R

karşılıklı benzersizlik özelliğine sahip olmak.

Her devre için ortalama bir uzunluk girebilirsiniz. ben evlenmek , temel kodun uzunluğunun matematiksel beklentisi olarak tanımlanır:

- kelime uzunlukları.

Uzunluk ben evlenmek Şema S ile kodlama yapılırken ortalama kelime uzunluğunun kaç kat arttığını gösterir.

gösterilebilir ki ben evlenmek minimumuna ulaşır ben * bazı S üzerinde ve olarak tanımlanır

Tanım .Şema S ile tanımlanan kodlarben bkz = ben * , arandı minimum fazlalık içeren kodlar veya Huffman kodları.

Minimum artıklığa sahip kodlar, ortalama olarak, uygun kodlama ile kelime uzunluklarında minimum artışı sağlar.

Bizim durumumuzda, Y alfabesi =( A 1 ,..., A R) giriş akışının sembollerini ve W =(0,1) alfabesini, yani sadece sıfır ve birden oluşur.

Devre S'yi oluşturmak için algoritma aşağıdaki gibi temsil edilebilir:

Aşama 1. Giriş alfabesinin tüm harflerini azalan olasılık sırasına göre düzenleriz. Eşleşen tüm kelimeleri sayma B Benalfabesinden W =(0,1) boştur.

Adım 2İki karakteri birleştirmek bir ben r-1 Ve bir ben Raz olasılıkla pi r-1 Ve pi Rsahte bir karaktere A"{bir ben r-1 hava ) olasılıkla pi r-1+pi R. B kelimesinin başına 0 ekleyin Ben r-1(B Ben r-1=0B Ben r-1 ) ve B kelimesinin başına 1 Ben R(B Ben R=1B Ben R).

Aşama 3 Sıralı karakterler listesinden çıkarma bir ben r-1 Ve bir ben R, oraya bir sözde sembol koy A"{bir ben r-1 hava ). Gerekirse tüm kelimeler için 1 veya sıfır ekleyerek 2. adımı gerçekleştiriyoruz. B Ben, listede 1 sözde karakter kalana kadar sözde karakterlere karşılık gelir.

Örnek: Diyelim ki alfabemizde 4 harf var Y =( A 1 ,..., A 4 } (R =4 ), P 1 =0.5, P 2 =0.24,P 3 =0.15,P 4 = 0.11 Daha sonra devreyi oluşturma süreci aşağıdaki gibi gösterilebilir:

2. adıma karşılık gelen eylemleri gerçekleştirerek, 0.26 olasılıkla sözde bir karakter elde ederiz (ve karşılık gelen kelimelere 0 ve 1 atarız). Değiştirilen liste için bu eylemleri tekrarlayarak, 0,5 olasılıkla sahte bir sembol elde ederiz. Ve son olarak, son adımda, toplam 1 olasılık elde ederiz.

Kodlama kelimelerini geri yüklemek için, ortaya çıkan ikili ağacın ilk karakterlerinden sonuna kadar okları takip etmemiz gerekiyor. Yani, olasılığı olan bir sembol için P 4 , B 4 = 101 elde ederiz, çünkü P 3 için B 3 = 100 elde ederiz P 2 için B 2 = 11 elde ederiz P 1 B 1 elde ederiz = 0. Şema ne anlama gelir: A 1 - 0,
A 2 - 11
A 3 - 100
A 4 - 101 Bu şema, bir Huffman kodu olan bir önek kodudur. Akışta en sık görülen karakter A 1 en kısa kelimeyi 0 ve en az sıklıkta kodlayacağız A 4 uzun kelime 101.

Karakterin bulunduğu 100 karakterlik bir dizi için A 1 50 kez buluşacak, sembol A 2 - 24 kez, sembol A 3 - 15 kez ve simgesi A 4 - 11 kez, bu kod 176 bitlik bir dizi elde etmenizi sağlar ( ). Onlar. akış sembolü başına ortalama 1,76 bit harcayacağız.

Teoremin ispatları ve inşa edilen devrenin aslında bir Huffman kodunu tanımladığı gerçeği için bkz.

Yukarıdan da anlaşılacağı gibi, klasik Huffman algoritması, kodlanmış karakterlerin ve kodlama zincirlerinin bir dosyaya karşılık geldiği bir tablo yazmayı gerektirir.

Uygulamada çeşitleri kullanılmaktadır. Bu nedenle, bazı durumlarda ya sabit bir tablo kullanmak ya da onu "uyarlanabilir", yani arşivleme/arşivden çıkarma sürecinde. Bu hileler bizi görüntünün üzerinden iki kez geçmekten ve tabloyu dosyayla birlikte saklama ihtiyacından kurtarıyor. Sabit tablo kodlaması, JPEG arşivlemede ve aşağıda tartışılan CCITT Grup 3 algoritmasında son adım olarak kullanılır.

Klasik Huffman algoritmasının özellikleri:

Sıkıştırma oranları: 8, 1.5, 1 (en iyi, ortalama, en kötü oranlar).

Görüntü sınıfı: Saf görüntülere neredeyse hiç uygulanmadı. Genellikle daha karmaşık devrelerde sıkıştırma adımlarından biri olarak kullanılır.

Simetri: 2 (sıkıştırılmış veri dizisinden iki geçiş gerektirmesi nedeniyle).

Özellikler: En kötü durumda orijinal verilerin boyutunu büyütmeyen tek algoritma (arama tablosunu dosyayla birlikte saklama ihtiyacı dışında).

Algoritmanın benzer bir modifikasyonu, siyah beyaz görüntüleri sıkıştırırken kullanılır (piksel başına bir bit). Bu algoritmanın tam adı CCITT Grup 3'tür. Bu, bu algoritmanın Uluslararası Telgraf ve Telefon Danışma Komitesi'nin (Uluslararası Telgraf ve Telefon Danışma Komitesi) üçüncü standardizasyon grubu tarafından önerildiği anlamına gelir. İçindeki ardışık siyah ve beyaz noktaların dizileri, sayılarına eşit bir sayı ile değiştirilir. Ve bu dizi de Huffman'a göre sabit bir tablo ile sıkıştırılmıştır.

Tanım: Aynı renkteki ardışık görüntü noktaları kümesine denir. seri.Bu nokta kümesinin uzunluğuna denir. seri uzunluğu.

Aşağıdaki tablo iki tür kodu tanımlar:

• Seri tamamlama kodları- 0'dan 63'e 1'lik artışlarla ayarlayın.
• Bileşik (ek) kodlar- 64'lük artışlarla 64'ten 2560'a ayarlanır.

Uygulamada, görüntünün siyahın hakim olduğu durumlarda, sıkıştırmadan önce görüntüyü ters çeviririz ve bununla ilgili bilgileri dosya başlığına yazarız.

Sıkıştırma algoritması şöyle görünür:

for(resmin tüm satırlarında) (
Dizeyi bir dizi çalışma uzunluğuna dönüştürün;
(tüm seriler için) (
if(seri beyaz) (
L= seri uzunluğu;
while(L > 2623) ( // 2623=2560+63)
L=L-2560;
BeyazKodFor(2560);
}
eğer(L > 63) (
L2=MaksimumSabitKodDaha AzL(L);
L=L-L2;
YazBeyazKodFor(L2);
}
YazBeyazKodFor(L);
//Bu her zaman bir çıkış kodudur
}
başka(
[Beyaz seriye benzer kod,
yazılı olmaları farkıyla
siyah kodlar]
}
}
// Resim satırı bitişi
}

Siyah ve beyaz dizi dönüşümlü olduğundan, beyaz dizi kodu ve siyah dizi kodu aslında dönüşümlü olarak çalışacaktır.

açısından düzenli ifadeler görüntümüzün her satırı için (yeterince uzun, beyaz bir noktadan başlayarak) şu şekilde bir çıktı bit akışı elde edeceğiz:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Burada ()* - 0 veya daha fazla tekrar, () + .- 1 veya daha fazla tekrar, - 1 veya 0 defa içerir.

Yukarıdaki örnek için: 0, 3, 556, 10... algoritma aşağıdaki kodu üretecektir:<Б-0><Ч-3><Б-512><Б-44><Ч-10>veya tabloya göre 00110101 10 0110010100101101 0000100 (konudaki farklı kodlar kolaylık sağlamak için vurgulanmıştır). Bu kod, önek kodları özelliğine sahiptir ve kolayca bir çalışma uzunlukları dizisine geri katlanabilir. Verilen 569 bitlik dizi için 33 bitlik bir kod aldığımızı hesaplamak kolaydır, yani. sıkıştırma oranı yaklaşık 17 kattır.

Soru: En kötü durumda dosya boyutu kaç kat artar? Neden? (Algoritma belirtimlerinde verilen cevap tam değildir, çünkü en kötü sıkıştırma oranının daha büyük değerleri olabilir. Bunları bulun.)

Egzersiz yapmak:Çalışma uzunlukları - 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, 120 bayt boyutunda ((442+2+..+231)/8) olarak yazılmış bir görüntü dizesi verildi. CCITT Grup 3 algoritmasını kullanarak bu dizinin sıkıştırma oranını hesaplayın.

Tamamlama kodu tablosu:

Bileşik kod tablosu:

Bu algoritma TIFF formatında uygulanmaktadır.

Algoritma Özellikleri CCITT Grup 3

Tipik bir dijital kamera görüntüsü yaklaşık 3000x2000 çözünürlüğe sahiptir, yani yaklaşık 6 megapiksel; Rengi temsil etmek için tipik olarak piksel başına 24 bit kullanılır. Böylece, ilk veri miktarı yaklaşık 17 megabayttır. Profesyonel görüntü giriş aygıtları için, ortaya çıkan bit eşlemin boyutu çok daha büyük olabilir ve renk derinliği piksel başına 48 bit olabilir ("Modern bit eşlem grafik donanımı"). Buna göre, bir görüntünün boyutu 200 megabayttan fazla olabilir. Bu nedenle, algoritmalar çok alakalı. sıkıştırma görüntüler veya başka bir deyişle, bir görüntüyü temsil eden veri miktarını azaltmanıza izin veren algoritmalar.

İki ana algoritma sınıfı vardır:

1. A'ya algoritma denir kayıpsız sıkıştırma(eng. kayıpsız sıkıştırma ) herhangi bir görüntü için I A (I) = I 1 ve A -1 (I 1) = I olacak şekilde bir A -1 (A'nın tersi) algoritması varsa. Görüntü I, bir dizi piksel özellik değeri olarak tanımlanır; A algoritmasını I'e uyguladıktan sonra, I1 veri setini elde ederiz. Kayıpsız sıkıştırma kullanılır grafik formatlarıŞunlar gibi görüntü temsilleri: GIF, PCX, PNG, TGA, TIFF 1 Genel konuşma, verilen format kayıplı sıkıştırmayı da destekler., bir demet kendi formatları dijital fotoğraf makinesi üreticilerinden vb.);
2. A'ya algoritma denir kayıplı sıkıştırma(eng. kayıplı sıkıştırma), orijinal görüntüyü doğru bir şekilde geri yükleme yeteneği sağlamıyorsa. Yaklaşık kurtarma sağlayan A ile eşleştirilen algoritma A * olarak gösterilecektir: görüntü için I A(I) = I 1 , A * (I 1) = I 2 ve ortaya çıkan geri yüklenen görüntü I 2, I ile tam olarak örtüşmez. . A, A * çifti, yüksek sıkıştırma oranları sağlamak ve yine de görsel kaliteyi korumak için seçilir, örn. I ve I 2 arasındaki algıda minimum bir fark elde etmek için. Kayıplı sıkıştırma şu grafik biçimlerinde uygulanır: JPEG, JPEG2000, vb.

Bu ders, bilginin büyük bir maliyetle elde edildiği durumlarda (örneğin, tıbbi görüntüler veya uydu görüntüleri) veya diğer durumlarda gerekli olan kayıpsız sıkıştırma hakkındadır. en ufak bir bozulma istenmeyen.

13.2. İdeal bir algoritmanın olmaması

Önceki paragrafta daha önce bahsedildiği gibi, görüntü I bir piksel öznitelik değerleri kümesi (dizisi) olarak kabul edilir. Bu derste ayrıca, tüm algoritmalar ve ifadeler hem görüntülere hem de öğeleri sonlu sayıda değer alabilen gelişigüzel dizilere uygulanır.

Bildirim 13.2.1. Herhangi bir veri setini kayıpsız sıkıştırabilen bir algoritma yoktur.

N bit boyutunda 2 N dizi vardır (bir biti minimum bilgi taşıyıcı olarak kabul edeceğiz). Öyle bir A algoritması olsun ki, burada |I| - veri hacmi (dizi uzunluğu). M = maksimum M k , sonra M olsun< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 +...+2 M = 2 M+1 -2< 2 N . Çelişki.

Belirli bir görüntü sınıfını etkili bir şekilde sıkıştıracak algoritmalar geliştirmenin mantıklı olduğu ifadeden çıkar; aynı zamanda, bu algoritmalar için her zaman sıkıştırma sağlamayacakları görüntüler olacaktır.

13.3. Uzunluk Kodlama (RLE) Algoritmalarını Tekrarla

Bu tür algoritmalar (tekrar uzunluğu kodlama algoritmaları 2 Literatürde sıklıkla başka bir isim bulunur - grup kodlaması.(RLE 3 İngilizce Çalıştırma Uzunluğu Kodlaması)) en basit ilkeye dayanmaktadır: orijinal dizinin yinelenen öğe gruplarını bir çiftle (nicelik, öğe) veya yalnızca nicelikle değiştireceğiz.

RLE - bit seviyesi

Orijinal verileri bir bit dizisi düzeyinde ele alacağız; örneğin, temsil eden siyah beyaz görüntü. Genellikle art arda birkaç 0 veya 1 vardır ve yalnızca bir satırdaki aynı basamakların sayısını hatırlayabilirsiniz. Onlar. 0000 11111 000 11111111111 dizisi, 4 5 3 11 tekrar sayısının sayı kümesine karşılık gelir. Aşağıdaki nüans ortaya çıkar: tekrar sayısını gösteren sayıların da bit olarak kodlanması gerekir. Her tekrar sayısının 0 ila 7 arasında değiştiğini varsayabiliriz (yani, tam olarak üç bit ile kodlanabilir), ardından 11111111111 dizileri 7 0 4 , yani. 7 birler, 0 sıfırlar, 4 birler. Örneğin 21 bir, 21 sıfır, 3 bir ve 7 sıfırdan oluşan bir dizi şu şekilde kodlanır: 111 000 111 000 111 111 000 111 000 111 011 111 , yani 51 bit uzunluğundaki orijinal diziden 36 bitlik bir dizi elde edilmiştir.

Bu yöntemin fikri, faks gönderirken kullanılır.

RLE - bayt düzeyi

Girişin, piksel yoğunluk değerine 1 baytın atandığı gri tonlamalı bir görüntü olduğunu varsayalım. Açıktır ki, siyah beyaz bir raster ile karşılaştırıldığında, aynı bitlerden oluşan uzun bir zincir beklentisi önemli ölçüde azalır.

Giriş akışını baytlara (harflere) ayıracağız ve tekrarlanan harfleri bir çift (sayı, harf) olarak kodlayacağız.

Onlar. AABBBCDAA kodlaması (2A) (3B) (1C) (1D) (2A) . Ancak, hiçbir şeyin tekrarlanmadığı uzun veri uzantıları olabilir ve biz her harfi bir çift (sayı, harf) olarak kodlarız.

Diyelim ki sabit bir sayımız (harf) M (0'dan 255'e kadar) var. Daha sonra tek bir harf kendi başına kodlanabilir, - çıktı = S ve birkaç harf veya varsa, o zaman çıktı = CS , burada C > M ve C - M, ardışık S harflerinin sayısıdır. Örneğin, yalnızca kod çözme algoritmasını veriyoruz.

// M - sabit sınır // karakterleri giriş akışından sırayla oku // giriş - giriş - sıkıştırılmış sıra // çıkış - çıkış - sıkıştırılmamış sıra while(in.Read(c)) ( if(c > M) ( // durum sayacı n = c - M;in.Read(c);for(i = 0;i)< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Listeleme 13.1. RLE Kod Çözme Algoritması - Bayt Seviyesi

M numarası genellikle 127'dir. Bu algoritmanın bir modifikasyonu daha yaygın olarak kullanılır, burada sayaç işareti, okunan karakterin en önemli 2 bitindeki birlerin varlığıdır. Kalan 6 bit, sayacın değeridir.

Bu algoritmanın bu modifikasyonu PCX formatında kullanılır. Ancak, bu algoritmanın modifikasyonları nadiren kendi başlarına kullanılır, çünkü Bu algoritmanın etkili olduğu dizilerin alt sınıfı nispeten dardır. Algoritma değişiklikleri, sıkıştırma hattının aşamalarından biri olarak kullanılır (örneğin, JPEG'de,

Algoritmanın ilk versiyonu

Bu algoritmanın uygulanması son derece kolaydır. Çalışma Uzunluğu Kodlaması (RLE), en eski ve en basit grafik arşivleme algoritmalarından biridir. İçindeki görüntü (aşağıda açıklanan birkaç algoritmada olduğu gibi), tarama çizgileri boyunca bir bayt zincirine çekilir. RLE'de sıkıştırmanın kendisi gerçekleşir orijinal görüntüde aynı bayt zincirlerinin olması nedeniyle. Onları çiftlerle değiştirmek<счетчик повторений, значение>veri fazlalığını azaltır.

algoritma baskıyı azaltmaşuna benziyor:

başlatma(...); Yapmak(

bayt= ImageFile.ReadNextByte(); if(counter(byte)) ( counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l to counter)

DecompressedFile.WriteByte(değer))

DecompressedFile.WriteByte(byte)) while (UmageFile.EOF ()) ;

Bu algoritmada sayacın (counter) işareti, okunan dosyanın ilk iki bitindekilerdir:

Buna göre kalan 6 bit, 1'den 64'e kadar değer alabilen bir sayaçta harcanıyor. 64 tekrarlı baytlık bir diziyi 2 bayta dönüştürüyoruz, yani 32 kez sıkıştıracağız.

Egzersiz yapmak. Algoritma yap sıkıştırma RLE algoritmasının ilk versiyonu için.

Algoritma, iş grafikleri için tasarlanmıştır - geniş tekrar eden renk alanlarına sahip görüntüler. Dosyanın büyüdüğü durum, bu basit algoritma için çok nadir değildir. İşlenmiş renkli fotoğraflara parti kodlaması uygulanarak kolayca elde edilebilir. Görüntüyü 2 kat büyütmek için tüm piksellerin değerleri ikili 11000000'den büyük olan ve arka arkaya çiftler halinde tekrar etmeyen bir görüntüye uygulanmalıdır.

Egzersiz yapmak. RLE algoritması için 2-3 "kötü" görüntü örneği önerin. Neden boyutunu açıklayın sıkıştırılmış dosya orijinal dosyadan daha büyük.

Bu algoritma PCX biçiminde uygulanmaktadır. Ek 2'deki bir örneğe bakın.

Algoritmanın ikinci versiyonu

Bu algoritmanın ikinci varyantı daha yüksek bir maksimum sıkıştırma oranına sahiptir ve orijinal dosyanın boyutunu küçültür. Bunun için dekompresyon algoritması şöyle görünür:

başlatma(...); Yapmak(

bayt = ImageFile.ReadNextByte(); sayaç = Düşük7bit(bayt)+1; if(if repeat flag(byte)) ( değer = ImageFile.ReadNextByte(); for (i=l saymak için)

CompressedFile.WriteByte(değer)

for(i"=l saymak için) (

değer = ImageFile.ReadNextByte(); CompressedFile.WriteByte(değer) } ) while (!ImageFile.EOFO) ;

Bu algoritmadaki bir tekrar işareti, karşılık gelen baytın yüksek sırasındaki bir birimdir:

J 0 7 bit___ I Neyi atlayacağım ben ... Neyi atlayacağım ben

^1 7 bit I Neyi tekrarlamalıyım I

Kolayca hesaplanabileceği gibi, bu algoritma dosyayı en iyi ihtimalle 64 kat sıkıştırır (önceki sürümdeki gibi 32 kez değil), en kötü ihtimalle 1/128 oranında artırır. Bu algoritmanın sıkıştırma derecesinin ortalama göstergeleri, birinci varyantın göstergeleri seviyesindedir.

(Ek Egzersiz. RLE algoritmasının ikinci versiyonu için bir sıkıştırma algoritması yazın.

Benzer sıkıştırma şemaları, TIFF formatının yanı sıra TGA formatında da desteklenen algoritmalardan biri olarak kullanılır.

RLE algoritmasının özellikleri:

Sıkıştırma seviyeleri: ilk seçenek: 32, 2, 0.5. İkinci seçenek: 64, 3, I 128/129. (En iyi, ortalama, en kötü derece).

Görüntü sınıfı: algoritma, I olmayan görüntülere odaklanır büyük miktar renkler: ticari ve bilimsel grafikler.

Simetri: yaklaşık bir

Özellikler: Algoritmanın olumlu yönleri, belki de yalnızca ek bellek gerektirmemesi gerçeğine bağlanabilir. \ arşivlerken ve açarken de hızlı çalışır. İlginç özel! Grup kodlamanın özelliği, olmayanlar için arşivleme derecesinin! Hangi görüntüler, yalnızca görüntü paletindeki renklerin sırasını değiştirerek önemli ölçüde geliştirilebilir.

Basit kodlama yöntemi ( ÇALIŞMA UZUNLUĞU KODLAMASI), popüler arşivleyiciler tarafından başarıyla kullanılır.

Bu yöntem, bir satırda tekrarlanan karakterlerin uzunluğunu saymaya ve bu karakterlerin bir dizisi yerine paketlenmiş dosyaya yazmaya dayanır, tip bilgisi: karakter sayısı ve tekrarlanan karakterin kendisi. Örneğin, " gibi bir dize var. AAAAABBCCADDDEEL". Şunun gibi bir dizi halinde toplanacak: " 5A3B3CADDEEL". Örnekten de görülebileceği gibi 5 harfli "A" dizisi "5" ve "A" olmak üzere iki karaktere sıkıştırılmış ve "DD", "EE", "L" dizileri hiç paketlenmemiştir. , çünkü bu karakterleri "uzunluk" + "harf" türünde bir diziye dönüştürmekten kazanç yoktur.

Bu yöntemi kullanarak bir dosyayı paketlemeyi uygularken, paket açıcının kontrol bilgilerini paketlenmiş bir dosyadan paketlenmemiş verilerden nasıl ayırt edeceği gibi zorluklar ortaya çıkar. Örneğin, yukarıda tartışılan durumda olduğu gibi, paket açıcı "5" kontrol karakterini aynı koda sahip paketlenmemiş bir karakterden ayırt edecek mi? Bu sorunu çözmek için iki seçenek vardır:

(BEN). Paketlenmiş dosyada diğerlerinden daha az geçen veya hiç görülmeyen bir sembol bulun ve onu kontrol olarak kullanın. Aşağıdaki açıklamada kolaylık olsun diye önek diyelim. Şimdi "AAAAA" dizisi, paketleyici tarafından ön eke (8 bit), "A" (8 bit), miktara (8 bit) dönüştürülecek, yani 5 bayt üç ile değiştirilecektir. Paketleme sırasında kaynak dosyada önek koduna sahip bir bit ile karşılaşılırsa, ortaya çıkan dosyaya önek koduna sahip iki bayt yazılır ve bu özellikle paket açıcı, önekin nerede bir sembol olduğunu ve kontrolün nerede olduğunu belirleyecektir. bilgi. Bu yöntemin modifikasyonları mümkündür, örneğin:

1. Miktarı sekiz bit ile değil, üç, dört vb. ile kodlayın; bu, paketleme yüzdesini artıracak, ancak sınırlayacaktır. maksimum uzunluküç bitlik kodlama durumunda paketlenebilen yinelenen karakterler (3'ten 10'a, yani 000=3, ..., 111=10) ve uzunluk 10 karakterden fazlaysa on karakter paketleyin.

2. Tekrarlanan karakterlerin sayısı sekiz bit değil, üç bit ile kodlandığında ve tekrarlanan karakterlerin uzunluğu 265 ile sınırlandırıldığında ikinci bir değişiklik mümkündür. 256 farklı uzunluğun 3 bite nasıl kodlanacağı sorusu ortaya çıkar. Mümkün olduğu ortaya çıktı, ancak yalnızca aralık 3'ten 9'a kadardır, ancak tekrarlanan karakterlerin uzunluğu 9'dan fazlaysa, o zaman "111" üç bit olarak yazılır. ikili kod, "7" ye eşittir. Bu, dizinin gerçek uzunluğunun bir sonraki baytta olduğu anlamına gelir (10 ila 256 karakter arasındaki uzunluklar için 8 bit tahsis edilir).

İşte bazı örnekler:

Sıralarımız var:

a) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"

b) "CBBBBBBBBEEEEEEEEEA"

Onları paketleyelim:

1. RLE yöntemiyle (çalışma uzunluğu kodlaması - tekrarlanan baytları paketleyin).

a) "D" ön ekini alın, şunu elde ederiz:
"D", "D", "A", 5, "D", "B", 10, "C", "D", "A", 15.

Sıkıştırma yüzdesi = 12 bayt/32 bayt = %37,5

Paketlenmiş bir dosyada, önek baytı ilk bayttır, böylece paketi açan kişi hangi baytın önek olduğunu bilir.

b) "A"'ya eşit bir önek alın, ancak aslında paketleyici bunu yapmayacaktır, çünkü bu dizide çok fazla karakter yoktur, bu nedenle arşivleyici kullanılmayan bir karakteri önek olarak alacaktır.

Paketlenmiş sıra:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"

Sıkıştırma yüzdesi = 10 bayt/22 bayt = %45,5

2.Şimdi verimliliği analiz etmek için RLE yönteminin 1. modifikasyonuna göre aynı satırları aynı önek değerleri ile paketleyelim.

"D" , "D" , "A" , 2 , "D" , "B" , 7 ,
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit

"D" , "A" , 7 , "D" , "A" , 2
8 bit 8 bit 3 bit 8 bit 8 bit 3 bit

Sıkıştırma yüzdesi=84 bit/(22*8) bit = %32,8

"A" , "C" , "A" , "B" , 7 , "A" , "E" , 7 , "A" , "A"
8 bit 8 bit 8 bit 8 bit 4 bit 8 bit 8 bit 3 bit 8 bit 8 bit

Sıkıştırma yüzdesi=70 bit/(22*8) bit = %39,8

3. Şimdi son değişikliğin etkinliğini kontrol edelim:

a) Paketlenmiş sıra:

"D" , "D" , "A" , 2 , "D" , "B" , 7 , 0
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit 8 bit

"D" , "A" , 7 , 5
8 bit 8 bit 3 bit 8 bit

Sıkıştırma yüzdesi = 81 bit/(32*8) bit = %31,6

b) Paketlenmiş sıra:

"A" , "C" , "A" , "B" , 7 , 0 , "A" , "E"
8 bit 8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 8 bit

7 , 0 , "A" , "A"
3 bit 8 bit 8 bit 8 bit

Sıkıştırma yüzdesi = 86 bit/(22*8) bit = %48,9

Bu örnekler, paketlenmiş verilerin içeriğine bağlı olarak, algoritmalardan birinin veya diğerinin etkili olduğunu göstermektedir, dolayısıyla hangi algoritmanın daha verimli olduğunu seçmek için bunları farklı dosya türleri üzerinde test etmeniz gerekir.

(II). Paketi açıcı için kontrol bilgilerinin kaydedilmesi için ikinci seçenek şu şekildedir: metinde tek bir karakter varsa, o zaman bir kontrol biti bire eşittir ve bu karakterin kendisi çıktı dosyasına yazılır. Bir tekrarlanan bayt dizisi varsa, örneğin "AAAAAA" varsa, paketlenmiş bilgi şu şekilde görünecektir: 0 (1 bit), bayt A (8 bit), say (3-8 bit);

Netlik için bir örnek verelim. Bunu yapmak için, önceki örneklerden dizileri alın.

1) Tekrarlanan bayt sayısı 8 bit olarak kodlanmıştır.

a) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.

Sıkıştırma yüzdesi = 71 bit/256 bit = %27,7

b) 1 , "C" , 0 , "B" , 10 , 0 , "E" , 10 , 1 , "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.

Sıkıştırma yüzdesi = 52 bit/176 bit = %29,5

2) Şimdi, 2 ila 8 (0 - 6) arasındaki değerlerin kodlanabileceği tekrarlanan bayt sayısını kodlamak için 3 bit alalım, eğer tekrar eden dizinin uzunluğu daha büyükse, bu üç bit şunları içerir: "111" (7 ondalık) ve gerçek uzunluk bir sonraki bayttadır (uzunluk 9 - 264).

a) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.

Sıkıştırma yüzdesi = 64 bit/256 bit = %20,3

b) 1 , "C" , 0 , "B" , 7 , 1 , 0 , "E" , 7 , 1 , 1, "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.

Sıkıştırma yüzdesi = 58 bit / 176 bit = %33

Miktar 4 bit (2..16) olarak kodlanmışsa, o zaman

1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.

Sıkıştırma yüzdesi = 44 bit / 176 bit = %25

Örneklerden de görebileceğiniz gibi, ikinci paketleme seçeneği, genellikle büyük çoğunluğu oluşturan iki karakterle başlayan dizileri sıkıştırdığından daha etkilidir. İlk varyant, üç karakterden başlayan dizileri paketledi.