Çoğu bit eşlem dosya biçimi tarafından desteklenen veriler: TIFF, BMP ve PCX. RLE, içeriği ne olursa olsun her tür veriyi sıkıştırmak için uygundur, ancak verinin içeriği sıkıştırma oranını etkiler. Çoğu RLE algoritması, daha karmaşık yöntemlerin yüksek sıkıştırma oranlarını sağlayamasa da, aracın uygulanması kolay ve yürütülmesi hızlıdır, bu da onu iyi bir alternatif haline getirir.

RLE sıkıştırma algoritması neye dayanır?

RLE, tekrarlanan bir karakter dizisinin fiziksel boyutunu küçülterek çalışır. Run adı verilen bu dize genellikle iki bayt olarak kodlanır. İlk bayt, çalıştırmadaki karakter sayısını temsil eder ve çalıştırma sayacı olarak adlandırılır. Pratikte, kodlanmış bir çalıştırma 1 ila 128 ve 256 karakter arasında olabilir. Sayaç genellikle eksi bir karakter sayısını içerir (0 ile 127 ve 255 arasındaki değerler aralığında bir değer). İkinci bayt, 0 ile 255 arasında değişen ve tetik değeri olarak adlandırılan çalıştırma karakteri değeridir.

Sıkıştırma olmadan, 15 karakterlik bir karakter çalıştırması tipik olarak aşağıdakileri depolamak için 15 bayt gerektirir:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAte

Aynı satırda, RLE kodlamasından sonra sadece iki bayt gereklidir: 15A.

Bir karakter dizisini temsil etmek için oluşturulan 15A kodlamasına RLE paketi denir. Bu kodda, ilk bayt 15, çalıştırma sayacıdır ve gerekli sayıda tekrarı içerir. İkinci bayt A, çalıştırma değeridir ve çalıştırmada tekrarlanan gerçek değeri içerir.

Başlangıç ​​karakteri her değiştirildiğinde veya çalıştırmadaki karakter sayısı maksimum sayıyı her aştığında yeni bir paket oluşturulur. 15 karakterlik dizenin koşullara göre 4 farklı karakter içerdiğini varsayalım:

Dize uzunluğu kodlamasını kullanarak dört çift baytlık pakete sıkıştırılabilir:

Dize uzunluğuna kodlandıktan sonra, 15 baytlık bir dize, orijinal 15 baytın aksine dizeyi temsil etmek için yalnızca sekiz bayt veri gerektirir. Bu durumda, çalışma zamanı kodlaması, neredeyse 2'ye 1'lik bir sıkıştırma oranı verdi.

özellikler

Bazı veri türlerinde uzun çalıştırmalar nadirdir. Örneğin, ASCII düz metni nadiren uzun koşular içerir. Önceki örnekte, son çalıştırma (t karakterini içeren) yalnızca bir karakter uzunluğundaydı. 1 karakter çalıştırması hala çalışıyor. Her 2 karakterlik çalışma için hem tetikleme sayısı hem de tetikleme değeri kaydedilmelidir. RLE algoritmasını kullanarak bir kilometreyi kodlamak için en az iki karakterlik bilgi gereklidir. Bu nedenle, tek karakterleri başlatmak aslında daha fazla yer kaplar. Aynı nedenlerle, tamamen 2 karakterli çalışmalardan oluşan veriler, RLE kodlamasından sonra değişmeden kalır.

RLE sıkıştırma şemalarının yürütülmesi basit ve hızlıdır, ancak performansları kodlanan görüntü verisinin türüne bağlıdır. Kitap sayfaları gibi çoğunlukla beyaz olan siyah beyaz bir görüntü, aynı renge sahip büyük miktarda bitişik veri nedeniyle çok iyi kodlanacaktır. Ancak, fotoğraf gibi birçok renge sahip bir görüntü de kodlanmayacaktır. Bunun nedeni, bir görüntünün karmaşıklığının çok sayıda farklı renk biçiminde ifade edilmesidir. Ve bu karmaşıklık nedeniyle, aynı rengin nispeten az sayıda çalışması olacaktır.

Uzunluk kodlama seçenekleri

Çalışma zamanında kodlama için birkaç seçenek vardır. Görüntü verileri tipik olarak, görsel içeriği 2B veri haritasından ziyade 1B akış olarak ele alan sıralı bir süreçte kodlanır. Sıralı işlemede, bitmap, sol üst köşeden başlayarak kodlanır ve her tarama çizgisi boyunca soldan sağa, bitmap'in sağ alt köşesine yönlendirilir. Ancak alternatif RLE şemaları, 2B döşemelere sıkıştırmak için sütunlar boyunca bitmap uzunluk verilerini kodlamak veya hatta pikselleri zikzak biçiminde çapraz olarak kodlamak için de yazılabilir. RLE'nin tuhaf varyantları son derece özel uygulamalarda kullanılabilir, ancak genellikle oldukça nadirdir.

Çalışma uzunluğu hata kodlama algoritması

Diğer bir nadir seçenek, çalışma uzunluğu hatası RLE kodlama algoritmasıdır. Bu araçlar genellikle kayıpsız sıkıştırma gerçekleştirir, ancak kodlama işlemi sırasında, genellikle her pikselde en az bir veya iki en az anlamlı biti sıfırlayarak verileri atmak, karmaşık görüntülerin kalitesini olumsuz etkilemeden sıkıştırma oranlarını artırabilir. Bu RLE algoritma programı, yalnızca piksel değerlerinde pek çok ince değişiklik içeren gerçek dünya görüntüleri ile iyi çalışır.

çapraz kodlama

Çapraz kodlama, sıkıştırma işlemi orijinal çizgiler arasındaki ayrımı kaybettiğinde ortaya çıkan tarama çizgilerinin birleştirilmesidir. Tek tek hatlardan gelen veriler RLE hayalet kodlama algoritması ile birleştirildiğinde, bir tarama hattının durdurulduğu ve diğerinin kaybolduğu nokta savunmasızdır ve tespit edilmesi zordur.

Bazen, kod çözme sürecini karmaşıklaştıran ve zaman içinde maliyet ekleyen çapraz kodlama meydana gelir. Bitmap dosya biçimleri için bu yöntem, bitmap'i tarama çizgileri boyunca düzenlemeyi amaçlar. Birçok dosya formatı belirtimi, bu satırların ayrı ayrı kodlanması gerektiğini açıkça belirtse de, birçok uygulama bu görüntüleri satır sınırlarını göz ardı ederek sürekli bir akış olarak kodlar.

RLE algoritmasını kullanarak bir görüntü nasıl kodlanır?

Uygulamanın görüntünün yalnızca bir bölümünü kullanması gerektiğinde, tarama satırlarının bireysel olarak kodlanması avantajlıdır. Fotoğrafın 512 tarama çizgisi içerdiğini ve yalnızca 100 ila 110 arasındaki satırların görüntülenmesi gerektiğini varsayalım.Tarama satırlarının kodlanmış görüntü verileriyle nerede başlayıp nerede bittiğini bilmeseydik, uygulamamız on satır bulmadan önce 1'den 100'e kadar olan satırların kodunu çözmek zorunda kalacaktı. bunlar gerekli. Tarama çizgileri arasındaki geçişler, kolayca tanınabilir bir sınır işaretiyle işaretlenmiş olsaydı, uygulama istediği hatlara ulaşana kadar işaretçileri sayarak kodlanmış verileri okuyabilirdi. Ancak bu yaklaşım oldukça etkisiz olacaktır.

Alternatif seçenek

Kodlanmış bir veri bloğundaki herhangi bir belirli tarama çizgisinin başlangıç ​​noktasını belirlemek için başka bir seçenek, bir tarama çizgisi tablosu oluşturmaktır. Bu tablo yapısı tipik olarak görüntüdeki her tarama çizgisi için bir giriş içerir ve her giriş, karşılık gelen tarama çizgisinin ofset değerini içerir. Tarama satırı 10'un ilk RLE paketini bulmak için kod çözücünün tek yapması gereken, onuncu tarama satırı arama tablosu girişinde depolanan ofset konum değerlerini bulmaktır. Tarama satırı tablosu, her satırı kodlamak için kullanılan bayt sayısını da içerebilir. 10. tarama satırının ilk RLE paketini bulmak için bu yöntemi kullanarak, kod çözücünüz tarama satırı tablosunun ilk 9 öğesinin değerlerini birleştirecektir. Tarama hattı 10 için ilk paket, RLE şifreli görüntü verisinin başlangıcından itibaren bu bayt ofsetinde başlayacaktır.

Birimler

Uzunluk kodlama algoritmalarının farklı olan kısımları, kodu çözülmekte olan veri türüne (örneğin, verilerin çalışma uzunluğu) dayalı olarak verilen kararlardır. Bit eşlem grafiklerini sıkıştırmak için kullanılan RLE şemaları, genellikle kodladıkları atomik (yani en temel) öğelerin türüne göre kategorilere ayrılır. Çoğu grafik dosya formatı tarafından kullanılan üç sınıf, bit, bayt ve piksel RLE'dir.

Sıkıştırma kalitesi

RLE devrelerinin bit seviyeleri, bir tarama satırındaki çoklu bit çalışmalarını kodlar ve bayt ve kelime sınırlarını yok sayar. Yalnızca monokrom (siyah beyaz), 1 bitlik görüntüler, bu sınıf RLE kodlamasını verimli kılmak için yeterli bit içerir. Tipik bir RLE bit düzeyi şeması, tek baytlık bir pakette bir ila 128 bit arasında kodlar. En önemsiz yedi bit, tetik sayısı eksi bir içerir ve en anlamlı bit, 0 veya 1 bit çalıştırma değerini içerir. 128 pikselden uzun bir çalıştırma, birden çok RLE kodlu pakete bölünür.

istisnalar

Bayt düzeyindeki RLE şemaları, tarama satırındaki bazı bitleri ve sözcük sınırlarını göz ardı ederek aynı bayt değerlerinin çalışmalarını kodlar. Bayt düzeyindeki en yaygın RLE şeması, bayt şeritlerini 2 baytlık paketler halinde kodlar. İlk bayt, 0 ile 255 arasında bir sayaç içerir ve ikincisi, tetikleyici bayt değerini içerir. İki baytlık bir kodlama şemasını, kodlanmış veri akışında değişmez, yazılmamış bayt çalıştırmalarını saklama yeteneğiyle desteklemek de yaygındır.

Böyle bir şemada, ilk baytın en az anlamlı yedi biti, çalıştırma sayısı eksi bir içerir ve ilk baytın en anlamlı biti, çalıştırma sayısı baytını izleyen tetik tipi göstergesidir. En anlamlı bit 1 olarak ayarlanmışsa, kodlanmış bir çalıştırmayı belirtir. Şifreli koşuların kodu, kilometre değeri okunarak ve döngü sayısıyla belirtilen sayıda tekrarlanarak çözülür. En anlamlı bit 0'a ayarlanırsa, bir hazır sayım görüntülenir; bu, bir sonraki çalıştırma sayım baytlarının, kodlanmış resim verilerinden tam anlamıyla okunduğu anlamına gelir. Yürütme sayacı baytı 0 ila 127 aralığında bir değer içerir (başlangıç ​​sayacı eksi bir). Bayt düzeyinde RLE şemaları, piksel başına bir bayt olarak depolanan görüntü verileri için iyidir.

Piksel düzeyinde RLE şemaları, bir pikselin değerlerini depolamak için iki veya daha fazla ardışık bayt görüntü verisi kullanıldığında kullanılır. Piksel düzeyinde, bitler yok sayılır ve her piksel değerini tanımlamak için baytlar sayılır. Kodlanmış paketlerin boyutu, kodlanmış piksel değerlerinin boyutuna bağlıdır. Piksel başına bit veya bayt sayısı, görüntü dosyasının başlığında saklanır. 3 baytlık piksel değerleri olarak saklanan görüntü verilerinin başlangıcı, bir işlem sayısı baytı ve ardından üç bayt bayt ile 4 baytlık bir pakete kodlanır. Kodlama yöntemi, bayt RLE ile aynı kalır.

10-15 yıl önce bile, arşivleyiciler esas olarak sabit disklerde yer kazanmak ve bir diskete maksimum miktarda veri sığdırmak için kullanılıyordu. Ancak, zaman değişti. Uzun süredir kimse disketleri bilgi aktarma ve depolama aracı olarak kullanmıyor ve sürücülerin maliyeti o kadar düşük hale geldi ki, hiç kimse yerden tasarruf etmek için verileri sıkıştırmayı düşünmedi bile. Ek olarak, veri hacimleri o kadar büyük hale geldi ki, yer kazanmak için onları arşivlemek ve arşivden çıkarmak çok zaman aldığından pratik değil. Gerçekten de, bugün kullanıcıların sürücülerindeki veri miktarı terabayt cinsinden ölçülmektedir. Şimdi bir terabaytlık veriyi arşivlemenin ne kadar süreceğini hayal edin. Bir hatta iki saat bile sürmez, ancak en az 10-12 saat, yani bilgisayarın bütün gece açık bırakılması gerekecek.

Görünüşe göre bugün arşivciler ilgilerini kademeli olarak kaybedecek. Ama öyle bir şey olmuyor. Diğer programların yanı sıra, kullanıcıların büyük çoğunluğunda arşivleyiciler kuruludur veya Windows işletim sisteminde yerleşik olarak bulunan arşivleyiciyi kullanırlar (bu yayında diğer işletim sistemlerini dikkate almıyoruz).

Gerçek şu ki, arşivleyicilerin amacı değişti. Bugün öncelikle Web'e veri yüklemek için kullanılıyorlar. Üreticilerin web sitelerindeki sürücülerin çoğu arşivlerde düzenlenmiştir ve çeşitli kaynaklardaki programların çoğu da arşivlenmiştir. Bu arada, kullanıcının kendisi, Ağa herhangi bir veri yüklemeden önce (örneğin, dosya paylaşım kaynaklarına), verileri bir arşive paketler.

Rusya pazarına gelince, en yaygın üç arşivleyicimiz vardır: WinRAR, WinZip ve 7-Zip, hem 32 hem de 64 bit sürümlerinde sunulur. Bu yazıda onları karşılaştıracağız. Ancak, önce arşivcilerin çalışmalarının bazı teorik yönlerini kısaca ele alacağız.

Bilgi sıkıştırma algoritmaları

Herhangi bir bilgi sıkıştırma algoritmasının özü, çıktıda, ilk bilgi bitleri setinin bir miktar dönüştürülmesiyle, belirli bir daha küçük boyutlu setin elde edilmesi gerçeğinde yatmaktadır. Ayrıca, tüm veri dönüştürme algoritmaları koşullu olarak iki sınıfa ayrılabilir: tersinir ve geri döndürülemez.

Tersine çevrilemez bir bilgi sıkıştırma algoritması, orijinal bit dizisinin, daha küçük boyutlu çıktı dizisinin giriş dizisinin doğru bir şekilde yeniden oluşturulmasına izin vermediği böyle bir dönüşümü anlamına gelir. Örneğin grafik, video ve ses verileriyle ilgili olarak geri dönüşü olmayan sıkıştırma algoritmaları kullanılır ve bu her zaman kalite kaybına yol açar. Doğal olarak, arşivleyicilerde geri dönüşü olmayan veri sıkıştırma algoritmaları kullanılmaz ve bu nedenle gelecekte bunları dikkate almayacağız.

Tersine çevrilebilir veri sıkıştırma algoritmaları, sıkıştırılmış diziden orijinal veri dizisini doğru bir şekilde yeniden oluşturmanıza olanak tanır. Arşivleyicilerde kullanılan bu algoritmalardır. Tüm sıkıştırma algoritmalarının ortak özellikleri, sıkıştırma oranı (orijinal ve sıkıştırılmış veri dizisinin hacimlerinin oranı), sıkıştırma oranı (belirli bir miktarda veriyi arşivlemek için geçen süre) ve sıkıştırma kalitesidir (sıkıştırılan değerdir). aynı veya farklı bir algoritmaya göre yeniden sıkıştırma uygulayarak veri dizisinin ne kadar sıkıştırıldığını gösterir).

Ayrık bilgilerin ekonomik kodlama teorisi olarak da bilinen bilgi sıkıştırma teorisi, matematik biliminin oldukça karmaşık bir dalıdır. Tabii ki, temellerinin sunumu bile bu makalenin kapsamının çok ötesine geçiyor ve bu nedenle, ayrıntılara girmeden çeşitli bilgi sıkıştırma algoritmalarını yalnızca yüzeysel olarak ele alacağız. Ayrıca günümüzde birçok veri sıkıştırma algoritması geliştirilmiştir ve bunların dikkate alınması da görevimize dahil edilmiştir. Bu nedenle, bilgi sıkıştırma yöntemleri hakkında genel bir fikir edinmenize izin veren birkaç algoritma hakkında yalnızca niteliksel düzeyde konuşacağız.

RLE algoritması

En eski ve en basit bilgi sıkıştırma yöntemlerinden biri, bir dizi diziyi kodlamak için bir algoritma olan RLE (Run Length Encoding) algoritmasıdır. Bu yöntemin uygulanması çok basittir ve arşivleme algoritmalarından biridir ve özü, bir dizi tekrarlanan bayt (grubu) bir kodlama baytı ve tekrarlarının sayısının bir sayacı ile değiştirmektir. Yani, bir grup özdeş bayt bir çift ile değiştirilecektir:<счетчик повторений, значение>, bu da veri fazlalığını azaltır.

Bu algoritmada sayaç, okunan baytın üst iki bitinde bulunanlarla gösterilir. Örneğin, ilk iki bit 11 ise, kalan 6 bit 1'den 64'e kadar değerler alabilen bir sayaca atanır. Buna göre, sadece iki bayt ile 64 tekrarlanan baytlık bir dizi belirlenebilir, yani 32 kez sıkıştırılmıştır.

Sayacın ilk baytında sayaç özniteliği 1 olduğunda, bu algoritmanın uygulanmasının başka bir çeşidi vardır. Bu durumda sayaç maksimum 127 değerini alabilir ve bu nedenle maksimum sıkıştırma oranı 64 olacaktır.

RLE algoritmasının yalnızca çok sayıda aynı bayttan oluşan uzun gruplar olduğunda etkili olduğu açıktır. Baytlar tekrarlanmazsa, RLE yönteminin kullanılması dosya boyutunu artırır.

RLE genellikle bitmap grafiklerini (BMP, PCX, TIF, GIF) sıkıştırmak için çok etkilidir çünkü bunlar çok sayıda tekrarlayan bayt dizisi içerirler.

Bilgi alfabesinin kısıtlanması

Bilgileri sıkıştırmanın oldukça basit bir yöntemi, bilgi alfabesini sınırlama olarak adlandırılabilir. Hemen not edelim ki böyle bir algoritma pratikte uygulanmamıştır ancak bu yöntemin sunumu değişken uzunluklu kodlar yönteminin daha iyi anlaşılmasına yardımcı olacaktır.

Aşağıda, bilgi alfabesi altında, bilgi dizisini kodlamak için kullanılan karakter kümesini kastediyoruz. Örneğin, bir metin mesajı olduğunu varsayalım. Bu mesajın her harfini kodlamak için 256 karakterlik bir ASCII tablosu kullanılır. Bu durumda, her karakterin kodlanması için tam olarak 8 bit (1 bayt) tahsis edilir. Bu durumda, bilgi alfabesi, ASCII kodlama tablosunun 256 karakterinin tamamıdır.

ASCII tablosunun 256 karakterinin tamamının orijinal metin mesajında ​​kullanılamayacağı açıktır. Örneğin, içinde sayı olmayan Rusça bir metin mesajından bahsediyorsak, 64 karakter yeterlidir (33 küçük harf ve 31 büyük harf). Buna noktalama işaretleri, paragraf işaretleri ve yeni satırlar eklerseniz, karakter sayısının 100'ü geçmeyeceği anlaşılır. Bu durumda, 8- değil 7-bit karakter kodlamasını kullanabilirsiniz, bu da bir 128 karakterlik tablo. Yani, sıralanacak her karakterin bit derinliğini azaltabildiğimiz için bilgi alfabesini bir şekilde sınırlandırıyoruz. Daha ileri gidebilirsiniz - bir metin mesajında ​​kullanılan karakter sayısını doğru bir şekilde belirlemek için. Örneğin, mesaja yalnızca 30 karakterin dahil olduğu ortaya çıkarsa (yeni satır karakterleri dahil), 32 karakter içeren 5 bitlik bir kodlama tablosu kullanabilirsiniz ve ardından metin mesajının sıkıştırma oranı daha da artacaktır. . Aslında, orijinal mesaj 8 bit karakter kodlaması kullanıyorsa ve sıkıştırılmış olan 5 bit kullanıyorsa, sıkıştırma oranı 8/5 olacaktır.

Alfabeyi sınırlama yönteminin görünen basitliğine rağmen, pratikte kullanılmamaktadır. Buradaki nokta, açıklanan yöntemin, ek bilgi aktarmadan orijinal mesajın doğru bir şekilde kodunun çözülmesine izin vermemesidir. Gerçekten de, bilgileri sıkıştırmak için kullanılan kodlama tablolarını bilmeden, kodunu çözmek imkansızdır. Yani, kodlanmış bilgi dizisi ile birlikte kodlama tablolarının iletilmesi gerekir. Bu durumda, sınırlı bir alfabe kullanmanın faydasının sıfıra indirgendiği açıktır.

Sınırlı alfabe yönteminin başka dezavantajları da vardır. Orijinal bilgi mesajı çok sayıda farklı karakter içeriyorsa, alfabe karakterlerinin rakam kapasitesini düşürmek mümkün olmayacak ve bu yöntem işe yaramayacaktır. Örneğin, orijinal veri mesajının 256 karakterlik bir alfabeden 129 karakter içerdiğini varsayalım. 7 bit sadece 128 karakterin kodlanmasına izin vereceğinden, bu durumda 7 bit karakter kodlaması kullanmak mümkün olmayacaktır. Bu nedenle, 129 karakter için orijinal 256 karakterlik alfabedekiyle aynı 8 bit kodlamaya geri dönmeniz gerekecektir.

Değişken uzunluk kodları

Alfabeyi sınırlayan varsayımsal yöntemin ana dezavantajlarından biri, bilgi alfabesinin tüm sembolleri aynı uzunlukta (8, 7 bit veya daha az) olduğunda tek tip bir kod kullanmasıdır. Karakter kodunun uzunluğunun bilgi mesajında ​​bulunma sıklığına bağlı olduğu böyle bir kodlama sistemi kullanmak daha mantıklı olacaktır. Yani, orijinal bilgi mesajında ​​bazı karakterler diğerlerinden daha sık bulunursa, onlar için kısa kodlar ve nadir olanlar için daha uzun kodlar kullanmak en uygunudur.

Varsayımsal bir örnek olarak, aşağıdaki bilgi mesajını göz önünde bulundurun: "Uçak kazası" hangi 14 karakter içerir. Bu mesajı kodlamamıza izin veren 14 karakterlik bir alfabemiz olduğunu varsayalım. Tek tip bir kod kullanılıyorsa, alfabenin her karakteri için 4 bit gerekir (4 bitlik bir kod uzunluğu 16 karakter oluşturmayı mümkün kılar). Bununla birlikte, bilgi mesajımızda "a" sembolünün beş kez, "t" sembolünün - iki kez ve sembollerin geri kalanının - bir kez geçtiğini görmek kolaydır. "A" karakteri için 2 bit uzunluğunda, "t" karakteri için - 3 bit uzunluğunda ve kalan karakterler için - 4 bit uzunluğunda bir kod kullanırsak, kesinlikle paradan tasarruf edebiliriz. Yalnızca değişken uzunluktaki kodların tam olarak nasıl oluşturulacağını ve kodun uzunluğunun, bilgi mesajındaki sembolün görünme sıklığına tam olarak nasıl bağlı olması gerektiğini anlamak gerekir.

Tüm karakterler bilgi mesajını aynı sıklıkta girerse (eşit olası), o zaman her karakteri kodlamak için N karakterlik bir bilgi alfabesiyle, tam olarak log 2 n biraz. Aslında, bu tek tip bir kodun durumudur.

Bir bilgi mesajında ​​sembollerin farklı oluşma olasılıkları varsa, o zaman K. Shannon'un teorisine göre, oluşma olasılığı p'ye eşit olan bir sembol optimaldir ve özellikle önemli olan, bir uzunluk kodunun ilişkilendirilmesine teorik olarak izin verilir. -günlük 2 P... "Uçak kazası" bilgi mesajıyla örneğimize dönersek ve "a" (p(a)) sembolünün ortaya çıkma olasılığının 5/14 olduğunu düşünürsek, "t" sembolünün ortaya çıkma olasılığı 2'dir. /14 ve diğer tüm sembollerin ortaya çıkma olasılığı 1 / 14'tür, şunu elde ederiz: "a" karakteri için en uygun kod uzunluğu –log 2 (5/14) = 1.48 bit; "t" sembolü için - –log 2 (2/14) = 2,8 bit ve diğer tüm semboller için –log 2 (1/14) = 3,8'dir. Bizim durumumuzda kodun uzunluğu yalnızca bir tamsayı değerine sahip olabileceğinden, yuvarlama, "a" karakteri için "t" karakteri için 2 bit uzunluğunda bir kod kullanmanın en uygun olduğunu elde ederiz. - 3 bitlik bir uzunluk ve geri kalanı için - 4 bitlik bir uzunluk.

Bu kodlamayı kullanırken sıkıştırma oranını hesaplayalım. 14 karakterlik bir alfabeye dayalı tek tip bir kod kullanılmışsa, "uçak kazası" kelimesini kodlamak için 56 bit gerekli olacaktır. Değişken uzunluklu kodlar kullanılırken 5 × 2 bit + 2 × 3 bit + 7 × 4 bit = 44 bit gereklidir, bu nedenle sıkıştırma oranı 1.27'dir.

Şimdi değişken uzunluklu kodlar elde etmek için algoritmalara bakalım.

önek kodlaması

Değişken uzunluklu kodlar elde etmenin en basit yöntemi, tamsayı uzunluklu kodlar elde etmenizi sağlayan ön ek kodlamadır. Ön ek kodlarının ana özelliği, sistemlerinin her birinde, uzunluk olarak daha kısa kodların, daha uzun kodların başlangıcı (ön eki) ile çakışmamasıdır. Bilgilerin kodunun çözülmesini çok kolaylaştıran önek kodlarının bu özelliğidir.

Ön ek kodlarının bu özelliğini özel bir örnekle açıklayalım. Üç ön kodlu bir sistem olsun: (0, 10, 11). Gördüğünüz gibi, daha kısa kod 0, daha uzun kodlar 10 ve 11'in başlangıcıyla örtüşmez. 0 kodunun "a" karakterini, kod 10 - "m" karakterini ve kod 11 - " karakterini belirtmesine izin verin. P". Daha sonra "frame" kelimesi 110100 dizisi ile kodlanır. Bu dizinin kodunu çözmeye çalışalım. İlk bit 1 olduğundan, ilk karakter sadece "m" veya "p" olabilir ve ikinci bitin değeri ile belirlenir. İkinci bit 1 olduğundan, ilk karakter "p" dir. Üçüncü bit 0'dır ve "a" karakteriyle benzersiz bir şekilde eşleşir. Dördüncü bit 1'dir, yani bir sonraki bitin 0 olan değerine bakmanız gerekir, ardından üçüncü karakter "m" olur. Son bit, benzersiz olarak "a" karakterine karşılık gelen 0'dır. Böylece önek kodlarının, daha kısa kodların daha uzun kodların başlangıcıyla örtüşmemesi özelliği, değişken uzunluklu önek kodlarıyla kodlanmış bir bilgi mesajının açık bir şekilde kodunun çözülmesini mümkün kılar.

Önek kodları genellikle (bir ikili sistem için) kod ağaçları oluşturularak elde edilir. Böyle bir ikili ağacın her bir iç düğümü, bir kenarı "0" ikili karakterine ve diğeri - "1"e karşılık gelen iki giden kenara sahiptir. Kesinlik için, sol kenarın "0" sembolü ve sağ kenarın - "1" sembolü ile ilişkilendirilmesi gerektiği konusunda hemfikir olabiliriz.

Ağaçta döngü olamayacağı için, kök düğümden yaprak düğüme her zaman tek bir rota oluşturabilirsiniz. Ağacın kenarları numaralandırılmışsa, bu tür yolların her biri benzersiz bir ikili diziye karşılık gelir. Tüm bu dizilerin kümesi bir önek kod sistemi oluşturacaktır.

"a", "m" ve "p" sembollerini tanımlayan üç önek kodundan oluşan bir sistem örneği için: (0, 10, 11), kod ağacı Şek. 1.

Pirinç. 1. Sistem için kod ağacı
üç önek kodundan: (0, 10, 11)

Önek kodlarının ağaç benzeri temsilinin uygunluğu, önek kodlarının ana koşulunu, yani daha kısa kodların ön ekini oluşturan koşulu karşılayan değişken uzunlukta kodlar üretmeyi mümkün kılan ağaç benzeri yapı olduğu gerçeğinde yatmaktadır. daha uzun kodların başlangıcı ile çakışmaz.

Şimdiye kadar sadece değişken uzunluklu önek kodları fikrine baktık. Ön ek kodlarını elde etme algoritmalarına gelince, bunlardan birkaçı var, ancak en ünlüsü iki yöntem: Shannon-Fano ve Huffman.

Shannon-Fano algoritması

Önek kodlarını elde etmek için bu algoritma bağımsız olarak R. Fano ve K. Shannon tarafından önerildi, aşağıdakilerden oluşuyor. İlk adımda, orijinal bilgi dizisinin tüm sembolleri, görünümlerinin azalan veya artan olasılıklarına (görünüşlerinin sıklığına) göre sıralanır, ardından sıralı sembol dizisi bir yerde iki parçaya bölünür, böylece her birinde onlara sembol frekanslarının toplamı yaklaşık olarak aynıdır. Bir gösteri olarak, bize zaten tanıdık gelen kelimeyi düşünün "Uçak kazası" .

Belirli bir kelimeyi oluşturan semboller, oluşma sıklıklarına göre azalan sıraya göre sıralanırsa, aşağıdaki sırayı elde ederiz: (a (5), t (2), (1) ve (1), to ( 1), c (1), p (1), o (1), f (1)) (kelime içindeki sembolün tekrarlanma sıklığı parantez içinde belirtilmiştir). Daha sonra, bu diziyi iki bölüme ayırmamız gerekiyor, böylece her birinde sembol frekanslarının toplamı yaklaşık olarak aynı (mümkün olduğunca). Bölümün "t" ve "b" sembolleri arasından geçeceği ve bunun sonucunda iki dizinin oluşturulacağı açıktır: (a (5), t (2)) ve ((1)'de ve (1'de) ), ila (1), c (1), p (1), o (1), φ (1)). Ayrıca, birinci ve ikinci dizilerdeki sembollerin tekrarlanma sıklıklarının toplamı aynı ve 7'ye eşit olacaktır.

Bir karakter dizisini bölmenin ilk adımında, her karakterin kodunun ilk basamağını alırız. Kural basittir: soldaki sırada görünen karakterler için kod "0" ile ve sağdakiler için - "1" ile başlar.

Özellikle, (a (5), m (2)) dizisi iki ayrı karaktere bölünecektir: a (5) ve m (2) (başka bölüm yoktur). Ardından "a" sembolü için kodun ikinci basamağı "0" ve "t" - "1" sembolü için. Diziyi bölmenin bir sonucu olarak, bireysel öğeler aldığımız için, artık bölünmezler ve "a" sembolü için 00 kodunu ve "t" sembolü için - 01 kodunu alırız.

((1)'de, u (1), ila (1), c (1), p (1), o (1), f (1)) dizisi, ((1)'de, ve (1), k (1)) ve (c (1), p (1), o (1), φ (1)), veya on (in (1), u (1), k (1) ), (c (1)) ve (p (1), o (1), φ (1)).

İlk durumda, birinci ve ikinci dizilerdeki simgelerin tekrar oranlarının toplamı sırasıyla 3 ve 4 ve ikinci durumda sırasıyla 4 ve 3 olacaktır. Açıklık adına, ilk seçeneği kullanacağız.

Ortaya çıkan yeni dizinin karakterleri için (1'de ve (1)'den (1)'e) (bu soldaki dizidir), kodun ilk iki basamağı 10 ve dizi için (c ( 1), p (1), o (1 ), φ (1)) - 11.

Örneğimizde (Şekil 2 ve 3) aşağıdaki önek kodları sistemi elde edilir: "a" - 00, "t" - 01, "b" - 100, "u" - 1010, "k" - 1011, " c" - 1100, "p" - 1101, "o" - 1110, "f" - 1111. Görüldüğü gibi kısa kodlar uzun kodların başlangıcı değildir yani önek kodlarının ana özelliği yerine getirilir.

Pirinç. 2. Shannon-Fano algoritmasının gösterimi

Pirinç. 3. "Uçak kazası" kelimesi için kod ağacı
Shannon-Fano algoritmasında

Huffman algoritması

Huffman algoritması, değişken uzunluklu önek kodlarını elde etmek için başka bir algoritmadır. Kodlama ağacının yukarıdan aşağıya doğru oluşturulmasını sağlayan Shannon-Fano algoritmasının aksine bu algoritma, kodlama ağacının ters sırada yani aşağıdan yukarıya (yaprak düğümlerinden köke doğru) oluşturulmasını ifade eder. düğüm).

İlk aşamada, Shannon-Fano algoritmasında olduğu gibi, orijinal karakter dizisi, karakterlerin tekrarlanma sıklığına (sıralama öğeleri) göre azalan düzende sıralanır. Yukarıdaki örnek için kelime ile "Uçak kazası" aşağıdaki sıralanmış eleman dizisini elde ederiz: (a (5), t (2), in (1), u (1), k (1), c (1), p (1), o (1), φ (1)).

Ayrıca dizinin son iki elemanı, orijinal elemanların tekrarlanabilirliğinin toplamına eşit bir tekrarlanabilirlik atanan yeni bir eleman S1 ile değiştirilir. Daha sonra dizinin elemanları tekrarlanabilirliklerine göre yeniden sıralanır. Bizim durumumuzda, o (1) ve φ (1) son iki elemanı S1 (2) elemanı ile değiştirilir ve yeni sıralanan dizi şu şekilde olur: (a (5), m (2), S1 ( 2), içinde (1) , u (1), k (1), c (1), p (1)).

Dizinin son iki elemanını toplam tekrarlanabilirliğe sahip yeni bir elemanla değiştirme ve ardından elemanların tekrarlanabilirliğine göre dizinin yeniden sıralanması prosedürüne devam ederek, dizide sadece bir elemanın kaldığı bir duruma ulaşıyoruz ( Şekil 4).

Pirinç. 4. Huffman algoritmasının gösterimi
"uçak kazası" kelimesi örneğini kullanarak

Elemanların değiştirilmesi ve dizinin yeniden sıralanması ile eş zamanlı olarak bir ikili kod ağacı oluşturulur. Ağaç oluşturma algoritması çok basittir: dizinin iki öğesini birleştirme (değiştirme) işlemi, kod ağacında yeni bir düğüm oluşturur. Yani, ağaca aşağıdan yukarıya bakarsanız, kod ağacının kenarları her zaman değiştirilen elemanlardan gelir ve değiştirme ile elde edilen dizi elemanına karşılık gelen yeni bir düğüm elemanında birleşir (Şekil 5). Bu durumda, kod ağacının sol kenarına "0" ve sağ kenarına - "1" değeri atanabilir. Bu değerler ayrıca önek kodu öğeleri olarak hizmet edecektir.

Pirinç. 5. Bir kod ağacı oluşturmak
Huffman algoritmasında
("o" ve "f" öğelerinin değiştirilmesi
yeni eleman S1)

Bir kelime için Huffman kod ağacını tamamlayın "Uçak kazası" , Şek. 6.

Pirinç. 6. "Uçak kazası" kelimesi için kod ağacını tamamlayın
Huffman algoritması tarafından oluşturulmuş

Kod ağacının kenarlarında yukarıdan aşağıya doğru yürürken, bilgi alfabemizin tüm sembolleri için önek kodlarını almak kolaydır:

Şimdi bir kelime yazmaya çalışırsanız "Uçak kazası" Huffman kodlamasında, 41 bitlik dizi 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0 elde ederiz. "uçak kazası" kelimesi. Yani, belirli bir örnekte, Huffman ve Shannon-Fano'nun kodlama verimliliği aynıdır. Ancak, gerçek bilgi alfabesinin 256 karakter olduğunu (ve örneğimizde olduğu gibi 14 değil) ve gerçek bilgi dizilerinin herhangi bir içerik ve uzunlukta dosyalar olduğunu dikkate alırsak, o zaman optimal önek kodu hakkında soru ortaya çıkar, yani, çıktı dizisinin minimum uzunluğunu elde etmenizi sağlayan bir kod.

Huffman algoritması kullanılarak elde edilen kodlar sisteminin, elde edilen kodlanmış bilgi dizisinin uzunluğunun minimum olması anlamında tüm olası önek kod sistemleri arasında en iyisi olduğu kanıtlanabilir. Yani, Huffman algoritması optimaldir.

Huffman algoritmasının ana dezavantajı, bir kod sistemi oluşturma sürecinin karmaşıklığıdır. Bununla birlikte, en yaygın değişken uzunluklu kod üretme algoritması olan ve çoğu bilgi sıkıştırma ve arşivleme yardımcı programında yer alan Huffman optimal algoritmasıdır.

aritmetik kodlama

Daha önce de belirttiğimiz gibi, Shannon'ın kriterine göre optimal kod, her karakter için –log 2 uzunluğunda bir kodun tahsis edildiği koddur. P biraz. Ve örneğin, belirli bir karakterin olasılığı 0,2 ise, kodunun optimal uzunluğu –log 2 0.2 = 2.3 bit olacaktır. Ön ek kodlarının böyle bir kod uzunluğu sağlayamayacağı ve bu nedenle optimal olmadığı açıktır. Genel olarak, Shannon kriteri tarafından belirlenen kodun uzunluğu sadece teorik bir sınırdır. Tek soru, hangi kodlama yönteminin bu teorik sınıra mümkün olduğunca yaklaşmanıza izin verdiğidir. Değişken uzunluklu önek kodları verimlidir ve uygulanması oldukça kolaydır, ancak daha verimli kodlama yöntemleri, özellikle bir aritmetik kodlama algoritması vardır.

Aritmetik kodlamanın arkasındaki fikir, tek tek karakterleri kodlamak yerine, kodun tüm bilgi dizisine aynı anda atanmasıdır. Tek bir karakter başına kodun uzunluğunun bir tamsayı olmayabileceği açıktır. Bu kodlama yönteminin önek kodlamadan çok daha verimli olmasının ve Shannon'ın kriteriyle daha tutarlı olmasının nedeni budur.

Aritmetik kodlama algoritmasının arkasındaki fikir aşağıdaki gibidir. Daha önce ele alınan tüm kodlama yöntemlerinde olduğu gibi, orijinal bilgi dizisinin her sembolü, kendi olasılığı ile karakterize edilir. İlk kodlanmamış diziye bir yarım aralık i atanır. ha!"

Daha fazla netlik için, tekrarlanan dizilerin karşılıklarının ve ilk oluşumlarının göründüğü şemaya bakalım:

Belki de burada belirsiz olan tek nokta "Hahahahaha!" dizisi olacaktır. Ancak burada olağandışı bir şey yok, algoritmanın bazen daha önce açıklanan RLE gibi davranmasını sağlayan bir numara kullandık.

Gerçek şu ki, paketi açarken sözlükten belirtilen sayıda karakter okuyacağız. Ve tüm dizi periyodik olduğundan, yani. İçindeki veriler belirli bir periyotla tekrarlandığından ve ilk periyodun sembolleri paket açma pozisyonunun hemen önünde yer alacağından, önceki periyodun sembollerini basitçe kopyalayarak tüm zinciri onlardan yeniden oluşturabiliriz. sonraki.

Bununla düzeldi. Şimdi bulunan kopyaları sözlüğe bağlantılar ile değiştirelim. Bağlantıyı, P, zincirin dizedeki ilk oluşumunun konumu, L uzunluğu olduğu biçimde yazacağız.

“Sıkıştırma ve t de bırakın i. ha!"

Ancak sürgülü bir pencere ile uğraştığımızı unutmayın. Daha iyi anlamak için, bağlantıların pencere boyutuna bağlı olmaması için, mutlak konumları aralarındaki farkla ve geçerli kodlama konumuyla değiştireceğiz.

“Sıkıştırma ve t de bırakın i. ha!"

Şimdi dizgedeki mutlak konumu elde etmek için mevcut kodlama konumundan P'yi çıkarmamız gerekiyor.

Pencerenin boyutuna ve kodlanmış cümlenin maksimum uzunluğuna karar verme zamanı. Metinle uğraştığımız için, metinde nadiren özellikle uzun tekrarlayan diziler olacaktır. Öyleyse uzunlukları için tahsis edelim, diyelim ki 4 bit - bir seferde 15 karakterlik bir limit bizim için yeterli.

Ancak pencerenin boyutu, aynı zincirleri ne kadar derinlemesine aradığımıza bağlıdır. Küçük metinlerle uğraştığımız için kullandığımız bit sayısını iki bayta eklemek doğru olacaktır: bunun için 12 bit kullanarak 4096 bayt aralığındaki bağlantıları ele alacağız.

Tüm değerlerin kullanılamayacağını RLE deneyiminden biliyoruz. Açıkçası, bir bağlantının minimum değeri 1 olabilir, bu nedenle, 1..4096 aralığında geri adreslemek için, kodlama sırasında bağlantıdan bir tane çıkarmalı ve kod çözme sırasında geri eklemeliyiz. Aynısı dizilerin uzunlukları için de geçerlidir: 0..15 yerine 2..17 aralığını kullanacağız, çünkü sıfır uzunluklarla çalışmıyoruz ve bireysel karakterler diziler değil.

Şimdi kodlanmış metnimizi şu değişikliklerle birlikte sunalım:

“Sıkıştırma ve t de bırakın i. ha!"

Şimdi yine sıkıştırılmış zincirleri bir şekilde verilerin geri kalanından ayırmamız gerekiyor. En yaygın yol, yapıyı yeniden kullanmak ve sıkıştırılmış verilerin nerede olduğunu ve nerede olmadığını doğrudan belirtmektir. Bunu yapmak için, kodlanmış verileri sekiz öğeden oluşan gruplara (semboller veya bağlantılar) böleceğiz ve bu grupların her birinin önüne bir bayt ekleyeceğiz, burada her bit öğenin türüne karşılık gelir: bir sembol için 0 ve 1 bir bağlantı için.

Gruplara ayırıyoruz:

• "komp"
• "Resyon"
• "Ve t de"
• "Terk etmek"
• "BEN. ha"

Grupların oluşturulması:

“(0.0.0.0.0.0.0.0) Comp (0.0.0.0.0.0.0.0) resion (0.0.0.0.0.1 , 0,0) ve t de (1,0,0,0,0,0,1) ,0) (0,1,0,0,0,0,0,1) bırak i. Hah (0)! "

Bu nedenle, paket açma sırasında bit 0 ile karşılaşırsak, karakteri çıktı akışına okuruz, bit 1 ise bağlantıyı okuruz ve referans olarak diziyi sözlükten okuruz.

Şimdi tek yapmamız gereken sonucu bir bayt dizisi halinde gruplandırmak. Bitleri ve baytları en anlamlı sırada kullandığımızı kabul edelim. Bir örnek kullanarak bağlantıların baytlara nasıl paketlendiğini görelim:

Sonuç olarak, sıkıştırılmış akışımız şöyle görünecektir:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #ve t ## de ### l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 saçak ## # i ##. hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Olası iyileştirmeler

Prensip olarak, RLE için açıklanan her şey burada doğru olacaktır. Özellikle buluşsal kodlamanın faydalarını göstermek için aşağıdaki örneği göz önünde bulundurun:

“Uzun goooooong. Çooook bağlı."

Sadece "loooooower" kelimesi için dizileri bulalım:

“Uzun goooooong. Wer bağlı."

Böyle bir sonucu kodlamak için bağlantılar için dört bayta ihtiyacımız var. Ancak, bunu yapmak daha ekonomik olacaktır:

“Uzun goooooong. Ben bağlıydım."

O zaman bir bayt daha az harcardık.

Sonuç yerine

Basit olmalarına ve görünüşte çok büyük verimlilikleri olmamasına rağmen, bu algoritmalar BT alanının çeşitli alanlarında hala yaygın olarak kullanılmaktadır.

Artıları basitlik ve hızdır ve daha karmaşık ve verimli algoritmalar ilkelerine ve kombinasyonlarına dayanabilir.

Umarım bu şekilde sunulan bu algoritmaların özü, birinin temelleri anlamasına ve daha ciddi şeylere bakmaya başlamasına yardımcı olur.