Aritmetik Kodlama

Aritmetik kodlama, kayıpsız veri sıkıştırmasında kullanılan bir entropi kodlaması biçimidir. Normalde, “merhaba orada” gibi bir karakter dizisi, ASCII kodunda olduğu gibi, karakter başına sabit sayıda bit kullanılarak temsil edilir. Bir dize aritmetik kodlamaya dönüştürüldüğünde, sık kullanılan karakterler daha az bitle depolanır ve bu kadar sık olmayan karakterler daha fazla bit ile depolanır ve toplamda daha az bit elde edilir. Aritmetik kodlama, Huffman kodlaması gibi diğer entropi kodlama biçimlerinden farklıdır, çünkü girdiyi bileşen sembollerine ayırmak ve her birini bir kodla değiştirmek yerine, aritmetik kodlama tüm mesajı tek bir sayıya, rastgele hassasiyetli kesir q burada 0.0 ≤ q <1.0. Mevcut bilgileri iki sayı ile tanımlanan bir aralık olarak temsil eder. Asimetrik sayısal sistemler olarak adlandırılan son entropi kodlayıcı ailesi , mevcut bilgileri temsil eden tek bir doğal sayı üzerinde doğrudan çalışma sayesinde daha hızlı uygulamalara izin verir.

Üç sembolün “A”, “B” ve “C” sabit olasılık dağılımını varsayarak aritmetik bir kodlama örneği. “A” olasılığı% 50, “B” olasılığı% 33 ve “C” olasılığı% 17’dir. Ayrıca, her adımda özyineleme derinliğinin bilindiğini varsayıyoruz. Birinci adımda [0,5, 0,83) aralığında olan “B” kodluyoruz: “0,10 x ” ikili sayı , tamamen [0,5, 0,83) içindeki bir Aralığı temsil eden en kısa koddur. ” x “, rastgele bir bit dizisi anlamına gelir. İki uç durum vardır: en küçük x , temsil edilen aralığın sol tarafını temsil eden sıfır anlamına gelir. Ardından aralığın sol tarafı dec (0.10) = 0.5’dir. Diğer uçta, xüst limit dec (0.11) = 0.75 olan sınırlı bir sekans anlamına gelir. Bu nedenle, “0.10 x “, [0.5, 0.83) içindeki [0.5, 0.75) aralığını temsil eder. Şimdi “0” ı bırakabiliriz. çünkü tüm aralıklar “0” ile başlar. ve ” x ” bölümünü göz ardı edebiliriz, çünkü hangi bit dizisini temsil ederse et, içeride kalacağız [0.5, 0.75).

Uygulama ayrıntıları ve örnekleri

“WIKI” mesajını aritmetik kodlama ile kodlama

1.	Harf frekansları bulunur.
2.	[0, 1) aralığı, frekansların oranına bölünür.
3-5.	İlgili aralık, mesajdaki her harf için yinelemeli olarak bölümlenir.
6.	Son aralıktaki herhangi bir değer, mesajı temsil edecek şekilde seçilir.
2 * -6 *.	Bölümleme ve ileti yerine “KIWI” değeri.

Yukarıdaki örnek bir daire olarak görselleştirildi, “WIKI” ve “KIWI” kırmızı kodlamalarındaki değerler – SVG görüntüsünde , vurgulamak ve istatistiklerini göstermek için bir aralığın üzerine gelir.

Eşit olasılıklar

En basit durumda, her sembolün meydana gelme olasılığı eşittir. Örneğin, her biri eşit olarak meydana gelmesi muhtemel A, B ve C olmak üzere üç simge kümesini düşünün. Basit blok kodlama , sembol başına 2 bit gerektirir, bu da israftır: bit varyasyonlarından biri asla kullanılmaz. Yani A = 00, B = 01 ve C = 10, ancak 11 kullanılmıyor.

Daha verimli bir çözüm, bu üç sembolün bir dizisini, her bir basamağın bir sembolü temsil ettiği, taban 3’te rasyonel bir sayı olarak temsil etmektir. Örneğin, “ABBCAB” dizisi , [0, 1) aralığında bir değer olarak aritmetik kodlamada 0.011201 ₃ olabilir . Bir sonraki adım, bu üçlü sayıyı 0.0010110010 ₂ gibi kurtarmak için yeterli sayıda sabit noktalı ikili sayı kullanarak kodlamaktır – bu sadece 10 bittir; Saf blok kodlama ile karşılaştırıldığında 2 bit kaydedilir. Bu, uzun diziler için mümkündür, çünkü keyfi olarak kesin sayıların tabanını dönüştürmek için verimli, yerinde algoritmalar vardır.

Değerin kodunu çözmek için, orijinal dizenin uzunluğu 6 olduğunu bilerek, basitçe taban 3’e geri dönebilir, 6 basamağa yuvarlanabilir ve dizeyi kurtarabilir.

Bir model tanımlama

Genel olarak, aritmetik kodlayıcılar, verilen herhangi bir sembol ve olasılık kümesi için neredeyse optimal çıktı üretebilir (optimal değer, olasılık P’nin her sembolü için −log ₂ P bitidir , bkz. Kaynak kodlama teoremi ). Aritmetik kodlama kullanan sıkıştırma algoritmaları , verilerin bir modelini belirleyerek başlar – temel olarak mesajın sembollerinde hangi kalıpların bulunacağının bir tahmini. Bu tahmin ne kadar doğru olursa, çıktının optimal seviyesine o kadar yakın olacaktır.

Örnek : Belirli bir izleme aracının çıkışını zaman içinde açıklamak için basit, statik bir model şunlar olabilir:

% 60 sembol NÖTR
% 20 sembol şansı POZİTİF
% 10 sembol şansı OLUMSUZ
% 10 sembol SON BİLGİ. (Bu sembolün varlığı, veri sıkıştırmasında oldukça yaygın olduğu gibi akışın ‘dahili olarak sonlandırılacağı’ anlamına gelir; bu sembol veri akışında göründüğünde, kod çözücü tüm akışın kodunun çözüldüğünü bilecektir.)

Modeller ayrıca, bu örnek için seçilen basit dört sembol seti dışındaki harfleri de işleyebilir. Daha sofistike modeller de mümkündür: yüksek dereceli modelleme, bir sembolün mevcut olasılığından önceki tahminini ( bağlam ) temel alarak değiştirir , böylece İngilizce metin modelinde, örneğin, ” u “,” Q “veya” q “harfini izlediğinde çok daha yüksek olur. Modeller uyarlanabilir bile olabilir , böylece verilerdeki tahminlerini akışın gerçekte içerdiği şeye göre sürekli olarak değiştirirler. Kod çözücü kodlayıcı ile aynı modele sahip olmalıdır.

Kodlama ve kod çözme: genel bakış

Genel olarak, kodlama işleminin son aşaması hariç her adımı aynıdır; kodlayıcının temelde dikkate alınması gereken sadece üç veri parçası vardır:

Kodlanması gereken bir sonraki sembol
Geçerli aralık (kodlama işleminin en başında aralık [0,1] olarak ayarlanır, ancak bu değişir)
Modelin, bu aşamada mümkün olan çeşitli sembollerin her birine atadığı olasılıklar (daha önce belirtildiği gibi, yüksek dereceli veya uyarlanabilir modeller, bu olasılıkların her adımda aynı olması anlamına gelmez.)

Kodlayıcı, geçerli aralığı alt aralıklara böler; her biri geçerli aralıktaki o sembolün olasılığı ile orantılı olarak geçerli aralığın bir kısmını temsil eder. Hangi aralık kodlanacak bir sonraki asıl sembole karşılık gelirse, bir sonraki adımda kullanılan aralık olur.

Örnek : yukarıdaki dört sembollü model için:

NÖTR için aralık [0, 0,6) olacaktır
POZİTİF aralığı [0.6, 0.8)
NEGATİF aralığı [0.8, 0.9)
VERİ SONU aralığı [0.9, 1) olacaktır.

Tüm semboller kodlandığında, ortaya çıkan aralık onu üreten sembollerin sırasını açık bir şekilde tanımlar. Kullanılmakta olan aynı son aralığa ve modele sahip olan herkes, son aralığa ulaşmak için enkodere girmesi gereken sembol dizisini yeniden oluşturabilir.

Ancak, son aralığı iletmek gerekli değildir; yalnızca bu aralıkta bulunan bir kesri iletmek gerekir . Özellikle, fraksiyonun yeterli basamağını (hangi bazda olursa olsun) iletmek gerekir, böylece bu rakamlarla başlayan tüm fraksiyonlar son aralığa düşer; bu, ortaya çıkan kodun bir önek kodu olmasını garanti eder .

Kodlama ve kod çözme: örnek

Örnek modelde 0.538’in (dairesel nokta) kod çözülmesini gösteren bir diyagram. Bölge, sembol frekanslarıyla orantılı alt bölgelere ayrılmıştır, daha sonra noktayı içeren alt bölge, aynı şekilde alt bölümlere ayrılmıştır.

Verilen dört sembollü modelle kodlanmış bir mesajın şifresini çözme işlemini düşünün. İleti, 0,538 fraksiyonunda kodlanır (ikili yerine netlik için ondalık kullanarak; ayrıca iletinin kodunu çözmek için gereken sayıda basamak olduğu varsayılarak).

İşlem, kodlayıcı tarafından kullanılan aynı aralık ile başlar: [0,1) ve aynı modeli kullanarak, kodlayıcının sahip olması gereken aynı dört alt aralığa böler. 0.538 fraksiyonu NÖTR için alt aralığa düşer, [0, 0.6); bu, kodlayıcının okuduğu ilk sembolün NÖTR olması gerektiğini gösterir, bu nedenle bu mesajın ilk sembolüdür.

Sonra [0, 0,6) aralığını alt aralıklara bölün:

NÖTR aralığı [0, 0,36), % 60 [0, 0,6) olacaktır .
POZİTİF aralığı [0.36, 0.48), % 20 [0, 0.6) olacaktır .
NEGATİF aralığı [0.48, 0.54), % 10 [0, 0.6) olacaktır .
VERİ SONU için aralık [0.54, 0.6), % 10 [0, 0.6) olacaktır .

.538, [0.48, 0.54) aralığında olduğu için mesajın ikinci sembolü NEGATİF olmalıdır.

Mevcut aralığımızı tekrar alt aralıklara ayırın:

NÖTR için aralık [0.48, 0.516) olacaktır.
POZİTİF aralığı [0.516, 0.528) olacaktır.
NEGATİF aralığı [0.528, 0.534) olacaktır.
VERİ SONU için aralık [0.534, 0.540) olacaktır.

Şimdi 0,538, SON-OF-VERİ sembolü aralığına düşer; bu nedenle, bu bir sonraki sembol olmalıdır. Aynı zamanda dahili sonlandırma sembolü olduğu için, kod çözmenin tamamlandığı anlamına gelir. Akış dahili olarak sonlandırılmazsa, akışın nerede durduğunu belirtmenin başka bir yolu olmalıdır. Aksi takdirde, kod çözme işlemi sonsuza kadar devam edebilir, yanlışlıkla fraksiyondan aslında kodlanmış olandan daha fazla sembol okuyabilir.

Verimsizlik kaynakları

Önceki örnekteki 0.538 mesajı, eşit derecede kısa fraksiyonlar olan 0.534, 0.535, 0.536, 0.537 veya 0.539 tarafından kodlanmış olabilir. Bu, ikili yerine ondalık kullanımının bir miktar verimsizlik getirdiğini göstermektedir. Doğru; üç basamaklı ondalık sayının bilgi içeriği ${\ displaystyle 3 * \ log _ {2} (10) \ yaklaşık 9.966}$ bit ; aynı mesaj sadece 8 bitlik bir maliyetle 0.10001010 (0,5390625 ondalık sayıya eşdeğer) ikili kesimlerinde kodlanmış olabilir. (Son sıfır, ikili kısımda belirtilmelidir, aksi takdirde mesaj, sıkıştırılmış akış boyutu gibi harici bilgiler olmadan belirsiz olur.)

Bu 8 bit çıkış, mesaj içeriğinden veya mesajın entropisinden daha büyüktür.

$\ sum - \ log _ {2} (p_ {i}) = - \ log _ {2} (0.6) - \ log _ {2} (0.1) - \ log _ {2} (0.1) = 7.381 {\ metin {bit}}$

Ancak ikili kodlamada bir tam sayı bit kullanılmalıdır, bu nedenle bu mesaj için bir kodlayıcı en az 8 bit kullanır ve bu da entropi içeriğinden% 8.4 daha büyük bir mesajla sonuçlanır. En fazla 1 bitlik bu verimsizlik, mesaj boyutu büyüdükçe nispeten daha az ek yük ile sonuçlanır.

Ayrıca, talep edilen sembol olasılıkları [0.6, 0.2, 0.1, 0.1) idi, ancak bu örnekteki gerçek frekanslar [0.33, 0, 0.33, 0.33) idi. Aralıklar bu frekanslar için yeniden ayarlanırsa, mesajın entropisi 4.755 bit olur ve aynı NÖTR NEGATİF SONU VERİ SONU mesajı aralık [0, 1/3) olarak kodlanabilir; [1/9, 2/9); [5/27, 6/27); ve bir ikili aralık [0.00101111011, 0.00111000111). Bu, ayrıca aritmetik kodlama gibi istatistiksel kodlama yöntemlerinin, özellikle olasılık modeli kapalıysa, giriş mesajından daha büyük bir çıkış mesajı üretebileceğinin bir örneğidir.

Uyarlanabilir aritmetik kodlama

Aritmetik kodlamanın diğer benzer veri sıkıştırma yöntemlerine göre bir avantajı adaptasyon kolaylığıdır. Uyarlama , veriler işlenirken frekans (veya olasılık) tablolarının değiştirilmesidir. Kod çözmedeki frekans tablosu kodlamayla aynı adımda ve değiştirildiği sürece, kodu çözülen veriler orijinal verilerle eşleşir. Senkronizasyon, genellikle, kodlama ve kod çözme işlemi sırasında meydana gelen sembollerin bir kombinasyonuna dayanır.

Hassasiyet ve renormalizasyon

Aritmetik kodlamanın yukarıdaki açıklamaları bazı basitleştirmeleri içerir. Özellikle, kodlayıcı, aralığın uç noktalarını temsil eden kesirleri tam olarak sonsuz hassasiyet kullanarak hesaplamış ve sadece kesri kodlamanın sonunda nihai biçimine dönüştürmüş gibi yazılır . Sonsuz hassasiyeti simüle etmeye çalışmak yerine, çoğu aritmetik kodlayıcı, kod çözücünün eşleşebileceğini bildikleri sabit bir hassasiyet sınırında çalışır ve hesaplanan kesirleri bu hassasiyette en yakın eşdeğerlerine yuvarlar. Bir örnek, model aralık için çağrılırsa bunun nasıl çalışacağını gösterir $[0,1)$ üçe bölündü ve bu 8 bit hassasiyetle yaklaştırıldı. Şu andan itibaren hassasiyetin bilindiği gibi, kullanabileceğimiz ikili aralıklar da biliniyor.

sembol	olasılık	Aralık sekiz bit hassasiyete düşürüldü		Aralık
sembol	(kesir olarak ifade edilir)	(kesir olarak)	(ikili dosyada)	(ikili dosyada)
bir	1/3	$[0, 85/256)$	[0.00000000, 0.01010101)	00000000 – 01010100
B	1/3	$[85/256, 171/256)$	[0.01010101, 0.10101011)	01010101 – 10101010
C	1/3	$[171/256, 1)$	[0.10101011, 1.00000000)	10101011-11111111

Renormalizasyon adı verilen bir işlem , sonlu hassasiyetin kodlanabilecek toplam sembol sayısı üzerinde bir sınır olmasını engeller. Aralık, aralıktaki tüm değerlerin belirli başlangıç basamaklarını paylaştığı noktaya düştüğünde, bu basamaklar çıktıya gönderilir. Bilgisayar kesinlik ancak birçok basamak için olabilir mevcut basamak sola ötelenir, böylece, artık, bundan daha az ilgileniyor ve sağda, yeni rakam mümkün olduğunca geniş bir yelpazesini genişletmek için eklenir işlemek. Bu sonucun, önceki örneğimizin üç vakasından ikisinde meydana geldiğini unutmayın.

sembol	olasılık	Aralık	Çıktıya gönderilebilen rakamlar	Renormalizasyon sonrası aralık
bir	1/3	0 0000000 – 0 1010100	0	0000000 0 – 1010100 1
B	1/3	01010101 – 10101010	Yok	01010101 – 10101010
C	1/3	1 0.101.011 – 1 1111111	1	0101011 0 – 1111111 1

Genel bir radix değişikliği olarak aritmetik kodlama

Sembollerin eşit olasılıklara sahip olduğu durumlarda, aritmetik kodlamanın basit bir taban veya yarıçap değişimi ile uygulanabileceğini hatırlayın. Genel olarak, aritmetik (ve aralık) kodlama, genelleştirilmiş bir radix değişikliği olarak yorumlanabilir . Örneğin, herhangi bir sembol dizisine bakabiliriz:

DABDDB

dahil edilen sembollerin sıralı bir küme oluşturduğunu ve sıralı kümedeki her sembolün A = 0, B = 1, C = 2, D = 3 vb. Bu, aşağıdaki frekanslar ve kümülatif frekanslar ile sonuçlanır:

sembol	Oluşma sıklığı	Kümülatif frekans
bir	1	0
B	2	1
D	3	3

Kümülatif frekans Bir öğe için madde, önceki tüm frekanslar toplamıdır. Başka bir deyişle, kümülatif frekans, çalışan frekansların toplamıdır.

Konumsal bir sayı sisteminde yarıçap veya taban, sayısal olarak sayıyı ifade etmek için kullanılan bir dizi farklı simgeye eşittir. Örneğin, ondalık sistemde sembol sayısı 10’dur, yani 0, 1, 2, 3, 4, 5, 6, 7, 8 ve 9. Yarıçap, varsayılan bir çarpandaki herhangi bir sonlu tamsayıyı ifade etmek için kullanılır. polinom formu. Örneğin, 457 sayısı aslında 4 × 10 ² + 5 × 10 ¹ + 7 × 10 ^0’dır , burada taban 10 varsayılır, ancak açıkça gösterilmez.

Başlangıçta, DABDDB’yi bir taban-6 rakamına dönüştüreceğiz, çünkü 6 dize uzunluğudur. Dize ilk olarak 301331 rakam dizesine eşlenir ve daha sonra polinom tarafından bir tam sayı ile eşlenir:

6 ^ {5} \ times 3 + 6 ^ {4} \ times 0 + 6 ^ {3} \ times 1 + 6 ^ {2} \ times 3 + 6 ^ {1} \ times 3 + 6 ^ {0} \ times 1 = 23671

Sonuç 23671 , yaklaşık 9 bit olan teorik sınıra ( mesajın entropisi ) çok yakın olmayan 15 bit uzunluğa sahiptir .

Bilgi teorisinin getirdiği teorik sınıra yakın bir uzunluğa sahip bir mesajı kodlamak için, yarıçapı değiştirmek için klasik formülü biraz genelleştirmemiz gerekir. L ve U alt ve üst sınırlarını hesaplayacağız ve aralarından bir sayı seçeceğiz. L’nin hesaplanması için, yukarıdaki ifadedeki her bir terimi, daha önce meydana gelen tüm sembollerin frekanslarının çarpımı ile çarpıyoruz: ${\ begin {align} \ mathrm {L} = {} & (6 ^ {5} \ times 3) + {} \\ & 3 \ times (6 ^ {4} \ times 0) + {} \\ & ( 3 \ times 1) \ times (6 ^ {3} \ times 1) + {} \\ & (3 \ times 1 \ times 2) \ times (6 ^ {2} \ times 3) + {} \\ & (3 \ kez 1 \ kez 2 \ kez 3) \ kez (6 ^ {1} \ kez 3) + {} \\ & (3 \ kez 1 \ kez 2 \ kez 3 \ kez 3) \ kez (6 ^ {0} \ times 1) {} \\ = {} & 25002 \ end {align}}$

Bu polinom ve yukarıdaki polinom arasındaki fark, her terimin, daha önce meydana gelen tüm sembollerin frekanslarının çarpımı ile çarpılmasıdır. Daha genel olarak, L şu şekilde hesaplanabilir:

\ mathrm {L} = \ toplam _ {i = 1} ^ {n} n ^ {ni} C_ {i} {\ prod _ {k = 1} ^ {i-1} f_ {k}}

nerede $\ scriptstyle f_ {k}$ meydana gelme sıklıklarıdır. Dizinler, bir iletideki sembolün konumunu gösterir. Tüm frekansların olduğu özel durumda $\ scriptstyle f_ {k}$ 1, bu baz değişim formülüdür.

Üst sınır U, L artı tüm frekansların çarpımı olacaktır; bu durumda U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. Genel olarak, U aşağıdakiler tarafından verilir:

$\ mathrm {U} = \ mathrm {L} + \ prod _ {k = 1} ^ {n} f_ {k}$

Şimdi mesajı temsil etmek için [L, U) aralığından herhangi bir sayı seçebiliriz; uygun bir seçenek, 251 × 10 ² olarak sonucu temsil ederek sıkıştırmaya ulaşmamızı sağladığı için, mümkün olan en uzun sıfır noktası olan 25100 olan değerdir . Mesajın uzunluğu ayrı olarak depolanırsa, sıfırlar da kesilebilir ve 251 verilir. Daha uzun mesajlar daha uzun sıfır izine sahip olma eğilimindedir.

25100 tamsayısının kodunu çözmek için, polinom hesaplaması aşağıdaki tabloda gösterildiği gibi tersine çevrilebilir. Her aşamada geçerli sembol tanımlanır, ardından karşılık gelen terim sonuçtan çıkarılır.

kalan	Kimlik	Tanımlanmış sembol	Kalan düzeltildi
25100	25100/6 ⁵ = 3	D	(25100-6 ⁵ × 3) / 3 = 590
590	590/6 ⁴ = 0	bir	(590-6 ⁴ × 0) / 1 = 590
590	590/6 ³ = 2	B	(590-6 ³ × 1) / 2 = 187
187	187/6 ² = 5	D	(187-6 ² × 3) / 3 = 26
26	26/6 ¹ = 4	D	(26-6 ¹ × 3) / 3 = 2
2	2/6 ⁰ = 2	B	–

Kod çözme sırasında 6’ya karşılık gelen güce böldükten sonra zemini alırız. Sonuç daha sonra kümülatif aralıklarla eşleştirilir ve arama tablosundan uygun sembol seçilir. Sembol tanımlandığında sonuç düzeltilir. İşlem, iletinin bilinen uzunluğu boyunca veya kalan sonuç pozitif olduğunda devam eder. Klasik baz değişimine kıyasla tek fark, her sembolle ilişkili bir dizi değer olabileceğidir. Bu örnekte, A her zaman 0, B ya 1 ya da 2’dir ve D 3, 4, 5’ten herhangi biridir. Bu, frekanslarla belirlenen aralıklarımıza tam olarak uygundur. Tüm aralıklar 1’e eşit olduğunda, klasik temel değişikliği özel bir durumumuz var.

Sıkıştırılmış mesajın teorik sınırı

Alt sınır L asla n ^n’yi aşmaz , burada n mesajın boyutudur ve bu nedenle $\ scriptstyle \ log _ {2} (n ^ {n}) \; = \; n \ log _ {2} (n)$ bit. Üst sınır U ‘nun hesaplanmasından ve en uzun sıfır izi ile [ L , U ) aralığından bir sayı seçerek mesajın azaltılmasından sonra bu uzunluğun azaltılabileceğini varsayabiliriz. $\ scriptstyle \ log _ {2} \ left (\ prod _ {k = 1} ^ {n} f_ {k} \ sağ)$ bit. Bir üründeki her bir frekans, bu frekansın değeriyle tam olarak aynı sayıda oluştuğundan , ürünün hesaplanması için A alfabesinin boyutunu kullanabiliriz

\ eşya _ {k = 1} ^ {n} f_ {k} = \ eşya _ {k = 1} ^ {A} f_ {k} ^ {f_ {k}}

Mesajdaki tahmini bit sayısı için günlük ₂ uygulandığında , son mesaj (mesaj uzunluğu ve frekans tabloları için logaritmik bir ek yük saymaz), entropi tarafından verilen , uzun mesajlar için en uygun olan bit sayısı ile eşleşir :

{\ displaystyle - \ left [\ sum _ {i = 1} ^ {A} f_ {i} \ log _ {2} (f_ {i}) \ right] * n}

Diğer sıkıştırma yöntemleriyle bağlantılar

Huffman kodlama

Aritmetik kodlama bir seferde bir veriyi sıkıştırmadığı için, iid dizelerini sıkıştırırken keyfi olarak entropiye yakınlaşabilir . Buna karşılık, kullanarak uzantısı ve Huffman kodlama alfabe sembolleri bütün olasılıklar Huffman ve aritmetik hem entropi elde kodlama bu durumda ikisinin güçleri olmadıkça (dizeleri) entropi ulaşmaz.

Saf olarak Huffman ikili dizeleri kodlarken, entropi düşük olsa bile (örn. ({0, 1}) olasılıklar {0.95, 0.05}) mümkün değildir. Huffman kodlaması, her bir değere 1 bit atar ve girişle aynı uzunlukta bir kodla sonuçlanır. Aksine, aritmetik kodlama bitleri iyi sıkıştırır ve optimum sıkıştırma oranına yaklaşır.

1 - [- 0.95 \ log _ {2} (0.95) + - 0.05 \ log _ {2} (0.05)] \ yaklaşık 71.4 \%.

Huffman kodlamasının alt optitesini ele almanın basit bir yolu, her yeni sembolün orijinal alfabeden bir dizi orijinal sembolü – bu durumda bitleri – temsil ettiği yeni bir alfabe oluşturmak için sembolleri birleştirmektir (“engelleme”). Yukarıdaki örnekte, kodlamadan önce üç sembolün dizilerinin gruplanması, aşağıdaki frekanslarla yeni “süper semboller” üretecektir:

000:% 85.7
001, 010, 100: Her biri% 4.5
011, 101, 110: Her biri% 0.24
111:% 0.0125

Bu gruplamayla, Huffman kodlaması, orijinal kodlamadaki her sembol için bir bit ile karşılaştırıldığında, her üç sembol için ortalama 1.3 bit veya sembol başına 0.433 bit anlamına gelir. ${\ displaystyle 56.7 \%}$ sıkıştırma. Rasgele büyük dizilere izin vermek, tıpkı aritmetik kodlama gibi, entropiye keyfi olarak yakınlaşır, ancak bunun için büyük kodlar gerektirir, bu nedenle bu amaç için aritmetik kodlama kadar pratik değildir.

Bir alternatif, çalışma uzunluklarını Huffman tabanlı Golomb-Rice kodlarıyla kodlamaktır . Böyle bir yaklaşım, aritmetik kodlama ve hatta Huffman kodlamasından daha basit ve daha hızlı kodlama / kod çözme sağlar, çünkü ikincisi tablo aramaları gerektirir. {0.95, 0.05} örneğinde, dört bit kalanı olan bir Golomb-Rice kodu ${\ displaystyle 71.1 \%}$ , üç bitlik bloklar kullanmaktan çok daha yakın. Golomb-Rice kodları yalnızca bu örnekteki gibi Bernoulli girdileri için geçerlidir , bu nedenle her durumda engellemenin yerini tutmaz.

Patentler

Aritmetik kodlama için çeşitli spesifik teknikler tarihsel olarak ABD patentleri tarafından kapsanmış olsa da, patentlerin süresi doldukça iyi bilinen çeşitli yöntemler kamuya açık hale getirilmiştir. Patentlerin kapsadığı teknikler, bazı uluslararası standartlarda belirtilen aritmetik kodlama algoritmalarının uygulanması için gerekli olabilir. Böyle bir durum söz konusu olduğunda, bu tür patentler genellikle “makul ve ayrımcı olmayan” adı altında lisanslama için kullanılabilir ( RAND) lisans koşulları (en azından standartlar komitesi politikası olarak). Bazı iyi bilinen durumlarda (süresi dolmuş IBM patentlerini içeren bazıları da dahil olmak üzere), bu tür lisanslar ücretsiz olarak sağlanmıştır ve diğer durumlarda lisans ücretleri gereklidir. RAND koşulları altında lisansların bulunması, özel bir ticari yazılım ürünü hazırlayan bir şirket için “makul” görünebileceğinden, teknolojiyi kullanmak isteyebilecek herkesi tatmin etmek zorunda değildir, özgür yazılım veya açık kaynaklı bir proje için çok daha az makul görünebilir .

En az bir önemli sıkıştırma yazılım programı olan bzip2 , o sırada algılanan patent durumu nedeniyle Huffman kodlaması lehine aritmetik kodlama kullanımını kasten durdurmuştur. Ayrıca, hem Huffman kodlaması hem de aritmetik kodlama için seçeneklere sahip olan JPEG dosya formatındaki kodlayıcılar ve kod çözücüler , genellikle yalnızca orijinal olarak patent endişeleri nedeniyle olan Huffman kodlama seçeneğini destekler; sonuç, günümüzde kullanılan hemen hemen tüm JPEG görüntülerinin Huffman kodlaması ^{[1] kullanmasıdır,} ancak JPEG’in aritmetik kodlama patentlerinin ^[2] süresi, JPEG standardının yaşı nedeniyle (tasarımı yaklaşık 1990’a kadar tamamlanmıştır) dolmuştur. ^[3] PackJPG gibi, Huffman kodlu dosyaları aritmetik kodlama (özel dosya adı .pjg ile) olanlara% 25’e kadar boyut tasarrufu gösteren kayıpsız bir şekilde dönüştürebilen bazı arşivler vardır.

JPEG görüntü sıkıştırma formatının aritmetik kodlama algoritması, aşağıda belirtilen patentlere dayanmaktadır (süresi dolmuş olduğundan). ^[4]

ABD Patenti 4,652,856 – ( IBM ) 4 Mart 1986’da dosyalandı, 24 Mart 1987 verildi – Kottappuram MA Mohiuddin, Jorma Johannen Rissanen – Çarpım gerektirmeyen çoklu alfabe aritmetik kodu
ABD Patenti 4,905,297 – (IBM) 18 Kasım 1988’de dosyalandı, 27 Şubat 1990 verildi – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannen Rissanen – Aritmetik kodlayıcı kodlayıcı ve kod çözücü sistemi
ABD Patenti 4.935.882 – (IBM) 20 Temmuz 1988’de dosyalandı, 19 Haziran 1990 verildi – William B. Pennebaker, Joan L. Mitchell – Aritmetik kodlayıcılar için olasılık uyarlaması
JP Patent 1021672 – ( Mitsubishi ) 21 Ocak 1989’da dosyalandı, 10 Ağustos 1990 verildi – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Kodlama sistemi
JP Patent 2-46275 – (Mitsubishi) 26 Kasım 1990’da dosyalandı, 5 Kasım 1991 verildi – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Kodlama cihazı ve kodlama yöntemi

Aritmetik kodlamaya ilişkin diğer patentler (çoğunlukla süresi dolmuş) aşağıdakileri içerir.

ABD Patenti 4,122,440 – (IBM) 4 Mart 1977’de dosyalandı, 24 Ekim 1978 verildi – Glenn George Langdon, Jorma Johannen Rissanen – Aritmetik dizi kodlama yöntemi ve araçları
ABD Patenti 4,286,256 – (IBM) 28 Kasım 1979’da dosyalandı, 25 Ağustos 1981 verildi – Glen George Langdon, Jorma Johannen Rissanen – Az sayıda işlem kullanarak aritmetik kodlama yöntemi ve araçları
ABD Patenti 4.467.317 – (IBM) 30 Mart 1981’de dosyalandı, 21 Ağustos 1984 verildi – Glen George Langdon, Jorma Johannen Rissanen – Eşzamanlı değer güncellemesi kullanılarak yüksek hızlı aritmetik sıkıştırma kodlaması
ABD Patenti 4,891,643 – (IBM) 15 Eylül 1986’da dosyalandı, 2 Ocak 1990 verildi – Joan L. Mitchell, William B. Pennebaker – Seçici olarak kullanılan çeşitli aritmetik kodlayıcı kodlayıcılar ve kod çözücüler tarafından aritmetik kodlama veri sıkıştırma / sıkıştırma
JP Patent 11782787 – ( NEC ) 13 Mayıs 1987’de dosyalandı, 18 Kasım 1988 verildi – Michio Shimada – Veri sıkıştırma aritmetik kodlama cihazı
JP Patent 15015487 – ( KDDI ) 18 Haziran 1987’de dosyalandı, 22 Aralık 1988 verildi – Shuichi Matsumoto, Masahiro Saito – Aritmetik kodlamada taşıma yayılımını önleme sistemi
ABD Patenti 4,933,883 – (IBM) 3 Mayıs 1988’de dosyalandı, 12 Haziran 1990 verildi – William B. Pennebaker, Joan L. Mitchell – Aritmetik kodlayıcılar için olasılık uyarlaması
ABD Patenti 4.989.000 – (IBM) 29 Haziran 1991’de dosyalanan 19 Haziran 1989’da sunuldu – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Basitleştirilmiş olasılık alt aralık tahminiyle aritmetik kodlama kullanarak veri dizisi sıkıştırma
ABD Patenti 5,099,440 – (IBM) 5 Ocak 1990’da dosyalandı, 24 Mart 1992 verildi – William B. Pennebaker, Joan L. Mitchell – Aritmetik kodlayıcılar için olasılık uyarlaması
ABD Patenti 5,272,478 – ( Ricoh ) 17 Ağustos 1992’de dosyalandı, 21 Aralık 1993 verildi – James D. Allen – Entropi kodlaması için yöntem ve aparat

Not: Bu liste ayrıntılı değildir. Daha fazla ABD patentinin listesi için aşağıdaki bağlantılara bakın. ^[5] Dirac kodek aritmetik kodlama kullanır ve patentli değildir. ^[6]

Aritmetik kodlama ile ilgili patentler başka ülkelerde de bulunabilir; tüm dünyada yazılımın patentlenebilirliği hakkında bir tartışma için yazılım patentlerine bakın .

Deneyler ve diğer teknik özellikler

Aritmetik kodlamanın her programlı uygulaması farklı bir sıkıştırma oranına ve performansa sahiptir. Sıkıştırma oranları sadece biraz değişse de (genellikle% 1’in altında), ^[7] kod yürütme süresi 10 katına kadar değişebilir. Performans ve sıkıştırma oranı nedeniyle doğru kodlayıcıyı halka açık enkoderler listesinden seçmek basit bir iş değildir. veri türüne, özellikle de alfabenin boyutuna (farklı sembollerin sayısı) bağlıdır. İki özel kodlayıcıdan biri küçük alfabe için daha iyi performans gösterirken diğeri büyük alfabe için daha iyi performans gösterebilir. Kodlayıcıların çoğunun alfabenin boyutu konusunda sınırlamaları vardır ve birçoğu tam olarak iki sembolün (0 ve 1) alfabeleri için uzmanlaşmıştır.

Kaynakça:

[1] JPEG nedir? comp.compression Sık Sorulan Sorular (bölüm 1/3)
“Tavsiye T.81 (1992) Düzeltme 1 (01/04)” . Tavsiye T.81 (1992) . Uluslararası Telekomünikasyon Birliği. 9 Kasım 2004 . Erişim tarihi: 3 Şubat 2011 .
JPEG Hareketsiz Görüntü Veri Sıkıştırma Standardı , WB Kaleci ve JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1
“T.81 – SÜREKLİ TON HALA GÖRÜNTÜLERİNİN DİJİTAL SIKIŞTIRILMASI VE KODLANMASI – GEREKLİLİKLER VE KILAVUZLAR” (PDF) . CCITT . Eylül 1992 . Erişim tarihi: 12 Temmuz 2019 .
[2] comp.compression Sık Sorulan Sorular (bölüm 1/3)
[3] Dirac video codec bileşeni 1.0 yayınlandı
Örneğin, Howard & Vitter (1994) , gerçek sayı aralıklarına dayalı aritmetik kodlama versiyonlarını, bu aralıklara tamsayı yaklaşımları ve ikili yarı aritmetik kodlama adını verdikleri daha da kısıtlı bir yaklaşım türünü tartışmaktadır. Gerçek ve tamsayı sürümler arasındaki farkın ihmal edilebilir olduğunu, yarı aritmetik yöntemlerinin sıkıştırma kaybının keyfi olarak küçük olabileceğini kanıtlar ve yaklaşık bir tanesinin maruz kaldığı sıkıştırma kaybını% 0.06’dan daha az olarak bağlarlar. Bakınız: Howard, Paul G .; Vitter, Jeffrey S. (1994), “Veri sıkıştırma için aritmetik kodlama” (PDF) , IEEE Bildirileri , 82 (6): 857–865, doi :10,1109 / 5,286189 , hdl : 1808/7229 arşivlenmiş, orijinal (PDF) Ekim 2013 18 , alınan 17 Ekim 2013.

Kaynaklar

MacKay, David JC (Eylül 2003). “Bölüm 6: Akış Kodları” . Bilgi Kuramı, Çıkarım ve Öğrenme Algoritmaları . Cambridge Üniversitesi Yayınları . ISBN 0-521-64298-1. Arşivlenmiş orijinal (PDF / PostScript / DjVu / LaTeX ) 2007 22 Aralık . Erişim tarihi: 30 Aralık 2007 .
Basın, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). “Bölüm 22.6. Aritmetik Kodlama” . Sayısal Tarifler: Bilimsel Hesaplama Sanatı (3. baskı). New York: Cambridge Üniversitesi Yayınları. ISBN 978-0-521-88068-8.
Rissanen, Jorma (Mayıs 1976). “Genelleştirilmiş Kraft Eşitsizliği ve Aritmetik Kodlama” . IBM Araştırma ve Geliştirme Dergisi . 20 (3): 198-203. doi : 10.1147 / rd.203.0198 . Erişim tarihi: 21 Eylül 2007 .
Rissanen, JJ; Langdon GG, Jr (Mart 1979). “Aritmetik kodlama” (PDF) . IBM Araştırma ve Geliştirme Dergisi . 23 (2): 149-162. doi : 10.1147 / rd.232.0149 . Arşivlenmiş orijinal (PDF) 28 Eylül 2007 tarihinde . Erişim tarihi: 22 Eylül 2007 .
Witten, Ian H .; Neal, Radford M .; Cleary, John G. (Haziran 1987). “Veri Sıkıştırma için Aritmetik Kodlama” (PDF) . ACM’nin iletişimi . 30 (6): 520-540. doi : 10.1145 / 214762.214771 . 28 Eylül 2007 tarihinde kaynağından arşivlendi (PDF) . Erişim tarihi: 21 Eylül 2007 .

Rodionov Anatoly, Volkov Sergey (2010) “p-adik aritmetik kodlama” Çağdaş Matematik Cilt 508, 2010 Çağdaş Matematik
Rodionov Anatoly, Volkov Sergey (2007) ”p-adik aritmetik kodlama”, https://arxiv.org/abs//0704.0834v1

[1] [1] JPEG nedir? comp.compression Sık Sorulan Sorular (bölüm 1/3)

[2] “Tavsiye T.81 (1992) Düzeltme 1 (01/04)” . Tavsiye T.81 (1992) . Uluslararası Telekomünikasyon Birliği. 9 Kasım 2004 . Erişim tarihi: 3 Şubat 2011 .

[3] JPEG Hareketsiz Görüntü Veri Sıkıştırma Standardı , WB Kaleci ve JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1

[t81-4] “T.81 – SÜREKLİ TON HALA GÖRÜNTÜLERİNİN DİJİTAL SIKIŞTIRILMASI VE KODLANMASI – GEREKLİLİKLER VE KILAVUZLAR” (PDF) . CCITT . Eylül 1992 . Erişim tarihi: 12 Temmuz 2019 .

[5] [2] comp.compression Sık Sorulan Sorular (bölüm 1/3)

[6] [3] Dirac video codec bileşeni 1.0 yayınlandı

[7] Örneğin, Howard & Vitter (1994) , gerçek sayı aralıklarına dayalı aritmetik kodlama versiyonlarını, bu aralıklara tamsayı yaklaşımları ve ikili yarı aritmetik kodlama adını verdikleri daha da kısıtlı bir yaklaşım türünü tartışmaktadır. Gerçek ve tamsayı sürümler arasındaki farkın ihmal edilebilir olduğunu, yarı aritmetik yöntemlerinin sıkıştırma kaybının keyfi olarak küçük olabileceğini kanıtlar ve yaklaşık bir tanesinin maruz kaldığı sıkıştırma kaybını% 0.06’dan daha az olarak bağlarlar. Bakınız: Howard, Paul G .; Vitter, Jeffrey S. (1994), “Veri sıkıştırma için aritmetik kodlama” (PDF) , IEEE Bildirileri , 82 (6): 857–865, doi :10,1109 / 5,286189 , hdl : 1808/7229 arşivlenmiş, orijinal (PDF) Ekim 2013 18 , alınan 17 Ekim 2013.