Paylaşım Yap
Tüm Reklamları Kapat
Sorulara Dön
Ahmet B.
Ahmet B.
1,667 UP
Üye
7

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ı?
863 görüntülenme
0
  • Paylaş
  • Alıntıla
  • Alıntıları Göster
  • Dış Sitelerde Paylaş
  • Soruyu Takip Et
  • Raporla
  • Mantık Hatası Bildir
Tüm Reklamları Kapat
1 Cevap
Sefa Can Demir
Front-End Developer

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.

Tüm Reklamları Kapat

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.

Tüm Reklamları Kapat

Ö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

Tüm Reklamları Kapat

f 101

g 110

h 111

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

Tüm Reklamları Kapat

"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

Tüm Reklamları Kapat

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.

Tüm Reklamları Kapat

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

a 0110

b 1110

c 110

Tüm Reklamları Kapat

d 00

e 010

f 10

g 1111

Tüm Reklamları Kapat

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

Tüm Reklamları Kapat

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ı)

Tüm Reklamları Kapat

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ç:

Tüm Reklamları Kapat

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)

Tüm Reklamları Kapat

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)

Tüm Reklamları Kapat

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

Tüm Reklamları Kapat

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 :)

Tüm Reklamları Kapat

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!

414 görüntülenme

Kaynaklar

  1. Yazar Yok. Geom. (13 Temmuz 2019). Alındığı Tarih: 13 Temmuz 2019. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  2. Yazar Yok. Computer Science Field Guide. (13 Temmuz 2019). Alındığı Tarih: 13 Temmuz 2019. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  3. Yazar Yok. Geeksforgeeks. (13 Temmuz 2019). Alındığı Tarih: 13 Temmuz 2019. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
Bu cevabın içeriği ve doğruluğu, Evrim Ağacı editörleri tarafından kontrol edilmiş ve onaylanmıştır.
11
0
  • Paylaş
  • Alıntıla
  • Alıntıları Göster
  • Dış Sitelerde Paylaş
  • Raporla
  • Mantık Hatası Bildir
Daha Fazla Cevap Göster
Cevap Ver
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.
Popüler Yazılar
30 gün
90 gün
1 yıl
Evrim Ağacı'na Destek Ol

Evrim Ağacı'nın %100 okur destekli bir bilim platformu olduğunu biliyor muydunuz? Evrim Ağacı'nın maddi destekçileri arasına katılarak Türkiye'de bilimin yayılmasına güç katın.

Evrim Ağacı'nı Takip Et!
Aklımdan Geçen
Komünite Seç
Aklımdan Geçen
Fark Ettim ki...
Bugün Öğrendim ki...
İşe Yarar İpucu
Bilim Haberleri
Hikaye Fikri
Video Konu Önerisi
Başlık
Gündem
Kafana takılan neler var?
Bağlantı
Kurallar
Komünite Kuralları
Bu komünite, aklınızdan geçen düşünceleri Evrim Ağacı ailesiyle paylaşabilmeniz içindir. Yapacağınız paylaşımlar Evrim Ağacı'nın kurallarına tabidir. Ayrıca bu komünitenin ek kurallarına da uymanız gerekmektedir.
1
Bilim kimliğinizi önceleyin.
Evrim Ağacı bir bilim platformudur. Dolayısıyla aklınızdan geçen her şeyden ziyade, bilim veya yaşamla ilgili olabilecek düşüncelerinizle ilgileniyoruz.
2
Propaganda ve baskı amaçlı kullanmayın.
Herkesin aklından her şey geçebilir; fakat bu platformun amacı, insanların belli ideolojiler için propaganda yapmaları veya başkaları üzerinde baskı kurma amacıyla geliştirilmemiştir. Paylaştığınız fikirlerin değer kattığından emin olun.
3
Gerilim yaratmayın.
Gerilim, tersleme, tahrik, taciz, alay, dedikodu, trollük, vurdumduymazlık, duyarsızlık, ırkçılık, bağnazlık, nefret söylemi, azınlıklara saldırı, fanatizm, holiganlık, sloganlar yasaktır.
4
Değer katın; hassas konulardan ve öznel yoruma açık alanlardan uzak durun.
Bu komünitenin amacı okurlara hayatla ilgili keyifli farkındalıklar yaşatabilmektir. Din, politika, spor, aktüel konular gibi anlık tepkilere neden olabilecek konulardaki tespitlerden kaçının. Ayrıca aklınızdan geçenlerin Türkiye’deki bilim komünitesine değer katması beklenmektedir.
5
Cevap hakkı doğurmayın.
Bu platformda cevap veya yorum sistemi bulunmamaktadır. Dolayısıyla aklınızdan geçenlerin, tespit edilebilir kişilere cevap hakkı doğurmadığından emin olun.
Ekle
Soru Sor
ve seni takip ediyor

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