WinRAR ve türevi uygulamalar nasıl oluyorda bir dosyanın kapladığı alanı küçültebiliyorlar?

Buna benzer bir soru sorulduğu için alıntılıyorum.

https://evrimagaci.org/soru/pi-sayisi-sikistirilabilir-mi-1319

"Merhaba,

Sanırım soruda Huffman Kodlamasından örnek vermişsiniz. Fakat Kayıplı ve Kayıpsız veri sıkıştırma başlıkları altında onlarca veri sıkıştırma yöntemi (algoritması) yer almaktadır. Soruyu tüm bu algoritmaları inceleyerek ele almak gerekir. Fakat ben sorunuzu sadece bahsettiğiniz Huffman Kodlamasını ele alarak bilgim dahilinde cevaplamaya çalışacağım.

Huffman Kodlaması

Huffman Kodlaması verideki karakterlerin frekansına yani kullanım sırasına göre bir kodlama oluşturur ve bu sayede sık kullanılan karakterlerin daha az, nadir kullanılan karakterlerin ise daha fazla yer kaplamasını sağlar. Verideki karakterlerin dağılımı yani tekrarlanması eşit olmadığı sürece verimli performans göstermektedir. Fakat bu algoritmanın zayıf olduğu anlamına gelmez çünkü bir verideki karakterlerin eşit dağılıma sahip olması imkansıza yakın denilebilecek kadar düşük bir olasılığa sahiptir.

Örnek

Çok basit bir örnek vermek gerekirse 8 harften oluşan bir alfabeye sahip olduğumuzu varsayalım ve bu harfler "a,b,c,d,ef,g,h" olsun. 2³ = 8 olduğu için 8 bit yerine, 8 harfli alfabemizi ikili sistemde 3 bit ile kodlayabiliriz.

Alfabemizi 3 bit ile kodlayacak olursakta bu değerleri verebiliriz;

a 000

b 001

c 010

d 011

e 100

f 101

g 110

h 111

Bu alfabede "abeebc dccddff dhfffgf" mesajını kodlayacak olursak şu şekilde gözükecektir;

"001001001010011101101 100110110111100 000000000100100010101111"

Görüldüğü üzere 20 harfli bir mesajı kodlamak için harf sayısının 3 katı (60) byte kullanmak zorunda kalıyoruz. Dolayısıyla bu mesajı Huffman algoritması ile kodlamak istersek harflerin tekrar sayısının şemasını çıkarmamız gerekir;

a1

b2

c3

d4

e2

f6

h1

g1

Çıkardığımız şema doğrultusunda bir ağaç oluşturmamız gerekmekte;

Evrim Ağacı

Resme dikkatli bakacak olursanız harfler ve her harf düğümlerinin birleşim noktalarında ise o harflerin mesajdaki tekrar sayıları bulunmaktadır. Dikkat edilmesi gereken nokta ise resimdeki dallanmalardaki 0 ve 1 değerleridir. Huffman Ağacında sola giden her dal 0 sağa giden her dal ise koda 1 eklemektedir. Örnek verecek olursak ağaçtaki e harfine giderken "sol, sağ, sol" yapmaktayız buda bize 010 değerini vermekte. Daha net bir şekilde anlatmak gerekirse e harfine giden yol 20'nin solu, 8'in sağı,4'ün solu şeklindedir.

Bu şekilde ağaçtaki harflerin konumuna ve onlaran giden dalların değerine bakarak alfabemizi yeniden kodlarsak;

a 0110

b 1110

c 110

d 00

e 010

f 10

g 1111

h 0111

sonucu elde ederiz. Bu sonuca göre verimizi tekrar kodlayacak olursak da;

"011011100100101110110 0011011000001010 000111101010111110"

sonucu elde ederiz. Yani 20 harfli bir mesajı 60 byte tan 55 byte a sıkıştırmış oluruz. (%8.3 oran ile sıkıştırılmış olur.)

Sıkıştırma oranı size çok az gelebilir fakat bunun temel sebebi kullandığımız örnekte makalenin başında bahsettiğim gibi tekrar etme oranlarının bir birine biraz yakın olması. Aynı zamanda örnekteki verinin boyutunun düşük olması.

Asıl konumuz: Pi Sayısı sıkıştırılabilir mi?

Evet, az çok Huffman Algoritmasını sizlere anlatabildiysem fark edeceksinizdir ki soruya cevap verebilmek için tekrar eden rakamları ve kaç kere tekrar ettiklerini bilmemiz gerekmekte yani kısacası bir ağaç oluşturmamız gerekmekte. Dolayısıyla internetten edindiğim Pi sayısının ilk 100bin rakamının yardımcı bir yazılım ile Huffman Ağacını oluşturdum. Bu ağaca göre kodlama yapıp daha sonra kodlamadaki byte sayısının tekrar sayısı ile çarparsak bize o harfin sıkıştırılmış verinin boyutunu verecektir.

Örn: (rakamın kodlamadaki byte sayısı)*(rakamın tekrar sayısı) = (rakamın toplam byte sayısı)

Bu yöntem ile ilerleyip tüm rakamların toplam byte sayısını bulup toplarsak bize pi sayısının (Virgülden sonra 100.000) sıkıştırılmış boyutunu elde edebiliriz. Ham halinin boyutunu da yukarıda hesapladığımızdan kıyaslama yaparak sorunuzu cevaplayabiliriz.

Evrim Ağacı

Ve Sonuç:

0 = 001 (3 Byte) = 9.999 (tekrar sayısı) * 3 (byte sayısı) = 29.997 (byte)

1 = 101 (3 Byte) = 10.138 (tekrar sayısı) * 3 (byte sayısı) = 30.414 (byte)

2 = 1100 (4 Byte) = 9.908 (tekrar sayısı) * 4 (byte sayısı) = 39.632 (byte)

3 = 010 (3 Byte) = 10.026 (tekrar sayısı) * 3 (byte sayısı) = 30.078 (byte)

4 = 1110 (4 Byte) = 9.970 (tekrar sayısı) * 4 (byte sayısı) = 39.880 (byte)

5 = 011 (3 Byte) = 10.027 (tekrar sayısı) * 3 (byte sayısı) = 30.081 (byte)

6 = 101 (3 Byte) = 10.027 (tekrar sayısı) * 3 (byte sayısı) = 30,081 (byte)

7 = 000 (3 Byte) = 10.025 (tekrar sayısı) * 3 (byte sayısı) = 30.075 (byte)

8 = 1111 (4 Byte) = 9.978 (tekrar sayısı) * 4 (byte sayısı) = 39.912 (byte)

9 = 11011 (5 Byte) = 9.902 (tekrar sayısı) * 5 (byte sayısı) = 49.510 (byte)

Virgül/Nokta = 11010 (5 Byte) = 1 (tekrar sayısı) * 5 (byte sayısı) = 5 (byte)

Toplam: 29.997 + 30.414 + 39.632 + 30.078 + 39.880 + 30.081 + 30.081 + 30.075 + 39.912 + 49.510 + 5 = 349.665 byte

100.002 karakterli bir veriyi ikili sistemde 8 byte olarak kodladığımızda 800.016 byte elde edeceğimizden, 800.016 - 349.665 = 450.351 byte sıkıştırma sağlamış olacağız. Orana vurduğumuzda ise sıkıştırma oranı V olacaktır.

Yani evet Pi sayısı sıkıştırılabilir :)

Dip Not: Cevapta veya görsellerde hesap hatası, yazım hatası olabilir. Bu durumun sonucu değiştirmeyeceği düşüncesindeyim. Yine de konuya ilgili kişiler hesapta veya mantıkta yanlış arayıp bizleri bilgilendirebilir. Cevabı kendi bilgim dahilin de bir kaç makaleden ve araçtan yararlanarak verdim.

Merakla Kalın!"