Veri sıkıştırma hakkında sunum

Bilgisayar sıkıştırma programları kullanan herkes "zip", "implode", "stuffit", "diyet" ve "sıkma" gibi kelimelere aşinadır. Tüm bunlar, sıkıştırma için program adları veya yöntem adlarıdır. bilgisayar bilgisi. Bu kelimelerin değişen derecelerde tercümesi, tutturma, mühürleme, doldurma veya sıkıştırma anlamına gelir. Bununla birlikte, bu kelimelerin olağan, dilsel anlamı veya çevirileri, sıkıştırma sonucunda bilgiye ne olduğunun gerçek doğasını tam olarak yansıtmaz. Aslında, bilgisayar bilgilerini sıkıştırırken hiçbir şey doldurulmaz veya sıkıştırılmaz, yalnızca orijinal verilerde bulunan bazı fazla bilgiler kaldırılır. Artıklık, bilgi sıkıştırma teorisinde merkezi bir kavramdır. Fazla bilgi içeren herhangi bir veri sıkıştırılabilir. Artıklık olmayan veriler sıkıştırılamaz, nokta.

Bilginin ne olduğunu hepimiz çok iyi biliyoruz. Sezgisel olarak, bu bizim için oldukça açıktır, ancak daha çok konunun niteliksel bir algısıdır. Bilgi bize tam olarak tanımlanamayan, niceliği daha az olan varlıklardan biri gibi görünüyor. Bununla birlikte, bilginin nicel olarak çalışıldığı, bilgi teorisi adı verilen bir matematik alanı vardır. Bilgi teorisinin bir diğer önemli başarısı, fazlalığın oldukça titiz bir tanımıdır. Şimdi iki kişilik fazlalık olduğuna dikkat çekerek bu kavramı sezgisel olarak yorumlamaya çalışacağız. basit tipler bilgisayar verileri ve gereksiz olarak kaldırılan veriler nelerdir.

İlk bilgi türü metindir. Metin, bilgisayar verilerinin en önemli biçimidir. Büyük miktar bilgisayar programları ve uygulamalar doğası gereği sayısal değildir; temel bileşenleri metin karakterleri olan verilerle çalışırlar. Bilgisayar yalnızca depolama ve işleme yeteneğine sahiptir. ikili bilgi sıfırlar ve birlerden oluşur. Bu nedenle, metnin her karakteri bir ikili kodla ilişkilendirilmelidir. Modern bilgisayarlar sözde kullan ASCII kodları("asci" olarak telaffuz edilir ve ASCII kelimesinin kendisi " için kısadır" amerikan standardı kod bilgi için Interchange"), daha fazla bilgisayar ve uygulama yeni Unicode kodlarını kullanıyor olsa da. ASCII, her karaktere 8 bitlik bir dizi atandığı sabit uzunluklu bir koddur (kodun kendisi yedi bit kaplar ve sekizinci, orijinal olarak kodun güvenilirliğini artırmak için tasarlanmış bir kontroldür). Sabit uzunlukta bir kod, bilgisayar programlarının çeşitli metinlerin karakterleri üzerinde kolayca çalışmasına izin verdiği için en iyi seçim gibi görünüyor. Öte yandan, sabit uzunluklu bir kod esasen gereksizdir.

Rastgele bir metin dosyasında, her karakterin yaklaşık olarak aynı sayıda ortaya çıkmasını bekleriz. Ancak uygulamada kullanılan dosyaların rastgele olması pek olası değildir. Anlamlı metinler içerirler ve örneğin tipik bir İngilizce metinde "E", "T" ve "A" gibi bazı harflerin "Z" ve "Q" harflerinden çok daha sık meydana geldiği deneyimlerden bilinmektedir. ". Bu, ASCII kodunun neden gereksiz olduğunu açıklar ve fazlalığı ortadan kaldırmanın yollarına da işaret eder. ASCII gereksizdir, çünkü ister sık ​​ister nadiren kullanılmış olsun, her karaktere aynı sayıda bit (sekiz) bağımsız olarak atar. Bu fazlalığı kaldırmak için kodları kullanabilirsiniz. değişken uzunluk, daha sık görülen harflere kısa kodlar atanır ve nadiren oluşan harfler daha uzun kodlar alır. Huffman kodlaması tam olarak bu şekilde çalışır (bkz. § 1.4).

A dosyasının ASCII kodlarını kullandığı ve B'nin bazı değişken uzunluklu kodlar kullanılarak yazıldığı aynı metni içeren iki metin dosyası A ve B düşünelim. B dosyasının A'dan daha küçük olmasını bekliyoruz. O zaman A dosyasının B dosyasına sıkıştırıldığını söyleyebiliriz. Sıkıştırma derecesinin alınan metnin fazlalığına ve kullanılan değişken uzunluklu kodlara bağlı olduğu açıktır. Bazı karakterlerin çok sık geçtiği ve diğerlerinin çok nadiren çok fazla fazlalığa sahip olduğu metin: değişken uzunluklu kodlar uygun şekilde seçilirse iyi sıkıştırılır. Karşılık gelen B dosyasında, sık görülen karakterlerin kodları kısa, nadir karakterlerin kodları ise uzun olacaktır. Uzun kodlar, B dosyasında nadir olacağından sıkıştırma oranını düşüremez. Çoğu B kısa kodlardan oluşacaktır. Öte yandan, rastgele bir metin dosyası, kısa kodlar kullanılarak elde edilen sıkıştırma, uzun kodlar tarafından iptal edileceğinden, ASCII kodlarının değişken uzunluklu kodlarla değiştirilmesinden fayda sağlamaz. Bu özel örnekte, işe yarıyor Genel kural, bu, içinde fazlalık olmadığı için rastgele verilerin sıkıştırılamayacağını belirtir.

Savaş alevleri etrafımızda parlıyor, tartışmalı bir konudurşudur: kimin veri sıkıştırma programı en iyisidir. Ben de katılmaya ve kendi programımı yazmaya karar verdim. Elbette, çıtırdayan, sıkışan, sıkan, sıkan, paketleyen, ezen vb. programları duymuşsunuzdur. Şimdi bir TRASH programı var (çöp kutusuna). TRASH, dosyayı mümkün olan en küçük boyuta sıkıştırır: 0 bayt! Hiçbir şey bir dosyayı TRASH'den daha iyi sıkıştıramaz. Tarih/saat öznitelikleri etkilenmez ve dosya sıfır uzunlukta olduğundan, sabit sürücünüzde hiç yer kaplamaz! Ve TRASH çok hızlıdır. Dosyalarınız mikrosaniyeler içinde buruşacak! Dosya zaten işlenirken ayarlanacak parametrelere bakmak için daha fazla zaman harcayacaksınız. Bu, programımın satış öncesi sürümüdür. Bunu saklayabilir ve deneyimleyebilirsiniz. TRASH'imi ilk kez çalıştırmadan önce dosyalarınızı yedeklemenizi tavsiye ederim, yine de... TRASH'in bir sonraki sürümünde GUI ve kredi kartlarını kabul edin. TRASH C:\PAYROOL\*.* Ve tüm disklerle çalışın Ve AMAÇLA sisteminizin çöp dökümünü engelleyen ilk kişi olun! Hatta programımıza TRASH dosyalarını kurtarmayı öğretmeyi umuyoruz!

İkinci tür bilgisayar verisi sayısallaştırılmış görüntülerdir: fotoğraflar, çizimler, resimler, grafikler vb. Dijital görüntü, piksel adı verilen dikdörtgen renkli noktalar dizisidir. Her piksel bir bilgisayarda şu şekilde temsil edilir: renk kodu. (Bu paragrafın sonuna kadar "piksel" terimi sadece renk kodu için kullanılmıştır.) Kolaylık olması açısından dijital işleme görüntülerde tüm piksellerin aynı boyutta olduğu varsayılır. Bir pikselin boyutu, görüntüdeki renklerin sayısına bağlıdır ve bu genellikle 2'nin kuvvetidir. Farklı renkler içeriyorsa, her piksel bir -bitlik sayıdır.

Dijital görüntülerde iki tür artıklık vardır. İlk tür, bir metin dosyasındaki artıklığa benzer. Rastgele olmayan her görüntüde bazı renkler baskın olabilirken diğerleri nadir olabilir. Bu fazlalık, tıpkı metin dosyalarını sıkıştırırken olduğu gibi, farklı piksellere atanan değişken uzunluklu kodlar kullanılarak kaldırılabilir. Diğer tür artıklık çok daha önemlidir ve piksel korelasyonunun sonucudur. Gözlerimiz resmin etrafında hareket ettiğinde, çoğu durumda komşu piksellerin benzer renklerde olduğunu bulur. Mavi gökyüzünü, beyaz bulutları, kahverengi dağları ve yeşil ağaçları gösteren bir fotoğraf hayal edin. Dağlara bakarken, yakındaki pikseller benzer bir renge sahiptir; hepsinin veya hemen hemen hepsinin farklı kahverengi tonları vardır. Gökyüzünün yakın pikselleri hakkında mavinin farklı tonları olduğunu söyleyebiliriz. Ve sadece dağların gökyüzüyle buluştuğu ufukta, komşu pikseller tamamen farklı renklere sahip olabilir. Bu nedenle, bireysel pikseller tamamen bağımsız değildir. Görüntünün en yakın piksellerinin birbiriyle ilişkili olduğunu söyleyebiliriz. Bu tür bir fazlalık ele alınabilir Farklı yollar. Bu, 3. bölümde ele alınacaktır.

Bir görüntünün sıkıştırılma yönteminden bağımsız olarak, sıkıştırmanın etkinliği öncelikle içerdiği fazlalık miktarına göre belirlenir. Sınırlayıcı durum, tek renkli bir görüntüdür. Bitişik pikseller aynı olduğu için maksimum fazlalığa sahiptir. Böyle bir görüntünün pratik açıdan ilginç olmadığı açıktır, eğer gerçekleşirse, son derece nadirdir. Ancak, herhangi bir sıkıştırma yöntemiyle çok iyi sıkıştıracaktır. Başka bir uç durum, ilişkisiz, yani rastgele piksellere sahip bir görüntüdür. Böyle bir görüntüde, komşu piksellerin rengi genellikle çok farklıdır ve bu görüntünün fazlalığı sıfırdır. Herhangi bir yöntemle sıkıştırılamaz. Rastgele karışık renkli noktalara benziyor ve bu nedenle ilginç değil. Bu tür görüntüleri kaydetmemiz ve işlememiz pek olası değildir ve bunları sıkıştırmaya çalışmanın bir anlamı yoktur.

Aşağıdaki basit gözlem, ifadenin özünü açıklığa kavuşturmaktadır: "Veri sıkıştırma, onlardan fazlalık azaltılarak ve kaldırılarak elde edilir." Ayrıca çoğu dosyanın hiçbir şekilde sıkıştırılamayacağını da açıkça ortaya koyuyor. Dosyalarımızı sürekli sıkıştırdığımız için bu garip görünebilir. Bunun nedeni, çoğu dosyanın rastgele veya rastgeleye yakın olmasıdır ve bu nedenle, hiçbir fazlalık yoktur. Sıkıştırabileceğimiz nispeten az dosya var ve bunlar bizim sıkıştırmak istediklerimiz, bunlar her zaman üzerinde çalıştığımız dosyalar. Fazlalıkları vardır, rastgele değildirler ve bu nedenle yararlı ve ilginçtirler.

iki olsun farklı dosya A ve B, sırasıyla C ve D dosyalarına sıkıştırılır. C ve D'nin de birbirinden farklı olması gerektiği açıktır. Aksi takdirde, orijinal A ve B dosyalarını onlardan geri yüklemek imkansız olurdu.

Bir dosyanın bitlerden oluştuğunu ve onu verimli bir şekilde sıkıştırmak istediğimizi varsayalım. Bu dosyayı örneğin 10 bit olarak sıkıştıran herhangi bir algoritmayı memnuniyetle karşılıyoruz. 11 veya 12 bit sıkıştırma da harika olurdu. Dosyayı yarı boyutuna sıkıştırmak bizim için oldukça tatmin edici olacaktır. Toplam var çeşitli dosyalar boyut . 'den daha büyük olmayan farklı dosyalara sıkıştırılmalıdır. Ancak, bu tür dosyaların toplam sayısı

yani sadece kaynak dosyaları verimli bir şekilde küçülme şansına sahiptir. Sorun, sayının sayıdan önemli ölçüde daha az olmasıdır. İşte aralarındaki ilişkiye iki örnek.

(Yalnızca 100 bitlik bir dosya) için toplam dosya sayısı 'dir ve etkin biçimde sıkıştırılmış dosya sayısı . Ve onların bölümü sadece gülünç derecede küçük bir kesirdir. .

(1000 bitlik bir dosya, yani yaklaşık 125 baytlık bir dosya için), tüm dosyaların sayısı , sıkıştırılmış dosyaların sayısı ise . Onların payı feci şekilde küçük, eşittir .

En ilginç dosyalar en az birkaç bin bayt boyutundadır. Bu tür boyutlar için, etkin bir şekilde sıkıştırılabilir dosyaların oranı o kadar küçüktür ki, bir süper bilgisayarda bile kayan noktalı bir sayı olarak ifade edilemez (sonuç sıfır olacaktır).

Bu örneklerden, HERHANGİ bir dosyayı, hatta önemli bir bölümünü etkili bir şekilde sıkıştırabilecek hiçbir yöntem ve algoritma olmadığı açıkça ortaya çıkıyor. Bir dosyayı sıkıştırmak için, sıkıştırma algoritması önce onu incelemeli, içindeki fazlalığı bulmalı ve sonra onu kaldırmaya çalışmalıdır. Artıklık verinin türüne (metin, grafik, ses vb.) bağlı olduğundan, sıkıştırma yöntemleri bu tip akılda tutularak tasarlanmalıdır. Algoritma en iyi kendi verileriyle çalışacaktır. Bu alanda evrensel yöntemler ve çözümler yoktur.

Giriş bölümünün sonunda, bilgi sıkıştırma alanında kullanılan bazı önemli teknik terimleri hatırlıyoruz.

a) Sıkıştırıcı veya kodlayıcı - "ham" bir kaynak dosyayı sıkıştıran ve çıktıda çok az fazlalık olan sıkıştırılmış bir veri dosyası üreten bir program. Dekompresör veya kod çözücü ters yönde çalışır. Kodlayıcı kavramının çok genel olduğunu ve birçok anlamı olduğunu unutmayın, ancak veri sıkıştırmayı tartıştığımız için, kelime kodu ep kompresör anlamına gelir. Codec terimi bazen bir kodlayıcıya ve bir kod çözücüye atıfta bulunmak için kullanılır.

b) Uyarlanabilir olmayan sıkıştırma yöntemi, sıkıştırılan verilere bağlı olarak algoritmanın işlemlerini, parametrelerini ve ayarlarını değiştirememesi anlamına gelir. Bu yöntem, aynı türdeki verileri en iyi şekilde sıkıştırır. Bunlar, grup 3 ve grup 4 faks sıkıştırma yöntemlerini içerir (bkz. § 1.6). Faks makinelerinde sıkıştırmak için özel olarak tasarlanmıştır ve diğer veri türlerinde düşük performans gösterirler. Buna karşılık, uyarlamalı yöntemler önce ham girdi verilerini test eder ve ardından parametrelerini ve/veya işlemlerini testin sonucuna göre ayarlar. Böyle bir algoritmanın bir örneği, § 1.5'ten Huffman kodlamasıdır. Bazı sıkıştırma yöntemleri, dosyadan ilk geçişte bazı sıkıştırılmış veri istatistikleri toplandığında ve ikinci geçişte birinci aşamada hesaplanan parametreler kullanılarak sıkıştırma yapıldığında iki geçişli algoritmalar kullanır. Bu tür yöntemler yarı uyarlanabilir olarak adlandırılabilir. Sıkıştırma yöntemleri ayrıca yerel olarak uyarlanabilir olabilir; bu, algoritmanın parametrelerini dosyanın yerel özelliklerine göre ayarlama ve bunları giriş verilerinin alanından alanına hareket ederek değiştirme yeteneği anlamına gelir. Böyle bir algoritmanın bir örneği verilmiştir.

c) Kayıpsız/Kayıplı Sıkıştırma: Bazı sıkıştırma yöntemleri kayıplıdır. Bazı bilgiler atlanırsa daha iyi çalışırlar. Böyle bir kod çözücü verileri kurtardığında, sonuç orijinal dosyayla aynı olmayabilir. Sıkıştırılacak veriler grafik, ses veya video olduğunda bu tür yöntemlere izin verilir. Kayıplar küçükse, farkı tespit etmek imkansız olabilir. Ve bir bilgisayar programının metni gibi metinsel veriler, bir bit bilgi bile kaybolursa veya değiştirilirse tamamen kullanılamaz hale gelebilir. Bu tür dosyalar yalnızca kayıpsız yöntemlerle sıkıştırılabilir. (Metin dosyalarıyla ilgili olarak burada dikkat edilmesi gereken iki nokta vardır. (1) Metin dosyası şunları içeriyorsa: kaynak bilgisayar programı, daha sonra, derleyici genellikle onları dikkate almadığından, boşlukların çoğu ondan ağrısız bir şekilde çıkarılabilir. (2) Bir kelime işlemci programı, yazılan metni bir dosyaya kaydettiğinde, yazı tipi bilgilerini de dosyaya kaydeder. Bu tür bilgiler, yazar yalnızca eserinin metnini saklamak isterse de atılabilir).

d) Simetrik sıkıştırma, hem kodlayıcı hem de kod çözücünün aynı temel algoritmayı kullanması, ancak bunu zıt yönlerde kullanmasıdır. Bu yöntem, sürekli olarak aynı sayıda dosyayı sıkıştırıyor ve sıkıştırmasını açıyorsanız anlamlıdır. saat asimetrik yöntem kompresör veya dekompresör önemli bir işlem yapmalıdır iyi iş. Bu tür yöntemlerin de güneş altında yeri vardır, hiç de fena değiller. Sıkıştırma uzun süre boyunca ve dikkatli bir şekilde en karmaşık algoritma kullanılarak yapıldığında ve açma işlemi hızlı ve basit bir şekilde yapıldığında yöntem, arşivlerle çalışırken, sık sık veri çıkarmanız gerektiğinde oldukça haklıdır. Aynısı, mp3 ses dosyalarını oluştururken ve dinlerken de olur. Tersi durum, harici dosyaların sık sık değiştiği ve farklı dosyalarda kaydedildiği durumlardır. yedekler. Yedek verileri çıkarma olasılığı düşük olduğundan, kod çözücü kodlayıcıdan önemli ölçüde daha yavaş olabilir.

e) Sıkıştırma performansı: Sıkıştırma algoritmalarının verimliliğini hesaplamak için birkaç miktar kullanılır.

1) Sıkıştırma oranı formülle belirlenir.

0,6 katsayısı, sıkıştırılmış verilerin %60'ını kapladığı anlamına gelir. orijinal boyut. 1'den büyük değerler çıktı dosyasının girdiden daha büyük olduğunu gösterir (negatif sıkıştırma). Sıkıştırma oranı, girdi dosyasının bir bitini temsil etmek için ortalama olarak sıkıştırılmış bir dosyanın kaç bitinin gerektiğini gösterdiğinden, genellikle bpb (bit başına bit, bit başına bit) cinsinden ölçülür. sıkıştırıldığında grafik görüntüler benzer şekilde bpp değeri (bit per pixel, bit per pixel) belirlenir. Metin bilgilerini sıkıştırmaya yönelik modern verimli algoritmalarda, benzer bir bpc değeri (karakter başına bit, karakter başına bit), yani bir metin harfini saklamak için ortalama olarak kaç bit gerektiği hakkında konuşmak mantıklıdır.

Burada sıkıştırma oranı ile ilgili iki kavramdan daha bahsedilmelidir. Bit hızı terimi, bpb ve bpc'den daha geneldir. Bilgi sıkıştırmanın amacı, verileri en düşük bit hızında temsil etmektir. Bit bütçesi, sıkıştırılmış dosyadaki her bit için ekstra ağırlık anlamına gelir. Hayal etmek sıkıştırılmış dosya boyutun %90'ının kaynak dosyadaki belirli karakterlere karşılık gelen değişken uzunluklu kodlar tarafından işgal edildiği ve kalan %10'luk kısmın dekompresyon sırasında kod çözücü tarafından kullanılacak bazı tabloları depolamak için kullanıldığı. Bu durumda, bit bütçesi %10'dur.

2) Sıkıştırma oranının tersi sıkıştırma faktörü olarak adlandırılır:

Bu durumda 1'den büyük değerler sıkıştırma, 1'den küçük değerler ise genişleme anlamına gelir. Bu faktör çoğu insan için daha doğal bir gösterge gibi görünmektedir: faktör ne kadar büyükse, sıkıştırma o kadar iyi olur. Bu değer, § 4.1.2'de tartışılacak olan seyreklik faktörü ile uzaktan ilişkilidir.

3) Sıkıştırma oranı ifadesi sıkıştırma kalitesini de yansıtır. 60 değeri, sıkıştırma sonucunun orijinal dosyadan %60 daha az olduğu anlamına gelir.

4) bpp değeri, görüntü sıkıştırma algoritmalarının verimliliğini değerlendirmek için kullanılır. Bir pikseli depolamak için ortalama olarak kaç bit gerektiğini gösterir. Bu sayı, sıkıştırmadan önceki değeriyle karşılaştırmak için uygundur.

f) Olasılık modeli. Bu kavram, istatistiksel veri sıkıştırma yöntemlerinin geliştirilmesinde çok önemlidir. Sıklıkla, sıkıştırma algoritması, olasılıklı bir model ve kompresörün kendisi olmak üzere iki bölümden oluşur. Bir sonraki nesneyi (bit, bayt, piksel vb.) sıkıştırmaya başlamadan önce bir olasılık modeli etkinleştirilir ve bu nesnenin olasılığı hesaplanır. Bu olasılık ve nesnenin kendisi, sıkıştırma sırasında alınan bilgileri kullanan sıkıştırıcıya bildirilir. Olasılık ne kadar yüksek olursa, sıkıştırma o kadar iyi olur.

İşte siyah beyaz bir görüntü için basit bir model örneği. Böyle bir görüntünün her pikseli tek bir bittir. Algoritmanın 1000 pikseli okuyup sıkıştırdığını ve 1001. pikseli okuduğunu varsayalım. Bir pikselin siyah olma olasılığı nedir? Model, halihazırda okunan veri dizisindeki siyah piksellerin sayısını basitçe sayabilir. 350 siyah piksel varsa, model 1001. piksele bir olasılık atar. siyah ol. Bu olasılık, bir piksel (siyah veya beyaz) ile birlikte kompresöre iletilir. Ana nokta, kod çözücünün 1001. pikselin olasılığını da kolayca hesaplayabilmesidir.

g) Alfabe kelimesi, sıkıştırılmış verilerdeki karakter kümesi anlamına gelir. Alfabe, 128 karakterden 0 ve 1 olmak üzere iki karakterden oluşabilir. ASCII karakterleri, her biri 8 bitlik 256 bayt veya diğer karakterlerden.

h) Her sıkıştırma algoritmasının yeteneklerinin sınırlamaları vardır. Hiçbir algoritma herhangi bir dosyayı verimli bir şekilde sıkıştıramaz. Daha önce gösterildiği gibi, herhangi bir algoritma, rastgele olmayan dosyaların yalnızca küçük bir bölümünü verimli bir şekilde sıkıştırabilir. Rastgele veya yakının büyük çoğunluğu rastgele dosyalar sıkıştırılamaz.

Son sonuç biraz cesaret kırıcı görünüyor, ancak umarım okuyucunun bu kitabı bir iç çekerek kapatmasına ve diğer umut verici arayışlara dönmesine neden olmaz. Bu şaşırtıcıdır, ancak tüm olası boyut dosyaları arasında sıkıştırmak istediğimiz dosyalar iyi sıkıştırılacaktır. Kötü sıkıştıranlar rastgeledir ve bu nedenle bizim için ilgi çekici ve önemsizdir. Bunları sıkıştırmayacağız, iletmeyecek veya saklamayacağız.

Düğünden önceki harika günler, sıkıcı bir kitaba canlı bir giriş gibidir.
— Wilson Mizner

Arşiv - Dosya Sıkıştırma: Nasıl çalışır? - Dergi "Bilgisayar"

Merhaba! Acemi bir kullanıcıya dosyaların her türlü arşivleyici tarafından nasıl sıkıştırıldığını açıklayabilir misiniz? En azından genel anlamda. Ve bunun nasıl olabileceğini hayal bile edemiyorum.

canlı

Çok doğru Vitaly, hayal etmesi o kadar kolay değil, özellikle de algoritmayı bilmiyorsan. Ancak "Bilgisayar" dergisinin okuyucuları şanslıydı;), çünkü bir zamanlar veri sıkıştırma algoritmalarına çok ilgi duyuyordum ve bir programcı olarak kendi arşivleyicimi yazmaya bile çalıştım.

Veri sıkıştırma, hacimlerini azaltmak için gerçekleştirilen algoritmik bir veri dönüşümüdür. Daha fazlası için geçerlidir rasyonel kullanım veri depolama ve iletim cihazları. Sıkıştırma işlemi ayrıca veri paketleme veya sıkıştırma olarak da adlandırılır. Ters prosedüre veri kurtarma (açma, açma) denir.

Sıkıştırma, orijinal verilerde bulunan fazlalığın ortadan kaldırılmasına dayanır. Fazlalığın en basit örneği, metindeki parçaların tekrarlanmasıdır (örneğin, doğal kelimeler veya makine dili).

O halde basit bir örnekle başlayalım. Diyelim ki bir metin satırı içeren bir metin dosyamız var:

AAAGGDEEEEEEZHOOUUKKKIII

Metin oldukça garip, görüyorsunuz, ama şimdi onu sıkıştıracağız ve bizden daha az yer kaplayacak. Sıkıştırmanın temel ilkesi çok basittir ve şu şekilde özetlenebilir: ardışık olarak yinelenen karakterlerin her bir kombinasyonu, böyle bir karakter ve tekrarlarının sayısı ile değiştirilir. Onlar. sıkıştırılmış formdaki kaynak metnimiz şöyle görünecektir:

A3G2D1E4Zh2U3K4I3

Böylece 22 karakter yerine 16 karakter elde etmiş olduk. Tabii ki, orijinal metinimiz gibi metinler oldukça nadirdir, içindeki saçmalıktan bahsetmiyorum bile. Ama sonuçta sıkıştırılan dosyalar sadece metin dosyaları değil aynı zamanda her türlü resim, müzik, video, programdır.

Bu örnek oldukça basittir ve arşivleyicilerin genellikle sıkıştırırken gösterdiği verimliliği yansıtmaz. Böylece, arşivciler bir kural olarak dosyaları 2-10000 kez sıkıştırabilse de, 22/16 = 1.375 kez bir sıkıştırma elde ettik. Her şey dosyadaki bayt değerlerinin tekrarlanabilirliğine bağlıdır.

arşivciler nelerdir

Örneğin, unutulmaz MS-DOS günlerinde ARJ, PKZIP, HA, RAR, ARC, ACE arşivleyicileri ve LZEXE ve PKLITE program paketleyicileri vardı. Daha sonra işletim sistemi Windows WinAce, WinZIP, WinRAR, 7Zip ve bildiğim UPX paketleyicisi tarafından oluşturuldu.

Sıkıştırma kayıplı veya kayıpsız olabilir. Kayıpsız sıkıştırma, orijinal verileri bit doğruluğu ile geri yüklemenizi sağlar. Bu sıkıştırma, metinleri, programları, çeşitli verileri bir bölmede paketlemek için kullanılır ve yukarıda listelenen tüm arşivleyiciler tarafından gerçekleştirilir.

Kayıplı sıkıştırma çağrılabilir uyarlanabilir sıkıştırma, ve bu tür veriler kayıp olmadan çok az sıkıştırıldığından (sadece yaklaşık 2 kata kadar) görüntüleri, videoları ve sesi paketlemek için kullanılır.

Kayıplı sıkıştırma sayesinde, veri miktarında çoklu bir azalma elde etmek mümkündür ve sıkıştırılmış verileri görüntülerken, bir kişi orijinal arasındaki farkı neredeyse hiç hissetmeyecektir.

Ne kadar farklı dosya sıkıştırılır

Metin

Nitekim, örneğin, metin dosyalarıçok sıkı bir şekilde sıkıştırılabilir. Örneğin, Arkady ve Boris Strugatsky'nin 354.329 bayt boyutunda "Tanrı olmak zor" kitabı WinRAR arşivleyici 140.146 bayta sıkıştırılmış, yani 2.5 kez.

programlar

Program dosyaları da sıkıştırılabilir. Aynı zamanda, sıkıştırma hem diskte daha yoğun depolama hem de programın bir program olarak kaldığı, ancak başladığında kendini açtığı sıkıştırma içindir.

Bunun için UPX ve diğerleri gibi program paketleyiciler var. Metin düzeltici 524.288 bayt boyutundaki Superpad.exe, UPX paketleyici tarafından 179.200 bayta (2,9 kez) sıkıştırılır ve yine de bir program olarak bağımsız olarak çalışabilir.

Görüntüler

Bütün bir makale, hatta birden fazla makale, bu verileri sıkıştırma yöntemlerini açıklamaya ayrılabilir. Gerçek şu ki, bayt bayt sıkıştırılırsa görüntünün kendisi çok kötü bir şekilde sıkıştırılır. Ve yine de başarılı oluyor. Özellikle resimde çok fazla düz arka plan varsa.

İlk görüntü sıkıştırma algoritmalarından biri yukarıda bahsettiğim RLE algoritmasıydı. PCX görüntü depolama formatında kullanılır. RLE kayıpsız bir sıkıştırma algoritmasıdır. Ancak bazı durumlarda veri miktarında azalmaya değil, artmasına neden olabilir.

Bu nedenle, görüntü sıkıştırma için LZW bitsel sıkıştırma algoritması önerildi ve halen kullanılmaktadır. Algoritmanın kendisi zaten RLE'den çok daha verimlidir ve ayrıca kayıp sağlamaz. Ancak bir renk paletine sahip görüntüler için kullanıldığından, paleti uyarlayarak ve optimize ederek (yoğunlaştırarak) sıkıştırma verimliliğinde önemli bir artış elde edilebilir.

Pirinç. 1. BMP formatında güzel kurbağa

Karşılaştırma için, 799x599 piksel (nokta) çözünürlüğe sahip güzel bir kurbağayı (Şekil 1) alalım ve içine kaydedelim. farklı formatlar görüntü depolama Dosyaları alalım:

kurbağa.bmp - boyut 1 437 654 bayt ve aslında resim baytlarını Genişlik x Yükseklik x piksel başına 3 bayt + format başlığı biçiminde aldığından sıkıştırma ve kalite kaybı yok bmp dosyası Gerçek renk kalitesine göre (24 bit/piksel). Onlar. her nokta, her biri bir bayt kaplayan üç RGB bileşeni (Kırmızı-Kırmızı, Yeşil-Yeşil ve Mavi-Mavi) ile temsil edilir.

kurbağa24.png - 617.059 bayt, 2.33 kat sıkıştırma ve kayıpsız - PNG-24 formatının ana özelliği. BMP ve PNG verileri hemen hemen aynıdır.

Pirinç. 2. Frog_256colors.gif dosyası

kurbağa_256colors.gif - 261.956 bayt (Şekil 2), 5.48 kat kayıplı sıkıştırma, temel palet 256 renk (8 bit/piksel). BMP'de bu dosya ile orijinal arasındaki farkı yakalamak oldukça zordur, tıpkı "On farkı bul" oyunundaki gibi.

Pirinç. 3. Dosya kurbağa_64colors.gif

kurbağa_64colors.gif - 187.473 bayt (Şekil 3), 7.67 kat kayıplı sıkıştırma, temel palet 64 renge (6 bit/piksel) sıkıştırılmış. Ve burada renkler zaten solmuş, ancak görüntü orijinaline oldukça benziyor. Bu, özellikle kurbağanın gözüne bakarsanız fark edilir.

JPEG

Görüntülerin sıkıştırılması ve saklanmasında özel bir yer tutar jpeg formatı. Bu nedenle, ona özellikle dikkat etmek istiyorum. JPEG algoritması, parlaklık ve renkte yumuşak geçişlerle gerçekçi sahneler içeren fotoğrafları ve resimleri sıkıştırmak için en uygundur. JPEG en yaygın olarak dijital fotoğrafçılıkta ve interneti kullanarak görüntüleri depolamak ve iletmek için kullanılır.

Öte yandan, JPEG, komşu pikseller arasındaki keskin kontrastın gözle görülür yapaylıklara yol açtığı çizimleri, metinleri ve işaret grafiklerini sıkıştırmak için çok az kullanışlıdır. Bu tür görüntüleri TIFF, GIF, PNG veya RAW gibi kayıpsız formatlarda kaydetmeniz önerilir.

JPEG (diğer sıkıştırma yöntemlerinin yanı sıra), çok aşamalı işleme sırasında görüntüleri sıkıştırmak için uygun değildir, çünkü ara işleme sonuçları her kaydedildiğinde görüntülerde bozulmalar ortaya çıkacaktır.

JPEG, astronomik veya tıbbi görüntülerin sıkıştırılması gibi minimum kaybın bile kabul edilemez olduğu durumlarda kullanılmamalıdır. Bu gibi durumlarda, JPEG standardı (maalesef çoğu popüler codec bileşeni tarafından desteklenmez) veya standart tarafından sağlanan Kayıpsız JPEG sıkıştırma modu jpeg sıkıştırma-LS.

JPEG sıkıştırma algoritmasının açıklaması oldukça karmaşıktır, bu nedenle isteyen herkes http://el-izdanie.narod.ru/gl4/4-3.htm bağlantısından onunla tanışabilir. Peki, karşılaştırma için orijinal resmimizi şununla sıkıştıralım: farklı seviyeler nitelikler:

kurbağa %100.jpg - 216.168 bayt, 6.65 kat sıkıştırma, sözde %0 kayıp, yani. %100 görüntü kalitesi, ama buna bile güvenmezdim. İnanın bana, farklılıklar var, ancak gözle kesinlikle ayırt edilemezler.

kurbağa60%.jpg - 85.910 bayt, 16.7 kat sıkıştırma, yani resim kalitesi %60, ancak resim yine aynı görünüyor, ancak tek tip bir arka plana veya ince ayrıntılara sahip alanlara yakından bakarsanız, lekeli veya kare monokrom segmentler şeklinde artefaktlar görebilirsiniz.

kurbağa20%.jpg - 36.426 bayt, 39,5 kat sıkıştırma, resim kalitesi Orijinal görüntünün %20'si, ancak resim deneyimsiz gözleri hala yanıltabilir, ancak tek renkli açısal bölümler tek tip bir arka planda açıkça görülebilir ve ince ayrıntılar tamamen net çizgisini kaybetti.

MPEG

Bu, en eski ve en yaygın video depolama biçimlerinden biridir. Birkaç kez modernize edildi. Ancak basitleştirilmiş bir formda, algoritmanın JPEG sıkıştırmasına çok benzer olduğunu söyleyebiliriz, ancak videonun ilk karesinin her zaman orijinal ve orijinal olduğu ve sonraki karelerin yalnızca önceki ile arasındaki farkı depoladığı gerçeğini dikkate alarak. sonraki kareler. Bu nedenle, sonraki her çerçeve paketin açılması açısından tahmin edilebilir (Şekil 4 ve 5).

Pirinç. 4. Videonun orijinal kareleri

Pirinç. 5. Hareket dengeleme algoritmaları uygulamadan kareler arası fark

En iyilerinden biri güçlü teknolojiler, sıkıştırma derecesini artırmanıza izin verir - bu hareket telafisidir. Herhangi bir modern video sıkıştırma sisteminde, akıştaki sonraki kareler, sıkıştırma oranını artırmak için önceki karelerdeki alanların benzerliğini kullanır.

Ancak, çerçevedeki (veya kameranın kendisinin) herhangi bir nesnenin hareketi nedeniyle, komşu çerçevelerin benzerliğinin kullanımı eksikti. Hareket dengeleme teknolojisi, önceki kareye göre kaydırılmış olsalar bile benzer alanları bulmanızı sağlar.

Hareket Telafisi, video verilerinin işlenmesinde ve sıkıştırılmasında kullanılan ana algoritmalardan biridir. Algoritma, bir video dizisindeki komşu karelerin benzerliğini kullanır ve hareket vektörlerini bulur. ayrı parçalar görüntüler (genellikle 16x16 ve 8x8 bloklar).

Kompanzasyonun kullanılması, çerçevelerin eşleşen parçaları biçimindeki fazlalığı ortadan kaldırarak sıkıştırma sırasında sıkıştırma oranını tekrar tekrar artırmayı mümkün kılar. Yalnızca sıkıştırma için değil, aynı zamanda video filtreleme, kare hızını değiştirme vb. için de kullanılır.

Hemen hemen her videoda, bitişik kareler benzerdir, ortak nesneler, bir kural olarak, birbirine göre yer değiştirir. Ve videoyu, nesnelerin tekrar tekrar kodlanmayacağı, sadece bazı yer değiştirmelerinin tanımlanacağı şekilde kodlamayı istemek oldukça doğaldır.

Bu durumda, görüntü sözde anahtar karelere bölünür - bunlar birkaç saniye boyunca arka arkaya giden kare gruplarıdır. Bu tür ana karelerin süresini kontrol ederek sıkıştırma etkin bir şekilde kontrol edilebilir.

Örneğin, filmin konusu dinamik değilse, ana karelerin süresi birkaç saniye olabilir. Film hızlı hareket eden sahneler içeriyorsa, böyle anlarda ana karelerin süresi kısaltılabilir ve hızla değişen bir görüntünün sıkıştırılması daha verimli olacaktır.

Ana kareler ayrıca medya oynatıcılarda geri sarmayı basitleştirir ve hızlandırır, çünkü her bir ana karenin başlığı bir sonraki ana karenin başlangıcına bir bağlantı (video dosyasının başlangıcına göre bayt cinsinden ofset) içerir.

Ses ve müzik

Ses ve müzik kayıpsız veya kayıplı olarak WAV formatında saklanabilir. Örneğin, WAV formatı (Windows PCM) sıkıştırılmaz ve depolanır. ses sinyali tabiri caizse orijinalinde.

WAV formatı (ACM Waveform) aslında bir kapsayıcıdır ve MPEG katman 3 algoritması kullanılarak sıkıştırılmış sesi depolayabilir veya başka birçok OGG, FLAC, vb. format olmasına rağmen MP3 formatında müzik depolayabilir.

Ses sıkıştırma algoritmaları hakkında konuşacak zamanım yok, ayrıca dergimizin başlarında bu konuyla ilgili harika bir makale vardı.

slayt 2

• Çeşitli depolama ortamlarında verilerin uzun süreli depolanması için
• İletişim kanalları üzerinden veri aktarımı için

slayt 3

Veri yedekleme

• Verilerin çoğu gereksiz
• Artıklık, bilginin algılanmasını ve işlenmesini iyileştirir
• Depolama sırasında yedeklilik azalır
• Video bilgisi en yüksek fazlalığa sahiptir, ardından grafik, ses ve metin bilgisi en düşük fazlalığa sahiptir.

slayt 4

Sıkıştırma yöntemleri

• Kısmi bilgi kaybı ile: Görüntü, video ve ses kodunun sıkıştırılmasıyla üretilir.Bu olasılık, insan görme ve duymanın öznel yetenekleri ile ilişkilidir.
• Bilgi kaybı olmadan: - tek tip olmayan sembolik kodun kullanımı; - tekrar eden kod parçalarının tespiti.

slayt 5

Kısmi kayıp ile

• Bir pikselin parlaklığı, görme üzerinde renginden daha önemli bir etkiye sahiptir. Bu nedenle, renk kodlarının her piksel için değil, bir, iki vb. sonra saklanması nedeniyle video kodu miktarı azaltılabilir. raster pikseller. Bu boşluklar ne kadar büyük olursa, video verileri o kadar fazla sıkıştırılır, ancak görüntü kalitesi bozulur.
• Video filmlerini kodlarken - dinamik bir görüntü, görme eylemsizliğinin özelliği dikkate alınır. Hızlı hareket eden film klipleri, statik karelerden daha az ayrıntıyla kodlanabilir.
• Sıkıştırmak en zoru ses kodu. Ayrıca insan işitme duyusunun psikofizyolojik özelliklerini kullanır. İşitme duyumuzun hangi doğal ses harmoniklerine daha duyarlı olduğu ve hangisine - daha az olduğu dikkate alınır. Zayıf algılanabilir harmonikler matematiksel işlemlerle filtrelenir. Ses titreşimlerinin genliği ile ses hacminin kulağımız tarafından algılanması arasındaki doğrusal olmayan ilişki dikkate alınarak sıkıştırma da kolaylaştırılmıştır.

slayt 6

• İçeriğin bir kısmının resmi kaybının tüketici özelliklerinin kaybına yol açmadığı ve yüksek derecede sıkıştırma sağladığı veri türleri için kullanılır.
• Örnekler: MPG video, MP3 ses, JPG resimleri.

Slayt 7

Kayıp Yok - "Geri çevrilebilir"

• Metinler, veritabanları ve yukarıda bahsedilen tüm diğer türler için geçerlidir.
• Örnek: resimler - GIF, TIF, PCX, video - AVI, her türlü veri - ZIP, ARJ, RAR, vb.

Slayt 8

Arşivler

• Arşiv, bir veya daha fazla sıkıştırılmış dosya içeren bir dosyadır.
• Arşiv dosyası uzantısı, arşivleyici programına bağlıdır.
• Arşivleyici - arşiv oluşturma ve okuma programları Örnek: WinRar, WinZip, WinArj.

Slayt 9

Arşivler amaç için kullanılır

• medyanın verimliliğini artırın - bir medyaya daha fazla bilgi koyun
• sıkıştırılmış bir biçimde ayrı ortamlarda saklanacak değerli verilerin yedek kopyalarını oluşturmak.
• verileri bir parolayla yetkisiz erişime karşı koruyun - belgeler açılmaz bile
• örneğin, diskten diske veri kopyalama hızını artırın, elektronik sayfalar birçok küçük grafik dosyası içeren
• kullanıcı tarafından değiştirilen verilerin hızlı kurtarılması
• iletişim kanalları üzerinden bilgi aktarımı
• verileri paketlere bölme

Slayt 10

Arşivleyicilerin olanakları

Bir arşivin içeriğini görüntüleme

Veri bütünlüğü kontrolü

Arşivi açma

Hasarlı bir arşivi geri yükleme

Ayar koruması

Arşive dosya ekleme

Çok ciltli arşivlerin oluşturulması

Kendiliğinden açılan arşivler oluşturma

Yanlışlıkla değişikliğe karşı kilitle

slayt 11

kendiliğinden açılan

(SFX, SelF-eXtracting'den), yürütülebilir bir modülün eklendiği bir arşivdir. Bu modül, arşivi aşağıdaki gibi çalıştırarak dosyaları çıkarmanıza olanak tanır. düzenli program. Bu nedenle, bir SFX arşivinin içeriğinin çıkarılması ek bir işlem gerektirmez. harici programlar. SFX arşivleri, bir arşivi birine aktarmanız gereken ancak alıcının paketi açmak için uygun arşivleyiciye sahip olduğundan emin olmadığınız durumlarda kullanışlıdır.

Plan:

Tanıtım

• 1 Veri Sıkıştırma Prensipleri
• 2 Sıkıştırma algoritmalarının özellikleri ve uygulanabilirliği
  • 2.1 Sıkıştırma oranı
  • 2.2 kayıpların kabulü
  • 2.3 Algoritmaların sistem gereksinimleri
• 3 Veri sıkıştırma algoritmaları bilinmeyen biçim
Edebiyat

Tanıtım

Veri sıkıştırma(İngilizce) Veri sıkıştırma) hacimlerini azaltmak için gerçekleştirilen algoritmik bir veri dönüşümüdür. Depolama ve veri aktarım cihazlarının daha rasyonel kullanımı için kullanılır. Eş anlamlılar - veri paketleme, sıkıştırma, sıkıştırma kodlaması, kaynak kodlaması. Ters prosedüre veri kurtarma (açma, açma) denir.

Sıkıştırma, orijinal verilerde bulunan fazlalığın ortadan kaldırılmasına dayanır. Fazlalığın en basit örneği, metindeki parçaların tekrarlanmasıdır (örneğin, doğal kelimeler veya makine dili). Bu tür fazlalık, genellikle, tekrar eden dizinin, uzunluğunun bir göstergesi ile önceden kodlanmış bir parçaya bir referansla değiştirilmesiyle ortadan kaldırılır. Başka bir fazlalık türü, sıkıştırılan verilerdeki bazı değerlerin diğerlerinden daha sık meydana gelmesinden kaynaklanmaktadır. Veri miktarını azaltmak, sıklıkla meydana gelen verileri kısa kod sözcükleri ile ve nadir olanları uzun olanlarla (entropi kodlaması) değiştirerek elde edilir. Artıklık özelliğine sahip olmayan verileri sıkıştırma (örneğin, rastgele sinyal veya gürültü, şifreli mesajlar), kayıp olmadan temelde imkansızdır.

1. Veri sıkıştırma ilkeleri

Herhangi bir sıkıştırma yönteminin merkezinde bir veri kaynağı modeli veya daha doğrusu bir artıklık modeli bulunur. Başka bir deyişle, veri sıkıştırma, ne tür verilerin sıkıştırıldığına ilişkin bazı ön bilgileri kullanır. Kaynak hakkında böyle bir bilgi olmadan, mesajın boyutunu küçültecek dönüşüm hakkında herhangi bir varsayımda bulunmak imkansızdır. Artıklık modeli statik olabilir, sıkıştırılmış mesajın tamamı için değiştirilmemiş veya sıkıştırma (ve kurtarma) aşamasında oluşturulmuş veya parametreleştirilmiş olabilir. Girdi verilerine dayalı olarak bilgi artıklığı modelini değiştirmeye izin veren yöntemlere uyarlamalı denir. Uyarlanabilir olmayanlar, genellikle iyi tanımlanmış ve değişmez özelliklere sahip verilerle çalışmak için kullanılan oldukça özel algoritmalardır. Yeterince evrensel algoritmaların büyük çoğunluğu bir dereceye kadar uyarlanabilir.

Tüm veri sıkıştırma yöntemleri iki ana sınıfa ayrılır:

• kayıpsız sıkıştırma
• kayıplı sıkıştırma

Kayıpsız sıkıştırma kullanıldığında, Tam iyileşme orijinal veriler, kayıplı sıkıştırma, kurtarılan verilerin daha fazla kullanılması açısından genellikle önemsiz olan bozulmalara sahip verileri kurtarmanıza olanak tanır. Kayıpsız sıkıştırma genellikle metin verilerini, bilgisayar programlarını daha az sıklıkla aktarmak ve depolamak için kullanılır - ses ve video verilerinin hacmini azaltmak için, dijital fotoğraflar vb., bozulmaların kabul edilemez veya istenmeyen olduğu durumlarda. Kayıpsız sıkıştırmadan çok daha verimli olan kayıplı sıkıştırma, tipik olarak, bu tür bir azaltmanın öncelikli olduğu ve orijinal ve geri yüklenen verilerin tam eşleşmesinin gerekli olmadığı durumlarda ses, video ve dijital fotoğrafların miktarını azaltmak için kullanılır.

2. Sıkıştırma algoritmalarının özellikleri ve uygulanabilirliği

2.1. Sıkıştırma oranı

Sıkıştırma oranı, sıkıştırma algoritmasının ana özelliğidir. Orijinal sıkıştırılmamış veri hacminin sıkıştırılmış veri hacmine oranı olarak tanımlanır, yani:

k = SÖ / S C ,

nerede k- Sıkıştırma oranı, S o ilk veri miktarıdır ve S c - sıkıştırılmış dosyaların hacmi. Bu nedenle, sıkıştırma oranı ne kadar yüksek olursa, algoritma o kadar verimli olur. Belirtilmelidir:

• Eğer k= 1 ise, algoritma sıkıştırma yapmaz, yani çıkış mesajı hacim olarak girişe eşittir;
• Eğer k < 1, то алгоритм порождает сообщение daha büyük boy sıkıştırılmamış olduğundan, yani "zararlı" iş yapar.

ile durum k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или Eşit uzunluk. Bu gerçeğin mantığı, farklı uzunluktaki mesajların sayısının n bit tam olarak 2 n, uzunluğuna eşit veya daha küçük olan farklı mesajların sayısı n(daha küçük uzunlukta en az bir mesaj varsa) 2'den az olacaktır n. Bu, tüm orijinal mesajları sıkıştırılmış bir mesajla açık bir şekilde eşleştirmenin imkansız olduğu anlamına gelir: ya bazı orijinal mesajların sıkıştırılmış bir gösterimi olmaz ya da birkaç orijinal mesajın aynı sıkıştırılmış gösterimi olur, yani ayırt edilemezler.

Sıkıştırma oranı, sabit (A-law, μ-law, ADPCM, kesilmiş blok kodlama gibi ses, görüntü vb. sıkıştırmak için bazı algoritmalar) veya değişken olabilir. İkinci durumda, her biri için tanımlanabilir özel mesaj, veya bazı kriterlere göre değerlendirildi:

• ortalama (genellikle bazı test veri setleri için);
• maksimum (en iyi sıkıştırma durumu);
• minimum (en kötü sıkıştırma durumu);

veya herhangi bir başkası. Bu durumda, kayıplı sıkıştırma oranı, büyük ölçüde izin verilen sıkıştırma hatasına veya kalite, genellikle bir algoritma parametresi olarak işlev görür. İÇİNDE Genel dava sabit bir sıkıştırma oranı ancak kayıplı veri sıkıştırma yöntemleri ile sağlanabilir.

2.2. kayıpların kabulü

Sıkıştırma algoritmalarını ayırt etmek için ana kriter, yukarıda açıklanan kayıpların varlığı veya yokluğudur. Genel durumda, kayıpsız sıkıştırma algoritmaları, kullanımlarının herhangi bir tür veri için kesinlikle mümkün olması anlamında evrenseldir, ancak kayıplı sıkıştırma kullanma olasılığının gerekçelendirilmesi gerekir. Bazı veri türleri için bozulmalara prensipte izin verilmez. Onların arasında

• Değişikliği kaçınılmaz olarak semantiklerinde bir değişikliğe yol açan sembolik veriler: programlar ve kaynak metinleri, ikili diziler, vb.;
• hayati veriler, değişikliklere yol açabilecek kritik hatalar: örneğin, tıbbi ölçüm ekipmanından veya uçak, uzay aracı vb. kontrol cihazlarından elde edilen;
• grafik, ses ve video verilerinin çok aşamalı işlenmesi sırasında tekrar tekrar sıkıştırma ve kurtarmaya tabi tutulan ara veriler.

2.3. Algoritmaların sistem gereksinimleri

Çeşitli algoritmalar gerektirebilir farklı miktar Kaynaklar bilgi işlem sistemi uygulandıkları:

• RAM (ara veriler için);
• kalıcı bellek (program kodu ve sabitler altında);
• işlemci süresi

Genel olarak, bu gereksinimler algoritmanın karmaşıklığına ve "zekası"na bağlıdır. Genel eğilim şu şekildedir: Algoritma ne kadar verimli ve çok yönlü olursa, gerektirdiği bilgi işlem kaynakları için gereksinimler o kadar büyük olur. Bununla birlikte, belirli durumlarda, basit ve kompakt algoritmalar, karmaşık ve evrensel olanlar kadar iyi çalışabilir. Sistem gereksinimleri, tüketici niteliklerini belirler: algoritma ne kadar az talep edilirse, o kadar basit ve dolayısıyla daha kompakt, güvenilir ve ucuz sistem uygulanabilir.

Sıkıştırma ve kurtarma algoritmaları çiftler halinde çalıştığı için ilişki önemlidir. sistem gereksinimleri onlara. Çoğu zaman, bir algoritmayı karmaşık hale getirerek diğerini önemli ölçüde basitleştirmek mümkündür. Böylece, üç seçenek mümkündür:

Sıkıştırma algoritması, kurtarma algoritmasından daha fazla hesaplama kaynağı gerektirir. Bu, bir zamanlar sıkıştırılmış verilerin tekrar tekrar kullanılacağı durumlar için tipik olan en yaygın orandır. Bir örnek, dijital ses ve video oynatıcılardır. Sıkıştırma ve kurtarma algoritmaları, yaklaşık olarak eşit bilgi işlem kaynakları gerektirir. Sıkıştırma ve kurtarma iki ucunda bir kez gerçekleştiğinde (örneğin, dijital telefonda) iletişim hatları için en kabul edilebilir seçenek. Sıkıştırma algoritması, kurtarma algoritmasından önemli ölçüde daha az talepkardır. Bu durum, sıkıştırma prosedürünün basit, genellikle taşınabilir cihaz, örneğin bir uzay aracı veya büyük bir dağıtılmış sensör ağı gibi mevcut kaynakların miktarının çok kritik olduğu. CCTV görüntüleri gibi çok küçük bir vaka yüzdesinde sıkıştırılması gereken veriler de olabilir.

3. Bilinmeyen bir formattaki verileri sıkıştırmak için algoritmalar

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

• Sıkıştırma algoritmasının her adımında, bir sonraki sıkıştırılabilir karakter ya sıkıştırıcı kodlayıcının çıktı arabelleğine olduğu gibi yerleştirilir (sıkıştırılmadığını gösteren özel bir bayrakla) ya da birkaç sıkıştırılabilir karakterden oluşan bir grup bir bağlantı ile değiştirilir. eşleşen bir grup önceden kodlanmış karaktere. Bu şekilde sıkıştırılan verilerin kurtarılması çok hızlı olduğundan, bu yaklaşım genellikle kendi kendine açılan programlar oluşturmak için kullanılır.
• Her sıkıştırılabilir karakter dizisi için, kodlanmış verilerdeki oluşum istatistikleri, zamanın her anında veya bir kez toplanır. Bu istatistiklere dayanarak, bir sonraki kodlanmış karakterin (veya karakter dizisinin) değerinin olasılığı hesaplanır. Daha sonra entropi kodlamanın bazı biçimleri, örneğin aritmetik kodlama ya da Huffman kodlaması gibi, kısa kod sözcüklerinde sıklıkla meydana gelen dizileri ve daha uzun kodlarda seyrek olanları temsil etmek için uygulanır.

Edebiyat

• D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Veri sıkıştırma yöntemleri. Arşivleyicilerin düzenlenmesi, görüntü ve video sıkıştırma. - Dialog-MEPhI, 2002. - S. 384. - ISBN 5-86404-170-X 3000 kopya
• D. Salomon. Verilerin, görüntülerin ve sesin sıkıştırılması. - M.: Teknosfer, 2004. - S. 368. - ISBN 5-94836-027-X 3000 kopya

İyi günler.
Bugün kayıpsız veri sıkıştırma konusuna değinmek istiyorum. Halihazırda Habré ile ilgili bazı algoritmalar hakkında yazılar olmasına rağmen, bundan biraz daha detaylı bahsetmek istedim.
vermeye çalışacağım matematiksel açıklama, ve her zamanki biçimde bir açıklama, böylece herkes kendileri için ilginç bir şeyler bulabilir.

Bu yazıda sıkıştırmanın temellerine ve temel algoritma türlerine değineceğim.

Sıkıştırma. Günümüzde gerekli mi?

Tabii ki evet. Elbette, artık hem büyük hacimli depolama ortamlarının hem de yüksek hızlı veri aktarım kanallarının bizim için kullanılabilir olduğunu hepimiz anlıyoruz. Ancak aynı zamanda iletilen bilgi miktarı da artıyor. Birkaç yıl önce bir diske sığan 700 megabaytlık filmler izleseydik, bugün HD kalitesinde filmler onlarca gigabayt alabiliyor.
Elbette her şeyi ve her şeyi sıkıştırmanın pek bir faydası yok. Bununla birlikte, gerekli değilse sıkıştırmanın son derece yararlı olduğu durumlar vardır.

• belgeleri gönderme e-posta(özellikle mobil cihazları kullanan büyük hacimli belgeler)
• Belgeleri sitelerde yayınlarken, trafikten tasarruf etme ihtiyacı
• kaydetme disk alanı depolama tesislerinin değiştirilmesinin veya eklenmesinin zor olduğu durumlarda. Örneğin, bu, sermaye harcamaları için bütçe almanın kolay olmadığı ve yeterli disk alanının olmadığı durumlarda olur.

Elbette sıkıştırmanın faydalı olacağı daha birçok farklı durum düşünebilirsiniz, ancak bu birkaç örnek bizim için yeterli olacaktır.

Tüm sıkıştırma yöntemleri ikiye ayrılabilir büyük gruplar: kayıplı sıkıştırma ve kayıpsız sıkıştırma. Bilginin bit doğruluğu ile geri yüklenmesi gereken durumlarda kayıpsız sıkıştırma kullanılır. Bu yaklaşım, örneğin metin verilerini sıkıştırırken mümkün olan tek yaklaşımdır.
Ancak bazı durumlarda gerekli değildir. tam restorasyon bilgi ve kayıpsız sıkıştırmanın aksine, uygulanması genellikle daha kolay olan ve daha yüksek derecede arşivleme sağlayan kayıplı sıkıştırma uygulayan algoritmaların kullanılmasına izin verilir.

Öyleyse, kayıpsız sıkıştırma algoritmalarını dikkate almaya devam edelim.

Evrensel Kayıpsız Sıkıştırma Teknikleri

Genel durumda, sıkıştırma algoritmalarının üzerine kurulduğu üç temel değişken vardır.
İlk grup yöntemler - akış dönüşümü. Bu, yeni gelen sıkıştırılmamış verilerin önceden işlenmiş veriler açısından tanımlanmasını içerir. Bu durumda, hiçbir olasılık hesaplanmaz, karakter kodlaması yalnızca LZ yöntemlerinde olduğu gibi (Abraham Lempel ve Jacob Ziv'den sonra adlandırılan) gibi önceden işlenmiş veriler temelinde gerçekleştirilir. Bu durumda, kodlayıcı tarafından zaten bilinen bazı alt dizilerin ikinci ve sonraki oluşumları, ilk oluşumuna yapılan referanslarla değiştirilir.

İkinci grup yöntemler istatistiksel yöntemler sıkıştırma. Sırasıyla, bu yöntemler uyarlanabilir (veya akış) ve blok yöntemlerine ayrılır.
İlk (uyarlanabilir) varyantta, yeni veriler için olasılıkların hesaplanması, kodlama sırasında halihazırda işlenmiş verilere dayanmaktadır. Bu yöntemler, Huffman ve Shannon-Fano algoritmalarının uyarlanabilir versiyonlarını içerir.
İkinci (blok) durumda, her veri bloğunun istatistikleri ayrı ayrı hesaplanır ve en sıkıştırılmış bloğa eklenir. Bunlar, Huffman, Shannon-Fano ve aritmetik kodlama yöntemlerinin statik versiyonlarını içerir.

Üçüncü grup yöntemler sözde blok dönüştürme yöntemleridir. Gelen veriler bloklara bölünür ve daha sonra bir bütün olarak dönüştürülür. Ancak bazı yöntemler, özellikle blokların permütasyonuna dayalı olanlar, veri miktarında önemli (veya herhangi bir) azalmaya yol açmayabilir. Bununla birlikte, bu tür bir işlemden sonra, veri yapısı önemli ölçüde iyileştirilir ve ardından diğer algoritmalar tarafından yapılan sıkıştırma daha başarılı ve daha hızlıdır.

Veri sıkıştırmanın dayandığı genel ilkeler

Tüm veri sıkıştırma yöntemleri basit bir mantıksal ilkeye dayanmaktadır. En sık meydana gelen öğelerin daha kısa kodlarla kodlandığını ve daha az sıklıkla meydana gelen öğelerin daha uzun kodlarla kodlandığını hayal edersek, tüm verileri depolamak için tüm öğelerin aynı uzunlukta kodlarla temsil edilmesinden daha az alana ihtiyaç duyulacaktır.
Eleman frekansları ve optimal kod uzunlukları arasındaki kesin ilişki, limiti tanımlayan Shannon'ın kaynak kodlama teoreminde açıklanmıştır. maksimum sıkıştırma kayıpsız ve Shannon entropisi.

biraz matematik

Bir s i öğesinin ortaya çıkma olasılığı p(s i)'ye eşitse, bu öğeyi temsil etmek en avantajlı olacaktır - log 2 p(s i) bit. Kodlama sırasında tüm elemanların uzunluğunun log 2 p(s i) bitine indirilmesini sağlamak mümkün ise, o zaman tüm kodlanmış dizinin uzunluğu, tümü için minimum olacaktır. olası yöntemler kodlama. Ayrıca, tüm F = (p(s i)) öğelerinin olasılık dağılımı değişmezse ve öğelerin olasılıkları karşılıklı olarak bağımsızsa, ortalama kod uzunluğu şu şekilde hesaplanabilir:

Bu değer, F olasılık dağılımının entropisi veya zamanın belirli bir noktasında kaynağın entropisi olarak adlandırılır.
Ancak, genellikle bir elemanın ortaya çıkma olasılığı bağımsız olamaz, aksine bazı faktörlere bağlıdır. Bu durumda, her yeni kodlanmış eleman s i için olasılık dağılımı F bir miktar F k değerini alacaktır, yani her eleman için F= F k ve H= H k .

Başka bir deyişle, kaynağın k durumunda olduğunu söyleyebiliriz, bu da tüm si öğeleri için belirli bir olasılıklar kümesine karşılık gelir p k (s i) si .

Dolayısıyla bu düzeltmeyi dikkate alarak kodların ortalama uzunluğunu şu şekilde ifade edebiliriz:

Burada P k, kaynağı k durumunda bulma olasılığıdır.

Yakın zamanda bu aşama Sıkıştırmanın, sıklıkla meydana gelen öğeleri kısa kodlarla değiştirmeye dayandığını ve bunun tersinin de olduğunu biliyoruz ve ayrıca ortalama kodların uzunluğunu nasıl belirleyeceğimizi de biliyoruz. Fakat kod nedir, kodlama nedir ve nasıl olur?

hafızasız kodlama

Hafızasız kodlar, verileri sıkıştırmak için kullanılabilecek en basit kodlardır. Hafızasız bir kodda, kodlanmış veri vektöründeki her bir sembol, ikili diziler veya kelimelerin bir önek setinden bir kod kelimesi ile değiştirilir.
Bence, en net tanım değil. Bu konuyu biraz daha ayrıntılı olarak ele alalım.

Biraz alfabe verilsin , bazı (sonlu) sayıda harften oluşur. Bu alfabedeki her bir sonlu karakter dizisini isimlendirelim (A=a 1 , a 2 ,… ,a n) kelime, ve n sayısı bu kelimenin uzunluğudur.

Bir alfabe daha verilsin . Benzer şekilde bu alfabedeki kelimeyi de B olarak gösterelim.

Alfabedeki tüm boş olmayan kelimelerin kümesi için iki gösterim daha sunuyoruz. Let - ilk alfabedeki boş olmayan kelimelerin sayısı ve - ikincisinde.

Ayrıca birinci alfabedeki her A kelimesine ikinciden bir kelime B=F(A) atanan bir F eşlemesi verilsin. Sonra B kelimesi çağrılacak kod A kelimesi ve orijinal kelimeden koduna geçiş çağrılacak kodlama.

Bir kelime aynı zamanda bir harften oluşabileceğinden, birinci alfabenin harfleri ile ikinci alfabenin karşılık gelen kelimeleri arasındaki yazışmaları belirleyebiliriz:
1<->B1
2<->B2
…
bir<->ben

Bu yazışma denir şema, ve ∑ ile gösterilir.
Bu durumda, B 1 , B 2 ,…, Bn kelimeleri denir. temel kodlar, ve onların yardımıyla kodlama türü - alfabetik kodlama. Elbette çoğumuz yukarıda anlattıklarımın hepsini bilmeden bile bu tür kodlamalarla karşılaşmışızdır.

Yani, kavramları tanımladık alfabe, kelime, kod, Ve kodlama. Şimdi konsepti tanıtalım önek.

B kelimesi B=B"B"" şeklinde olsun. O zaman B" başlangıç ​​olarak adlandırılır veya önek B kelimesi ve B"" - sonu. Bu oldukça basit bir tanımdır, ancak herhangi bir B kelimesi için hem bazı boş ʌ ("boşluk") kelimesinin hem de B kelimesinin kendisinin hem başlangıç ​​hem de son olarak kabul edilebileceğine dikkat edilmelidir.

Böylece, hafızasız kodların tanımını anlamaya yaklaştık. Anlamamız gereken son tanım, önek kümesidir. Herhangi bir 1≤i, j≤r, i≠j için, B i kelimesi B j kelimesinin bir öneki değilse, ∑ şeması önek özelliğine sahiptir.
Basitçe söylemek gerekirse, bir önek kümesi, hiçbir elemanın başka bir elemanın öneki (veya başlangıcı) olmadığı sonlu bir kümedir. Böyle bir kümenin basit bir örneği, örneğin sıradan alfabedir.

Böylece, temel tanımları ele aldık. Peki hafızasız kodlamanın kendisi nasıl oluyor?
Üç aşamada gerçekleşir.

1. Ψ karakterden oluşan bir alfabe derlenir Orijinal mesaj, mesajda görünme olasılıklarına göre azalan sırada sıralanmış alfabetik karakterlerle.
2. Ψ alfabesindeki her a i karakteri, Ω önek kümesinden bir B i kelimesi ile ilişkilendirilir.
3. Her karakter kodlanır, ardından sıkıştırmanın sonucu olacak şekilde kodların tek bir veri akışında birleşimi gelir.

gösteren kanonik algoritmalardan biridir. Bu method, Huffman algoritmasıdır.

Huffman algoritması

Huffman algoritması, giriş veri bloğunda aynı baytların oluşma sıklığını kullanır ve sıklıkla meydana gelen blokları daha küçük uzunluktaki bit zincirleriyle eşleştirir ve bunun tersi de geçerlidir. Bu kod minimum gereksiz koddur. Giriş akışından bağımsız olarak, çıkış akışının alfabesinin yalnızca 2 karakterden oluştuğunu düşünün - sıfır ve bir.

Öncelikle Huffman algoritması ile kodlama yaparken bir ∑ devresi kurmamız gerekiyor. Bu şu şekilde yapılır:

1. Giriş alfabesinin tüm harfleri, azalan olasılık sırasına göre sıralanmıştır. Çıkış akışının alfabesindeki tüm kelimeler (yani, kodlayacağımız şey) başlangıçta boş olarak kabul edilir (çıkış akışının alfabesinin yalnızca karakterlerden (0,1) oluştuğunu hatırlayın).
2. Giriş akışının en düşük gerçekleşme olasılığına sahip iki karakteri a j-1 ve j, olasılık ile tek bir "sözde karakter"de birleştirilir. P içerdiği sembollerin olasılıklarının toplamına eşittir. Daha sonra B j-1 kelimesinin başına 0 ve B j kelimesinin başına 1 ekleriz, bunlar sırasıyla a j-1 ve a j karakter kodları olacaktır.
3. Bu sembolleri orijinal mesajın alfabesinden çıkarıyoruz, ancak oluşturulan sözde sembolü bu alfabeye ekliyoruz (elbette, olasılığını hesaba katarak alfabeye doğru yerde eklenmelidir).

Alfabenin tüm orijinal karakterlerini içeren yalnızca 1 sözde karakter alfabede kalana kadar 2. ve 3. adımlar tekrarlanır. Aynı zamanda, her adımda ve her karakter için karşılık gelen B i kelimesi değiştirildiğinden (bir veya sıfır eklenerek), bu prosedürün tamamlanmasından sonra, ai alfabesinin her ilk karakteri belirli bir B koduna karşılık gelecektir. ben .

Daha iyi açıklamak için küçük bir örnek düşünün.
Sadece dört karakterden oluşan bir alfabemiz olsun - ( a 1 , a 2 , a 3 , a 4). Ayrıca bu sembollerin oluşma olasılıklarının sırasıyla p 1 =0.5 olduğunu varsayalım; p2=0.24; p3=0.15; p 4 =0.11 (tüm olasılıkların toplamı açıkça bire eşittir).

Öyleyse, bu alfabe için bir şema oluşturalım.

1. En düşük olasılıklı (0.11 ve 0.15) iki karakteri bir sözde karakter p" olarak birleştirin.
2. En düşük olasılığa sahip (0.24 ve 0.26) iki karakteri bir p"" sözde karakterinde birleştirin.
3. Birleştirilmiş karakterleri kaldırıyoruz ve ortaya çıkan sözde karakteri alfabeye ekliyoruz.
4. Son olarak kalan iki karakteri birleştiriyoruz ve ağacın tepesini elde ediyoruz.

Bu işlemin bir örneğini yaparsanız, şöyle bir şey elde edersiniz:

Gördüğünüz gibi, her bir birleştirme ile, birleştirilmiş karakterlere 0 ve 1 kodlarını atadık.
Bu sayede ağaç inşa edildiğinde her karakterin kodunu kolayca alabiliriz. Bizim durumumuzda, kodlar şöyle görünecek:

A1 = 0
a2 = 11
3 = 100
a4 = 101

Bu kodların hiçbiri diğerinin öneki olmadığından (yani, kötü şöhretli önek setimiz var), çıktı akışındaki her kodu benzersiz bir şekilde tanımlayabiliriz.
Böylece, en sık kullanılan karakterin en kısa kodla kodlanmasını ve bunun tersini sağladık.
Başlangıçta her karakteri depolamak için bir bayt kullanıldığını varsayarsak, verileri ne kadar azaltmayı başardığımızı hesaplayabiliriz.

Girişte, 1 karakterinin 500 kez, 2 - 240, 3 - 150 ve 4 - 110 kez geçtiği 1000 karakterlik bir dizimiz olsun.

İlk olarak verilen dize 8000 bit işgal etti. Kodlamadan sonra ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 bit uzunluğunda bir string elde edeceğiz. Böylece, akışın her bir sembolünü kodlamak için ortalama 1,76 bit harcayarak verileri 4,54 faktörü ile sıkıştırmayı başardık.

Shannon'a göre kodların ortalama uzunluğunun . Olasılıklarımızı bu denklemde yerine koyarsak, sonucumuza çok çok yakın olan 1.75496602732291'e eşit ortalama kod uzunluğunu elde ederiz.
Ancak, verilerin kendisine ek olarak, kodlanmış verilerin son boyutunu biraz artıracak bir kodlama tablosu depolamamız gerektiğini unutmayın. Açıktır ki içinde farklı durumlar algoritmanın farklı varyasyonları kullanılabilir - örneğin, bazen önceden kullanmak daha verimlidir verilen tablo olasılıklar ve bazen sıkıştırılabilir verilerden geçerek dinamik olarak oluşturmak gerekir.

Çözüm

Yani, bu yazıda bahsetmeye çalıştım Genel İlkeler, kayıpsız sıkıştırma için kullanılan ve aynı zamanda kanonik algoritmalardan biri olarak kabul edilen - Huffman kodlaması.
Makale habrocommunity'nin zevkine uygunsa, devamını yazmaktan mutluluk duyacağım, çünkü kayıpsız sıkıştırma ile ilgili çok daha ilginç şeyler var; bunlar hem klasik algoritmalar hem de ön veri dönüşümleri (örneğin, Burrows-Wheeler dönüşümü) ve elbette ses, video ve görüntüleri sıkıştırmak için özel algoritmalar (bence en ilginç konu).

Edebiyat

• Vatolin D., Ratushnyak A., Smirnov M. Yukin V. Veri sıkıştırma yöntemleri. Arşivleyicilerin düzenlenmesi, görüntü ve video sıkıştırma; ISBN 5-86404-170-X; 2003
• D. Salomon. Veri, görüntü ve ses sıkıştırma; ISBN 5-94836-027-X; 2004