Puan Ver
6
Puan Ver

Pi sayısı sıkıştırılabilir mi?

Dijital verilerin sıkıştırılması: veri üzerinde tekrar eden örüntüleri belirleyip, bunları daha küçük serilere dönüştürmekle ilgili. Pi sayısı bilindiği üzre kendini tekrarlamayan, benzersiz bir sayı. Bu durumda pi sayısını (örn. Virgülden sonraki 100. 000 rakamını) sıkıştırılmanın bir yolu var mı?

1
Favorilerime Ekle
Sonra Cevapla
Takip Et
1 Cevap

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;

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 vermizi tekrar kodlayacak olursakta;

"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. 

pi

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!

Favorilerime Ekle
10

Kaynaklar

  1. Geom Pi Sayısının ilk 100.000 basamağı.
  2. Computer Science Field Guide Huffman Tree Generator - Araç
  3. GeeksforGeeks Huffman Algortiması
Cevap Ver
Bu soruya cevap vermek için lütfen
Evrim Ağacı Soru & Cevap Platformu, Türkiye'deki bilimseverler tarafından kolektif ve öz denetime dayalı bir şekilde sürdürülen, özgür bir ortamdır. Evrim Ağacı tarafından yayınlanan makalelerin aksine, bu platforma girilen soru ve cevapların içeriği veya gerçek/doğru olup olmadıkları Evrim Ağacı yönetimi tarafından denetlenmemektedir. Evrim Ağacı, bu platformda yayınlanan cevapları herhangi bir şekilde desteklememekte veya doğruluğunu garanti etmemektedir. Doğru olmadığını düşündüğünüz cevapları, size sunulan denetim araçlarıyla işaretleyebilir, daha doğru olan cevapları kaynaklarıyla girebilir ve oylama araçlarıyla platformun daha güvenilir bir ortama evrimleşmesine katkı sağlayabilirsiniz.
Türkiye'deki bilimseverlerin buluşma noktasına hoşgeldiniz!

Göster

Şifremi unuttum Üyelik Aktivasyonu

Göster

Şifrenizi mi unuttunuz? Lütfen e-posta adresinizi giriniz. E-posta adresinize şifrenizi sıfırlamak için bir bağlantı gönderilecektir.

Geri dön

Eğer aktivasyon kodunu almadıysanız lütfen e-posta adresinizi giriniz. Üyeliğinizi aktive etmek için e-posta adresinize bir bağlantı gönderilecektir.

Geri dön

Close
“Delilik, aynı hataları tekrar edip farklı sonuçlar beklemektir.”
Narcotics Anonymous
Geri Bildirim Gönder