Jump to content

Yeni bir kayıpsız sıkıştırma algoritması üzerinde çalışıyorum.


Recommended Posts

Arkadaşlar yeni bir kayıpsız sıkıştırma algoritması üzerinde çalışıyorum. Bu yöntemde yapılan sıkıştırma, verilerin diziliminden bir başka deyişle bir sonraki veriden bağımsız olarak her 4 byte lık veri bloğunu kendi içerisinde sıkıştırır.

 

İki bitlik işlem kodları
00 - Sıkıştırma yok
01 - 2 ^ N + D ifadesi -> Burda N maksimum 5 bit ve D ise 23 bittir. Toplam 28 bit
02 - X ^ 2 + D iadesi -> Burada X, 2 byte (16 bit), D ise 12 bittir. Toplam 28 bit
03 - Pi - Prime index -> Sayı asalsa prime indeksi saklıyoruz. 2 ^ 32 'nin altında 203280221 asal sayı vardır ve max 28 bitte saklanabilir.

 

 

Şimdi 4 byte (32 bit) lık rastgele seçilen bir sayının 1. 2.ya da 3. yöntemle gösterilebilme olasılığı %50'nin üzerinde midir değil midir? Matematik bilen arkadaşlardan rica ediyorum.

 

rastgele seçilen bir sayının asal oma ihtimali yaklaşık N / log(N)'dir. Çünkü bu N sayısına kadar olan asal sayıların sayısıdır. Bunu çok defa deneyerek buldum. Bir dosyayı 4 byte lık bloklara böldüğümde oluşan uint türündeki 4 byte lık sayıların yaklaşık %10 asal çıkıyor.

 

3. için olasılık teoreminden daha fazla determine edilmiş bir konu olduğu için elimde veri var. 

 

Fakat ilk iki yöntem için rastgele seçilen bir sayının

 

1. yöntemle gösterilebilme olasılığı ??

2. yöntemle gösterilebilme olasılığı ??

 

ve son olarak 3'ündn en az biriyle gösterilebilme olasılıklarını nasıl hesaplayabilirim. 

 

Bunun için bana yol gösterebilir misiniz?

 

Örneğin 1. Yöntemde ifade edilebilecek 

 

2 ^ 5 * 2 ^ 23

= 32 * 8.388.608 

= 268.435.456 farklı sayı vardır.

 

 

1.için kolay bir yol bulabilirim fakat 4 byte lık bir sayının, bir tam kareye uzaklığının 4095'den az olma ihtimali için nasıl bir olasılık yöntemi uygulanabilir.

 

2. yöntemde X'i asal seçsek ki 65536'dan küçük 6542 asal sayı vardır ve bu sayıya kadar olan sayılar asal indeksleriyle gösterilirse X için 13 bit ve D için 15 bit kullanılabilir böylece daha fazla sayı kapsanmış olur.

 

Sonuç olarak rastgele seçilen bir sayının, bu üç yöntemden biriyle gösterilebilme ihtimali kaba bir hesapla %50'nin üzerinde midir değil midir?

 

Bu konuda fikir yürütebilecek arkadaşlar var mı? Eğer %50'nin üzerinde çıkarsa bunu yeni bir sıkıştırma algoritması olarak kayıtlara geçirebilirsiniz.

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş
gönderildi (düzenlendi)
42 dakika önce, mirasyedi yazdı:

232=4294967296

228=268435456

28 bit ile 32 bit verinin   268435456/4294967296= 1/16=0.0625 = % 6.25  gösterebilirsin.

 

geride  kalan  4294967296-268435456=4026531840  adet sayıyı hangi bit ile göstereceksin?

 

Sen bunu boşver bu öyle hesaplanmaz rastgele seçilen her 10 sayıdan 1'i asal demek ki kazanç var.

 

Rastgele seçilen 32 bitlik sayının bu gösterimlerden en az biriyle gösterilebilme ihtimali üzerine düşün 28 bit ile gösterimdeki kombinasyon sayısı bizi çok bağlamaz. Hem zaten her 4 byte lık bloğu değil % kaçını gösterebiliriz buna bakıyoruz.

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş

Forumda böyle işleri merak edenleri görmek çok güzel.

 

11 saat önce, John_Ahmet yazdı:

Şimdi 4 byte (32 bit) lık rastgele seçilen bir sayının 1. 2.ya da 3. yöntemle gösterilebilme olasılığı %50'nin üzerinde midir değil midir? Matematik bilen arkadaşlardan rica ediyorum.

 

Aslında sorulması gereken doğru soru bu değil. Zira bu bahsettiğin olasılık %99 olsa dahi, yine sayıyı 32 bitle ifade etmiş oluyorsun. Soru şu olmalı: Bu yöntemlerle 32 bitle ifade ettiğim sayıların hepsini ifade edip, üzerine ikili gösterimle gösteremediğim(32 bitte) sayıları ifade edebilir miyim?

 

Cevabını da vereyim, edemezsin...

 

Aynı zamanda birçok sayı için aynı diziyi kullanmış olursun. Örneğin 5 sayısını düşünelim. Bu sayıyı sıkıştırmadan gösterebilirsin, 2 ^ 2 + 1 olarak da gösterebilirsin, 2^2 +1 olarak da gösterebilirsin(2'inci yöntem) ve asal indisini tutabilirsin. 5 sayısı için birden fazla ifade var gördüğün gibi. Sayılar küçüldükçe bu daha da sorun olmaya başlar. Çünkü küçük sayılarda o üstel ve polinomal ifadeleri birçok farklı şekilde yazabilirsin. Birçok farklı şekilde yazabildiğin durumların hepsinde kombinasyonları israf etmiş olursun aslında.

 

Tekrar ediyorum, istersen 32 bitle ifade edebildiğin her sayı bu yöntemlerden biriyle gösterilebiliyor olsun, ki kayıpsız sıkıştırma yaptığını iddia ediyorsan bu şarttır. Senin yönteminle, 32 bitle ifade edemediğim kaç sayıyı ifade edebiliyor olacağım? Bu yöntemlerle integerların hepsini göstermen de mümkün değildir. Örneğin 2^32-1 sayısını integer olarak gösterebilirsin. Ama senin yönteminle gösteremezsin. Böyle çok fazla sayı olduğunu tahmin ediyorum. Dediğim gibi sıkıştırmayla o oranın alakası yok ama tahmin ettiğin gibi %50'yi dahi bulmayabilir.

Link to post
Sitelerde Paylaş
9 saat önce, Bir Buçuk yazdı:

Forumda böyle işleri merak edenleri görmek çok güzel.

 

 

Aslında sorulması gereken doğru soru bu değil. Zira bu bahsettiğin olasılık %99 olsa dahi, yine sayıyı 32 bitle ifade etmiş oluyorsun. Soru şu olmalı: Bu yöntemlerle 32 bitle ifade ettiğim sayıların hepsini ifade edip, üzerine ikili gösterimle gösteremediğim(32 bitte) sayıları ifade edebilir miyim?

 

Cevabını da vereyim, edemezsin...

 

Aynı zamanda birçok sayı için aynı diziyi kullanmış olursun. Örneğin 5 sayısını düşünelim. Bu sayıyı sıkıştırmadan gösterebilirsin, 2 ^ 2 + 1 olarak da gösterebilirsin, 2^2 +1 olarak da gösterebilirsin(2'inci yöntem) ve asal indisini tutabilirsin. 5 sayısı için birden fazla ifade var gördüğün gibi. Sayılar küçüldükçe bu daha da sorun olmaya başlar. Çünkü küçük sayılarda o üstel ve polinomal ifadeleri birçok farklı şekilde yazabilirsin. Birçok farklı şekilde yazabildiğin durumların hepsinde kombinasyonları israf etmiş olursun aslında.

 

Tekrar ediyorum, istersen 32 bitle ifade edebildiğin her sayı bu yöntemlerden biriyle gösterilebiliyor olsun, ki kayıpsız sıkıştırma yaptığını iddia ediyorsan bu şarttır. Senin yönteminle, 32 bitle ifade edemediğim kaç sayıyı ifade edebiliyor olacağım? Bu yöntemlerle integerların hepsini göstermen de mümkün değildir. Örneğin 2^32-1 sayısını integer olarak gösterebilirsin. Ama senin yönteminle gösteremezsin. Böyle çok fazla sayı olduğunu tahmin ediyorum. Dediğim gibi sıkıştırmayla o oranın alakası yok ama tahmin ettiğin gibi %50'yi dahi bulmayabilir.

Konu başlığı güzel.

Bildiğimiz sıkıştırma yöntemlerini anlatsak daha iyi olur.

İnternette ve kitaplarda sözde sıkıştırma yöntemi olarak anlatılan sıfırların birlerin sayısını çarpan olarak kullanma yöntemide aynı.

Çarpanları makine koduna çevirince  veri boyu kısalacağına uzuyor. :)

Link to post
Sitelerde Paylaş
On 01.01.2020 at 21:31, John_Ahmet yazdı:

 

Sen bunu boşver bu öyle hesaplanmaz rastgele seçilen her 10 sayıdan 1'i asal demek ki kazanç var.

 

Rastgele seçilen 32 bitlik sayının bu gösterimlerden en az biriyle gösterilebilme ihtimali üzerine düşün 28 bit ile gösterimdeki kombinasyon sayısı bizi çok bağlamaz. Hem zaten her 4 byte lık bloğu değil % kaçını gösterebiliriz buna bakıyoruz.

asal sayı indeksi kaç byte yer kaplıyor?

Link to post
Sitelerde Paylaş
On 02.01.2020 at 12:27, mirasyedi yazdı:

Konu başlığı güzel.

Bildiğimiz sıkıştırma yöntemlerini anlatsak daha iyi olur.

İnternette ve kitaplarda sözde sıkıştırma yöntemi olarak anlatılan sıfırların birlerin sayısını çarpan olarak kullanma yöntemide aynı.

Çarpanları makine koduna çevirince  veri boyu kısalacağına uzuyor. :)

 

Haklısınız kaç kişi ilgilenir bilmiyorum. Örneğin Kormogolov karmaşasından bahsedilebilir. Bilirsiniz ben bir şeyin yapılmasının fiziksel sınırlarını hesaplayabileceğini sanan kormogolov karmaşası, termodinamik kanunları, entropi ile ilgili diğer tez ve hipotezleri pek sevmem. İnsanoğlu kendine sınırlar çiziyor sonra bu sınırları aşanlar mutlaka oluyor.

Link to post
Sitelerde Paylaş
gönderildi (düzenlendi)
8 dakika önce, mirasyedi yazdı:

asal sayı indeksi kaç byte yer kaplıyor?

 

Örneğin 0-255 arasında 54 asal sayı vardır. Bir bytelık asal sayılar 0-53 arası sayılarla ifade edilebilir. Bu da 8 bit yerine 6 bit demek oluyor. Aslında bunun için daha iyi bir formül var bu belirli bir N sayısına kadar olan asal sayıların miktarı ile ilgilidir.

 

(Edit: Neden altı bit? 2 ^ 6 = 64, bu sayıya kadar olan sayıları 6 bit ile saklayabilirsiniz. 64 hariç.)

 

N / log(N) bu bize bir şeyler anlatabilir. https://en.wikipedia.org/wiki/Prime-counting_function

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş
gönderildi (düzenlendi)
19 dakika önce, TanrıBeniNiyeKorudu yazdı:

çok özür dileyerek yazdıklarınıza ve konuya çok bir katkı sağlayacağımı düşünmüyorum ama hep merak ettiğim birşey var örneğin 16 gb lık bir hafıza kartını 32 gb lık bir hafıza kartına dönüştürmek mümkünmüdür?

 

16GB ve 32GB SD kartların boyutu aynıdır. Demek ki fiziksel olarak 32GB daha fazla alana ihtiyaç duymuyorsa 256GB'da saklayabilirsiniz demektir.

 

Elbette sıkıştırma algoritmalarıyla uğraşan bizler her ne kadar veri diziliminden bağımsız sıkıştırma algoritması üretebileceğimizi söylesek de tamamen verilerden bağımsız düşünmüyoruz.

 

Dolayısıyla büyük ihtimalle senin bu hafıza kartında metin, fotoğraf ve video saklayacağını öngörerek bilinen sıkıştırma algoritmaları ile 16GB alanda sıkıştırılmış formatlar ile 32GB'lık veri saklamanı sağlayabiliyorlar.

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş
21 saat önce, John_Ahmet yazdı:

 

16GB ve 32GB SD kartların boyutu aynıdır. Demek ki fiziksel olarak 32GB daha fazla alana ihtiyaç duymuyorsa 256GB'da saklayabilirsiniz demektir.

 

Elbette sıkıştırma algoritmalarıyla uğraşan bizler her ne kadar veri diziliminden bağımsız sıkıştırma algoritması üretebileceğimizi söylesek de tamamen verilerden bağımsız düşünmüyoruz.

 

Dolayısıyla büyük ihtimalle senin bu hafıza kartında metin, fotoğraf ve video saklayacağını öngörerek bilinen sıkıştırma algoritmaları ile 16GB alanda sıkıştırılmış formatlar ile 32GB'lık veri saklamanı sağlayabiliyorlar.

Bitler transistorlar ile saklanır işlenir.

Transistorların  alanı küçütülürse aynı alana daha çok bit saklarsın.

32 gb Sd kartta 16 gb Sd karta göre daha çok transistor vardır.
Transistorların boyutlarını küçültme imkanın yoksa yonga levhalar ince olduğu için üst üstede dizebilirsin.Alan aynı kalır.

 

Link to post
Sitelerde Paylaş
gönderildi (düzenlendi)
7 dakika önce, mirasyedi yazdı:

Bitler transistorlar ile saklanır işlenir.

Transistorların  alanı küçütülürse aynı alana daha çok bit saklarsın.

32 gb Sd kartta 16 gb Sd karta göre daha çok transistor vardır.
Transistorların boyutlarını küçültme imkanın yoksa yonga levhalar ince olduğu için üst üstede dizebilirsin.Alan aynı kalır.

 

Elbette ancak kullanılan madde miktarı ile ilişkilendirdiğinde 16GB ve şu an bildiğim en yüksek boyut olan 512GB aynı boyuttadır. Sınır bilimin uzandığı en son nokta henüz piyasada olmasa da 2TB boyutuna kadar ulaşabiliyor. Grafen gibi yeni teknolojilerle bunu milyonlarca kat artırabileceklerini söylüyorlar. Peki nereye kadar gider? Her elektronda 1bit olabilir mi? Bunun ötesine geçmenin mümkün olup olmayacağını henüz deneyimlemedik dolayısyla mümkün olabilir. Böylece bunun bir sınırı olabileceğinden bahsetmek için henüz çok erken ben bunu kastetmiştim.

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş

Ayrıca bir konuya değinelim.

Integer(4 bayt olarak ele alırsak), 4.294.967.296 farklı değer alır. Aslında bunu birebir eşleme yapan bir fonksiyon olarak düşünebilirsin. Hedefin nedir? Integer'ları daha az baytla göstermek mi? O kümeyi daha az baytla ifade edemezsin. Zaten 4 baytın bütün kombinasyoları ayrı bir sayıyı ifade ediyor. Bunu 4 bayt bazında geçmen mümkün değil. Nasıl ifade etmeye çalışırsan çalış.

4 baytı farklı kullanabilirsin, tersten yazabilirsin, "her yazdığım sayının 10 katını ifade ediyor olayım" diyebilirsin, aralıkları vs değiştirebilirsin. Ama bu şekilde herhangi bir sıkıştırma yapamazsın Integer'lar üzerinde. Limit o çünkü.

Link to post
Sitelerde Paylaş
gönderildi (düzenlendi)
7 saat önce, Bir Buçuk yazdı:

Ayrıca bir konuya değinelim.

Integer(4 bayt olarak ele alırsak), 4.294.967.296 farklı değer alır. Aslında bunu birebir eşleme yapan bir fonksiyon olarak düşünebilirsin. Hedefin nedir? Integer'ları daha az baytla göstermek mi? O kümeyi daha az baytla ifade edemezsin. Zaten 4 baytın bütün kombinasyoları ayrı bir sayıyı ifade ediyor. Bunu 4 bayt bazında geçmen mümkün değil. Nasıl ifade etmeye çalışırsan çalış.

4 baytı farklı kullanabilirsin, tersten yazabilirsin, "her yazdığım sayının 10 katını ifade ediyor olayım" diyebilirsin, aralıkları vs değiştirebilirsin. Ama bu şekilde herhangi bir sıkıştırma yapamazsın Integer'lar üzerinde. Limit o çünkü.

 

Haklısın açıklama yapmayınca konu havada kalıyor ve senin sorduğun sorular insanın kafasında oluşuyor. Merak etme hepsine çözüm var.

 

İlk olarak şunu söyleyeyim her 4 byte'ı sıkıştırmıyoruz bir kural ya da desen arıyoruz.

 

Örneğin;

 

Basit bir örnek olması açısından çift sayıları sıkıştıralım. Bunu nasıl yapıyoruz? Bir dosyayı 4 baytlık dilimlere ayıralım. Sonra bu 4 baytlık sayıların tek sayı olanlarını aynen kaydedelim ama çift sayı ise (2n) sadece n'i 31 bitte saklayalım..

 

Şimdi bunu yaparken bize bir bit haritası gerekli olacak her 4 bayt için bir bit kullanıyoruz. Sayı çift ise bit 1, tek ise bit 0.

 

Eee diyeceksin bunu yaparak nasıl kazanç sağlıyacaksın. Bu dosya boyutunu azaltacağı yerde artırmaz mı?

 

Evet ham haliyle evet artırır. Zaten herhangi bir dosyadaki çift sayılar ve tek sayıların oranı yaklaşık olarak %50 %50 oluyor.

 

Dosya boyutunun 8 milyon bayt olduğunu düşün. Yaklaşık 1 milyon tek ve 1 milyon çift sayımız olur.

 

2 milyon biti bit haritası için kullanacağız demektir. Bu da 125 bin bayt eder. Peki her çift sayıyı da 31 bite saklayacaktık bu da dosyanın 1/2 * 1/32 = 1/64'ü kadar kısalacağı anlamına gelir.

 

Dosya 1 / 64 kısalıp 1 / 32 artarsa toplamda dosya boyutu artar.

 

1 - (1 / 64) + (1 / 32) = 1,015625

 

Ancak bit haritasını ham haliyle kaydetmiyoruz. Çift sayı olunca 1, tek sayı olunca 0 şeklinde oluşturduğumuz bit haritasında çok fazla tekrar eden bayt oluşuyor. Bunun nedeni örneğin sekiz adet 1 ya da sekiz adet 0'ın çok az sayıda olması ve orta değerlerdeki sayıların daha fazla olmasından mütevellit bu bayt dizisini Huffman, LZ4 ya da PAQ8 gibi algoritmalarla sıkıştırıp %50'den fazla sıkışmasını sağlıyoruz. Eğer %50'den fazla bir başarı sağlanmış olursa Örneğin % 40 için tekrar hesaplayalım.

 

1 - (1/64) + (1/32*40/100) = 0,996875 böylece dosya boyutunu azaltmış olduk.

 

Hatta PAQ8 algoritması bu konuda çok iyi ve %30'lara varan oranlarda bit haritamızı sıkıştırabiliyor.

 

(Not: compression ratio = compressed size / orginal size olarak hesaplanır)

 

 

Sonuç olarak bayt dizisinden ve tekrar eden baytlardan bağımsız olarak bir sıkıştırma algoritması geliştirmiş olduk ve bunu tekrar tekrar uygulayabiliyoruz.

 

Örneğin yukarıdaki oranı 1000 tekrar için hesaplarsak toplam sıkıştırma oranımız

 

0,996875 ^ 1000 = 0,04372247491698905175391507256631‬

 

Neredeyse 25 kat küçültmüş olduk.

 

Bu yöntemde artık sayıların azalacağını, dolayısıyla her sıkıştırmada dizideki çift sayıların azalacağı düşünülebilir. Olsun tek sayıları da 2n+1 olarak ifade edip n'i yine saklayabiliriz. Her defasında yalnız 1 algoritma kullanmak şartıyla en uygun olanı seçilip o kullanılacak olsun. Bu tekrarları da saklamak gerekecek ve 1000 tekrar için dosya boyurumuz 25'te birine düşerken sadece 125 bayt artacak. Hiç sorun değil.

 

Asal sayı konusu da buna benzer şekilde çalışıyor ve o daha da verimli bir yöntem.

 

Dosyanın türü ne olursa olsun bu yöntemde hemen hemen aynı başarıyı alıyoruz. Arşiv dosyalarını sıkıştırmak için kullanabilirsin.

 

 

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş

4 byte'ı tamsayıya çevireceksin,

2'ye bölünüyor mu diye bakacaksın,

2'ye bölünüyorsa bit indexine 0 yazacaksın, yani 4 byte'ın son byte'ını shift ile alacaksın.

 

Örneğin 4 byte:

55 

22 

11 

02

Bit cinsinden:

0000 0000 0011 0111

0000 0000 0001 0110

0000 0000 0000 1011

0000 0000 0000 0010

 

Bit indexine yazacaksın, sayıyı logical shift operasyonuyla öteleyeceksin. Fakat bilgisayarda 3.875 byte'lık alanlar yok, word ve dword var. Yani shift başa bir 0 koyacak.

00000 0000 0011 011

10000 0000 0001 011

00000 0000 0000 101

10000 0000 0000 001

 

Bir şekilde bütün yerleştirme sorunlarını çözsen bile sonuçta elde edeceğin şey 4 byte - 1 bit = 3.875 byte  + 0.125 byte index. Şimdi sen sadece indexi sıkıştırmak istiyorsun.  Halbuki indexin dağılımı "daha efektif sıkışacak" diye bir kural yok. Çünkü çift sayı bitlerinin yerlerini bilmiyorsun. Rastgele dağılıyorlar. Onların dosyadaki yerlerini de tutan başka bir indexin olsa bit başına en az 4 byte harcaman gerek.  1 bit için 32 katı büyüklüğünde bir sayı harcayıp sonra da bunun efektif sıkışıp sıkışmayacağını soryursun.

 

Hiçbir işe yaramayan bir index yapıp sıkıştırmaya çalışmak birden bire dosyanı küçültmez.

 

Link to post
Sitelerde Paylaş
On 01.01.2020 at 15:24, John_Ahmet yazdı:

Bu yöntemde yapılan sıkıştırma, verilerin diziliminden bir başka deyişle bir sonraki veriden bağımsız olarak her 4 byte lık veri bloğunu kendi içerisinde sıkıştırır.

 

15 saat önce, John_Ahmet yazdı:

İlk olarak şunu söyleyeyim her 4 byte'ı sıkıştırmıyoruz bir kural ya da desen arıyoruz.

Evet ham haliyle evet artırır. Zaten herhangi bir dosyadaki çift sayılar ve tek sayıların oranı yaklaşık olarak %50 %50 oluyor.

Dosya boyutunun 8 milyon bayt olduğunu düşün. Yaklaşık 1 milyon tek ve 1 milyon çift sayımız olur.

Sonuç olarak bayt dizisinden ve tekrar eden baytlardan bağımsız olarak bir sıkıştırma algoritması geliştirmiş olduk ve bunu tekrar tekrar uygulayabiliyoruz.

 

İddian hangisi?

Ben diyorum ki, ilk alıntıladığım iddiandaki şeyi yapman mümkün değil. Sonra verdiğin örnekse ilk iddiandakiyle aynı şey değil.

Link to post
Sitelerde Paylaş
6 saat önce, bayşapka yazdı:

son byte'ını

 

Son byte'ını değil ilk byte'ını. En düşük değerli byte son byte değil ilk byte'dır. Sadece byte ları düşün.

 

Örneğin 7 bitte 0-127 arasındaki sayıları saklayabilirsin. Örneğin 254 8 bitlik bir sayıdır fakat yarısı 127 7 bitte saklanabilir. Sayıyı ikiye bölüp sadece anlamlı bitleri saklıyoruz. En yüksek değerdeki biti almıyoruz, çünkü zaten 0 oluyor. Şimdi anladınız mı? Bu 32 bit için de aynen geçerli bu defa 31 bit kullanarak saklayabiliyoruz.

 

Bit haritası da 4 baytlık sayı dizisindeki çift sayılara denk gelen her sayı için 1, tek sayılara denk gelenler için de sırası ile 0 bitini kullanıyoruz. Böylece her 4 baytlık sayının sıkıştırılıp sıkıştırılmadığı bilgisi 1 bitte saklanmış oluyor. Sonra bu bit dizisini bytelarda saklayıp (her 8 bit bir byte) bilinen algoritmalarla %50'den daha fazla sıkıştırmayı deniyoruz. PAQ8 bu konuda çok başarılı denediğim için biliyorum.

 

Bir dizi 32 bit ve 31 biti ardı ardına nasıl saklarız? Bu da ince programcılık bilgisi gerektiriyor. BitStack isimli bir sınıf oluşturuyoruz. Benim hazırladığım MyBitArray isimli bir sınıfım var. Bu sınıf ile bir yığın bit dizisini byte dizilerinde saklayabiliyorum ve istediğim bitine erişebiliyorum. Bu sınıftan türüyen ve write31Bit, write32Bit, read31Bit, read32Bit isimli metodlara sahip BitStack isimli bir sınıfı rahatlıkla türetebilirim.

 

2 saat önce, Bir Buçuk yazdı:

İddian hangisi?

Ben diyorum ki, ilk alıntıladığım iddiandaki şeyi yapman mümkün değil. Sonra verdiğin örnekse ilk iddiandakiyle aynı şey değil.

 

Güleyim mi ağlayayım mı? Anlamadığınız nasıl da belli, nasıl aynı şey değil aynı prensiplerle çalışıyoruz. X ^ 2 + D şeklinde D 17 bit olmak koşulu ile gösterilebilenler gösterilemeyenler, asallarda da yine aynı asal olanlar 28 bitte indeksleriyle saklanıyor vs.

 

public class BitStack: MyBitArray

{

  long bitIndex;

 

     uint read31Bit() {

     // todo

  }

 

 

  uint read32Bit() {

     // todo

  }

 

 

     void write31Bit(uint dword) {

     // todo

  }

 

 

  void write32Bit(uint dword) {

     // todo

  }

}

 

public class MyBitArray: IDisposable
    {
        byte[] bytes;
        public MyBitArray(long limit, bool defaultValue = false)
        {
            long byteCount = Convert.ToInt64((limit >> 3) + 1);
            this.bytes = new byte[byteCount];
            for(long i = 0; i < byteCount; i++)
            {
                bytes = (defaultValue == true ? (byte)0xFF : (byte)0x00);
            }
            this.limit = limit;
        }

        public MyBitArray(long limit, byte[] bytes)
        {
            this.limit = limit;
            this.bytes = bytes;
        }

        public bool this[long index]
        {
            get
            {
                return getValue(index);
            }
            set
            {
                setValue(index, value);
            }
        }

        bool getValue(long index)
        {
            if ( index < 8 )
            {
                return getBit(bytes[0], (byte)index);
            }

            long byteIndex = (index & 7) == 0 ? ((index >> 3) - 1) : index >> 3;
            byte bitIndex = (byte)(index & 7);
            return getBit(bytes[byteIndex], bitIndex);
        }
        void setValue(long index, bool value)
        {
            if ( index < 8 )
            {
                bytes[0] = setBit(bytes[0], (byte)index, value);
                return;
            }

            long byteIndex = (index & 7) == 0 ? (index >> 3) - 1 : index >> 3;
            byte bitIndex = (byte)(index & 7);

            
            bytes[byteIndex] = setBit(bytes[byteIndex], bitIndex, value);
        }

        bool getBit(byte byt, byte index)
        {
            return ((byt & (1 << index)) >> index) == 1;
        }

        byte setBit(byte byt, byte index, bool value)
        {
            return (byte)((byt & ~(1 << index)) + (value ? 1 << index : 0));
        }

        public void Dispose()
        {
            GC.Collect(2, GCCollectionMode.Optimized);
        }

        private long limit;
        public long Limit { get { return limit; } }
        public byte[] Bytes { get { return this.bytes; } } 
    }

 

 

 

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş

Merak etmeyin yakında GNU standartlarında ari isimli bir executable ile dosyalarınızı

 

ari -c ---repeat 1000 filename

 

şeklinde sıkıştırıp

 

ari -e filename

 

ile extract edebileceksiniz. ARI benim soy ismimin ilk üç harfi ve i sayıda sıkıştırılabilen archive dosyalarını anımsatması ile isabet oldu. :)

 

Önceki yazımı okumayı ihmal etmeyin.

tarihinde John_Ahmet tarafından düzenlendi
Link to post
Sitelerde Paylaş

İNFORMASYON ENTROPİSİ

Link to post
Sitelerde Paylaş
  • Konuyu Görüntüleyenler   0 kullanıcı

    Sayfayı görüntüleyen kayıtlı kullanıcı bulunmuyor.

×
×
  • Yeni Oluştur...