Aritmetik kodlama

Aritmetik kodlama , bir olduğu kodlama entropi kullanılan veri sıkıştırma kaybı olmadan. Huffman ağacının yapraklarının / düğümlerinin / köklerinin tüm ağırlıklarının 2'nin katları olduğu ve bu durumda iki yöntemin eşdeğer olduğu durumlar dışında, Huffman kodlamasından daha iyi sıkıştırma sağlar .

Bu avantajına rağmen, uygulaması çok karmaşık olduğu için pek kullanılmadı ; Sözlük sıkıştırma ( Huffman'dan çok daha iyi veya aritmetik kodlama ) popülerlik kazanmaya başladıkça uygulama yöntemleri sonunda bulundu .

Bununla birlikte, sıkıştırmada kullanımı görüntüleri için JPEG 2000 ve JBIG2 standartları .

Prensip

Aritmetik kodlama (gibi Huffman kodlama ) (sabit boyutta bir sembol yani bir değişken uzunluk kodu olan bit tercihen,) bitlerinin farklı sayıda kodlanmış ya da orijinal boyutuna eşittir. Sembollerin yoğunluğu bu nedenle değiştirilmez, kapladıkları alanı azaltmak için kodlamaları değiştirilir.

Aritmetik kodlamayı diğer kaynak kodlamalarından ayıran şey, mesajı parçalar halinde kodlamasıdır (teorik olarak herhangi bir boyuttaki tüm bir mesajı kodlayabilir, ancak pratikte ortalama olarak yalnızca yaklaşık on beş simgeden oluşan parçaları kodlayabiliriz) ve bu parçaların her birini bir Huffman'ın her sembolü belirli bir kodla kodladığı sayı (kayan nokta) . Huffman kodlaması için ortaya çıkan problem, ortaya çıkma olasılığı çok yüksek olan bir karakterin en az bir bit üzerinde kodlanacak olmasıdır. Örneğin,% 90 ile temsil edilen bir karakter kodlanmaya çalışılırsa, karakter kodunun optimal boyutu 0.15 bit olurken, Huffman bu sembolü en az 1 bit üzerinde, yani 6 kat fazla kodlayacaktır. Aralıklı kodlamaya yakın bir algoritma sayesinde aritmetik kodlamanın doldurduğu bu boşluktur . $değil$

Özellikleri

Sıkıştırma

Sıkıştırma, aşağıdakileri içeren istatistiksel bir tablo gerektirir ( sıkıştırılacak sembolleri içeren dosyada gözlemlenebilir istatistiklere mümkün olduğunca yakın ): $Fn$ $değil$

İletide bulunan tüm semboller sıkıştırılacaktır. $s$
Mesajdaki sembolle karşılaşma olasılıkları . $p$ $s$
Aralığı aralıklarla bölünmüş olasılık orantısına sembol, (: orada örneğin eğer mesaj görüntülenir , kendi aralığı uzunluk 0.5 olacak görünen bir% 50 şansın). $[0; 1 [$ $p$ $s$ $s$

Şimdi amaç, bir sembol her eklendiğinde limitlerini değiştirmek ve olasılıkların sayısını mümkün olduğunca sınırlandırmak için belirli bir aralığa (genellikle seçilen aralık ) bir dizi işlem uygulamak olacaktır . çıktılar. $[0; 1 [$ $s$

Sembol eklerken gerçekleştirilecek işlemler şunlardır : $s$

Üst sınır (BS) ve alt sınır (BI) arasındaki fark kaydedilir. Bu değer BB not edilecektir.
BS aşağıdaki değeri alır: BI + BB * (BS_du_symbole_s)
BI şu değeri alır: BI + BB * (BI_du_symbole_s)

İlk sembolü ekledikten sonra, aralık, eklenen sembolün aralığı ile aynı sınırlara sahip olacak, ardından her ekleme, sınırlarını yaklaştıracaktır. Yeterli sayıda simge depolandığında, algoritma bu aralıkta yer alan bir kayan sayı döndürecektir . Bu sayı, girdi dosyasının tamamını temsil eder.

Yüksek görünme olasılığına sahip bir dizi simgenin, aralığın çok az görünen bir dizi simgeyle uğraştığımıza göre çok daha yavaş yakınsamasına neden olacağını fark ederiz. Bu nedenle, yavaş yakınsayan bir aralıktaki bir sayı, son derece hassas bir aralıktaki bir sayıdan daha az anlamlı basamakla kodlanacaktır, dolayısıyla kazanç.

Ayrıca, yalnızca dosyanın sonunu belirtmek için kullanılacak bir sembol eklemeyi düşünmek de gerekir, aksi takdirde açma algoritması süresiz olarak çalışarak dosyayı sözde rasgele bit dizisini üreterek riske atar.

Baskıyı azaltma

Bir dosyayı açmak için (bir sayı ile gösterilir ), sıkıştırma için kullanılan aynı tabloyu kullanmanız ve ardından dosyanın sonuna kadar aşağıdaki adımları gerçekleştirmeniz gerekir: $değil$

Hangi sembolün sayı olduğunu aralıkta gözlemleyin , açılmış dosyaya ekleyin ve olasılığını ve onun BI'sını hafızada tutun . $s$ $s$ $p$ $s$
$değil$ değer alır . $n = (n-BI) / p$

Son işaretleyiciye ulaşıldığında, algoritma durur ve dosya sıkıştırılmamış olarak kabul edilir.

Misal

Sıkıştırma

Burada aritmetik sıkıştırma algoritması "WIKI" metnine uygulanacaktır. Bu nedenle aşağıdaki tabloyu elde ediyoruz:

Mektup	Olasılık	Aralık
W	1/4	[0; 0.25 [
ben	2/4	[0.25; 0.75 [
K	1/4	[0.75; 1 [

Geleneksel olarak, algoritma 0'a eşit bir alt sınır ve 1'e eşit bir üst sınır ile başlatılır. Yalnızca daha önce bir karakterin her ilavesine görülen işlemler dizisini uygulamak kalır.

Karakter eklendi	Alt sınır	Üst sınır
	0	1
W	0	0.25
ben	0,0625	0,1875
K	0.15625	0,1875
ben	0,1640625	0,1796875

Dolayısıyla, aralıktaki herhangi bir sayı "WIKI" dizesinin sıkıştırılmış bir sürümü olacaktır. 0.17 sayısı bu aralığa dahil edildiğinden, sıkıştırılmış "WIKI" yi temsil etmek için uygun olabilir. Tersine, 0.16 veya 0.1796875 aralıkta olmadığından, uymayacaklar ve kod çözme sırasında hatalara neden olacaklar. $[0.1640625; 0.1796875 [$

Baskıyı azaltma

0.17 sıkıştırılmış mesajı aldığımızı varsayalım, kodu şu şekilde çözülecektir:

(Her harfin aralıklarını ve görünme olasılıklarını bilmek için açıkça aynı tabloyu kullanıyoruz).

Sıkıştırılmış kod	Aralık	İlgili mektup	Kurtarılan metin
0.17	[0; 0.25 [	W	W
0.68	[0.25; 0.75 [	ben	WI
0.86	[0.75; 1 [	K	WIK
0.44	[0.25; 0.75 [	ben	WIKI

Bu nedenle, önceden sıkıştırılmış doğru karakter dizesini buluruz.

Zayıf yönler

Bu sıkıştırma yöntemi, şu anda bilinen ve düzeltilen iki ana kusurla karşılaşır:

Birincisi, Huffman kodlamasında olduğu gibi aynı sorunlara neden olan sabit bir istatistik tablosu kullanmak gerçeğidir, yani bir dosyanın tipik olmayan istatistiklerle sıkıştırılması (çok az olması gereken semboller, yüksek bir olasılıkla bulunur) sıkıştırmadan sonra öncekinden daha büyük olabilir. Bu nedenle, burada da en etkili çözüm, bir sembolün her karşılaşmasında, istatistikleri güncellenen ve aralıkları uyarlanan, frekanslarının tümü eşit başlayan uyarlanabilir bir tablo kullanmaktır.

İkinci büyük sorun, bilgisayar terimleriyle virgül sayılarının işlenmesinin daha karmaşık olmasıdır, ancak dekompresyon sırasında ölümcül olabilecek yuvarlama hataları (bir bilgisayarın destekleyebileceği ondalık noktadan sonraki sonlu basamak sayısı nedeniyle) üretebilir. Bu problemin üstesinden gelmek için, başlangıç aralığını 00000'e eşit bir alt sınırla ve 99999'a eşit bir üst sınırla başlatmak mümkündür ... Bu durumda hesaplamalar ondalık sayılarla aynıdır, ancak tam sayılar üzerinde yapılır. Örneğin, her iki terminal çok yakın olduğunda yeni bir sorun ortaya çıkabilir . Bu aralık aslında hiçbir tamsayı değeri içermez ve yeni sembollerin eklenmesi onu değiştirmez. Bu noktaya geldiğimizde, ya algoritmayı daha önce durdurmalıyız ya da ilk rakamlar arasında sadece 1 fark varsa ve sonraki rakam alt sınır için 9 ve üst rakam için 0 değerindeyse, önce bunları silin. rakamları girin ve aşağıdaki rakamları sola kaydırın. Son rakamlar alt limit için 0'a ve üst limit için 9'a eşit olacak ve bu aralıkta yeni bir sayı bulmayı mümkün kılacaktır. $[6999 ...; 7000 ... [$

İlgili Makaleler

Kaynakça

(en) David MacKay, Information Theory, Inference, and Learning Algorithms , Cambridge University Press ,2003( ISBN 0-521-64298-1 ) [ basımların ayrıntıları ]

Referanslar

Mark Nelson ( çeviren. Hervé Soulard), Veri sıkıştırma: metinler, görüntüler ve sesler , Dunod ,1993, 421 s. ( ISBN 2-10-001681-4 )
" COMPRESSION - aritmetik sıkıştırma " ( 17 Ocak 2015'te erişildi )
" Data Compression - Arithmetic Coding " ( 17 Ocak 2015'te erişildi )
" Chapter 1: Arithmetic coding " ( 18 Ocak 2015'te erişildi )