Hangi sıkıştırma yöntemi en iyi sonucu verir. Örnek veri seti. Kayıplı sıkıştırma

dersin amacı: veri sıkıştırmanın ana türlerini ve algoritmalarını inceleyin ve Huffman yöntemini ve kod ağaçlarını kullanarak veri sıkıştırma sorunlarının nasıl çözüleceğini öğrenin.

Claude Shannon, bilgi sıkıştırma biliminin kurucusu olarak kabul edilir. Optimum kodlama konusundaki teoremi, bilgi kodlarken ne için çaba gösterilmesi gerektiğini ve şu veya bu bilginin ne kadar sıkıştırılacağını gösterir. Ayrıca, İngilizce metnin fazlalığının ampirik değerlendirmesi üzerine deneyler yaptı. Chenon, insanlardan bir sonraki harfi tahmin etmelerini istedi ve doğru tahmin etme olasılığını değerlendirdi. Bir dizi deneye dayanarak, şu sonuca vardı: Bilgi miktarı v İngilizce metin karakter başına 0,6 ila 1,3 bit arasında değişir. Shannon'ın araştırmasının sonuçlarının sadece on yıllar sonra gerçekten talep görmesine rağmen, bunların önemini abartmak zordur.

Veri sıkıştırma Artıklığı azaltarak veri miktarını azaltan bir süreçtir. Veri sıkıştırma, veri parçalarının kompakt bir şekilde düzenlenmesiyle ilişkilidir Standart boy... Veri sıkıştırma iki ana türe ayrılabilir:

• Kayıpsız sıkıştırma (tamamen tersine çevrilebilir)Önceden kodlanmış bir veri parçasının paketinden çıkarıldıktan sonra herhangi bir değişiklik yapılmadan kurtarıldığı bir veri sıkıştırma yöntemidir. Her veri türünün genellikle kendi optimal algoritmalar kayıpsız sıkıştırma
• Kayıplı sıkıştırma sağlamak için bir veri sıkıştırma yöntemidir. maksimum derece orijinal veri dizisi sıkıştırıldığında, içerdiği verilerin bir kısmı atılır. Metin, sayısal ve tablo verileri için bu tür sıkıştırma yöntemlerini uygulayan programların kullanılması kabul edilemez. Temel olarak, bu tür algoritmalar, ses ve video verilerini, statik görüntüleri sıkıştırmak için kullanılır.

Veri sıkıştırma algoritması (arşivleme algoritması) Veri yazma fazlalığını ortadan kaldıran bir algoritmadır.

Materyalin sunumunda daha sonra kullanılacak bir dizi tanım sunalım.

kod alfabesi- giriş akışının tüm sembollerinin kümesi. İngilizce metinleri sıkıştırırken, genellikle 128 ASCII kodunun çoğu kullanılır. Görüntüleri sıkıştırırken, bir dizi piksel değeri 2, 16, 256 veya başka herhangi bir sayıda öğe içerebilir.

kod karakteri Sıkıştırılacak en küçük veri birimidir. Tipik olarak bir karakter 1 bayttır, ancak bir bit, bir trit (0,1,2) veya başka bir şey olabilir.

kod kelimesi sıra mı kod karakterleri kodun alfabesinden. Tüm kelimeler aynı uzunluğa (karakter sayısı) sahipse, böyle bir kod denir. üniforma (sabit uzunluk), ve farklı uzunluktaki kelimelere izin veriliyorsa, o zaman - düzensiz ( değişken uzunluk) .

Kod, eksiksiz bir sözcük kümesidir.

Jeton- bir sıkıştırma algoritması tarafından sıkıştırılmış bir akışa yazılan bir veri birimi. Bir belirteç, sabit veya değişken uzunlukta birkaç alandan oluşur.

İfade etmek- sıkıştırmada daha fazla kullanım için bir sözlüğe yerleştirilen bir veri parçası.

kodlama- veri sıkıştırma işlemi.

kod çözme- veri kurtarma işleminin gerçekleştirildiği ters kodlama işlemi.

Sıkıştırma oranı Bir sıkıştırma yönteminin etkinliğini belirtmek için en yaygın olarak kullanılan niceliklerden biridir.

0,6 değeri, verilerin orijinal hacmin %60'ı olduğu anlamına gelir. 1'den büyük değerler, çıkış akışının giriş akışından daha büyük olduğu anlamına gelir (negatif sıkıştırma veya genişleme).

Sıkıştırma oranı Sıkıştırma oranının tersidir.

1'den büyük değerler sıkıştırmayı, 1'den küçük değerler ise genişlemeyi gösterir.

Ortalama kod kelimesi uzunluğu Tüm kod sözcüklerinin uzunluklarının olasılık ağırlıklı toplamı olarak hesaplanan bir değerdir.

L cp = p 1 L 1 + p 2 L 2 + ... + p n L n,

kod kelimelerinin olasılıkları nerede;

L 1, L 2, ..., L n kod sözcüklerinin uzunluklarıdır.

Sıkıştırma gerçekleştirmenin iki ana yolu vardır.

İstatistiksel Yöntemler- giriş akışının sembollerine değişken uzunlukta kodlar atayan sıkıştırma yöntemleri ve daha fazlası kısa kodlar içinde meydana gelme olasılığı yüksek olan sembollere veya sembol gruplarına atanır. giriş akışı... En iyisi istatistiksel yöntemler Huffman kodlaması uygulanır.

Sözlük sıkıştırma Veri parçalarını bir "sözlükte" depolayan sıkıştırma yöntemleridir (bazıları veri yapısı). Girişe gelen yeni veri satırı, sözlükte bulunan herhangi bir parçayla aynıysa, bu parçaya bir işaretçi çıkış akışına yerleştirilir. En iyi kelime yöntemleri Ziv-Lempel yöntemini uygular.

İyi bilinen birkaç veri sıkıştırma algoritmasını daha ayrıntılı olarak ele alalım.

Huffman yöntemi

Bu algoritma kodlama bilgisi D.A. tarafından önerildi. Huffman'ın 1952 yılında Huffman kodlaması (sıkıştırma) atayan yaygın olarak kullanılan bir sıkıştırma yöntemidir. alfabenin sembolleri bu karakterlerin ortaya çıkma olasılıklarına dayalı değişken uzunluklu kodlar.

Algoritmanın fikri şudur: Kaynak metinde karakterlerin ortaya çıkma olasılıklarını bilerek, tam sayıda bitten oluşan değişken uzunluklu kodlar oluşturma prosedürünü tanımlayabiliriz. Sembollere daha kısa kodlar atanması daha olasıdır. Bu nedenle, bu yöntemde, verileri sıkıştırırken, her karaktere, metinde bulunma olasılığına bağlı olarak en uygun önek kodu atanır.

önek kodu Hiçbir kod sözcüğünün başka bir kod sözcüğünün öneki olmadığı bir koddur. Bu kodlar değişken uzunluktadır.

Optimal önek kodu Minimum ortalama uzunluğa sahip bir önek kodudur.

Huffman algoritması iki aşamaya ayrılabilir.

1. Kaynak metinde görünen karakterlerin olasılığının belirlenmesi.

   Başlangıçta, kaynak metnin tamamını okumak ve içindeki karakterlerin oluşma olasılıklarını hesaplamak gerekir (bazen her karakterin kaç kez geçtiğini sayarlar). 256 karakterin tümü dikkate alınırsa, bir metnin veya başka bir dosya biçiminin sıkıştırılmasında hiçbir fark olmayacaktır.

2. Optimal önek kodunu bulma.

   Daha sonra, en düşük gerçekleşme olasılığına sahip iki a ve b sembolü bulunur ve yerine gelme olasılığı a ve b sembollerinin gerçekleşme olasılıklarının toplamına eşit olan bir hayali sembol x ile değiştirilir. Ardından, bu prosedürü yinelemeli olarak kullanarak, daha küçük bir karakter kümesi için en uygun önek kodunu bulun (burada a ve b karakterlerinin tek bir x karakteriyle değiştirildiği yer). Orijinal karakter kümesinin kodu, değiştirilen karakter kodundan önce 0 veya 1 eklenerek değiştirilen karakter kodlarından elde edilir ve bu iki yeni kod, yedek karakter kodları olarak alınır. Örneğin, karakter kodu a, x kodunu, bu kodun önüne bir sıfır eklenerek eşleşir ve b karakteri için, karakter kodu x'in önüne bir bir eklenir.

Huffman kodlarının benzersiz bir öneki vardır, bu da değişken uzunluklarına rağmen benzersiz bir şekilde deşifre edilmelerine olanak tanır.

örnek 1. Yazılım uygulaması Huffman yöntemi.

#include "stdafx.h" #include ad alanı std kullanarak; geçersiz Beklenti (); uzun MinK (); geçersiz Özet (); geçersiz BuildBits (); void OutputResult (char ** Sonuç); geçersiz Temizle (); const int MaksK = 1000; uzun k, a, b; karakter bitleri; karakter sk; bool Ücretsiz; karakter * res; uzun i, j, n, m, kj, kk1, kk2; karakter dizisi; int _tmain (int argc, _TCHAR * argv) (char * BinaryCode; Temizle (); cout<< "Введите строку для кодирования: "; cin >> str; Beklenti (); Özetle (); BuildBit (); ÇıktıSonucu (& BinaryCode); cout<< "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 >2) (s1 = MinK (); m1 = m; s2 = MinK (); m2 = m; kk2 ++; k = s1 + s2; a = m1; b = m2; Serbest = doğru; kk1--;) ) // void BuildBits () (strcpy (bit, "1"); Serbest = false; strcpy (bit], bit); strcat (bit], "0"); strcpy (bit) önek kodlarını oluşturmak için işlevin açıklaması ], bit); strcat (bit], "1"); i = MinK (); strcpy (bit [m], "0"); Serbest [m] = true; strcpy (bit], bit [m]) ; strcat (bitler] , "0"); strcpy (bitler], bitler [m]); strcat (bitler], "1"); for (i = kk2 - 1; i> 0; i--) if ( Serbest [i] ) (strcpy (bitler], bitler [i]); strcat (bitler], "0"); strcpy (bitler], bitler [i]); strcat (bitler], "1");) ) // fonksiyon açıklaması veri çıktısı void OutputResult (char ** Sonuç) ((* Sonuç) = new char; for (int t = 0; i< 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

Huffman algoritması evrenseldir, herhangi bir türdeki verileri sıkıştırmak için kullanılabilir, ancak küçük dosyalar için etkisizdir (sözlük kaydetme ihtiyacı nedeniyle). Şu anda, bu yöntem pratik olarak saf haliyle kullanılmamaktadır, genellikle daha karmaşık şemalarda sıkıştırma aşamalarından biri olarak kullanılmaktadır. Bu, en kötü durumda orijinal verilerin boyutunu artırmayan tek algoritmadır (arama tablosunu dosyayla birlikte saklama ihtiyacı dışında).

Modern kullanıcılar genellikle sabit diskte boş alan olmaması sorunuyla karşı karşıyadır. Birçoğu, en azından biraz boş alan boşaltmak amacıyla, tüm gereksiz bilgileri sabit sürücüden silmeye çalışır. Daha ileri düzey kullanıcılar, veri miktarını azaltmak için özel sıkıştırma algoritmaları kullanır. Bu sürecin etkinliğine rağmen, birçok kullanıcı bunu hiç duymadı bile. Veri sıkıştırmanın ne anlama geldiğini, bunun için hangi algoritmaların kullanılabileceğini anlamaya çalışalım.

Günümüzde bilgi sıkıştırma, her PC kullanıcısının ihtiyaç duyduğu oldukça önemli bir prosedürdür. Bugün, herhangi bir kullanıcı, büyük miktarda bellek kullanma yeteneği sağlayan modern bir veri depolama cihazı satın alabilir. Bu tür cihazlar, kural olarak, bilgi yayınlamak için yüksek hızlı kanallarla donatılmıştır. Ancak, her yıl kullanıcıların ihtiyaç duyduğu bilgi miktarının giderek arttığına dikkat edilmelidir. Sadece 10 yıl önce standart bir video filmin hacmi 700 MB doları geçmiyordu. Şu anda, HD kalitesinde filmlerin hacmi onlarca gigabayta ulaşabilir.

Veri sıkıştırma ne zaman gereklidir?

Bilgi sıkıştırma sürecinden fazla bir şey beklememelisiniz. Yine de, bilgi sıkıştırmanın basitçe gerekli ve son derece yararlı olduğu durumlar vardır. Bu vakalardan bazılarını ele alalım.

E-posta iletimi.

Çoğu zaman, büyük miktarda veriyi e-posta ile göndermeniz gereken durumlar vardır. Sıkıştırma, aktarılan dosyaların boyutunu önemli ölçüde azaltabilir. Bilgi göndermek için mobil cihazları kullanan kullanıcılar, özellikle bu prosedürün avantajlarını takdir edeceklerdir.

İnternet sitelerinde ve portallarda veri yayınlamak.

Sıkıştırma prosedürü, genellikle çeşitli İnternet kaynaklarında yayınlanmak üzere kullanılan belgelerin hacmini azaltmak için kullanılır. Bu, trafikten önemli ölçüde tasarruf etmenizi sağlar.

Boş disk alanından tasarruf.

Sisteme yeni depolama ortamı eklemek mümkün olmadığında, boş disk alanından tasarruf etmek için sıkıştırma prosedürünü kullanabilirsiniz. Öyle olur ki, kullanıcının bütçesi son derece sınırlıdır ve sabit diskte yeterli boş alan yoktur. Sıkıştırma prosedürünün geldiği yer burasıdır.

Yukarıda listelenen durumlara ek olarak, muhtemelen veri sıkıştırma işleminin çok faydalı olabileceği daha birçok durum vardır. Sadece en yaygın olanları listeledik.

Bilgi sıkıştırma yöntemleri

Mevcut tüm bilgi sıkıştırma yöntemleri iki ana kategoriye ayrılabilir. Kayıpsız ve kayıplı sıkıştırmadır. İlk kategori, yalnızca orijinal bilgilerin tek bir bitini kaybetmeden verileri yüksek doğrulukla kurtarmaya ihtiyaç duyulduğunda geçerlidir. Bu özel yaklaşımı kullanmanız gereken tek durum, metin belgelerinin sıkıştırılmasıdır.

Sıkıştırılmış bilgilerin en doğru şekilde kurtarılması için özel bir ihtiyaç olmaması durumunda, belirli sıkıştırma kayıplarına sahip algoritmaların kullanılması olasılığının sağlanması gerekir.

Bilgi kaybı olmadan sıkıştırma

Bu bilgi sıkıştırma yöntemleri, büyük miktarda bilgiyi e-posta ile iletirken, bir müşteriye tamamlanmış bir çalışma gönderirken veya bir bilgisayarda depolanan bilgilerin yedek kopyalarını oluştururken kullanıldıkları için öncelikle ilgi çekicidir. Bu bilgi sıkıştırma yöntemleri, bilgi kaybına izin vermez, çünkü bunlar yalnızca fazlalığının ortadan kaldırılmasına dayanırken, bilginin neredeyse her zaman fazlalığı vardır, ikincisi orada olmasaydı, sıkıştırılacak hiçbir şey olmazdı.

örnek 1

Basit bir örnek verelim. Rus dili 33 $ harf, 10 $ rakam ve yaklaşık 15 $ noktalama işaretleri ve diğer özel karakterleri içerir. Sadece büyük Rusça harflerle yazılan metinler için (örneğin, telgraflarda olduğu gibi), 60 $ 'lık farklı değerler oldukça yeterli olacaktır. Bununla birlikte, her karakter genellikle 8 bit olduğunu bildiğimiz şeyi içeren bir bayt tarafından kodlanır ve 256 $ farklı kodlarla ifade edilebilir. Bu, fazlalığı karakterize eden ilk faktörlerden biridir. Telgraf metni için karakter başına 6 $ bit oldukça yeterli olacaktır.

Örnek 2

Başka bir örneğe bakalım. ASCII karakterlerinin uluslararası kodlamasında, herhangi bir karakteri kodlamak için aynı sayıda bit (8 $) tahsis edilirken, herkes uzun zamandır en yaygın karakterleri daha az karakterle kodlamanın mantıklı olduğunu iyi biliyor. Yani örneğin Mors alfabesinde çok yaygın olan "E" ve "T" harfleri $ 1 $ işaretiyle kodlanmıştır (sırasıyla bu bir nokta ve bir tiredir). Ve "U" ($ - - $) ve "C" ($ - - $) gibi nadir harfler 4 $ karakterle kodlanmıştır.

Açıklama 1

Verimsiz kodlama, artıklığı karakterize eden ikinci faktördür. Bilgilerin sıkıştırıldığı programlar kendi kodlamalarını girebilir ve farklı dosyalar için farklı olabilir ve sıkıştırılmış dosyaya, açma programının hakkında bilgi okuyacağı bir tablo (sözlük) biçiminde atayabilir. dosyanın nasıl kodlandığı, belirli semboller veya bunların grupları.

Bilgilerin yeniden kodlanmasına dayalı algoritmalara Huffman algoritmaları denir.

Huffman algoritması

Bu algoritmada bilgi sıkıştırma, entropi kodlaması veya önceden oluşturulmuş bir sözlük temelinde gerçekleştirilir. İstatistiksel Huffman algoritmasına göre, her giriş sembolüne belirli bir kod atanır. Bu durumda, en sık kullanılan sembol en kısa koddur ve en nadiren kullanılan - daha uzun olanıdır. Örnek olarak, diyagram, İngiliz alfabesinin tek tek harflerini kullanma sıklığının dağılımını göstermektedir (Şekil 1). Böyle bir dağıtım Rus dili için de oluşturulabilir. Kodlama tabloları önceden oluşturulmuştur ve boyut olarak sınırlıdır. Bu algoritma en hızlı performansı ve en düşük gecikmeyi sağlar. İstatistiksel yöntem, yüksek sıkıştırma oranları elde etmek için büyük miktarda bellek gerektirir.

Şekil 1. İngilizce harflerin kullanım sıklıklarına göre dağılımı

Sıkıştırma miktarı, işlenen bit dizisinin fazlalığı tarafından belirlenir. Doğal dillerin her birinin belirli bir miktarda fazlalığı vardır. Avrupa dilleri arasında Rusça, en yüksek fazlalık düzeyine sahiptir. Bu, İngilizce metnin Rusça çevirisinin boyutuna göre değerlendirilebilir. Genellikle yaklaşık 30 $ \% $ daha fazladır. Şiirsel bir metinden bahsediyorsak, fazlalık 2 $ kat daha fazla olabilir.

Açıklama 2

Kodlarla ilgili en büyük zorluk, sıkıştırılan her veri türü için olasılık tablolarına sahip olma ihtiyacıdır. İngilizce veya Rusça metnin sıkıştırıldığı biliniyorsa bu sorun değildir. Bu durumda, kodlayıcıya ve kod çözücüye İngilizce veya Rusça metin için uygun bir kod ağacı sağlıyoruz. Genel durumda, giriş verileri için sembollerin olasılığı bilinmediğinde, statik Huffman kodları etkisiz bir şekilde çalışır.

Bu sorunun çözümü, verilerin ilk geçişi sırasında gerçekleştirilen kodlanmış verilerin istatistiksel analizi ve buna dayalı olarak bir kod ağacının derlenmesidir. Bu durumda, gerçek kodlama ikinci geçişte gerçekleştirilir.

Kodların bir başka dezavantajı, onlar için minimum kod kelime uzunluğunun birden az olmaması, bir mesajın entropisinin hem 0.1 $ hem de 0.01 $ bit / harf olabilmesidir. Bu durumda, kod önemli ölçüde gereksiz hale gelir. Sorun, algoritmayı karakter bloklarına uygulayarak çözülür, ancak daha sonra kodlama / kod çözme prosedürü daha karmaşık hale gelir ve kod ağacı önemli ölçüde genişler, bu da sonuçta kodla birlikte saklanması gerekir.

Bu kodlar, hemen hemen her metinde bulunan karakterler arasındaki ilişkileri dikkate almaz.

Açıklama 3

Bugün, bilgi çağında, hemen hemen her kullanıcının veri iletimi ve büyük hacimli medya için yüksek hızlı kanallara erişimi olmasına rağmen, veri sıkıştırma konusu güncelliğini korumaktadır. Veri sıkıştırmanın basitçe gerekli bir işlem olduğu durumlar vardır. Bu özellikle, verilerin e-posta yoluyla iletilmesi ve İnternet'te bilgi gönderilmesi için geçerlidir.

Veri sıkıştırma yöntemleri, ilk bilgisayarın ortaya çıkmasından çok önce başlayan oldukça uzun bir gelişme geçmişine sahiptir. Bu makale, ana teoriler, fikir kavramları ve bunların uygulamalarına, ancak tamamlanmış olduğunu iddia etmeden kısa bir genel bakış sunmaya çalışacaktır. Daha ayrıntılı bilgi, örneğin, R.E. Krichevsky'de bulunabilir. , Ryabko B. Ya. , Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. ve benzeri.

Bilginin sıkıştırılması, oldukça uzun bir geçmişi olan bir problemdir, (tarih) genellikle bilgi kodlama ve şifreleme probleminin gelişim tarihi ile birlikte giden bilgisayar teknolojisinin gelişim tarihinden çok daha eskidir. Tüm sıkıştırma algoritmaları, minimum birimi bir bit ve maksimum birimi birkaç bit, bayt veya birkaç bayt olan bir bilgi giriş akışı üzerinde çalışır. Sıkıştırma işleminin amacı, kural olarak, başlangıçta kompakt olmayan bazı girdi akışlarından, bunların bazı dönüşümleri yoluyla daha kompakt bir bilgi birimleri çıktı akışı elde etmektir. Sıkıştırma işlemlerinin ana teknik özellikleri ve çalışmalarının sonuçları şunlardır:

İlk ve son akışların hacimlerinin sıkıştırma oranı (sıkıştırma derecesi) veya oranı (oran);

Sıkıştırma oranı - giriş akışındaki belirli bir miktarda bilgiyi sıkıştırmak için harcanan zaman, ondan eşdeğer bir çıkış akışı elde edilene kadar;

Sıkıştırma kalitesi, çıktı akışının aynı veya farklı bir algoritma kullanılarak yeniden sıkıştırma uygulanarak ne kadar güçlü paketlendiğini gösteren bir değerdir.

Bilgi sıkıştırma sorununa birkaç farklı yaklaşım vardır. Bazıları çok karmaşık bir teorik matematiksel temele sahiptir, diğerleri bilgi akışının özelliklerine dayanır ve algoritmik olarak oldukça basittir. Verilerin sıkıştırılmasını veya sıkıştırılmasını uygulayan herhangi bir yaklaşım ve algoritma, tersine çevrilebilir veya geri döndürülemez dönüşümü aracılığıyla çıktı bilgi akışının hacmini bit olarak azaltmak için tasarlanmıştır. Bu nedenle, her şeyden önce, verilerin doğası veya formatı ile ilgili kritere göre, tüm sıkıştırma yöntemleri iki kategoriye ayrılabilir: tersinir ve geri döndürülemez sıkıştırma.

Geri döndürülemez sıkıştırma ile, belirli bir bilgi formatına dayalı çıktı akışının, belirli bir bakış açısından, giriş akışına dış özellikler bakımından oldukça benzer, ancak farklı bir nesneyi temsil ettiği, giriş veri akışının böyle bir dönüşümü kastedilmektedir. ondan hacim olarak. Giriş ve çıkış akışları arasındaki benzerlik derecesi, bu bilgi akışı tarafından temsil edilen nesnenin belirli özellikleri (yani, belirli bir veri formatına göre sıkıştırılmış ve sıkıştırılmamış bilgiler) arasındaki yazışma derecesi ile belirlenir. Bu tür yaklaşımlar ve algoritmalar, örneğin akışta baytların tekrarlanabilirliği düşük olan bitmap grafik dosyalarının verilerini sıkıştırmak için kullanılır. Bu yaklaşım, grafik dosya formatının yapısının özelliğini ve birkaç (veya daha doğrusu n) şekilde görüntü kalitesinde (insan gözü tarafından algılanması için) yaklaşık olarak benzer bir grafik görüntü sunma kabiliyetini kullanır. Bu nedenle, bu tür algoritmalarda sıkıştırma derecesi veya miktarına ek olarak kalite kavramı ortaya çıkar. Orijinal görüntü sıkıştırma işlemi sırasında değişirse kalite, orijinal görüntü ile elde edilen görüntü arasındaki, bilgi formatına dayalı olarak öznel olarak değerlendirilen yazışma derecesi olarak anlaşılabilir. Grafik dosyaları için, bu tür yazışmalar görsel olarak belirlenir, ancak buna karşılık gelen akıllı algoritmalar ve programlar da vardır. Giriş ve çıkış akışlarının bilgi yapısının tam olarak eşleşmesinin gerekli olduğu alanlarda geri dönüşü olmayan sıkıştırma uygulanamaz. Bu yaklaşım, JPEG ve JFIF algoritmaları ve JPG ve JIF dosya biçimleri olarak bilinen video ve fotoğraf bilgilerinin sunulması için popüler biçimlerde uygulanmaktadır.

Tersinir sıkıştırma, bilgi içeriğini değiştirmeden her zaman çıktı bilgi akışının hacminde bir azalmaya yol açar, yani. - bilgi yapısını kaybetmeden. Ayrıca, bir kurtarma veya açma algoritması kullanarak çıktı akışından girdi alabilirsiniz ve kurtarma işlemine açma veya açma adı verilir ve yalnızca açma işleminden sonra veriler dahili formatlarına göre işlemeye uygun hale gelir.

Tersinir algoritmalarda, bir süreç olarak kodlama, yalnızca sıkıştırma algoritmaları oluşturmak için değil, aynı zamanda verimliliklerini değerlendirmek için daha da yararlı olan istatistiksel bir bakış açısıyla görülebilir. Tüm tersine çevrilebilir algoritmalar için bir kodlama maliyeti kavramı vardır. Kodlama maliyeti, kod kelimesinin bit cinsinden ortalama uzunluğunu ifade eder. Kodlamanın fazlalığı, kodlamanın maliyeti ve entropisi arasındaki farka eşittir ve iyi bir sıkıştırma algoritması her zaman fazlalığı en aza indirmelidir (bilgi entropisinin, bozukluğunun bir ölçüsü olarak anlaşıldığını hatırlayın). Shannon'ın bilgi kodlama konusundaki temel teoremi, "kodlamanın maliyeti, keyfi olarak ona yakın olabilse de, her zaman kaynağın entropisinden daha az değildir" der. Bu nedenle, herhangi bir algoritma için, giriş akışının entropisi tarafından belirlenen sıkıştırma oranının her zaman belirli bir sınırı vardır.

Şimdi doğrudan tersine çevrilebilir algoritmaların algoritmik özelliklerine dönelim ve kodlama sistemleri ve bilgi sıkıştırma yöntemlerinin uygulanmasıyla ilişkili veri sıkıştırmaya yönelik en önemli teorik yaklaşımları ele alalım.

Toplu kodlama ile sıkıştırma

Bilgilerin tersine çevrilebilir sıkıştırılması için en ünlü basit yaklaşım ve algoritma Çalışma Uzunluğu Kodlamasıdır (RLE). Bu yaklaşımın yöntemlerinin özü, dizeleri veya yinelenen bayt dizilerini veya dizilerini bir kodlama baytı ve tekrarlarının sayısının bir sayacı ile değiştirmektir. Tüm benzer yöntemlerle ilgili sorun, yalnızca, paket açma algoritmasının elde edilen bayt akışındaki kodlanmış serileri diğerlerinden - kodlanmamış bayt dizilerinden - ayırt edebilme yolunun belirlenmesindedir. Sorunun çözümü genellikle kodlanmış dizilerin başına işaretler yerleştirilerek elde edilir. Bu tür etiketler, örneğin kodlanmış bir çalışmanın ilk baytındaki karakteristik bit değerleri, kodlanmış bir çalışmanın ilk baytının değerleri vb. Bu yöntemler, kural olarak, raster grafik görüntüleri (BMP, PCX, TIF, GIF) sıkıştırmak için oldukça etkilidir, çünkü ikincisi oldukça fazla sayıda yinelenen bayt dizileri içerir. RLE yönteminin dezavantajı, oldukça düşük sıkıştırma oranı veya dosyaları az sayıda seriyle ve daha da kötüsü, bir dizide az sayıda tekrarlanan baytla kodlamanın maliyetidir.

RLE yöntemini kullanmadan sıkıştırma

RLE yöntemini kullanmadan verileri sıkıştırma işlemi iki aşamaya ayrılabilir: modelleme ve aslında kodlama. Bu süreçler ve uygulama algoritmaları oldukça bağımsız ve çeşitlidir.

Kodlama süreci ve yöntemleri

Kodlama, genellikle belirli bir alfabede bir karakter akışının (bizim durumumuzda, baytlar veya küçük parçalar) işlenmesi olarak anlaşılır ve akışta karakterlerin görülme sıklıkları farklıdır. Kodlamanın amacı, bu akışı, sembol frekanslarını dikkate alarak giriş akışının entropisini azaltarak elde edilen minimum uzunlukta bir bit akışına dönüştürmektir. Akış alfabesindeki karakterleri temsil eden kodun uzunluğu, giriş akışındaki bilgi miktarıyla orantılı olmalıdır ve akış sembollerinin bit cinsinden uzunluğu 8'in katı veya hatta değişken olmayabilir. Girdi akımının alfabesindeki sembollerin oluşum frekanslarının olasılık dağılımı biliniyorsa, optimal bir kodlama modeli oluşturulabilir. Ancak, çok sayıda farklı dosya formatının varlığı nedeniyle, görev çok daha karmaşık hale geliyor. veri sembollerinin frekans dağılımı önceden bilinmemektedir. Bu durumda genel olarak iki yaklaşım kullanılır.

Birincisi, girdi akışını görüntülemek ve toplanan istatistiklere dayalı olarak kodlamayı oluşturmaktır (bu durumda, dosyadan iki geçiş gerekir - biri istatistiksel bilgileri görüntülemek ve toplamak için, ikincisi - kodlamanın kapsamını bir şekilde sınırlayan kodlamak için. Bu tür algoritmaların uygulanması, çünkü bu nedenle, veri miktarının bazen bilinmediği telekomünikasyon sistemlerinde kullanılan "anında" tek geçişli kodlama olasılığı hariç tutulur ve bunların yeniden iletimi veya ayrıştırılması makul olmayan bir şekilde sürebilir. uzun zaman). Böyle bir durumda, kullanılan kodlamanın istatistiksel şeması çıkış akımına yazılır. Bu teknik, statik Huffman kodlaması olarak bilinir.

Tanıtım.

Sıkıştırma, bilgisayarda dosya depolamak için gereken alan miktarını azaltır ve

kanal seti üzerinden bilgi iletmek için gereken süre

Bant genişliği. Bu bir kodlama şeklidir. Kodlamanın diğer amaçları

hataların aranması ve düzeltilmesinin yanı sıra şifrelemedir. Arama süreci ve

hata düzeltme, sıkıştırmanın tersidir - veri fazlalığını artırır,

insan tarafından okunabilir bir biçimde sunulmaları gerekmediğinde. kaldırarak

metinden fazlalık, sıkıştırma, aramayı karmaşıklaştıran şifrelemeyi teşvik eder

kraker için mevcut olan istatistiksel bir yöntemi kullanarak şifreleyin.

İlk

metin sıkıştırılmış durumdan tam olarak kurtarılabilir. geri döndürülemez veya

gibi analog sinyallerin dijital kaydı için hatalı sıkıştırma kullanılır.

insan konuşması veya çizimleri. Tersinir sıkıştırma özellikle metinler için önemlidir,

doğal ve yapay dillerde kaydedildi, çünkü bu durumda

hatalar genellikle kabul edilemez. Her ne kadar birincil uygulama alanı

Söz konusu yöntemler, terminolojimize yansıyan metinlerin sıkıştırılmasıdır,

ancak, bu teknik, tersine çevrilebilir olanlar da dahil olmak üzere diğer durumlarda uygulama bulabilir.

ayrık veri dizilerinin kodlanması.

Bilgisayar kaynaklarını sıkıştırılmış kaynak olarak tahsis etmek için birçok iyi neden vardır.

temsil, çünkü için daha hızlı veri aktarımı ve azaltılmış alan

depolamaları, önemli miktarda para biriktirmenize ve genellikle iyileştirmenize olanak tanır

bilgisayar göstergeleri. Tüm nedenlerden dolayı sıkıştırmanın odakta kalması muhtemeldir.

bir bilgisayara depolanan ve iletilen veri hacminin artması, buna ek olarak,

gibi bazı fiziksel sınırlamaların üstesinden gelmek için kullanın,

örneğin, telefon kanallarının nispeten düşük bant genişliği.

VERİ SIKIŞTIRMA İÇİN GENİŞLETME AĞAÇLARININ UYGULAMASI.

Sıkıştırma algoritmaları, veri depolama ve iletim verimliliğini iyileştirebilir

fazlalıklarının miktarını azaltarak. Sıkıştırma algoritması devreye girer

kaynak metni girdi olarak ve karşılık gelen sıkıştırılmış metni üretir,

bir açılım algoritması olarak, girdi olarak sıkıştırılmış metne sahip olduğunda ve

kaynağın orijinal metnini çıkarır. Çoğu sıkıştırma algoritması

kaynak metni bir dizi alfabe harfleri olarak düşünün

kaynak metin.

S dizisinin temsilindeki fazlalık L (S) - H (S)'dir, burada L (S) uzunluktur

bitlerde temsil ve H (S) - entropi - bilgi içeriğinin bir ölçüsüdür, ayrıca

bit olarak ifade edilir. Bilgi kaybı olmadan sıkıştırabilen algoritmalar

entropisinden daha az bit içeren bir dize mevcut değildir. Eğer

kaynak metni rastgele bir kümeden her seferinde bir harf çıkartın,

A alfabesini kullanarak entropi şu formülle bulunur:

H (S) = C (S) p (c) log ----,

burada C (S) dizideki harf sayısıdır, p (c) statik olasılıktır

bazı C harfinin oluşumu. Eğer oluşum sıklığı p (c) tahmininde kullanılıyorsa

S dizesindeki her c harfinin, ardından H (C), S dizisinin öz entropisi olarak adlandırılır.

H (S) maddesi, bir dizgenin öz entropisini belirtmek için kullanılacaktır.

statik kaynak.

Genişleyen ağaçlar genellikle sözlükbilimsel sıralama biçimlerini tanımlar.

ikili arama için ağaçlar, ancak veri sıkıştırmada kullanılan ağaçlar

sürekli bir düzene sahip olmak. Siparişin ortadan kaldırılması şunlara yol açar:

temel genişletme işlemlerinin önemli ölçüde basitleştirilmesi. Sonuç

algoritmalar son derece hızlı ve kompakttır. Huffman kodlarının kullanılması durumunda,

genişletme, yerel olarak uyarlanmış bir sıkıştırma algoritması ile sonuçlanır.

Optimum sıkıştırma elde etmese de oldukça basit ve hızlıdır.

Aritmetik kodlara uygulandığında sıkıştırma sonucu şuna yakındır:

zaman açısından optimal ve yaklaşık olarak optimaldir.

ÖNEK KODLARI.

Yaygın olarak incelenen veri sıkıştırma algoritmalarının çoğu, kodlara dayanmaktadır.

Huffman. Huffman kodunda, kaynak metnin her harfi arşivde temsil edilir.

değişken uzunluk kodu Daha sık harfler kısa kodlarla temsil edilir,

daha az sıklıkta - uzun. Sıkıştırılmış metinde kullanılan kodlar bunlara uymalıdır

ön ekin özellikleri, yani: sıkıştırılmış metinde kullanılan kod

başka herhangi bir kodun önüne ekleyin.

Önek kodları, her yaprağın bulunduğu bir ağaç aracılığıyla bulunabilir.

kaynak alfabenin bir harfiyle eşleşir. Şekil 1 kod ağacını gösterir

4 harfli alfabenin ön eki. Bir harf için önek kodu tarafından okunabilir

ağacı kökünden bu harfe geçmek, burada 0, sol dalının seçimine karşılık gelir,

ve 1 - doğru. Bir Huffman kod ağacı, eşit ağırlıkta bir ağaçtır;

sayfa, orijinal metinde bir harfin görülme sıklığına eşit bir ağırlığa sahiptir ve

iç düğümlerin kendi ağırlıkları yoktur. Örnekteki ağaç, aşağıdaki durumlarda optimal olacaktır:

A, B, C ve D harflerinin frekansları sırasıyla 0.125, 0.125, 0.25 ve 0.5 olacaktır.

Normal Huffman kodları önceden frekans bilgisi gerektirir

kaynak metindeki harfler, bu da çift görüntüleme ihtiyacına yol açar - bir

harflerin frekanslarının değerlerini elde etmek için, diğeri sıkıştırmayı kendisi gerçekleştirmek için. V

daha sonra, bu frekansların değerleri, sıkıştırılmış metnin kendisiyle birleştirilmelidir.

gelecekte, onu dağıtmayı mümkün kılar. Uyarlanabilir sıkıştırma gerçekleştirildi

bir adımda, çünkü orijinal metnin her harfi için kullanılan kod,

Alfabenin diğer tüm harflerinin frekanslarında. Etkililik için temeller

uyarlanabilir Huffman kod uygulamaları Gallagher tarafından ortaya kondu, Knuth yayınlandı

böyle bir algoritmanın pratik bir versiyonuydu ve Witter bunu geliştirdi.

Optimum uyarlanmış Witter kodu her zaman için bir bit içinde bulunur.

genellikle en uygun statik Huffman koduna göre kaynak harfi

H'nin yüzde birkaçıdır. Ayrıca, statik Huffman kodları her zaman

H'den kaynak harf başına bir bit içinde bulunur (buna ulaşırlar

sınır sadece tüm harfler için p (C) = 2) olduğundadır. Sıkıştırma algoritmaları var

bu sınırlamaların üstesinden gelebilir. Örneğin Ziv-Lempell algoritması,

sabit uzunluktaki bir arşivdeki kelimeleri kaynak metin satırlarına atar

değişken uzunluk ve aritmetik sıkıştırma kodlamak için kullanılabilir

kaynak harfler birazcık bile.

Ön ek kodlarına bir uzantı uygulama.

Genişleyen ağaçlar ilk olarak 1983 yılında ve daha detaylı olarak tanımlanmıştır.

1985'te gözden geçirildi. Başlangıçta, bir tür kendi kendine dengeli olarak anlaşıldılar.

ikili arama için ağaçlar ve ayrıca izin verdikleri gösterilmiştir.

Öncelik sıralarının en hızlı uygulanması. Genişleyen bir ağaç düğümü ise

kullanılabilir, daha sonra uzatılır. Bu, kullanılabilir düğümün

kök, solundaki tüm düğümler yeni bir sol alt ağaç oluşturur, sağdaki düğümler -

yeni sağ alt ağaç. Genişleme, ağaçtan eski ağaçtan geçilerek sağlanır.

hedef düğüme kök ve bu durumda yerel değişiklikler yapmak, bu nedenle fiyat

genişleme, gidilen yolun uzunluğu ile orantılıdır.

Tarjan ve Slayton, genişleyen ağaçların statik olarak optimal olduğunu gösterdi.

Başka bir deyişle, mevcut düğümlerin kodları statik duruma göre alınırsa

olasılık dağılımı, ardından genişleyen ağaca erişim hızı ve

statik olarak dengelenmiş, bu dağıtımla optimize edilmiş,

birbirinden yeterli bir oranda fark edilen sabit bir katsayı ile farklılık gösterir

uzun erişim dizileri. Huffman ağacı bir örnek olduğu için

statik olarak dengeli ağaç, ardından sıkıştırma uzantısını kullanarak

veriler, sıkıştırılmış metnin boyutu, belirli bir katsayı içinde olacaktır.

Huffman kodu kullanılarak elde edilen arşivin boyutu.

Başlangıçta açıklandığı gibi, uzantı, depolanan ağaçlar için geçerlidir.

iç düğümlerdeki veriler, yapraklar değil. Önek kodu ağaçları her şeyi taşır

verileriniz yalnızca yapraklardadır. Ancak, adı verilen bir uzantı seçeneği vardır.

ön ek kod ağacı için geçerli olan yarım uzantı. Onunla, hedef

düğüm köke taşınmaz ve ardılları değiştirilmez,

bunun yerine, kökten hedefe giden yol basitçe yarıya indirilir. Yarı genişleme

sabit bir katsayı içinde aynı teorik sınırlar

uzantı.

Sözlükbilimsel ağacın zikzak geçişi durumunda,

genişleme ve yarı-genişleme, doğrudan güzergahın aksine daha karmaşıktır.

ağacın sol veya sağ kenarından hedef düğüme. Bu basit durum gösterilmektedir

Şekil 2. Yarım genişlemenin kökten (düğüm w) yaprağa giden yol üzerindeki etkisi

A düğümü, birbirini takip eden her bir dahili çift çiftinin değiştirilmesinden oluşur.

diğer düğümler, bunun sonucunda kökten yaprak düğümüne giden yolun uzunluğu azalır

2 kez. Yarı genişleme sürecinde, her bir çiftin düğümleri, kökten daha uzakta,

yeni yola dahil edilir (x ve z düğümleri) ve daha yakın olanlar

hariç tutulmuştur (w ve y düğümleri).

Kod ağaçlarında yarı genişletme işlemi ile sözlük düzeninin korunması

önek isteğe bağlıdır. Kod işlemlerinde önemli olan tek şey

önek, sıkıştırma prosedürü tarafından kullanılan ağaç için tam bir eşleşmedir

dağıtım prosedürü tarafından kullanılan ağaç. Yapılan herhangi bir değişiklik

ardışık harfler arasında, yalnızca

her iki prosedür de aynı değişiklikleri aynı sırayla yapar.

Sözlükbilimsel düzeni koruma ihtiyacı, işlerin yürütülmesini büyük ölçüde basitleştirir.

zikzak durumunu ortadan kaldırarak yarım genişletme işlemleri. Olabilir

Veri yazarken veya aktarırken, işlenmekte olan verilerin boyutunu küçültmek genellikle yardımcı olur. Bu amaca ulaşan teknolojiye veri sıkıştırma denir. Her biri kendi özel uygulama alanına sahip olan ve en iyi veya tersine en kötü sonuçları verdiği birçok veri sıkıştırma yöntemi vardır.

Çalıştırma uzunluğu kodlama yöntemi

Çalışma uzunluğu kodlaması, sıkıştırılacak veriler aynı değerlerin uzun dizilerinden oluşuyorsa en iyi sonuçları verir. Özünde, böyle bir kodlama yöntemi, tam olarak, bu tür dizileri, belirli bir dizideki tekrarlanan değeri ve tekrarlarının sayısını belirleyen bir kod değeriyle değiştirmekten oluşur. Örneğin, bit dizisinin 253 bir, ardından 118 sıfır ve 87 fazladan oluştuğu kodlanmış bilgiyi yazmak, tüm bu 458 biti numaralandırmaktan önemli ölçüde daha az yer alacaktır.

Örnek. Serinin uzunluğunu kodlama yöntemini kullanarak, dizi: 111111111100000000000000000 - aşağıdaki gibi gösterilebilir: 10.

Göreli kodlama yöntemi

Bazı durumlarda bilgi, her biri bir öncekinden biraz farklı olan veri bloklarından oluşabilir. Bir örnek, sıralı video kareleri olacaktır. Bu gibi durumlarda göreli kodlama yöntemi kullanılır. Bu yaklaşım, bu blokların kendilerini kaydetmek yerine, ardışık veri blokları arasında var olan farklılıkları kaydetmeyi varsayar. her blok, bir önceki blokla olan ilişkisine göre kodlanmıştır.

Örnek. Göreceli kodlama yöntemini kullanarak, sayı dizisi şöyledir: 1476; 1473; 1480; 1477 - aşağıdaki gibi gösterilebilir: 1476; -3; +7; -3.

Frekansa bağlı kodlama

Bu veri sıkıştırma tekniği, bir veri birimini temsil eden bit modelinin uzunluğunun, birimin kullanıldığı frekansla ters orantılı olduğu, frekansa bağlı kodlamanın kullanımını içerir. Bu tür kodlar, değişken uzunluklu kodlar grubuna dahildir, yani. bu kodlardaki veri öğeleri, farklı uzunluklardaki bit desenleriyle temsil edilir. Frekansa bağlı yöntem kullanılarak kodlanmış İngilizce metni alırsak, en yaygın karakterler [e, t, a, i] kısa bit kombinasyonları ve daha az yaygın olan karakterler - daha uzun bit kombinasyonları ile temsil edilecektir. Sonuç olarak, tüm metnin Unicode veya ASCII gibi normal kodlardan daha kısa bir temsilini elde ederiz. Frekansa bağlı kodların tasarımında yaygın olarak kullanılan algoritmanın yapısı David Huffman'a atfedilir, bu nedenle bu tür kodlara genellikle Huffman kodları denir. Günümüzde kullanılan frekansa bağlı kodların çoğu Huffman kodlarıdır.

Örnek. Dört sembol α, β, γ ve λ'dan oluşan αγααβααγααβαλαβαβαβαβαα dizisini frekansa bağlı yöntemi kullanarak kodlamanın gerekli olduğunu varsayalım: Ayrıca bu dizide α 15 kez, β - 6 kez, γ - 2 kez ve λ - 1 kez meydana gelir.

Huffman yöntemine göre sembolleri temsil etmek için aşağıdaki ikili kodu seçelim:

α - 1
β - 01
y - 001
λ - 000

Lempel-Ziv yöntemi

Bu yöntem, yaratıcıları Abraham Lempel ve Jacob Ziv'in adını almıştır. Lempel-Ziv kodlama sistemleri, uyarlanabilir kelime kodlama teknolojisini kullanır. Bu bağlamda, kelime dağarcığı terimi, sıkıştırılmış bir mesajın oluşturulduğu yapı taşları kümesini ifade eder. İngilizce metin sıkıştırılmışsa, yapı taşları alfabe karakterleri olabilir. Bilgisayarınızda depolanan verilerin boyutunu küçültmek istiyorsanız, yapı taşları sıfırlar ve birler olabilir. Uyarlamalı kelime kodlaması sırasında, kelime dağarcığının içeriği değişebilir. Örneğin, İngilizce metni sıkıştırırken, sonun ve makalenin sözlüğe eklenmesi tavsiye edilebilir. Bu durumda, sonun ve makalenin gelecekteki kopyalarının kapladığı alan, üç farklı referansın bir kombinasyonu yerine tek referanslar olarak yazılarak azaltılabilir. Lempel-Ziv kodlama sistemleri, kodlama veya sıkıştırma sırasında karmaşık ve yüksek verimli kelime uyarlama teknikleri kullanır. Özellikle, kodlama sürecinin herhangi bir noktasında sözlük, önceden kodlanmış [sıkıştırılmış] kombinasyonlardan oluşacaktır.

Örnek olarak, LZ77 olarak bilinen belirli bir Lempel-Ziv sistemini kullanarak mesaj sıkıştırmayı nasıl gerçekleştirebileceğinizi düşünün. Süreç, pratik olarak mesajın ilk bölümünün yeniden yazılmasıyla başlar, ancak belirli bir anda, her biri iki tamsayı ve ardından metnin bir karakterinden oluşacak üçlüler kullanılarak gelecekteki bölümlerin temsiline geçiş yapılır. Her üçlü, mesajın bir sonraki bölümünün nasıl oluşturulduğunu açıklar. Örneğin, paketlenmemiş metnin şöyle göründüğünü varsayalım:

αβααβλβ

αβααβλβ dizesi zaten mesajın paketlenmemiş kısmıdır. Mesaj metninin geri kalanını açmak için, önce zaten içinde bulunan kısmı ekleyerek satırı genişletmelisiniz. Üçlüdeki ilk sayı, eklenen parçanın ilk karakterini bulmak için satırda kaç karakterin geriye doğru sayılması gerektiğini gösterir. Bu durumda, ters yönde 5 karakter saymak gerekir ve zaten paketlenmemiş dizenin solundan ikinci karakter a'ya ulaşacağız. Üçlüdeki ikinci sayı, eklenen segmenti oluşturan baş harfinin sağındaki ardışık karakterlerin sayısını belirtir. Örneğimizde bu sayı 4'tür, yani eklenen segment ααβλ olacaktır. Bunu satırın sonuna kopyalıyoruz ve mesajın paketlenmemiş kısmının yeni değerini alıyoruz: αβααβλβααβλ.

Son olarak, son eleman [bizim durumumuzda, bu α sembolüdür] uzatılmış dizginin sonuna yerleştirilmelidir, bunun sonucunda tamamen paketlenmemiş bir mesaj alırız: αβααβλβααβλα.

Görüntüleri sıkıştırma

Modern dijital görüntü dönüştürücülerde kullanılan bitmap formatı, bir görüntüyü piksel başına üç baytlık bir formatta kodlamayı içerir, bu da bitmap dosyalarıyla çalışmak için zahmetli, elverişsiz oluşturulmasına yol açar. Diskteki bu tür dosyaların kapladığı alanı azaltmak için özel olarak bu biçim için birçok sıkıştırma şeması geliştirilmiştir. Böyle bir şema, CompuServe tarafından geliştirilen GIF formatıdır. İçinde kullanılan yöntem, bir pikselin renk gölgelerinin sayısını 256'ya düşürmektir, bunun sonucunda her pikselin rengi üç yerine bir bayt ile temsil edilebilir. Renk paleti adı verilen bir tablo kullanarak, geçerli piksel tonlarının her biri, bazı kırmızı-yeşil-mavi renk kombinasyonlarıyla ilişkilendirilir. Kullanılan paleti değiştirerek görselde görünen renkleri değiştirebilirsiniz.

Genellikle GIF paletindeki renklerden biri "şeffaflık" olarak yorumlanır. Bu, görüntünün bu renkle dolu alanlarında bulunduğu arka planın renginin görüntülendiği anlamına gelir. Bu ve görüntülerin göreceli kullanım kolaylığı nedeniyle, GIF formatı, ekranda birçok farklı resmin hareket ettiği bilgisayar oyunlarında yaygınlaştı.

Görüntü sıkıştırma sisteminin başka bir örneği de JPEG formatıdır. ISO organizasyonu içindeki Joint Photographic Experts Group [bu nedenle bu standardın adı] tarafından geliştirilen bir standarttır. JPEG formatının, renkli fotoğrafların sunulmasında etkili bir yöntem olduğu kanıtlanmıştır. Bu nedenle, bu standart modern dijital kamera üreticileri tarafından kullanılmaktadır. Gelecekte dijital görüntüleme alanında önemli bir etkiye sahip olması beklenmektedir.

Aslında, JPEG standardı, her biri kendi amacı olan bir görüntüyü temsil etmenin birkaç yolunu içerir. Örneğin, maksimum görüntü doğruluğu gerektiğinde, JPEG formatı, adı doğrudan görüntü kodlama prosedürünün herhangi bir bilgi kaybı olmadan gerçekleştirileceğini belirten bir "kayıpsız" mod sunar. Bu modda, her pikselin parlaklığını ayrı ayrı saklamak yerine, ardışık pikseller arasındaki farkları depolayarak alandan tasarruf edilir. Teoriye göre, çoğu durumda, komşu pikseller arasındaki farkın derecesi, tek tek piksellerin gerçek parlaklık değerlerinden daha kısa bit desenlerinde kodlanabilir. Mevcut farklılıklar, bellek kullanımını daha da azaltmak için kullanılan değişken uzunluklu bir kod kullanılarak kodlanır.

Ne yazık ki, "kayıpsız" modu kullanırken, oluşturulan raster görüntü dosyaları o kadar büyüktür ki, modern teknoloji kullanılarak işlenmesi zordur ve bu nedenle pratikte nadiren kullanılır. Mevcut uygulamaların çoğu, "temel çizgiler" modu olan JPEG formatının başka bir standart yöntemini kullanır. Bu modda, piksellerin her biri ayrıca üç bileşenle temsil edilir, ancak bu durumda zaten bir parlaklık bileşeni ve iki renk bileşenidir. Kabaca konuşursak, yalnızca parlaklık bileşenlerinden bir görüntü oluşturursak, bu bileşenler yalnızca pikselin aydınlatma seviyesini yansıttığı için görüntünün siyah beyaz bir versiyonunu görürüz.

Renk ve parlaklık arasındaki bu ayrımın ardındaki mantık, insan gözünün parlaklıktaki değişikliklere renklerden daha duyarlı olmasıdır. Örneğin, birinde küçük bir parlak nokta, diğerinde ise mavi arka planla aynı parlaklığa sahip küçük yeşil bir nokta olması dışında tamamen aynı olan tek tip renkli iki mavi dikdörtgen düşünün. Gözün yeşil bir nokta yerine parlak bir noktayı algılaması daha kolay olacaktır. JPEG standardının temel modu, her pikselin parlaklık bileşenini kodlayarak, ancak dört piksellik bloklar için renk bileşenlerinin ortalamasını alarak ve renk bileşenlerini yalnızca bu bloklar için yazarak bu özellikten yararlanır. Sonuç olarak, son görüntü sunumu parlaklıktaki ani değişiklikleri korur, ancak ani renk değişikliklerini bulanık bırakır. Bu şemanın avantajı, dört piksellik her bir bloğun, üç değerlik bir şema kullanırken gerekli olacak on iki yerine yalnızca altı değerle [parlaklık için dört değer ve renkler için iki değer] temsil edilmesidir. piksel başına.