Evrim Ağacı Soru & Cevap
Reklamı Kapat
Puan Ver
2
Puan Ver

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

2
Teşekkür
Hatırla
Takip
Paylaş
Reklamı Kapat
2 Cevap

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;

Resim 1
Resim 1
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.

Resim 2
Resim 2
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!"

231 görüntülenme
Puan Ver
2
Puan Ver
Teşekkür
Paylaş
2

Kaynaklar

  1. Kaynak
  2. Alternatif

Merhaba,

Bir metin dosyasını ele alıp sıkıştırma yöntemlerine bir örnek verelim. "Evrim Ağacı" kelimesinin bayt olarak karşılığını çevirince

45 76 72 69 6d 20 41 c4 9f 61 63 c4 b1

dizisini elde ederiz. Buradaki çift basamaklı sayıların her biri karakterlere karşılık geliyor. Bu çevirme işleminin yapmamızın nedeni bilgisayarların metin karakterlerini sayısal olarak tutmaları ve işlemelerinden kaynaklanıyor. Yani görüntüde gördüğümüz tüm metin ve simgeler hepsi sayı. Ayrıca bu sayılar onaltılık tabandadır. Bu sayıları makine kodlarına çevirirsek

1000101 1110110 1110010 1101001 1101101 100000 1000001 100011111 1100001 1100011 100110001

olarak çevirilir. Çünkü bilgisayar onaltılık sayılardan da anlamaz. Bu sayı işlemek için her zaman 0 ve 1'lerde oluşan 8'li, 16'lı, 32'li, 64'lü ya da 128'li gruplar kullanır. İşlemciler bu sayı gruplarını işlerler. Buraya kadar "Evrim Ağacı" metninin bilgisayardaki makine kodları karşılığının ne uzunlukta olduğunu gördük.

Peki bunu nasıl sıkıştırabiliriz? Örneğin boşluk karakterine 0, a harfine 1, b harfine 2, c harfine 3 dersek ve bunu tüm alfabe için yaparsak elimize sayısallaştırılmış bir alfabe olur(ğ bu örnek için liste dışı). "Evrim Ağacı" metnini dönüştürürsek

5 22 18 9 13 0 1 7 1 3 9

sayı dizisini elde ederiz. Bu sayı dizisinin bilgisayardaki makine kodları karşılığını elde edelim:

00110101 00110010 00110010 00110001 00111000 00111001 00110001 00110011 00110000 00110001 00110111 00110001 00110011 00111001

Dizi başlarındaki "0011"li tekrar eden bölgeler atılıp kısaltılmış bir dizi elde edilir. Bu yöntemle basitçe veri kaybetmeden metin sıkıştırması yapmış oluruz.

Bu tekniğe benzer olarak tekrarlayan kelimeler için sayı ataması yapılabilir. Ne kadar çok kelime tekrarı varsa o kadar kısaltmış oluruz. Günümüzde bunlardan farklı çeşitli kayıplı-kayıpsız sıkıştırma algoritmaları ve yöntemleri var.

İyi bilimler dilerim.

Puan Ver
0
Puan Ver
Teşekkür
Paylaş
0

Kaynaklar

  1. Çevirici karakterlerin çeviricisi
  2. Çevirici birim çeviricisi
  3. Şifreleme ve çözme makale
  4. Çevirici
  5. Vikipedi Basit tanımlar
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.
Reklamı Kapat
Reklamsız Deneyim

Evrim Ağacı'nın çalışmalarına Kreosus, Patreon veya YouTube üzerinden maddi destekte bulunarak hem Türkiye'de bilim anlatıcılığının gelişmesine katkı sağlayabilirsiniz, hem de site ve uygulamamızı reklamsız olarak deneyimleyebilirsiniz. Reklamsız deneyim, Evrim Ağacı'nda çeşitli kısımlarda gösterilen Google reklamlarını ve destek çağrılarını görmediğiniz, daha temiz bir site deneyimi sunmaktadır.

Kreosus

Kreosus'ta her 10₺'lik destek, 1 aylık reklamsız deneyime karşılık geliyor. Bu sayede, tek seferlik destekçilerimiz de, aylık destekçilerimiz de toplam destekleriyle doğru orantılı bir süre boyunca reklamsız deneyim elde edebiliyorlar.

Kreosus destekçilerimizin reklamsız deneyimi, destek olmaya başladıkları anda devreye girmektedir ve ek bir işleme gerek yoktur.

Patreon

Patreon destekçilerimiz, destek miktarından bağımsız olarak, Evrim Ağacı'na destek oldukları süre boyunca reklamsız deneyime erişmeyi sürdürebiliyorlar.

Patreon destekçilerimizin Patreon ile ilişkili e-posta hesapları, Evrim Ağacı'ndaki üyelik e-postaları ile birebir aynı olmalıdır. Patreon destekçilerimizin reklamsız deneyiminin devreye girmesi 24 saat alabilmektedir.

YouTube

YouTube destekçilerimizin hepsi otomatik olarak reklamsız deneyime şimdilik erişemiyorlar ve şu anda, YouTube üzerinden her destek seviyesine reklamsız deneyim ayrıcalığını sunamamaktayız. YouTube Destek Sistemi üzerinde sunulan farklı seviyelerin açıklamalarını okuyarak, hangi ayrıcalıklara erişebileceğinizi öğrenebilirsiniz.

Eğer seçtiğiniz seviye reklamsız deneyim ayrıcalığı sunuyorsa, destek olduktan sonra YouTube tarafından gösterilecek olan bağlantıdaki formu doldurarak reklamsız deneyime erişebilirsiniz. YouTube destekçilerimizin reklamsız deneyiminin devreye girmesi, formu doldurduktan sonra 24-72 saat alabilmektedir.

Diğer Platformlar

Bu 3 platform haricinde destek olan destekçilerimize ne yazık ki reklamsız deneyim ayrıcalığını sunamamaktayız. Destekleriniz sayesinde sistemlerimizi geliştirmeyi sürdürüyoruz ve umuyoruz bu ayrıcalıkları zamanla genişletebileceğiz.

Giriş yapmayı unutmayın!

Reklamsız deneyim için, maddi desteğiniz ile ilişkilendirilmiş olan Evrim Ağacı hesabınıza üye girişi yapmanız gerekmektedir. Giriş yapmadığınız takdirde reklamları görmeye devam edeceksinizdir.

Destek Ol
Türkiye'deki bilimseverlerin buluşma noktasına hoşgeldiniz!

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
“İhtiyacımız olan tek şey var: Çalışmak!”
Mustafa Kemal Atatürk