Aritmetik kodlama - Arithmetic coding

Aritmetik kodlama ( AC ), kayıpsız veri sıkıştırmada kullanılan bir entropi kodlama biçimidir . Normalde, 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 bit ile depolanacak ve çok sık olmayan karakterler daha fazla bit ile depolanacak ve toplamda daha az bit kullanılmasına neden olacaktır. Aritmetik kodlama, Huffman kodlaması gibi diğer entropi kodlama biçimlerinden farkı , girdiyi bileşen sembollerine ayırmak ve her birini bir kodla değiştirmek yerine, aritmetik kodlamanın tüm mesajı tek bir sayı, isteğe bağlı kesinlikli bir kesir q olarak kodlamasıyla , burada 0.0 ≤ q < 1.0 . Mevcut bilgiyi iki sayı ile tanımlanan bir aralık olarak temsil eder. Asimetrik sayı sistemleri olarak adlandırılan yeni bir entropi kodlayıcı ailesi , mevcut bilgiyi temsil eden tek bir doğal sayı üzerinde doğrudan çalışma sayesinde daha hızlı uygulamalara izin verir.

Üç "A", "B" ve "C" sembolünün sabit bir olasılık dağılımını varsayan bir aritmetik 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ığı içindeki "B"yi kodluyoruz: "0.10 x " ikili sayısı , tamamen [0.5, 0.83) içinde olan bir aralığı temsil eden en kısa koddur. " x " keyfi 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. O zaman aralığın sol tarafı dec(0.10) = 0.5 olur. Diğer uçta, x , dec(0.11) = 0.75 üst limitine sahip sonlu bir diziyi temsil eder. Bu nedenle, "0.10 x ", [0.5, 0.83) içindeki [0.5, 0.75) aralığını temsil eder. Şimdi "0" ı dışarıda bırakabiliriz. tüm aralıklar "0" ile başladığından beri. ve " x " kısmını yok sayabiliriz çünkü hangi bit dizisini temsil ederse etsin [0.5, 0.75] içinde kalacağız.

Uygulama ayrıntıları ve örnekleri

"WIKI" mesajını aritmetik kodlama ile kodlama

1.	Harf frekansları bulunur.
2.	[0, 1) aralığı, frekansların oranında bölünür.
3-5.	Karşılık gelen aralık, mesajdaki her harf için yinelemeli olarak bölünür.
6.	Son aralıktaki herhangi bir değer mesajı temsil etmek için seçilir.
2*–6*.	Bunun yerine mesaj "KIWI" ise bölümleme ve değer.

Yukarıdaki örnek bir daire olarak görselleştirilmiştir, kırmızı kodlamalı değerler "WIKI" ve "KIWI" - SVG görüntüsünde , vurgulamak ve istatistiklerini göstermek için bir aralığın üzerine gelin

Eşit olasılıklar

En basit durumda, her sembolün ortaya çıkma olasılığı eşittir. Örneğin, A, B ve C olmak üzere üç sembolden oluşan ve her birinin oluşma olasılığı eşit olan bir küme düşünün. Basit blok kodlama , sembol başına 2 bit gerektirir, bu da israftır: bit varyasyonlarından biri asla kullanılmaz. Başka bir deyişle, A, B ve C sembolleri sırasıyla 00, 01 ve 10 olarak kodlanmış ve 11'i kullanılmamış olabilir.

Daha verimli bir çözüm, bu üç sembolün bir dizisini, her basamağın bir sembolü temsil ettiği taban 3'te rasyonel bir sayı olarak temsil etmektir. Örneğin, dizi "ABBCAB" 0.011201 haline gelebilir ₃ aralığında [0, 1) bir değer olarak aritmetik kodlama. Sonraki adım, bu üçlü sayıyı kurtarmak için yeterli hassasiyette sabit noktalı bir ikili sayı kullanarak, örneğin 0.0010110010 ₂ - bu yalnızca 10 bittir; Saf blok kodlamaya kıyasla 2 bit kaydedilir. Bu, uzun diziler için uygundur, çünkü keyfi kesin sayıların tabanını dönüştürmek için verimli, yerinde algoritmalar vardır.

Değerin kodunu çözmek için, orijinal dizginin 6 uzunluğunda olduğunu bilmek, basitçe 3 tabanına geri dönebilir, 6 basamağa yuvarlayabilir ve dizgiyi kurtarabilir.

Model tanımlama

Genel olarak, aritmetik kodlayıcılar, verilen herhangi bir sembol ve olasılık seti için optimuma yakın çıktı üretebilir. (En uygun değer -log olan ₂ p olasılığı her sembol için bit P , bakınız Kaynak kodlama teoremi .) Belirleyici ile başlangıç kodlama, aritmetik kullanımı Sıkıştırma süreci modeli verileri - desenler semboller bulunabilir ne temelde bir tahmini mesajın. Bu tahmin ne kadar doğru olursa, çıktı optimale o kadar yakın olur.

Örnek : belirli bir izleme aracının çıktısını zaman içinde tanımlayan basit, statik bir model şöyle olabilir:

• %60 NÖTR sembolü şansı
• 20% POZİTİF sembolü şansı
• %10 NEGATİF sembol şansı
• %10 END-OF-VERİ sembolü şansı. (Bu sembolün varlığı, veri sıkıştırmada 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, bu örnek için seçilen basit dört sembollü set dışındaki alfabeleri de kullanabilir. Daha karmaşık modeller de mümkündür: daha yüksek dereceli modelleme, bir sembolün mevcut olasılığına ilişkin tahminini kendisinden önce gelen sembollere ( bağlam ) dayalı olarak değiştirir, böylece İngilizce metin için bir modelde, örneğin, yüzde şansı " u", bir "Q" veya "q" izlediğinde çok daha yüksek olacaktır. Modeller uyarlanabilir bile olabilir , böylece akışın gerçekte ne içerdiğine bağlı olarak verilere ilişkin tahminlerini 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, sonuncusu hariç, kodlama işleminin her adımı aynıdır; kodlayıcının temel olarak dikkate alması gereken yalnızca üç 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şecektir)
• Modelin bu aşamada mümkün olan çeşitli sembollerin her birine atadığı olasılıklar (daha önce belirtildiği gibi, daha yüksek dereceli veya uyarlanabilir modeller, bu olasılıkların her adımda mutlaka aynı olmadığı anlamına gelir.)

Kodlayıcı, geçerli aralığı alt aralıklara böler; bunların her biri, geçerli bağlamda o sembolün olasılığıyla orantılı olarak geçerli aralığın bir kısmını temsil eder. Bir sonraki kodlanacak olan gerçek sembole karşılık gelen aralık, 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) olur
• POZİTİF için aralık [0.6, 0.8) olacaktır
• NEGATİF için aralık [0.8, 0.9) olacaktır
• VERİ SONU için aralık [0.9, 1) olacaktır.

Tüm semboller kodlandığında, ortaya çıkan aralık, onu üreten sembol dizisini açık bir şekilde tanımlar. Aynı son aralığa ve kullanılan modele sahip olan herkes, bu son aralığa neden olmak için kodlayıcıya girmiş olması gereken sembol dizisini yeniden oluşturabilir.

Ancak son aralığı iletmek gerekli değildir; sadece bu aralık içinde yer alan bir kesri iletmek gereklidir . Özellikle, kesrin yalnızca yeterli basamaklarını (hangi bazda olursa olsun) iletmek gerekir, böylece bu basamaklarla başlayan tüm kesirler 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 (yuvarlak nokta) kodunun çözülmesini gösteren bir diyagram. Bölge, sembol frekanslarıyla orantılı olarak alt bölgelere bölünür, ardından noktayı içeren alt bölge de aynı şekilde art arda alt bölgelere bölünür.

Verilen dört sembollü modelle kodlanmış bir mesajın kodunu çözme sürecini düşünün. Mesaj 0,538 fraksiyonunda kodlanmıştır (açıklık için ikili yerine ondalık kullanılır; ayrıca mesajın kodunu çözmek için yalnızca gerektiği kadar basamak olduğu varsayılır.)

İşlem, kodlayıcı tarafından kullanılan aynı aralıkla başlar: [0,1) ve aynı modeli kullanarak, onu kodlayıcının sahip olması gereken aynı dört alt aralığa bölerek başlar. 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, dolayısıyla bu, mesajın ilk sembolüdür.

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

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

0.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 bölün:

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

Şimdi 0,538, VERİ SONU sembolünün aralığına giriyor; bu nedenle, bu bir sonraki sembol olmalıdır. Aynı zamanda dahili sonlandırma sembolü olduğundan, kod çözmenin tamamlandığı anlamına gelir. Akış dahili olarak sonlandırılmamışsa, 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 kesirden aslında kodlanmış olandan daha fazla sembol okuyabilir.

verimsizlik kaynakları

Önceki örnekteki 0,538 mesajı, 0,534, 0,535, 0,536, 0,537 veya 0,539 eşit kısa kesirler tarafından kodlanmış olabilir. Bu, ikili yerine ondalık kullanımının bazı verimsizlikler getirdiğini göstermektedir. Doğru; üç basamaklı ondalık sayının bilgi içeriği bit'tir ; aynı mesaj, sadece 8 bitlik bir maliyetle 0.10001010 (0,5390625 ondalık sayıya eşdeğer) ikili kesirde kodlanabilirdi. (Son sıfır ikili kesirde belirtilmelidir, aksi takdirde sıkıştırılmış akış boyutu gibi harici bilgiler olmadan mesaj belirsiz olacaktır.) ${\displaystyle 3*\log _{2}(10)\yaklaşık 9.966}$

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

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

Ancak ikili kodlamada tam sayıda 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, iddia edilen sembol olasılıkları [0.6, 0.2, 0.1, 0.1), ancak bu örnekteki gerçek frekanslar [0.33, 0, 0.33, 0.33)'tür. Bu frekanslar için aralıklar yeniden ayarlanırsa, mesajın entropisi 4.755 bit olur ve aynı NÖTR NEGATİF VERİ SONU mesajı, [0, 1/3] aralıkları olarak kodlanabilir; [1/9, 2/9); [5/27, 6/27); ve bir ikili aralık [0.001011111011, 0.00111000111). Bu aynı zamanda, 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ı, uyarlama kolaylığıdır. Uyarlama , veriler işlenirken frekans (veya olasılık) tablolarının değiştirilmesidir. Kodu çözülen veriler, kod çözmedeki frekans tablosu, kodlamadakiyle aynı şekilde ve aynı adımda değiştirildiği sürece 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 yeniden normalleştirme

Aritmetik kodlamanın yukarıdaki açıklamaları bazı basitleştirmeler içermektedir. Özellikle, kodlayıcı ilk önce aralığın uç noktalarını temsil eden kesirleri sonsuz hassasiyet kullanarak tam olarak hesaplamış ve kodlamanın sonunda kesri yalnızca son biçimine dönüştürmüş gibi yazılır . Çoğu aritmetik kodlayıcı, sonsuz kesinliği simüle etmeye çalışmak yerine, kod çözücünün eşleştirebileceğini bildikleri sabit bir kesinlik sınırında çalışır ve hesaplanan kesirleri bu hassasiyetteki en yakın eşdeğerlerine yuvarlar. Bir örnek, modelin [0,1) aralığının üçe bölünmesini talep etmesi durumunda bunun nasıl çalışacağını gösterir ve bu, 8 bitlik bir hassasiyetle yaklaşık olarak hesaplanır. Şu andan itibaren kesinliğin bilindiğine dikkat edin, kullanabileceğimiz ikili aralıklar da öyle.

Yeniden normalleştirme adı verilen bir süreç , sonlu kesinliğin 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üşürüldüğünde, bu basamaklar çıkışa 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ğimizdeki üç durumdan ikisinde gerçekleştiğine dikkat edin.

Genelleştirilmiş bir sayı tabanı değişikliği olarak aritmetik kodlama

Sembollerin eşit olasılıklara sahip olduğu durumda, aritmetik kodlamanın basit bir taban veya taban değişikliği 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:

${\displaystyle \mathrm {DABDDB} }$

ilgili sembollerin sıralı bir küme oluşturduğunu ve sıralı kümedeki her sembolün sıralı bir tamsayı A = 0, B = 1, C = 2, D = 3 vb. gösterdiğini varsayarak belirli bir tabandaki bir sayı olarak. Bu, aşağıdaki frekanslar ve kümülatif frekanslarla sonuçlanır:

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 , sayı tabanı veya taban, sayıyı ifade etmek için kullanılan bir dizi farklı sembole sayısal olarak eşittir. Örneğin, ondalık sistemde simge sayısı 10'dur, yani 0, 1, 2, 3, 4, 5, 6, 7, 8 ve 9'dur. polinom formu. Örneğin, 457 sayısı aslında 4×10 ²  + 5×10 ¹  + 7×10 ^0'dır , burada 10 tabanı varsayılır ancak açıkça gösterilmez.

Başlangıçta, DABDDB'yi 6 tabanlı bir sayıya dönüştüreceğiz, çünkü 6 dizenin uzunluğudur. Dize ilk önce 301331 rakam dizisine eşlenir, bu daha sonra polinom tarafından bir tamsayıya eşlenir:

${\displaystyle 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 bitlik bir uzunluğa sahiptir .

Enformasyon teorisinin dayattığı teorik sınıra daha yakın uzunlukta bir mesajı kodlamak için, tabanı 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 terimi, daha önce meydana gelen tüm sembollerin frekanslarının çarpımı ile çarpıyoruz:

${\displaystyle {\begin{aligned}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\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{ 0}\times 1){}\\={}&25002\end{hizalı}}}$

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

${\displaystyle L=\sum _{i=1}^{n}n^{ni}C_{i}{\prod _{k=1}^{i-1}f_{k}}}$

nerede kümülatif frekanslar ve oluşumların frekansları. İndeksler, bir mesajdaki sembolün konumunu belirtir. Tüm frekansların 1 olduğu özel durumda , bu taban değişim formülüdür. ${\displaystyle \scriptstyle C_{i}}$${\displaystyle \scriptstyle f_{k}}$${\displaystyle \scriptstyle f_{k}}$

Ü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 şu şekilde verilir:

${\displaystyle U=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çim, mümkün olan en uzun sıfır izine sahip değer olan 25100'dür, çünkü sonucu 251×10 ² olarak temsil ederek sıkıştırma elde etmemizi sağlar . İletinin uzunluğu ayrı olarak saklanırsa, sıfırlar da 251 vererek kesilebilir. Daha uzun mesajlar daha uzun sıfır izlerine sahip olma eğiliminde olacaktır.

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

Kod çözme sırasında, karşılık gelen 6 kuvvetine böldükten sonra zemini alırız. Daha sonra sonuç, kümülatif aralıklarla eşleştirilir ve arama tablosundan uygun sembol seçilir. Sembol tanımlandığında sonuç düzeltilir. Mesajın bilinen uzunluğu boyunca veya kalan sonuç pozitif olduğu sürece işleme devam edilir. Klasik taban değişikliği ile karşılaştırıldığında tek fark, her bir sembolle ilişkili bir dizi değerin olabilmesidir. Bu örnekte A her zaman 0'dır, B 1 veya 2'dir ve D 3, 4, 5'ten herhangi biridir. Bu, frekanslar tarafından belirlenen aralıklarımızla tam olarak uyumludur. Tüm aralıklar 1'e eşit olduğunda, klasik taban değişikliğinin özel bir durumu vardır.

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

Alt sınır L hiçbir zaman n ⁿ değerini aşmaz , burada n mesajın boyutudur ve bu nedenle bit olarak gösterilebilir. U üst sınırının hesaplanmasından ve [ L ,  U ) aralığından en uzun sıfır izi ile bir sayı seçilerek mesajın indirgenmesinden sonra, bu uzunluğun bitlerle azaltılabileceğini varsayabiliriz . Bir çarpımdaki her frekans, bu frekansın değeriyle tam olarak aynı sayıda gerçekleştiğinden, çarpım hesaplaması için A alfabesinin boyutunu kullanabiliriz.${\displaystyle \scriptstyle \log _{2}(n^{n})\;=\;n\log _{2}(n)}$${\displaystyle \scriptstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\sağ)}$

${\displaystyle \prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}}$

Mesajdaki tahmini bit sayısı için log ₂ uygulandığında , son mesaj (mesaj uzunluğu ve frekans tabloları için logaritmik bir ek yükü saymaz), uzun mesajlar için optimale çok yakın olan entropi tarafından verilen bit sayısıyla eşleşir :

${\displaystyle -\sol[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\sağ]*n}$

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

Huffman kodlaması

Aritmetik kodlama bir seferde bir veriyi sıkıştırmadığından, iid dizgilerini sıkıştırırken keyfi olarak entropiye yaklaş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 (örneğin ({0, 1}) {0.95, 0.05} olasılıkları olsa bile) sıkıştırma mümkün değildir. Huffman kodlaması, her değere 1 bit atar ve girişle aynı uzunlukta bir kod verir. Buna karşılık, aritmetik kodlama, bitleri iyi sıkıştırır ve optimum sıkıştırma oranına yaklaşır.

${\displaystyle 1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\yaklaşık$

Huffman kodlamasının alt optimalliğini ele almanın basit bir yolu, her yeni sembolün orijinal alfabeden bir orijinal sembol dizisini - bu durumda bitleri - temsil ettiği yeni bir alfabe oluşturmak için sembolleri birleştirmektir ("engelleme"). Yukarıdaki örnekte, kodlamadan önce üç sembolün dizilerini gruplamak, aşağıdaki frekanslarda 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 gruplama ile, Huffman kodlaması, orijinal kodlamada, yani sıkıştırmada , sembol başına bir bit ile karşılaştırıldığında, her üç sembol için ortalama 1,3 bit veya sembol başına 0,433 bit alır . Rastgele büyük dizilere izin vermek, tıpkı aritmetik kodlama gibi, keyfi olarak entropiye yaklaşır, ancak bunu yapmak için çok büyük kodlar gerektirir, bu nedenle bu amaç için aritmetik kodlama kadar pratik değildir. ${\görüntüleme stili 56.7\%}$

Bir alternatif, çalışma uzunluklarını Huffman tabanlı Golomb-Rice kodları aracılığıyla kodlamaktır . Böyle bir yaklaşım, aritmetik kodlamaya ve hatta Huffman kodlamasına göre daha basit ve daha hızlı kodlama/kod çözme sağlar, çünkü ikincisi bir tablo araması gerektirir. {0.95, 0.05} örneğinde, dört bitlik kalanlı bir Golomb-Rice kodu, üç bitlik bloklar kullanmaktan optimuma çok daha yakın bir sıkıştırma oranı elde eder . Golomb-Rice kodları yalnızca bu örnekteki gibi Bernoulli girişleri için geçerlidir , bu nedenle her durumda engellemenin yerini tutmaz. ${\görüntüleme stili 71.1\%}$

Tarihçe ve patentler

Aritmetik kodlama için temel algoritmalar , IBM Research'ten Jorma J. Rissanen ve Ph.D. Richard C. Pasco tarafından bağımsız olarak geliştirildi . Stanford Üniversitesi'nde öğrenci ; her ikisi de Mayıs 1976'da yayınlandı. Pasco, Rissanen'in makalesinin bir yayın öncesi taslağını alıntılıyor ve eserleri arasındaki ilişki hakkında yorum yapıyor:

Ailenin bir algoritması bağımsız olarak Rissanen [1976] tarafından geliştirilmiştir. Toplama ve üs alma ile elde edilen bir işaretçi kullanarak kod öğesini akümülatörün en önemli ucuna kaydırır. Şimdi üç seçenekteki alternatifleri karşılaştıracağız ve akümülatör yerine kod öğesinin kaydırılmasının ve kod öğelerinin akümülatörün en az anlamlı ucuna eklenmesinin tercih edildiğini göreceğiz.

Yayınlanmasından bir yıldan kısa bir süre sonra IBM , Rissanen'in çalışmaları için bir ABD patenti için başvuruda bulundu . Pasco'nun çalışması patentli değildi.

Aritmetik kodlama için çeşitli özel teknikler, geçmişte ABD patentleri tarafından kapsanmıştır, ancak o zamandan beri, patentlerin süresi doldukça, iyi bilinen çeşitli yöntemler kamu alanına geçmiştir. Patentlerin kapsadığı teknikler, bazı resmi uluslararası standartlarda belirtilen aritmetik kodlama algoritmalarının uygulanması için gerekli olabilir. Durum böyle olduğunda, bu tür patentler genellikle "makul ve ayrımcı olmayan" ( RAND ) lisanslama koşulları (en azından standartlar-komite politikası açısından) olarak adlandırılan koşullar altında lisanslama için mevcuttur . Bazı iyi bilinen örneklerde (bazıları dahil olmak üzere süresi dolan IBM patentleri dahil), bu tür lisanslar ücretsiz olarak mevcuttu ve diğer durumlarda lisans ücretleri gerekliydi. RAND koşulları altında lisansların mevcudiyeti, teknolojiyi kullanmak isteyebilecek herkesi mutlaka tatmin etmeyebilir, çünkü özel bir ticari yazılım ürünü hazırlayan bir şirket için "makul" görünen şey, bir özgür yazılım veya açık kaynak projesi için çok daha az makul görünebilir .

En az bir önemli sıkıştırma yazılım programı, bzip2 , o sırada algılanan patent durumu nedeniyle Huffman kodlaması lehine aritmetik kodlamanın kullanımını kasıtlı olarak durdurdu. Ayrıca, hem Huffman kodlaması hem de aritmetik kodlaması için seçeneklere sahip olan JPEG dosya formatının kodlayıcıları ve kod çözücüleri , orijinal olarak patent endişeleri nedeniyle yalnızca Huffman kodlama seçeneğini destekler; sonuç, JPEG'in aritmetik kodlama patentlerinin süresi, JPEG standardının (tasarımı yaklaşık olarak 1990'da tamamlanmış olan) yaşı nedeniyle sona ermiş olmasına rağmen, bugün kullanılan hemen hemen tüm JPEG resimlerinin Huffman kodlamasını kullanmasıdır. JPEG XL ve PackJPG, Brunsli ve Lepton gibi arşivleyiciler, Huffman tarafından kodlanmış dosyaları kayıpsız bir şekilde aritmetik kodlamaya (veya JPEG XL durumunda asimetrik sayı sistemlerine ) sahip dosyalara dönüştürerek %25'e varan boyut tasarrufu sağlar.

JPEG görüntü sıkıştırma formatının aritmetik kodlama algoritması, aşağıda belirtilen patentlere dayanmaktadır (süresi dolduğundan beri).

• ABD Patenti 4,652,856 – ( IBM ) 4 Şubat 1986'da dosyalandı, 24 Mart 1987'de verildi – Kottappuram MA Mohiuddin, Jorma Johannen Rissanen – Çarpma gerektirmeyen çok alfabeli aritmetik kodu
• ABD Patenti 4,905,297 – (IBM) 18 Kasım 1988'de dosyalandı, 27 Şubat 1990'da verildi – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannen Rissanen – Aritmetik kodlama kodlayıcı ve kod çözücü sistemi
• ABD Patenti 4,935,882 – (IBM) 20 Temmuz 1988'de dosyalandı, 19 Haziran 1990'da 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'da verildi – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Kodlama sistemi
• JP Patent 2-46275 – (Mitsubishi) 26 Şubat 1990'da dosyalandı, 5 Kasım 1991'de verildi – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Kodlama aparatı ve kodlama yöntemi

Aritmetik kodlamayla ilgili diğer patentler (çoğunlukla süresi dolmuştur) aşağıdakileri içerir.

• ABD Patenti 4,122,440 – (IBM) 4 Mart 1977'de dosyalandı, 24 Ekim 1978'de verildi – Glen George Langdon, Jorma Johannen Rissanen – Aritmetik dizi kodlama için yöntem ve araçlar
• ABD Patenti 4,286,256 – (IBM) 28 Kasım 1979'da dosyalandı, 25 Ağustos 1981'de verildi – Glen George Langdon, Jorma Johannen Rissanen – Az sayıda işlem kullanan aritmetik kodlama için yöntem ve araçlar
• ABD Patenti 4,467,317 – (IBM) 30 Mart 1981'de dosyalandı, 21 Ağustos 1984'te verildi – Glen George Langdon, Jorma Johannen Rissanen – Eşzamanlı değer güncellemesini kullanan 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'da verildi – Joan L. Mitchell, William B. Pennebaker – Seçici olarak kullanılan, çeşitli aritmetik kodlama kodlayıcıları ve kod çözücüleri tarafından aritmetik kodlama veri sıkıştırma/açma
• JP Patent 11782787 – ( NEC ) 13 Mayıs 1987'de dosyalandı, 18 Kasım 1988'de verildi – Michio Shimada – Veri sıkıştırma aritmetik kodlama cihazı
• JP Patent 15015487 – ( KDDI ) 18 Haziran 1987'de dosyalandı, 22 Aralık 1988'de 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'da verildi – William B. Pennebaker, Joan L. Mitchell – Aritmetik kodlayıcılar için olasılık uyarlaması
• ABD Patenti 4,989,000 – (IBM) 19 Haziran 1989'da dosyalandı, 29 Ocak 1991'de verildi – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Basitleştirilmiş olasılık alt aralık tahmini ile aritmetik kodlamayı kullanan veri dizisi sıkıştırma
• ABD Patenti 5.099.440 – (IBM) 5 Ocak 1990'da dosyalandı, 24 Mart 1992'de 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'te verildi – James D. Allen – Entropi kodlaması için yöntem ve aygıt

Not: Bu liste ayrıntılı değildir. Diğer ABD patentlerinin listesi için aşağıdaki bağlantılara bakın. Dirac kodek aritmetik kodlama kullanır ve patentli değildir.

Aritmetik kodlamaya ilişkin patentler diğer yargı alanlarında bulunabilir; dünya çapında yazılımın patentlenebilirliğine ilişkin bir tartışma için yazılım patentlerine bakın .

Karşılaştırmalar ve diğer teknik özellikler

Aritmetik kodlamanın her programatik uygulamasının farklı bir sıkıştırma oranı ve performansı vardır. Sıkıştırma oranları çok az değişirken (genellikle %1'in altında), kod yürütme süresi 10 kat değişebilir. Herkese açık kodlayıcılar listesinden doğru kodlayıcıyı seçmek basit bir iş değildir çünkü performans ve sıkıştırma oranı da buna bağlıdır. veri türü, özellikle alfabenin boyutu (farklı sembollerin sayısı). Belirli iki kodlayıcıdan biri küçük alfabeler için daha iyi performans gösterirken diğeri büyük alfabeler için daha iyi performans gösterebilir. Çoğu kodlayıcının alfabenin boyutuyla ilgili sınırlamaları vardır ve bunların çoğu tam olarak iki sembolden (0 ve 1) oluşan alfabeler için uzmanlaşmıştır.

Ayrıca bakınız

• Asimetrik sayı sistemleri
• Bağlama-uyarlamalı ikili aritmetik kodlama (CABAC)
• Veri sıkıştırma
• entropi kodlaması
• Huffman kodlaması
• Aralık kodlaması

Notlar

Referanslar

• MacKay, David JC (Eylül 2003). "Bölüm 6: Akış Kodları" . Bilgi Teorisi, Çıkarım ve Öğrenme Algoritmaları . Cambridge Üniversitesi Yayınları . ISBN'si 0-521-64298-1. Orijinalinden (PDF/ PostScript / DjVu / LaTeX ) 22 Aralık 2007'de arşivlendi . 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 University Press. ISBN'si 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 İletişimi . 30 (6): 520–540. doi : 10.1145/214762.214771 . 28 Eylül 2007'de orijinalinden arşivlendi (PDF) . Erişim tarihi: 21 Eylül 2007 .

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

Dış bağlantılar

•  Bu makale  ,  NIST belgesinden kamu malı materyali içermektedir :  Black, Paul E. "aritmetik kodlama" . Algoritmalar ve Veri Yapıları Sözlüğü .
• Kısa çalışılmış bir aritmetik kodlama örneği içeren haber grubu gönderisi (yalnızca tamsayı).
• Aritmetik kodlama üzerine PlanetMath makalesi
• Aralık Kodlayıcının Anatomisi Bu makale hem aralık hem de aritmetik kodlamayı açıklar. Ayrıca performans karşılaştırması ile birlikte 3 farklı aritmetik kodlayıcı için kod örneklerine sahiptir.
• Aritmetik Kodlamaya Giriş . 60 sayfa.
• Eric Bodden, Malte Clasen ve Joachim Kneis: Aritmetik Kodlama ortaya çıktı . Teknik Rapor 2007-5, Sable Araştırma Grubu, McGill Üniversitesi.
• Aritmetik Kodlama + İstatistiksel Modelleme = Mark Nelson'dan Veri Sıkıştırma .
• Aritmetik Kodlama ile Veri Sıkıştırma , Mark Nelson (2014)
• James K. Bonfield tarafından menzil kodlaması ve rANS'ın hızlı uygulanması