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

İyi çalışmalarınızı bilgi bankasına göndermek basittir. Aşağıdaki formu kullanın

Bilgi tabanını çalışmalarında ve işlerinde kullanan öğrenciler, lisansüstü öğrenciler, genç bilim adamları size çok minnettar olacaklar.

http://www.allbest.ru/ adresinde barındırılmaktadır

Veri sıkıştırma

1. Bilgi. Türleri ve özellikleri

Literatürde, "bilgi" teriminin oldukça fazla tanımı bulunabilir. Farklı yaklaşımlar Bu kavramın yorumlanması için. Sözlük Rus dili Ozhegova, "bilgi" kelimesinin 2 tanımını verir:

Bir kişi veya özel bir cihaz tarafından algılanan, çevreleyen dünya ve içinde gerçekleşen süreçler hakkında bilgi.

Durum hakkında, bir şeyin durumu hakkında bilgi veren mesajlar. (Bilimsel-teknik ve gazete bilgileri, kitle iletişim araçları - basın, radyo, televizyon, sinema).

Bilgi ve özellikleri, bilgi teorisi (bilgi iletim sistemlerinin matematiksel teorisi), sibernetik (makinelerde ve hayvanlarda olduğu kadar toplumda ve insanda iletişim ve kontrol bilimi) gibi bir dizi bilimsel disiplinin çalışma konusudur. varlıklar), semiyotik (işaretler ve işaret sistemleri bilimi), teori kitlesel iletişim(medyanın incelenmesi ve toplum üzerindeki etkilerinin incelenmesi), bilgisayar bilimi (her türlü bilgiyi ve otomatik işleme araçlarını toplama, dönüştürme, depolama, koruma, arama ve iletme süreçlerinin incelenmesi), fizik ve matematik.

Bilginin ikili bir karakteri vardır: malzeme - iletilebilir, saklanabilir vb.; ve soyut - iletimin kükürtüne göre doldurulabilir. Bilgi, kendisi olmadan var olamaz. malzeme taşıyıcı, onu uzayda ve zamanda aktarmanın bir yolu. Fiziksel nesnenin kendisi veya enerji eşdeğeri, ses, ışık, elektrik ve diğer sinyaller gibi bir taşıyıcı görevi görebilir.

Bunu yapmak için, şu anda, harici (insan beynine göre) ortamlarda bilgi depolamak ve uzak mesafelere iletmek için birçok yöntem icat edilmiştir.

Sunum biçimindeki ana bilgi türleri, kodlama ve depolama yöntemleri, sahip olduğu en yüksek değer bilgisayar bilimi için bu:

· grafik veya resimsel - kaya resimleri biçiminde ve daha sonra resimler, fotoğraflar, diyagramlar, kağıt, tuval, mermer ve resimleri tasvir eden diğer malzemeler üzerindeki çizimler şeklinde, çevredeki dünya hakkında bilgi depolama yönteminin uygulandığı ilk tür gerçek dünyanın;

· ses- çevremizdeki dünya seslerle dolu ve bunların depolanması ve çoğaltılması sorunu 1877'de ses kayıt cihazlarının icadıyla çözüldü; çeşitliliği müzikal bilgidir - bu tür için, benzer şekilde saklamayı mümkün kılan özel karakterler kullanarak bir kodlama yöntemi icat edilmiştir. grafik bilgi;

· metinsel- insan konuşmasını kodlamanın bir yolu özel karakterler- mektuplar ve farklı insanların sahip olduğu farklı diller ve kullan çeşitli setler konuşmayı göstermek için harfler; bu yöntem özellikle kağıt ve matbaanın icadından sonra önem kazandı;

· sayısal- çevreleyen dünyadaki nesnelerin ve özelliklerinin nicel ölçüsü; ticaretin, ekonominin ve para mübadelesinin gelişmesiyle özellikle büyük önem kazandı; aynı şekilde metin bilgisi görüntülemek için özel karakterlerle - sayılarla kodlama yöntemi kullanılır ve kodlama sistemleri (sayılar) farklı olabilir;

· video bilgisi- sinemanın icadıyla ortaya çıkan, çevremizdeki dünyanın "canlı" resimlerini korumanın bir yolu.

bilgileri aktarmak için uzun mesafeler başlangıçta kodlanmış ışık sinyalleri elektriğin icadıyla kullanıldı - belirli bir şekilde kodlanmış bir sinyalin teller üzerinden iletilmesi, daha sonra - radyo dalgaları kullanılarak.

Bilgisayarların (veya ülkemizde ilk olarak adlandırıldıkları şekliyle bilgisayarlar - elektronik bilgisayarlar) ortaya çıkmasıyla, bir işleme aracı sayısal bilgi. Ancak gelecekte, özellikle yaygın kullanımından sonra kişisel bilgisayarlar(PC), metinsel, sayısal, görsel, işitsel ve görüntülü bilgilerin saklanması, işlenmesi, iletilmesi ve aranması için bilgisayarlar kullanılmaya başlandı. İlk kişisel bilgisayarların - PC'lerin (20. yüzyılın 80'leri) - ortaya çıkışından bu yana, çalışma sürelerinin% 80'e kadarı metin bilgileriyle çalışmaya ayrılmıştır.

Bilgisayarları kullanırken bilgilerin depolanması manyetik diskler veya kurdeleler, lazer diskler(CD ve DVD), özel kalıcı bellek aygıtları (flash bellek vb.). Bu yöntemler sürekli geliştirilmekte, yeni cihazlar ve bilgi taşıyıcıları icat edilmektedir. Bilgi işleme (çoğaltma, dönüştürme, aktarma, üzerine kaydetme) harici medya) bilgisayarın işlemcisi tarafından yürütülür. Bilgisayar yardımıyla her türlü yeni bilgiyi oluşturmak ve depolamak mümkündür. özel programlar bilgisayarlarda ve giriş aygıtlarında kullanılır.

Şu anda özel bir bilgi türü, sunulan bilgiler olarak kabul edilebilir. küresel ağİnternet. Büyük hacimli dağıtılmış bilgileri depolamak, işlemek, aramak ve iletmek için özel teknikler ve özel çalışma yöntemleri kullanır. çeşitli tipler bilgi. Sürekli geliştirilmiş yazılım, her türlü bilgi ile toplu çalışma sağlar.

Bilgi özellikleri

Bilginin birçok farklı özelliğinden bahsedilebilir. Her bilimsel disiplin, kendisi için daha önemli olanları dikkate alır. Bilgisayar bilimi açısından, aşağıdaki özellikler en önemlileridir:

1. Bilginin nesnelliği ve öznelliği. Daha objektif bilgi, yöntemlerin daha küçük bir sübjektif unsur getirdiği bilgi olarak kabul edilir. Sırasında bilgi süreci bilginin nesnellik derecesi her zaman azalır.

2. Bilgilerin eksiksizliği. Bilginin eksiksizliği, büyük ölçüde bilginin kalitesini karakterize eder ve karar verme veya mevcut verilere dayalı olarak yeni veriler oluşturma için verilerin yeterliliğini belirler.

3. Bilginin güvenilirliği. Veriler, sinyallerin kaydedildiği anda oluşur, ancak tüm sinyaller "faydalı" değildir - her zaman bir dış sinyal seviyesi vardır.

5. Bilginin mevcudiyeti.

6. Alaka düzeyi.

2. Veri sıkıştırma

İyi bilinen kural bilgisayar Dünyası bu kapasitans sabit disk pek olmuyor Gerçekten de, onunla aynı fikirde olmamak zor: Satın alırken sabit sürücü ne kadar büyük görünürse görünsün, herhangi biriyle hızla tıkanır. gereksiz bilgi. Her şeyi silmek üzücü olduğu için, zaman zaman tüm bunları bir tür depoda, arşivde "depolamaya" değer.

İLEVeri sıkıştırma- hacimlerini azaltmak için gerçekleştirilen verileri yeniden kodlama prosedürü. Depolama ve veri aktarım cihazlarının daha rasyonel kullanımı için kullanılır. Bitmiş belgelere bilgi sıkıştırma yöntemleri uygulanırsa, "veri sıkıştırma" terimi genellikle "veri arşivleme" terimi ile değiştirilir.

Sıkıştırma, orijinal verilerde bulunan bilgilerin fazlalığının ortadan kaldırılmasına dayanır. Fazlalığa bir örnek, metindeki parçaların tekrarıdır (örneğin, doğal veya makine dilindeki kelimeler). Bu tür bir fazlalık, genellikle yinelenen dizinin daha kısa bir değerle (kod) değiştirilmesiyle ortadan kaldırılır. Başka bir fazlalık türü, sıkıştırılmış verilerdeki bazı değerlerin diğerlerinden daha sık ortaya çıkmasından kaynaklanırken, sık oluşan verileri daha kısa kodlarla ve nadir olanları daha uzun kodlarla değiştirmek mümkündür (olasılıksal sıkıştırma). Fazlalık özelliği olmayan verilerin sıkıştırılması (örneğin, rastgele sinyal veya gürültü) kayıp olmadan mümkün değildir. Ayrıca, şifrelenmiş bilgileri sıkıştırmak genellikle mümkün değildir.

Bilinmeyen bir biçimdeki metinleri / dosyaları sıkıştırmak için algoritmalar

Bilinmeyen formattaki dosyaları sıkıştırmak için 2 ana yaklaşım vardır.

Sıkıştırma algoritmasının her adımında, ya bir sonraki karakter olduğu gibi yerleştirilir (sıkıştırılmadığını belirten özel bir bayrakla) ya da dosyadaki sonraki karakterlerle eşleşen önceki yığından kelime sınırları belirtilir. Bu şekilde sıkıştırılmış dosyaları açmak çok hızlıdır, bu nedenle bu algoritmalar kendi kendine açılan programlar oluşturmak için kullanılır.

Her sekans için, dosyadaki oluşum istatistikleri zamanın her anında toplanır. Bu istatistiklere dayanarak, bir sonraki karakter için değerlerin olasılığı hesaplanır. Aritmetik kodlama veya Huffman kodlaması gibi bir tür entropi kodlaması, daha sonra sıklıkla meydana gelen dizileri daha kısa olanlarla ve seyrek olanları daha uzun olanlarla değiştirmek için uygulanabilir.

Sıkıştırma kayıpsız (orijinal verileri bozulma olmadan kurtarmak mümkün olduğunda) veya kayıplı (kurtarılan verilerin daha fazla kullanılması açısından önemsiz olan bozulmalarla kurtarma mümkündür) olabilir. Kayıpsız sıkıştırma, işlemede yaygın olarak kullanılır bilgisayar programları ve veriler, daha seyrek olarak - ses, fotoğraf ve video bilgilerinin hacmini azaltmak için. Kayıplı sıkıştırma, ses, fotoğraf ve video bilgilerinin hacmini azaltmak için kullanılır, kayıpsız sıkıştırmadan çok daha verimlidir.

3. Veri sıkıştırma yazılımı

Bitmiş belgelere bilgi sıkıştırma yöntemleri uygulanırsa. Genellikle "veri sıkıştırma" terimi, "veri arşivleme" terimi ile değiştirilir ve yazılım bu işlemleri yapanlara denir arşivciler.

Arşivleyiciler, dosyaları sıkıştırmak için tasarlanmıştır, örn. disk alanlarını azaltmak için. Disklerdeki bilgileri sıkıştırmak için özel bilgi paketleme yöntemlerinin kullanılmasına, dosyaların kopyalarının tek bir arşiv dosyasında oluşturulmasına izin verirler. Bilgisayar belleği miktarı sürekli artmasına rağmen arşivleme ihtiyacı azalmıyor.

Bu nedenle, arşivleme kullanışlı olabilir:

1) Dosyaların ve disketlerin kopyalarını saklarken, çünkü disketin boyutu sınırlıdır;

2) Sabit disk alanını boşaltmak için;

3) Ağ üzerinden bilgi iletirken.

Bilginin arşivlenmesi, hacminin azalmadığı, ancak bilgi miktarının aynı kaldığı bir bilgi dönüşümüdür.

Sıkıştırılmış dosyaya arşiv denir. Arşiv dosyası- bu, sıkıştırılmış ve sıkıştırılmamış biçimde bir veya daha fazla dosya ve adlarıyla ilgili hizmet bilgilerini içeren özel olarak düzenlenmiş bir dosyadır.

Bilgi sıkıştırma derecesi, kaynak dosyanın türüne, kullanılan programa ve seçilen paketleme yöntemine bağlıdır. Sıkıştırılacak en iyi dosyalar grafik nesneler, metin dosyaları ve sıkıştırma oranı %5-40'a ulaşabilen veri dosyaları, dosyalar daha az sıkıştırılır yürütülebilir programlar ve önyükleme modülleri -%60-90.

Çeşitli geliştiriciler birçok arşivleme programı oluşturmuştur. Bunlar arasında Windows için en yaygın olanları WINRAR, WINZIP'dir.

Popülerliğine göre WinRAR arşivleyici , şüphesiz Rusya'da birinci sırada ve tüm dünyada ilklerden biri. Arşivleyici, 2003 yılında Evgeny Roshal tarafından geliştirilmiştir. program sağlar tam kontrol arşivlerdeki dosyalar, kurtarma hasarlı arşivler, şifreleme, kendi kendine açılan ve çok ciltli arşivlerin oluşturulması.

WinZip, tüm dünyadaki çeşitli bilgisayar yayınlarından önemli sayıda ödül alan, İnternet'teki en popüler programlardan biridir.

Zip'in kendisi - algoritma düzinelerce programda serbestçe kullanılır, ancak çoğu için Windows kullanıcıları TAM OLARAK WinZip standart program arşivlerle çalışmak için. Yerleşik WinZIP arşiv işleme araçları, ZIP, CAB, Microsoft Compress, GZIP, TAR vb. gibi yaygın olarak kullanılan arşiv formatlarından dosyaları paketlemenize, görüntülemenize ve ayıklamanıza olanak tanır. WinZip çok basit ve kullanımı kolaydır.

Ancak, ayrı arşivleyicilerin kendi arşivleriyle kullanılması her zaman doğru değildir. grafik kabukları. Arşivciler için en uygun kabuk olağandır dosya yöneticisiörneğin, ZTP, ARJ, RAR, TAR, GZ, CAB, ACE arşiv dosyalarını görüntüleme ve paketinden çıkarma yeteneğine sahip Windows Commander. Yine de, arşivler de dahil olmak üzere dosyalarla ilgili çoğu işlem bu tür yöneticilerde gerçekleştirilir.

4. Kayıplı veri sıkıştırma

Kayıplı veri sıkıştırma sıkıştırılmış dosyanın orijinalinden farklı olduğu ancak bir şekilde yararlı olacak kadar "yeterince yakın" olduğu bir veri sıkıştırma yöntemidir. Bu sıkıştırma türü internette, özellikle akış ve telefonda sıklıkla kullanılır. Bu yöntemlere bu bağlamda genellikle kodekler denir. Alternatif, kayıpsız sıkıştırmadır.

Kayıplı sıkıştırma türleri

İki ana kayıplı sıkıştırma şeması vardır:

Dönüşüm kodeklerinde, görüntü veya ses kareleri alınır, küçük parçalara bölünür, yeni bir temel uzaya dönüştürülür ve niceleme yapılır. Sonuç daha sonra entropi yöntemleriyle sıkıştırılır.

Öngörülü kodeklerde, önceki ve/veya sonraki veriler, bir görüntünün veya sesin geçerli karesini tahmin etmek için kullanılır. Öngörülen veri ile gerçek veri arasındaki hata, tahmini üretmek için gereken ek bilgi ile birlikte daha sonra nicelenir ve kodlanır.

Bazı sistemler, tahmin aşamasında üretilen hatalı sinyalleri sıkıştırmak için dönüşüm kodeklerini kullanarak bu iki tekniği birleştirir.

Kayıplı ve Kayıpsız Sıkıştırma

Kayıpsız sıkıştırma yöntemlerinin kayıpsız sıkıştırma yöntemlerine göre avantajı, gereksinimleri karşılamaya devam ederken sıkıştırma oranından önemli ölçüde daha iyi performans göstermesidir.

Kayıplı sıkıştırma teknikleri genellikle ses veya görüntüleri sıkıştırmak için kullanılır.

Bu gibi durumlarda, sıkıştırılmış dosya orijinalinden bit bit düzeyinde çok farklı olabilir, ancak çoğu pratik uygulamada insan kulağı veya gözü için neredeyse ayırt edilemez.

Birçok yöntem, insanın duyu organlarının yapısal özelliklerine odaklanır. Psikoakustik model, algılanan ses kalitesini bozmadan sesin ne kadar sıkıştırılabileceğini tanımlar. İnsan kulağı veya gözü tarafından görülebilen kayıplı sıkıştırmanın neden olduğu kusurlar, sıkıştırma artefaktları olarak bilinir.

Kayıplı sıkıştırılmış ses verileri, sıkıştırılmış bilgilerin sıkıştırma yapaylıkları kazanması ve kaydın yapıldığı ortamın doğal gürültüsünü kaybetmesi nedeniyle mahkemeler tarafından maddi delil olarak kabul edilmez (hatta dikkate alınmaz). Bu bağlamda, kaydın gerçek mi yoksa sentezlenmiş mi olduğunu tespit etmek imkansızdır. Bu nedenle, önemli kayıtların PCM formatında yapılması veya bir kayıt cihazı kullanılması önerilir.

kaydedilen fotoğraflar JPEG biçimi, mahkeme tarafından kabul edilebilir (veriler kayıplı sıkıştırmaya tabi tutulmuş olmasına rağmen). Ancak aynı zamanda, yapıldıkları kamera veya ilgili renk oluşturma tablosu da sağlanmalıdır.

Kayıplı veri sıkıştırma yöntemleri

v Görüntü sıkıştırma:

Azaltılmış renk derinliği

· Ana bileşen yöntemi;

· Fraktal sıkıştırma;

v Video sıkıştırma:

Flaş (hareket etmeyi de destekler JPEG resimleri);

MPEG-1 Bölüm 2;

· MPEG-2 Bölüm 2;

· MPEG-4 Bölüm 2;

v Ses sıkıştırma:

· MP3 - MPEG-1 belirtimi ile tanımlanmıştır;

Ogg Vorbis (patent kısıtlamalarının olmaması ve daha fazlası ile dikkate değer) yüksek kalite);

· AAC, AAC+ - örneğin Apple Computer'da kullanılan MPEG-2 ve MPEG-4 belirtimleriyle tanımlanan çeşitli sürümlerde bulunur;

eAAC+, Sony tarafından AAC ve AAC+'ya alternatif olarak sunulan bir biçimdir;

· WMA - Microsoft'un mülkü;

bilgi sıkıştırma arşivleyici kaybı

5. Kayıpsız veri sıkıştırma

kayıpsız sıkıştırma(eng. Kayıpsız veri sıkıştırma) - kodlanmış bilgilerin bir bit içinde geri yüklenebildiği bir bilgi sıkıştırma yöntemi. Bu durumda, orijinal veriler sıkıştırılmış durumdan tamamen geri yüklenir. Bu sıkıştırma türü temelde kayıplı veri sıkıştırmasından farklıdır. Her tür için dijital bilgi, kural olarak, optimal kayıpsız sıkıştırma algoritmaları vardır.

Birçok uygulamada kayıpsız veri sıkıştırma kullanılır. Örneğin, popüler dosyada kullanılır. ZIP biçimi ve Unix yardımcı programı Gzip. Ayrıca kayıplı sıkıştırmada bir bileşen olarak kullanılır.

Kayıpsız sıkıştırma, sıkıştırılmış verinin orijinal ile kimliği önemli olduğunda kullanılır. Yaygın bir örnek yürütülebilir dosyalar Ve kaynak. Bazı grafik dosya formatları PNG veya GIF gibi , yalnızca kayıpsız sıkıştırma kullanın; diğerleri (TIFF, MNG) ise hem kayıplı hem de kayıpsız sıkıştırmayı kullanabilir.

Kayıpsız sıkıştırma tekniği

Kombinatoriklerden, herhangi bir dosyayı en az bir bayt azaltabilen kayıpsız bir sıkıştırma algoritması olmadığı sonucu çıkar. Ancak bu, bir sıkıştırma algoritmasının kalitesinin bir işareti değildir - algoritma, tasarlandığı veriler üzerinde etkili bir şekilde çalışmalıdır.

Çok amaçlı sıkıştırma algoritmaları, yürütülebilir dosyalar, veri dosyaları, metinler, grafikler vb. gibi çok çeşitli verileri azaltabilmeleri ve arşivleyicilerde kullanılmaları ile ayırt edilir. Özel algoritmalar belirli bir dosya türü (metin, grafik, ses vb.) için tasarlanmıştır, ancak bu tür dosyaları çok daha güçlü bir şekilde sıkıştırırlar. Örneğin: arşivleyiciler sesi yaklaşık üçte bir oranında (1,5 kat) sıkıştırırken, FLAC 2,5 kat sıkıştırır. Çoğu özel algoritma, "yabancı" dosya türleri için çok az işe yarar: örneğin, ses verileri, metinler için tasarlanmış bir algoritma tarafından zayıf bir şekilde sıkıştırılır.

Çoğu kayıpsız sıkıştırma algoritması iki aşamada çalışır: ilki gelen veriler için istatistiksel bir model oluşturur, ikincisi gelen verileri bitmapler, modeli kullanarak "olasılıksal" (yani sık sık meydana gelen) verileri üretir; bu, diğerlerinden daha sık kullanılır. "olası olmayan" veriler..

Metin (veya yürütülebilir dosyalar gibi metin tabanlı ikili veriler) için istatistiksel algoritma modelleri şunları içerir:

Burrows-Wheeler dönüşümü (sıkıştırmayı daha verimli hale getiren blok sıralama ön işlemesi)

LZ77 ve LZ78 (DEFLATE kullanarak)

Bit dizilerinin oluşturulması yoluyla kodlama algoritmaları:

Huffman algoritması (DEFLATE tarafından da kullanılır)

aritmetik kodlama

Kayıpsız sıkıştırma yöntemleri

· Çok Amaçlı

· Çalışma uzunluklarının kodlanması - basit devre, çok sayıda yinelenen değer içeren verilerin iyi bir şekilde sıkıştırılmasını sağlar

· LZW - gif ve diğerlerinde kullanılır.

· Deflate - Zip'in gelişmiş bir sürümü olan gzip'te ve PNG sıkıştırma işleminin bir parçası olarak kullanılır.

· LZMA - 7-zip'te kullanılır.

v Ses sıkıştırma:

· Apple Lossless - ALAC (Apple Lossless Audio Codec);

· Audio Lossless Coding - MPEG-4 ALS olarak da bilinir;

· Doğrudan Akış Aktarımı - DST;

· Ücretsiz Kayıpsız Ses Codec'i - FLAC;

v Grafik sıkıştırma

ABO - Uyarlanabilir İkili Optimizasyon;

· GIF - (yalnızca 256'dan az renk içeren resimler için kayıpsız);

· JBIG2 - (kayıplı S/B resimlerle veya bunlar olmadan);

· JPEG-LS - (kayıpsız / neredeyse kayıpsız sıkıştırma standardı);

· JPEG 2000 - (kayıpsız sıkıştırma içerir; San Diego Eyalet Üniversitesi profesörü Sunil Kumar tarafından da test edilmiştir);

· PGF - Aşamalı Grafik Dosyası (kayıplı/kayıpsız sıkıştırma);

PNG - Taşınabilir Ağ Grafikleri;

· WMPhoto - (kayıpsız sıkıştırma yöntemi dahil);

v Video sıkıştırma

Animasyon codec'i;

· CamStudio Video Codec'i;

6. Bilgilerin saklanması (metin, grafik, ses)

Bilgi, belirli depolama ortamları kullanılarak depolanır. Kişi bilgisini ya kendi belleğinde ya da bazı dış ortamlarda depolar.

İlk başta, bir kişi hafızasını bilgi depolamak ve biriktirmek için kullandı - alınan bilgiyi ezberledi ve bir süre hatırladı. Yavaş yavaş, insanlar bu bilgi depolama yönteminin bir takım dezavantajları olduğu sonucuna vardılar. Böyle bir bilgi depolama ve biriktirme yönteminin güvenilmezliğini fark eden bir kişi, papirüs üzerine ve daha sonra kitaplara yazmanın icadıyla bilgileri çizimler şeklinde yazmaya başladı. Ardından fotoğraf levhaları ve ses kayıt cihazları eleman olarak ortaya çıktı. harici bellek video ve ses bilgisi, defterler, harici veri depoları dediğimiz dizinler, ansiklopediler vb. 20. yüzyılın ortalarında bilgisayar icat edilmişti. Hemen bilgiyi nasıl saklayacağı sorusu ortaya çıktı.

Bilgi taşıyıcısı farklı bir yapıya sahip olabilir: kağıt. Mekanik, manyetik, elektrik. Ortam üzerine kaydedilen bilgiler, insan tarafından okunabilen bir sembol biçiminde veya şifrelenmiş bir biçimde olabilir. Teyp kaydedici, video kaydedici, film kamerası için bilgiler - sesözel cihazlarda saklanır: ses kasetleri, video kasetleri, filmler. Bir mikrofon ve diğer cihazlar yardımıyla ses bilgisi manyetik bir teybe kaydedilir.

Bilgisayarlarda, bilgileri yazmak için aygıtlar olarak kullanılmaya başlandı: delikli kart okuyucular; manyetik teyp sürücüleri, disket (disk sürücüsü) ve sabit (sabit sürücü) manyetik disk sürücüleri; kompakt disk sürücüleri (CD-ROM) ve daha fazlası modern cihazlar bilgi birikimi ve depolanması.

bibliyografik liste

1. 27 Temmuz 2006 tarih ve 149-FZ sayılı Rusya Federasyonu "Bilgi, Bilgilendirme ve Bilgi Koruma" Federal Kanunu.

2. Levin A.Ş. Bilgisayar eğitimi. - St.Petersburg: Peter, 2006. - 655 s.

3. Romanova N.I. Bilişimin temelleri. - St. Petersburg: Politeknik, 2004. -224 s.

4. Simonovich S.V. Bilgisayar Bilimi. Temel kurs. - St.Petersburg: Peter, 2008 - 640 s.

Allbest.ru'da barındırılıyor

Benzer Belgeler

Veri sıkıştırma türleri: kayıplı (kayıplı) ve kayıpsız (kayıpsız). Minimum fazlalık ile sıkıştırma. Shannon-Fano kodlaması. bmp ve xls dosyalarını sıkıştırmak için program kontrol ediliyor. Shannon ve Huffman sıkıştırma algoritmasının Delphi uygulaması.

dönem ödevi, 01/26/2011 eklendi


Veri sıkıştırma yönteminin sınıflandırılması ve temel özellikleri. Sıkıştırma oranlarının hesaplanması ve etkinliklerinin tahmini. Polinom, ekstrapolasyon ve enterpolasyon sıkıştırma yöntemleri için algoritmalar ve bunların karşılaştırılması. Optimum doğrusal tahmin.

dönem ödevi, 03/17/2011 eklendi


Görüntü sıkıştırma yöntemleri olarak arşivleme ve sıkıştırma. Veri sıkıştırma algoritmaları. Dosya boyutlarını küçültmek için kullanılan yardımcı araçlar: değiştir renk modeli görüntüler, çözünürlük değişikliği bit eşlem dosyası, yeniden örnekleme.

sunum, 01/06/2014 eklendi


Başlıca arşivleme program türlerinin incelenmesi. Arşivleme sırasında dosyaları sıkıştırma. Dosya sıkıştırma derecesi. En popüler paketleyicilerin işlevselliğinin değerlendirilmesi. Özellikler sıkıştırma işlemleri. Kayıpsız arşivleme yöntemleri.

özet, 12/05/2013 eklendi


Dosya sıkıştırmanın amacının açıklanması ve aktarım ve saklama kolaylığı için dosyaları bir arşive paketleyen ve paketten çıkaran programlar olarak arşivleyicilerin amacının açıklanması. Ana arşivleyici türleri: dosya, program, disk. Kayıpsız sıkıştırma yöntemi.

sunum, 04/05/2011 eklendi


Veri sıkıştırmanın temel kavramları ve yöntemleri. Bir dosyada saklanan bilgileri sunumundaki fazlalığı azaltan bir forma dönüştürmek. İstatistiksel ve sözlük sıkıştırma yöntemleri. Arşivleme programları, WinRAR'ın temel özellikleridir.

kontrol çalışması, 03/12/2011 eklendi


Kısa inceleme ana sıkıştırma teorileri. Fikir kavramları ve bunların uygulanması. Burrows-Wheeler dönüşümünü kullanarak veri sıkıştırma. Statik Huffman algoritması. Yerel olarak uyarlanabilir sıkıştırma algoritması. Ziv-Lempel algoritması (Welch) ve Shannon-Fano yöntemi.

pratik çalışma, 04/24/2014 eklendi


Entropi ve bilgi miktarı. Bilgi miktarının kombinatoryal, olasılıksal ve algoritmik tahmini. Modelleme ve kodlama. Bazı veri sıkıştırma algoritmaları. Aritmetik kodlama algoritması. Artımlı gönderme ve alma.

dönem ödevi, 07/28/2009 eklendi


İletişim kanalları üzerinden veri aktarım hızını artırmak için yüksek derecede sıkıştırma sağlayan algoritmaların kullanılması. Tekil değer ayrıştırmasını bulmanın özellikleri ve yöntemleri. SVD sıkıştırma kullanarak görüntü sıkıştırma uygulayan bir programın geliştirilmesi.

tez, 10/13/2015 eklendi


Arşiv oluşturmak için programlar. Veri sıkıştırma verimliliği en önemli özelliği arşivciler. Temel veri sıkıştırma yöntemleri. Paketleme metinleri için programın özellikleri ve WinRar programları. Dosyaları açma, dosyaları ve klasörleri paylaşılan bir arşive paketleme.

dersin amacı: veri sıkıştırmanın ana türlerini ve algoritmalarını incelemek ve Huffman yöntemini ve kod ağaçlarını kullanarak veri sıkıştırma problemlerini nasıl çözeceğinizi öğrenmek.

Claude Shannon, bilgi sıkıştırma biliminin kurucusu olarak kabul edilir. Optimal kodlama teoremi, bilgiyi kodlarken neyin çaba sarf etmesi gerektiğini ve bu veya bu bilginin ne kadar sıkıştırılacağını gösterir. Ayrıca, İngilizce metnin fazlalığının deneysel olarak değerlendirilmesi üzerine deneyler yaptı. Shannon, insanlardan bir sonraki harfi tahmin etmelerini istedi ve doğru tahmin etme olasılığını tahmin etti. Bir dizi deneye dayanarak, şu sonuca vardı: Bilgi miktarıİngilizce metinde karakter başına 0,6 - 1,3 bit arasında dalgalanır. Shannon'ın araştırmasının sonuçlarının on yıllar sonrasına kadar gerçekten rağbet görmediği gerçeğine rağmen, onların önemini abartmak zordur.

Veri sıkıştırma fazlalıklarını azaltarak veri hacmini azaltan bir süreçtir. Veri sıkıştırma, veri yığınlarının kompakt bir düzenlemesi ile ilişkilidir. Standart boy. Veri sıkıştırma iki ana türe ayrılabilir:

• Kayıpsız sıkıştırma (tamamen tersine çevrilebilir)- Bu, verilerin önceden kodlanmış bir kısmının, değişiklik yapılmadan tamamen sıkıştırıldıktan sonra geri yüklendiği bir veri sıkıştırma yöntemidir. Her veri türü için, kural olarak, optimal kayıpsız sıkıştırma algoritmaları vardır.
• Kayıplı sıkıştırma sağlamak için bir veri sıkıştırma yöntemidir. maksimum derece orijinal veri dizisinin sıkıştırılması, içinde bulunan verilerin bir kısmı atılır. Metin, sayısal ve tablo verileri için, bu tür sıkıştırma yöntemlerini uygulayan programların kullanılması kabul edilemez. Temel olarak, bu tür algoritmalar, ses ve video verilerini, statik görüntüleri sıkıştırmak için kullanılır.

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

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

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

kod sembolü sıkıştırılacak en küçük veri birimidir. Genellikle bir karakter 1 bayttır, ancak bir bit, bir trit (0,1,2) veya başka herhangi bir şey olabilir.

Bir kod sözcüğü kod alfabesinden bir kod simgeleri dizisidir. Tüm kelimeler aynı uzunluğa (karakter sayısına) sahipse, böyle bir kod denir üniforma (sabit uzunluk) ve farklı uzunluklardaki sözcüklere izin veriliyorsa, o zaman - düzensiz (değişken uzunluk).

Kod, eksiksiz bir kelime kümesidir.

Jeton– bazı sıkıştırma algoritmaları tarafından sıkıştırılmış bir akışa yazılan bir veri birimi. Bir belirteç, birkaç sabit veya değişken uzunluk alanından oluşur.

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

kodlama veri sıkıştırma işlemidir.

kod çözme– veri kurtarmanın gerçekleştirildiği ters kodlama işlemi.

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

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

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

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

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

kod kelimelerinin olasılıkları nerede;

L 1 ,L 2 ,...,Ln kod kelimelerinin uzunluklarıdır.

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

İstatistiksel Yöntemler– giriş akışındaki karakterlere değişken uzunluklu kodlar atayan, giriş akışında görünme olasılığı daha yüksek olan karakterlere veya karakter gruplarına daha kısa kodlar atanan sıkıştırma yöntemleri. En iyi istatistiksel yöntemler Huffman kodlaması kullanılmıştır.

sözlük sıkıştırma veri parçalarını bir "sözlükte" (bazıları veri yapısı). Yeni girdi verisi dizisi sözlükte zaten bulunan bir parçayla aynıysa, çıktı akışına o parçaya bir işaretçi yerleştirilir. En iyi sözlük yöntemleri Ziv-Lempel yöntemini kullanır.

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

Huffman yöntemi

Bu algoritma bilgi kodlama D.A. tarafından teklif edildi. 1952 yılında Huffmann Huffman kodlaması (sıkıştırma) atanan yaygın olarak kullanılan bir sıkıştırma yöntemidir. alfabe karakterleri Bu karakterlerin meydana gelme olasılıklarına bağlı olarak değişken uzunluklu kodlar.

Algoritmanın fikri şu şekildedir: kaynak metinde karakterlerin oluşma olasılıklarını bilmek, bir tamsayı bitten oluşan değişken uzunluklu kodları oluşturma prosedürünü açıklamak mümkündür. Karakterlere daha kısa kodlar atanma olasılığı daha yüksektir. Bu nedenle, bu yöntemde, veriler sıkıştırıldığında, metinde bulunma olasılığına bağlı olarak her karaktere en uygun önek kodu atanır.

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

Optimal önek kodu minimum ortalama uzunluğa sahip önek kodudur.

Huffman algoritması iki aşamaya ayrılabilir.

1. Kaynak metinde karakterlerin bulunma olasılığının belirlenmesi.

   Başlangıçta, kaynak metni tamamen okumak ve içinde karakterlerin olma olasılıklarını hesaplamak gerekir (bazen her karakterin kaç kez geçtiğini sayarlar). Bu, 256 karakterin tamamını hesaba katarsa, bir metni veya farklı biçimdeki bir dosyayı sıkıştırmada hiçbir fark olmayacaktır.

2. En uygun önek kodunu bulma.

   Daha sonra, en düşük oluşma olasılıklarına sahip iki sembol a ve b bulunur ve bunların yerine a ve b sembollerinin olma olasılıklarının toplamına eşit olma olasılığına sahip bir sahte sembol x konulur. Ardından, bu yordamı yinelemeli olarak kullanarak, daha küçük bir karakter kümesi için en uygun önek kodu bulunur (burada a ve b karakterleri tek bir x karakteriyle değiştirilir). Orijinal karakter setinin kodu, değiştirilen karakter kodlarından, değiştirilen karakter kodunun önüne 0 veya 1 eklenerek elde edilir ve bu iki yeni kod, değiştirilen karakter kodları olarak alınır. Örneğin, a karakter kodu, x koduyla bu koddan önce eklenen bir sıfırla eşleşecek ve b karakteri için, x karakter kodundan önce bir eklenecektir.

Huffman kodlarının, değişken uzunluklarına rağmen açık bir şekilde kodlarının çözülmesine izin veren benzersiz bir ön eki vardır.

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

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

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

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

Bilgi sıkıştırma, oldukça uzun bir geçmişe sahip, bilgisayar teknolojisinin gelişim tarihinden çok daha eski olan ve (tarih) genellikle bilgilerin kodlanması ve şifrelenmesi sorununun gelişim tarihiyle paralel giden bir sorundur. Tüm sıkıştırma algoritmaları, minimum birimi biraz ve maksimum birimi birkaç bit, bayt veya birkaç bayt olan bir bilgi giriş akışı üzerinde çalışır. Sıkıştırma işleminin amacı, kural olarak, başlangıçta kompakt olmayan bazı girdi akışlarından, bunların bazı dönüşümlerini kullanarak daha kompakt bir bilgi birimleri çıktı akışı elde etmektir. Sıkıştırma işlemlerinin ana teknik özellikleri ve çalışmalarının sonuçları şunlardır:

Sıkıştırma derecesi (sıkıştırma derecelendirmesi) veya kaynak ve sonuçtaki akışların hacimlerinin oranı (oran);

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

Sıkıştırma kalitesi - aynı veya başka bir algoritma kullanılarak yeniden sıkıştırma uygulanarak çıktı akışının ne kadar yoğun bir şekilde paketlendiğini gösteren bir değer.

Bilgi sıkıştırma sorununa birkaç farklı yaklaşım vardır. Bazıları çok karmaşık bir teorik matematiksel temele sahiptir, diğerleri bilgi akışının özelliklerine dayanır ve algoritmik olarak oldukça basittir. Veri sıkıştırmayı veya sıkıştırmayı uygulayan herhangi bir yaklaşım ve algoritma, tersine çevrilebilir veya geri alınamaz dönüşümünü kullanarak çıktı bilgi akışının hacmini bit cinsinden azaltmak için tasarlanmıştır. Bu nedenle, her şeyden önce, verinin doğası veya biçimiyle ilgili kritere göre, tüm sıkıştırma yöntemleri iki kategoriye ayrılabilir: geri döndürülebilir ve geri alınamaz sıkıştırma.

Geri döndürülemez sıkıştırma, giriş veri akışının, belirli bir bilgi formatına dayanan çıkış akışının, belirli bir bakış açısından, dış özelliklerde giriş akışına oldukça benzer, ancak farklı olan bir nesneyi temsil ettiği, bu tür bir dönüşüm anlamına gelir. ondan hacim olarak. Girdi ve çıktı akışlarının benzerlik derecesi, bu bilgi akışı tarafından temsil edilen nesnenin bazı özelliklerinin (yani, belirli bir veri formatına göre sıkıştırılmış ve sıkıştırılmamış bilgi) uyuşma derecesi ile belirlenir. Bu tür yaklaşımlar ve algoritmalar, örneğin, akışta düşük bir bayt yineleme hızına sahip raster grafik dosyası verilerini sıkıştırmak için kullanılır. Bu yaklaşımla, grafik dosyası biçiminin yapısının özelliği ve görüntü kalitesinde (insan gözünün algısı için) yaklaşık olarak benzer bir grafik görüntüsünü birkaç (veya daha doğrusu n) yolla sunma yeteneği kullanılır. Bu nedenle, sıkıştırma derecesi veya büyüklüğüne ek olarak, bu tür algoritmalarda kalite kavramı ortaya çıkar, çünkü Orijinal görüntü sıkıştırma işlemi sırasında değiştiğinden, kalite, bilgi formatına göre öznel olarak değerlendirilen, orijinal ile ortaya çıkan görüntü arasındaki uygunluk derecesi olarak anlaşılabilir. Grafik dosyaları için, karşılık gelen akıllı algoritmalar ve programlar olmasına rağmen, bu karşılık görsel olarak belirlenir. Girdi ve çıktı akışlarının bilgi yapısı arasında tam bir eşleşmenin gerekli olduğu alanlarda geri döndürülemez sıkıştırma kullanılamaz. Bu yaklaşım, JPEG ve JFIF algoritmaları olarak bilinen popüler video ve fotoğraf formatlarında ve JPG ve JIF dosya formatlarında uygulanmaktadır.

Tersine çevrilebilir sıkıştırma, bilgi içeriğini değiştirmeden her zaman çıktı bilgi akışının hacminde bir azalmaya yol açar, yani. - bilgi yapısı kaybı olmadan. Ayrıca girdi akışı, bir dekompresyon veya dekompresyon algoritması kullanılarak çıktı akışından elde edilebilir ve kurtarma işlemi dekompresyon veya dekompresyon olarak adlandırılır ve ancak dekompresyon işleminden sonra veriler dahili formatına uygun olarak işlenmeye uygundur.

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

Şimdi doğrudan tersine çevrilebilir algoritmaların algoritmik özelliklerine geçelim ve kodlama sistemlerinin uygulanması ve bilgi sıkıştırma yöntemleriyle ilgili veri sıkıştırmaya yönelik en önemli teorik yaklaşımları ele alalım.

Seri kodlama sıkıştırması

En iyi bilinen basit yaklaşım ve tersine çevrilebilir sıkıştırma algoritması, Çalışma Uzunluğu Kodlamasıdır (RLE). Bu yaklaşımın yöntemlerinin özü, zincirleri veya yinelenen bayt dizilerini veya bunların dizilerini bir kodlama baytı ve tekrarlarının sayısı için bir sayaçla değiştirmektir. Tüm benzer yöntemlerle ilgili sorun, yalnızca, sıkıştırmayı açma algoritmasının, sonuçta ortaya çıkan bayt akışında kodlanmış dizileri diğer kodlanmamış bayt dizilerinden nasıl ayırt edebileceğini belirlemektir. Sorunun çözümü genellikle kodlanmış zincirlerin başına etiketlerin yerleştirilmesiyle sağlanır. Bu tür işaretler, örneğin, bir kodlanmış çalıştırmanın ilk baytındaki karakteristik bit değerleri, bir kodlanmış çalıştırmanın ilk baytının değerleri ve benzerleri olabilir. Bu yöntemler, kural olarak, bitmap grafik görüntüleri (BMP, PCX, TIF, GIF) sıkıştırmak için oldukça etkilidir. ikincisi, birkaç uzun yinelenen bayt dizisi dizisi içerir. RLE yönteminin dezavantajı, oldukça düşük bir sıkıştırma oranı veya az sayıda seriye sahip ve daha da kötüsü, seri olarak az sayıda tekrarlanan bayt içeren dosyaları kodlama maliyetidir.

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

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

Kodlama süreci ve yöntemleri

Kodlama genellikle bir karakter akışının (bizim durumumuzda baytlar veya yarım baytlar) bazı alfabelerde işlenmesi olarak anlaşılır ve akışta karakterlerin oluşma sıklıkları farklıdır. Kodlamanın amacı, bu akışı minimum uzunlukta bir bit akışına dönüştürmektir; bu, sembol frekanslarını dikkate alarak giriş akışının entropisini azaltarak elde edilir. Akış alfabesindeki karakterleri temsil eden kodun uzunluğu, giriş akışındaki bilgi miktarıyla orantılı olmalıdır ve akış karakterlerinin bit cinsinden uzunluğu, 8'in katı veya değişken bile olamaz. Girdi akışının alfabesindeki karakterlerin oluşum sıklıklarının olasılık dağılımı biliniyorsa, optimal bir kodlama modeli oluşturmak mümkündür. Ancak, çok sayıda farklı dosya biçiminin varlığı nedeniyle görev çok daha karmaşık hale gelir. veri sembolü frekans dağılımı önceden bilinmemektedir. Bu durumda, genel olarak, iki yaklaşım kullanılır.

Birincisi, giriş akışının görüntülenmesi ve toplanan istatistiklere dayalı olarak kodlamanın oluşturulmasından oluşur (bu, dosyadan iki geçiş gerektirir - biri istatistiksel bilgileri görüntülemek ve toplamak için, ikincisi kodlama için, bu da bu tür algoritmaların kapsamını bir şekilde sınırlar, çünkü, bu nedenle , veri miktarının bazen bilinmediği ve bunların yeniden iletilmesinin veya ayrıştırılmasının makul olmayan bir şekilde uzun sürebildiği telekomünikasyon sistemlerinde kullanılan tek geçişli anında kodlama olasılığını ortadan kaldırır). Böyle bir durumda kullanılan kodlamanın entropi şeması çıkış akımına yazılır. Bu teknik, statik Huffman kodlaması olarak bilinir.

Giriiş.

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

belirli bir kanal üzerinden bilgi iletmek için gereken süre

Bant genişliği. Bir kodlama şeklidir. Diğer kodlama amaçları

şifrelemenin yanı sıra hataların aranması ve düzeltilmesidir. arama süreci ve

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

insanlar tarafından okunabilir bir biçimde sunulmaları gerekmediğinde. Kaldırma

metin fazlalığından, sıkıştırma şifrelemeyi teşvik eder, bu da aramayı zorlaştırır

kırıcının erişebileceği istatistiksel bir yöntemle şifreleyin.

Tersinir sıkıştırmayı veya girişimsiz sıkıştırmayı ele alalım;

metin tam olarak sıkıştırılmış durumdan geri yüklenebilir. geri alınamaz veya

gibi analog sinyalleri dijital olarak kaydetmek için zararlı sıkıştırma kullanılır.

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

doğal ve yapay dillerde yazılmış, çünkü bu durumda

hatalar genellikle kabul edilemez. Birincil uygulama alanı olmasına rağmen

Söz konusu yöntemlerden biri de terminolojimizi yansıtan metinlerin sıkıştırılmasıdır.

ancak bu teknik, geri dönüşümlü olanlar da dahil olmak üzere diğer durumlarda kullanılabilir.

ayrık veri dizilerinin kodlanması.

Bilgisayar kaynaklarını sıkıştırılmış dosyalar açısından tahsis etmek için pek çok iyi neden vardır.

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

bunları depolamak çok para tasarrufu sağlar ve çoğu zaman iyileştirir

bilgisayar göstergeleri. Sıkıştırma, tüm nedenlerden dolayı büyük olasılıkla odakta kalacaktır.

Bilgisayara depolanan ve iletilen veri miktarının artmasıyla birlikte,

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

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

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

Sıkıştırma algoritmaları, veri depolama ve iletiminin verimliliğini artırabilir

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

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

açılım algoritması metni girdi olarak sıkıştırdığında ve

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

kaynak metni alfabenin harflerinden oluşan bir dizi dizi olarak kabul edin

orjinal metin.

S dizi gösterimindeki artıklık L(S) - H(S)'dir, burada L(S) uzunluktur

bit cinsinden temsiller ve H(S) - entropi - bilgi içeriğinin bir ölçüsü, ayrıca

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

entropisinden daha az bit dizisi yoktur. Eğer

kaynak metinden rastgele bir kümenin bir harfini çıkarın,

A alfabesini kullanarak, entropi aşağıdaki formülle bulunur:

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

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

bazı C harflerinin oluşumu. Eğer oluşum sıklığı p(c)'yi tahmin etmek için kullanılıyorsa

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

H(S) makalesi, alınan bir dizinin öz entropisini belirtmek için kullanılacaktır.

statik kaynak.

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

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

sürekli düzen içinde olmak. Düzenin ortadan kaldırılmasına yol açar

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

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

genişletme, yerel olarak uyarlanmış bir sıkıştırma algoritmasına yol açar;

optimum sıkıştırmayı sağlayamasa da oldukça basit ve hızlıdır.

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

zaman içinde optimal ve yaklaşık olarak optimal.

ÖNEK KODLARI.

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

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

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

daha az sıklıkta - uzun. Yoğunlaştırılmış metinde kullanılan kodlara uyulmalıdır

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

başka herhangi bir kodun öneki.

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

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

4 harfli bir alfabe için önek. Bir harfin önek kodu şu şekilde okunabilir:

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

ve 1 - doğru. Huffman kod ağacı, her birinin ağırlık eşitlediği bir ağaçtır.

yaprak, kaynak metinde harfin geçiş sıklığına eşit bir ağırlığa sahiptir ve

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

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

Sıradan Huffman kodları, oluşma sıklığı hakkında önceden bilgi gerektirir.

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

harf frekans değerleri elde etmek için, diğeri sıkıştırmayı kendisi gerçekleştirmek için. İÇİNDE

Daha sonra, bu frekansların değerleri sıkıştırılmış metnin kendisi ile birleştirilmelidir.

gelecekte konuşlandırılmasını sağlar. Uyarlanabilir sıkıştırma devam ediyor

çünkü bir adımda kaynak metnin her harfi için kullanılan koda bağlıdır.

onun dışında alfabenin diğer tüm harflerinin frekanslarında. Etkili olmanın temelleri

uyarlanabilir Huffman kodu uygulamaları Gallagher tarafından ortaya kondu, Knuth yayınladı

böyle bir algoritmanın pratik versiyonu ve Witter onu geliştirdi.

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

genellikle optimum statik Huffman koduna göre kaynak mektubu

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

H'den düz metin harfi başına bir bit içinde yer alır (buna ulaşırlar)

yalnızca tüm harfler için p(C) = 2) olduğunda sınırlayın. Sıkıştırma algoritmaları var

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

sabit uzunlukta bir arşivden sözcükleri kaynak metin satırlarına atar

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

kaynak mektupları bile bir bitin kesirleri.

Önek kodlarına uzantı uygulayın.

Genişleyen ağaçlar ilk olarak 1983'te ve daha ayrıntılı olarak tanımlandı.

1985'te düşünüldü. Başlangıçta, bir tür kendi kendini dengeleyen araç olarak anlaşıldılar.

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

öncelik kuyruklarının en hızlı uygulaması. Genişleyen ağacın düğümü ise

mevcut, genişletilmiştir. Bu, kullanılabilir düğümün şu anlama gelir:

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

yeni sağ alt ağaç. Genişleme, ağacı eskisinden çaprazlayarak elde edilir.

yerel değişiklikler yaparken hedef düğüme kök, yani fiyat

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

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

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

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

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

sabit bir faktörle birbirinden farklılık gösterir, yeterince fark edilir

uzun erişim serisi. Huffman ağacı bir örnek olduğundan

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

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

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

Başlangıçta açıklandığı gibi, uzantı depolayan ağaçlara uygulanır.

veriler yapraklarda değil dahili düğümlerdedir. Önek kodlarının ağaçları hepsini taşır

verileri sadece yapraklardadır. Bununla birlikte, adı verilen bir uzantı seçeneği vardır.

önek kod ağacına uygulanabilen yarı uzantı. Onunla, hedef

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

bunun yerine, kökten hedefe giden yol yarıya indirilir. Yarım genişleme ulaşır

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

eklenti.

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

boyunca uzanan doğrudan yolun aksine, uzantılar ve yarı uzantılar daha karmaşık hale gelir

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

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

A düğümü, birbirini takip eden her bir dahili çifti değiştirmektir

kökten yaprak düğüme giden yolun uzunluğunun bir sonucu olarak diğer düğümler

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

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

hariç tutulur (w ve y düğümleri).

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

önek isteğe bağlıdır. Yalnızca kod işlemlerinde önemlidir

önek, sıkıştırma rutini tarafından kullanılan ağacın tam bir eşleşmesidir

dağıtım prosedürü tarafından kullanılan ağaç. Herhangi bir değişikliğe izin verilir

Ardışık harfler arasında, yalnızca şu durumlarda gerçekleştirilir:

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

Sözlük düzeni için destek eksikliği, uygulamayı büyük ölçüde basitleştirir

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

Amirim ve ben görüntü işleme üzerine kısa bir monografi hazırlıyoruz. Habra topluluğu mahkemesine görüntü sıkıştırma algoritmaları hakkında bir bölüm sunmaya karar verdim. Bir bölümün tamamını bir gönderiye sığdırmak zor olduğundan, onu üç gönderiye ayırmaya karar verdim:
1. Veri sıkıştırma yöntemleri;
2. Kayıpsız görüntü sıkıştırma;
3. Kayıplı görüntü sıkıştırma.
Serinin ilk yazısını aşağıdan okuyabilirsiniz.

Şu anda, koşullu olarak iki büyük gruba ayrılabilen çok sayıda kayıpsız sıkıştırma algoritması vardır:
1. Akış ve sözlük algoritmaları. Bu grup, RLE (çalışma uzunluğu kodlaması), LZ*, vb. familyalarının algoritmalarını içerir. Bu grubun tüm algoritmalarının bir özelliği, kodlamanın mesajdaki sembollerin sıklığı hakkında bilgi değil, diziler hakkında bilgi kullanmasıdır. daha önce karşılaştı.
2. İstatistiksel (entropi) sıkıştırma için algoritmalar. Bu algoritma grubu, bir mesajda farklı karakterlerin meydana geldiği eşit olmayan frekansları kullanarak bilgileri sıkıştırır. Bu grubun algoritmaları, aritmetik ve önek kodlama algoritmalarını içerir (Shannon-Fanno, Huffman, sekant ağaçları kullanılarak).
Bilgi dönüştürme algoritmaları ayrı bir grup olarak seçilebilir. Bu grubun algoritmaları bilgileri doğrudan sıkıştırmaz, ancak uygulamaları akış, sözlük ve entropi algoritmalarını kullanarak daha fazla sıkıştırmayı büyük ölçüde basitleştirir.

Akış ve Sözlük Algoritmaları

Çalışma uzunluğu kodlaması

Bu algoritmanın ana dezavantajı, tekrarlanmayan karakter dizileri üzerindeki son derece düşük etkinliğidir. Örneğin, "ABABAB" (6 bayt) dizisini düşünürsek, RLE algoritmasını uyguladıktan sonra "1A1B1A1B1A1B" (12 bayt)'a dönüşecektir. Tekrarlanmayan karakterler sorununu çözmek için çeşitli yöntemler vardır.

En basit yöntem aşağıdaki değişikliktir: tekrar sayısını kodlayan bayt, yalnızca tekrar sayısı hakkında değil, aynı zamanda varlığı hakkında da bilgi saklamalıdır. İlk bit 1 ise sonraki 7 bit karşılık gelen karakterin tekrar sayısını, ilk bit 0 ise sonraki 7 bit tekrarsız alınacak karakter sayısını gösterir. Bu değişikliği kullanarak "ABABAB" kodlarsak, "-6ABABAB" (7 bayt) elde ederiz. Açıkçası, önerilen teknik, RLE algoritmasının tekrar etmeyen karakter dizileri üzerindeki etkinliğini önemli ölçüde artırabilir. Önerilen yaklaşımın uygulanması Liste 1'de gösterilmektedir:

1. tip
2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: boolean ;
4. MatchCount: kısa;
5. EncodedString: TRLEEncodedString;
6. N, i: bayt;
7. başlamak
8. N:=0;
9. SetLength(EncodedString, 2 * uzunluk(InMsg) ) ;
10. uzunluk(InMsg) >= 1 yaparken
11. başlamak
12. MatchFl : = (uzunluk(InMsg) > 1 ) ve (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. Eşleşme Sayısı := 1 ;
14. süre (MaçSayısı<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount : = MatchCount + 1 ;
16. MatchFl ise o zaman
17. başlamak
18. N: = N + 2;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = sıra (InMsg[ 1 ] ) ;
21. başka
22. başlamak
23. Eşleşme Sayısı ise<>uzunluk(InMsg) sonra
24. MatchCount: = MatchCount-1;
25. N := N + 1 + MatchCount;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. i için := 1 - MatchCount yapmak
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. son ;
30. sil(InMsg, 1 , MatchCount) ;
31. son ;
32. SetLength(EncodedString, N) ;
33. RLEncode := EncodedString;
34. son ;

1. tip
2. TRLEEncodedString = bayt dizisi;
3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. Tekrar Sayısı: kısa;
5. i, j: sözcük;
6. OutMsg: ShortString;
7. başlamak
8. Giden Mesaj := "" ;
9. ben:=0;
10. ben iken< length(InMsg) do
11. başlamak
12. Tekrar Sayısı : = InMsg[i] - 128 ;
13. ben : = ben + 1 ;
14. tekrar sayısı ise< 0 then
15. başlamak
16. TekrarSayı := abs(TekrarSayı) ;
17. j için : = i'den i'ye + RepeatCount - 1 do
18. OutMsg := OutMsg + chr (InMsg[ j] ) ;
19. i := i + Tekrar Sayısı;
20. başka
21. başlamak
22. for j := 1 to RepeatCount do
23. OutMsg := OutMsg + chr (InMsg[ i] ) ;
24. ben : = ben + 1 ;
25. son ;
26. son ;
27. RLEDecode := OutMsg;
28. son ;

1. sabit
2. EOMsg="|" ;
3. işlev BWTEncode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, ben: sözcük;
7. başlamak
8. InMsg := InMsg + EOMsg;
9. N := uzunluk(InMsg) ;
10. ShiftTable[ 1 ] := InMsg;
11. i için := 2 ila N yapmak
12. başlamak
13. LastChar := InMsg[N] ;
14. InMsg : = LastChar + kopya(InMsg, 1 , N - 1 ) ;
15. ShiftTable[i] := InMsg;
16. son ;
17. Sırala(ShiftTable) ;
18. Giden Mesaj := "" ;
19. i için := 1 ila N yapmak
20. GidenMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode := OutMsg;
22. son ;

Onlar. doğrudan dönüştürmenin sonucu "|NNAAAC" dizesi olacaktır. Bu dizinin orijinalinden çok daha iyi olduğunu görmek kolaydır, RLE algoritması tarafından sıkıştırılmıştır, çünkü tekrarlanan harflerin uzun alt dizilerini içerir.
Diğer dönüşümler kullanılarak benzer bir etki elde edilebilir, ancak BWT dönüşümünün avantajı tersine çevrilebilir olmasıdır, ancak ters dönüşüm doğrudan olandan daha karmaşıktır. Orijinal diziyi geri yüklemek için aşağıdaki adımları gerçekleştirmelisiniz:
n*n boyutunda boş bir matris oluşturun; burada n, kodlanmış mesajdaki karakter sayısıdır;
En sağdaki boş sütunu kodlanmış mesajla doldurun;
Tablo satırlarını sözlük sırasına göre sıralayın;
Boş sütunlar olduğu sürece 2-3 adımlarını tekrarlayın;
Satır sonu karakteriyle biten dizeyi döndürür.

Ters dönüşümün uygulanması ilk bakışta zor değildir ve uygulamalardan biri Liste 4'te gösterilmektedir.

1. sabit
2. EOMsg="|" ;
3. işlev BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: ShortString dizisi;
6. N, i, j: sözcük;
7. başlamak
8. Giden Mesaj := "" ;
9. N := uzunluk(InMsg) ;
10. SetLength(ShiftTable, N + 1) ;
11. i için := 0 ila N yapmak
12. ShiftTable[i] := "" ;
13. i için := 1 ila N yapmak
14. başlamak
15. j için := 1'den N'ye yap
16. ShiftTable[j] : = InMsg[j] + ShiftTable[j] ;
17. Sırala(ShiftTable) ;
18. son ;
19. i için := 1 ila N yapmak
20. ShiftTable[ i] [N] = EOMsg ise, o zaman
21. OutMsg := ShiftTable[i] ;
22. sil(OutMsg, N, 1 ) ;
23. BWTDecode := OutMsg;
24. son ;

Yedinci adımda elde edilen tablo sıralandıktan sonra tablodan "|" sembolü ile biten bir satır seçilmesi gerekmektedir. Bunun tek çizgi olduğunu görmek kolaydır. O. BWT dönüşümünü belirli bir örnek üzerinde ele aldık.

Özetle, RLE algoritma grubunun ana avantajının basitlik ve işlem hızı (kod çözme hızı dahil) ve ana dezavantajının tekrarlanmayan karakter kümelerinde verimsizlik olduğunu söyleyebiliriz. Özel permütasyonların kullanılması, algoritmanın verimliliğini artırır, ancak çalışma süresini de (özellikle kod çözme) büyük ölçüde artırır.

Sözlük sıkıştırma (LZ algoritmaları)

Sözlük algoritmasının en basit versiyonu aşağıda açıklanmıştır:
Giriş dizesinde bulunan tüm karakterlerle sözlüğü başlatın;
Kodlanmış mesajın başlangıcıyla eşleşen en uzun diziyi (S) sözlükte bulun;
Bulunan dizinin kodunu verin ve kodlanmış mesajın başından kaldırın;
Mesajın sonuna ulaşılmamışsa bir sonraki karakteri okuyun ve sözlüğe Sc ekleyin, 2. adıma geçin. Aksi takdirde çıkın.

Örneğin, "CUCKOOCOOKOOHOOD" ifadesi için yeni başlatılan bir sözlük Tablo'da gösterilmektedir. 3:

Sıkıştırma işlemi sırasında sözlük, mesajda karşılaşılan dizilerle tamamlanacaktır. Sözlüğün güncellenme süreci Tablo'da verilmiştir. 4.

Algoritma açıklanırken, sözlüğün tamamen dolduğu durumun açıklaması kasıtlı olarak çıkarılmıştır. Algoritmanın varyantına bağlı olarak, farklı davranışlar mümkündür: sözlüğün tamamen veya kısmen temizlenmesi, sözlüğün doldurulmasının durdurulması veya sözlüğün kod kapasitesinde karşılık gelen bir artışla genişletilmesi. Bu yaklaşımların her birinin belirli dezavantajları vardır. Örneğin, sözlük yenilemesinin durdurulması, sözlüğün sıkıştırılmış dizenin başında oluşan ancak daha sonra oluşmayan dizileri sakladığı bir duruma yol açabilir. Aynı zamanda, sözlüğün temizlenmesi, sık kullanılan dizilerin kaldırılmasına neden olabilir. Sözlük doldururken kullanılan uygulamaların çoğu sıkıştırma derecesini takip etmeye başlar ve belirli bir seviyenin altına düştüğünde sözlük yeniden oluşturulur. Ardından, dolduğunda sözlüğü yenilemeyi bırakan en basit uygulamayı ele alacağız.

İlk olarak, sözlüğü yalnızca karşılaşılan alt dizileri değil, aynı zamanda sözlükte saklanan alt dizilerin sayısını da depolayan bir kayıt olarak tanımlıyoruz:

Daha önce karşılaşılan alt diziler, Words dizisinde saklanır ve kodları, bu dizideki alt dizilerin sayılarıdır.
Ayrıca sözlük aramasını tanımlıyoruz ve sözlük işlevlerine ekliyoruz:

1. sabit
2. MAKS_DICT_LENGTH = 256;
3. function FindInDict(D: TDictionary; str: ShortString) : tamsayı ;
4. r: tamsayı
5. ben: tamsayı;
6. fl: boole;
7. başlamak
8. r := - 1 ;
9. D. Kelime Sayısı > 0 ise o zaman
10. başlamak
11. i := D.WordCount ;
12. fl := yanlış ;
13. iken (fl değil) ve (i >= 0 ) yapar
14. başlamak
15. ben := ben - 1 ;
16. fl:=D.Kelimeler[i]=str;
17. son ;
18. son ;
19. fl ise o zaman
20. r :=i;
21. FindInDict := r;
22. son ;
23. prosedür AddToDict(var D: TDictionary; str: ShortString) ;
24. başlamak
25. D.WordCount ise< MAX_DICT_LENGTH then
26. başlamak
27. D.WordCount := D.WordCount + 1 ;
28. SetLength(D.Words , D.WordCount ) ;
29. D. Kelimeler [ D. Kelime Sayısı - 1 ] : = str;
30. son ;
31. son ;

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: KısaDize;
4. D: Sözlük;
5. i, N: bayt;
6. başlamak
7. SetLength(OutMsg, uzunluk(InMsg) ) ;
8. N:=0;
9. InitDict(D) ;
10. while uzunluk(InMsg) > 0 yap
11. başlamak
12. tmpstr := InMsg[ 1 ] ;
13. while (FindInDict(D, tmpstr) >= 0 ) ve (uzunluk(InMsg) > uzunluk(tmpstr) ) yapmak
14. tmpstr : = tmpstr + InMsg[ uzunluk(tmpstr) + 1 ] ;
15. FindInDict(D, tmpstr) ise< 0 then
16. sil(tmpstr, uzunluk(tmpstr) , 1 ) ;
17. OutMsg[N] := FindInDict(D, tmpstr) ;
18. N: = N + 1;
19. sil(InMsg, 1 , uzunluk(tmpstr) ) ;
20. uzunluk(InMsg) > 0 ise, o zaman
21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
22. son ;
23. SetLength(OutMsg, N) ;
24. LZWEncode := OutMsg;
25. son ;

Tek sorun şu durumda mümkündür: henüz sözlükte olmayan bir alt dizinin kodunu çözmek gerektiğinde. Bunun ancak mevcut adımda eklenmesi gereken bir alt dizginin çıkarılması gerektiğinde mümkün olduğunu görmek kolaydır. Ve bu, alt dizginin cSc kalıbını karşıladığı anlamına gelir, yani. aynı karakterle başlar ve biter. Bu durumda cS, önceki adımda eklenen alt dizedir. Ele alınan durum, henüz eklenmemiş bir dizenin kodunu çözmenin gerekli olduğu tek durumdur. Yukarıdakiler göz önüne alındığında, sıkıştırılmış bir dizenin kodunu çözmek için aşağıdaki seçeneği sunabiliriz:

1. function LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: Sözlük;
3. OutMsg, tmpstr: ShortString;
4. ben: bayt;
5. başlamak
6. Giden Mesaj := "" ;
7. tmpstr := "" ;
8. InitDict(D) ;
9. for i := 0 - uzunluk(InMsg) - 1 do
10. başlamak
11. InMsg[i] >= D.WordCount ise, o zaman
12. tmpstr : = D. Sözcükler [ InMsg[ i - 1 ] ] + D. Sözcükler [ InMsg[ i - 1 ] ] [ 1 ]
13. başka
14. tmpstr := D. Sözcükler [ InMsg[ i] ] ;
15. OutMsg := OutMsg + tmpstr;
16. eğer ben > 0 ise
17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. son ;
19. LZWDecode := OutMsg;
20. son ;

Entropi kodlaması

Shannon-Fano Ağaçları ile Kodlama

Kodlama olmadan mesaj 40 bit (her karakterin 4 bit ile kodlanması şartıyla) ve Shannon-Fano algoritması kullanıldığında 4*2+2+4+4+3+3+3=27 bit alacaktır. Mesaj hacmi %32,5 azaldı, ancak bu sonucun önemli ölçüde iyileştirilebileceği aşağıda gösterilecektir.

Huffman Ağaçları ile Kodlama

Shannon-Fano algoritmasıyla aynı örneği ele alalım. Huffman ağacı ve "AAAABVGDEZH" mesajı için alınan kodlar Şekil 1'de gösterilmektedir. 2:

Kodlanmış mesajın boyutunun Shannon-Fano algoritmasından daha az olan 26 bit olacağını hesaplamak kolaydır. Ayrı olarak, Huffman algoritmasının popülaritesi nedeniyle not edilmelidir. şu an Sembol frekanslarının iletimini gerektirmeyen uyarlamalı kodlama da dahil olmak üzere birçok Huffman kodlama çeşidi vardır.
Huffman algoritmasının dezavantajları arasında önemli bir kısım, uygulamanın karmaşıklığıyla ilgili problemlerdir. Frekansları depolamak için gerçek değişken sembollerinin kullanılması, doğruluk kaybıyla ilişkilendirilir, bu nedenle, pratikte genellikle tamsayı değişkenleri kullanılır, ancak, çünkü üst düğümlerin ağırlığı sürekli artıyor, er ya da geç bir taşma meydana geliyor. Bu nedenle, algoritmanın basitliğine rağmen, doğru uygulanması, özellikle büyük alfabeler için bazı zorluklara neden olabilir.

Sekant ağaçları ile kodlama

Ağaç, her düğüm alfabeyi mümkün olan en yakın parçalara bölecek şekilde oluşturulmuştur. Şek. Şekil 3, bir sekant ağacı örneğini göstermektedir:

Genel durumda sekant fonksiyonlarının ağacı, optimum kodlamayı garanti etmez, ancak son derece sağlar yüksek hız düğümlerdeki işlemin basitliği nedeniyle çalışır.

aritmetik kodlama