Paylaşım Yap
Tüm Reklamları Kapat
Sorulara Dön
Anonim
Anonim Üye
2

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

608 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
2 Cevap
Ufuk Derin
Öğrenci-Okur

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

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

Tüm Reklamları Kapat

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

Ö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

Tüm Reklamları Kapat

d 011

e 100

f 101

g 110

Tüm Reklamları Kapat

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;

Tüm Reklamları Kapat

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.

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

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.

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)

Tüm Reklamları Kapat

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)

Tüm Reklamları Kapat

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)

Tüm Reklamları Kapat

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

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

331 görüntülenme

Kaynaklar

  1. Yazar Yok. Kaynak. (22 Ocak 2020). Alındığı Tarih: 22 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  2. Yazar Yok. Alternatif. (22 Ocak 2020). Alındığı Tarih: 22 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
3
0
  • Paylaş
  • Alıntıla
  • Alıntıları Göster
  • Dış Sitelerde Paylaş
  • Raporla
  • Mantık Hatası Bildir
Alirıza Arıbaş
Bilgisayar Mühendisi

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

Tüm Reklamları Kapat

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.

Tüm Reklamları Kapat

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.

Kaynaklar

  1. Yazar Yok. Çevirici. (31 Ocak 2020). Alındığı Tarih: 31 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  2. Yazar Yok. Çevirici. (31 Ocak 2020). Alındığı Tarih: 31 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  3. Yazar Yok. Şifreleme Ve Çözme. (31 Ocak 2020). Alındığı Tarih: 31 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  4. Yazar Yok. Çevirici. (31 Ocak 2020). Alındığı Tarih: 31 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
  5. Yazar Yok. Vikipedi. (31 Ocak 2020). Alındığı Tarih: 31 Ocak 2020. Alındığı Yer: Bağlantı | Arşiv Bağlantısı
0
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
Bugün bilimseverlerle ne paylaşmak istersin?
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