Dictionary based compression'da ayraç

[SpiderS_DangeR]

Şimdi elimizde bazı film isimleri ve çok büyük bi film listesinden kelimelerin frekanslarına göre oluşturulmuş basit bi dictionary file var.
Dictionary şöyle bişey mesela

	1	the

	10	love

	11	kill

	

Movie title da şöyle olsun: He killed the love of my life.
şimdi bu titledaki sözlükte yer alan kelimeleri dictionarydeki değerleriyle değiştiriyorum ve sözlükte olmayan değerler aynen char char binary olarak kodlanıyor. Fakat dictionary değerleri fixed length olmadığı için bi şekilde bu değerleri diğer charlardan ayırt etmem gerekiyor. Her seferinde araya 1 bytelık bi değer koyabilirim (mesela $ falan) fakat 1 byte fazla bu iş için, 4 bitlik falan bişey olması lazım. Nasıl olur bu iş?

[Fly]

ondan once codewordler birbrinini prefixi olabiliyor, anlasilabilir bir daraltma olmuyor oylesine vermediysen kelimelerin karsiliklarini

bir suru sey mumkun dedigin olay icin

en kolayi her sembol ve codeworde 1 bit overhead katarak daralmis veya daralmamis bit serisi diye isaretlemek
veya rle kafasiyla usttekinden daha verimli oluyorsa devamindaki kac blogun daralmis/normal oldugunu belirleyip oyle
veya dedigin gibi bir delimiteri codewordlerinle karismayacak, daralmamis bloklarda da en az rastalanan prefix olacak sekilde sececeksin, onunla state degisimi yapacaksin
ama state degisimi cok olursa sacma olacak, hangi sembol/word ne kadar tekrar ediyor ona bakarak en uygununu sececeksin

kabaca kimin daralmis kimin normal oldugun bir sekilde isaretlemen gerek iste

ders olarak goruyorsan aslinda huffman agacidir entropidir ne ise yariyorlar bunlardan bahsetmis olmalari lazim, uncompressed veri birakma durumu oldugu icin sana %100 hitap etmese de onlarin yaptigi islerden ilham alabilirsin bu isaretlemede en uygun neler yapabilecegini kestirmek icin

atiyorum 3 daralmis 1 daralmamislar kumesi seklinde 4 codeword ve frekanslarini alip nelerle ifade edebilecegini hesaplayip son daralmamis sembolunu direk kullanmayacagini goz onune alarak yola cikabilirsin

[SpiderS_DangeR]

Huffmana falan baktım da, dediğin gibi o tür algoritmalarda bütün veriyi compress ettikleri için bulamadım bu soruna çare.

1 bitlik overheadde de şöyle bi sorun var, bir kelimenin kaç byte'dan oluştuğunu bilmediğim için hangi bitlerin overhead olduğunu anlayamıyorum. Belki her kelime 8in bir katı uzunluğunda bit sayısına sahip olmak zorunda olduğu için bir şekilde ayrıt edilebilir bu ekstra bit fakat bu sefer de dictionarydeki değerlerin kaç bit olduğu belli değil. Mesela en çok tekrar eden ilk iki kelimeyi 1 bitle kodlamak lazım, sonraki 4 kelimeyi 2 bitle vs.

[Fly]

kelime-byte derken ?
metnin encodingi mi habire degisiyor (ki cok enteresan bir durum olur bu) ?

bunu demediysen hayir, anlarsin
prensibi o zaten
duzgun kodlandiktan sonra kelimenin uzunlugu umrinda degil cozum sirasinda

tam compression yaptiginda dedigim prefix barindirmama kurali sayesinde delimitersiz algilayabiliyorsun kim nedir

ayni olayi buna uyarlayacaksin :

0 - awesome
10 - movie
11 - the

olsun total daraltma icin
hicbiri birinin prefixi degil dikkat ettiysen
bu ornekte cok bariz hani, 0 ile baslayan sadece ilki, 1 ile baslayan da 10 veya 11'e dallanabiliyor sadece

(0 ve 01 olsaydi iste o zaman patlardi mesela)

tipik ascii 8 bit encoding olsun normal yazi icin

0<0x31>111110100<0x32> -> 1 the awesome movie 2

flag 0 oldugunda pesinden gelecek 1 ascii karakteri
1 oldugunda pesinden daraltilmis bir veri, onun bitisini bilmenin sebebi ise prefix olmama kurali

normalde delimiter olmadan komple compressionda <>'lari codeword olarak dusunursen su yani kural

herhangi bir = olmayacak

bu sekilde tam compressionda bodoslama sifirlar birler versen de ayracsiz aciliyor metin

istedigin seye uzatirsak 1=11 olmayacak demek oluyor bu

1<>'leri de asil uretmek istedigin codeword olarak gorebilirsin bu vesileyle, 1= gibi
yine = olmayacak kuralina dusuyoruz buradan da, ama daha spesifik olarak bu codewordlarin daralmamis olan sembollerden ayrilabilmesi icin muhakkak 1 ile basliyor olusu

benim verdigim ornekte mesela imkani yok (10,111,110), ilk bitler hep 1 ve codewordlerin hicbiri digerine prefix olamiyor

zibilyon tane olursa napicaz dersen iste huffman tree vs orada devreye giriyor asil

[SpiderS_DangeR]

Abi tamam da şimdi hiçbir codeword'ün birbirinin prefixi olmaması için bu codewordlerin hepsinin aynı uzunlukta olması lazım. Mesela 001 olsun bi codeword, bu durumda 001xxxxxxxxxx lerin hiçbirini kullanamıyorum. Veya senin dediğin örnekte:
0, 10, 11 kullanmam durumunda başka hiçbir codeword kullanamıyorum çünkü bu verdiklerin yeni kullanacaklarımın prefixi olacak. Ama benim istediğim bazı kelimeler 1 bitlik codewordle ifade etmek mesela.
Veya ben ne dediğini anlamadım :D

[Fly]

tamam biraz anladim asil derdini

kisa cevap : geleneksel sekilde yapamazsin onu

uzun : dedigin gibi ABCxx'ler kapilmis oluyor, huffman agacinin olayi tersten giderek cok codewordun varsa daha uzun codewordler secerek cakismayi engellemek

ama 1 bitle ifade edlecek iki kelime, 2 bitle 4 tane... diye gitmek istiyorsun diye anladim ben

"bir bildikleri vardir" kivaminda olacak cevabim da dictionary bazli compression yapacaksan az bucuk yerlesmis prensipler bunlar; codeword uzunlugu azaltayim derken karisiklik olmasin diye ortaya delimiter koymadan halledemeyecegin bir durum ortaya cikacak, daha verimsiz bir sey elde edeceksin muhtemelen birkac spesifik durum disinda

(illa 1 bitle iki 3 bitle 8 farkli sey olabilecek demiyorsan gerisini okuma, aradigin sey agac olusturarak en uygun uzunlukta wordler olusturmak)

yine de sorun degil dersen sonra network protokollerinin bir kisminda oldugu gibi length vs belirttigin bir model alabilirsin

metinde degil de encoder icinde tut once compressed/normal olacak dedigin bloklari

mesela fieldin uzunlugu kac codewordun olacagina bagli degisir

dedigim uc codewordu dusun
metin icinde daraltmayacagin ve arka arkaya gelsin diyecegin en uzun kelime de 7 harf olsun, daha uzun seriler tekrar header alarak ifade edilsin :

Compressed/Normal | Length | Data

10010 -> awesome
101010 -> movie
101011 -> the

edit : hatta soyle olsun

1000 / awsum
1001 / muv
10100 / the

length field + 1 kadar data uzunlugu oldugunu varsayabilirsin misal

duz karakterler icin de

0100<0x31><0x32><0x33><0x34> -> 1234

ha mesela normal metin icin uzunluk olmasin veya
0<0x31>0<0x32>0<0x33>
seklinde de ayristirabilirdin 3 karaktere kadar
5 ve sonrasinda daha inefficient oalcakti

ya da 7 degil 3 yapayim bu siniri diyecektin farkli sonuclar olacakti vs vs

en olabilecek sey bu gibi geliyor

delimiter koyayim dersen o delimitera hicbir codeword sahip olamayacak diyebilirsin
ama codeword havuzun uzadikca isler sarpa sarmaya baslayacak
ve yine oyle bir havuzum olsun ki ambiguity olmasin olayina tekrar doneceksin delimiter yuzunden

0 1 ve 11 olsun wordlerin 0xff delimiter

0 0xff 1 0xff 11 0xff 0 0xff

mesela surada 1 ile 11'i ayirt edebilmenin tek yolu 11'den sonra gelen 0 oldugunu farkedip aa dur 0x010xff0x01 degil de 0x020xff ya bu diye geri donmek olacak

boyle olmasin dersen baska word secmek icin tablodan devam edeceksin uygun biseyler bulmaya
derken isler sarpa saracak

binaryde delimiterin sorun cikardigi nokta verinin bir sonrakine akip akmayacaginin garantisi olmamasi ; ethernet frame yapar gibi delimiter/veri farkini algilaman mumkun belki de farkli olarak bodoslama veri atmiyorsun, birazi dar birazi normal ortaya karisik bir corba var

alternatif olarak binary degil 4lu taban vs ile yapabilirsin eger epey bir kelime varsa codeword uzunlugun belli sayilarin katlari olsa da verimli olacaksa

sabit word uzunlugu alirsan en rahati her ne kadar sna uymasa da
daha buyuk blok alirsan okuman gereken kac bit oldugunu bilirsin

degisken uzunluk alirsan ambiguity olmayacak sekilde word sececeksin yine

karakter bazli bir ey yapayim dersen mesela buna en rahat ornek

| delimiterin olsun benden sonra compressed geliyor demek icin, > olsun normal demek icin
hicbir word | ve >'u icermesin

ab|a|cdsdggh>skgjhgfdgjhghsrw87t8gy>dfkjdsfjh|c

dediginde ayirt edebilmen cok rahat
da verimli olacak mi olmayacak mi onu bilemem

okul odevi yahut illa boyle olacak demeniz gereken bisey degilse standartlara don derim
oteki turlu dedigim protokol kafasi veya karakter tabanli olan en kolay yapilabilecekler

[SpiderS_DangeR]

Okul projesi, danışmanım böyle yap dedi ve yaklaşık 5k kelime var dictionaryde. Bu yöntemi seçmemizin nedeni decode ederken öyle huffman gibi tersen treede dolaşmamız gerekmemesi, sadece codeworde sözlükten bakıp, gerçek değeriyle replace edebilmemiz.
Şimdi şu compressed/uncompressed|length|data olayını düşünüyorum da compress edilebilecek word sayısının belirli bir oranın üstünde olması lazım ki compression'dan kar etmeye başlayabileyim.
Delimiter'de şöyle bir sorun var. Codewordlerin fixed size olmadığını varsayıyoruz. Diyelim ki delimiterim 00000000 ve 100 ve 001 olarak 2 codewordüm var. Bunlar ardarda gelince 10000000000001 oluyor, ben o aradaki hangi bitlerin delimiter olduğunu nasıl anlayabilirim?

[Fly]

abi hayir
treeyi ust uste binmeyecek wordler olusturmak icin, encode sirasinda kullaniyorsun
karsiliklar metadata olarak hashtable kafasinda tutulur
decode ederken direk orayi kullanirsin

benim takildigim nokta codeword havuzunun suyunu sikma durumu
danisman mi dedi bitin elverdigi kadar word sokustur diye
bir kismini daraltmamak niye zorunlu
veya delimiteri mi o zorladi, tam olarak ne kisitlar verdi

dedigin ornekte de word uzunlugu dinamik ise delimiterin mantigi zaten veriden net olarak ayirt edebilecegin bir blok olmasi, o olay olmazsa imkani yok

00 11 001 1 ahmet
001 1 00 11 ahmet

ayni seri, iki farkli yorum mesela
veri kaybetmemek icin ek seyler koyman lazim
onlarin da ambiguitye yol acmayacak sekilde olmasi icin yerlesmis metodlar da bahsettiklerim iste

lengthli olaya ek olarak ikinci bir kumede
(3<<1 | 0x0)(1<<1 | 0x0)(2<<1 | 0x0)(2<<1 | 0x0)(0x1)(0x1)... gibi kac biti kaale alacagini/compression state'i tutarsin

sonra onu run length encoding ile daraltmaca ve frekans domainine gecerek ifade etmek gibi zihnisihir projelerine yelken acabilirsin vs vs

[SpiderS_DangeR]

Danışmanın verdiği kısıt codewordün fixed length olmaması, bu durumda da blok blok okuma yapamayacağım için bir şekilde codeword bloklarını ayırt etmek için bir yol bulmam. Bazı kelimelerin compress edilmemesi de şunun için, şimdi bu bir XML dosyası, smart TV ile smart phone arasında transfer edilmesi lazım. Eğer dynamic veya semi-dynamic bi dictionary kullanırsak bu dictionarynin de her XML için ayrıca oluşturulup transfer edilmesi gerekecek, bu da smart TV gibi pek de yeterli olmayan cihazlar için ekstradan yük. Bunun olmasını istemiyor danışmanım, o yüzden statik bir dictionary kullanılması lazım. Statik kullanınca da doğal olarak bazı kelimeler bu dictionaryde olmayacak.

[Fly]

o kisit olmasa aklima bisey gelmisti de

**tek** kisit buysa, tek bite 2 eslestirmen vs zorunlu degilse, dinamik olacaksa huffman ve frekans/entropi hesabi arti compression flag olayi iste ?

direk frekans hesabiyla :

agirlikli frekanslari belirleyeceksin (ahmet 10 kez cekoslavakyalastiramadiklarimizdanmisiniz 5 kez ise ceko- daha agir yani)
huffmana sokacaksin bunlari, kisit olarak 0 veya 1 ile baslayacaklar (normal/compressed flag, hangisi neyi ifade etsin dersen),
overlap olmayan codewordler elde edeceksin

bunlarin icinde 001xxx olayi olacak evet, ama 5k entryli sozluk var diye direk belirttigin icin sonradan gelecek olanlar diye bahsettigin olayin bir gecerliligi yok

cozerken tree traversal stili bir search yapacaksin evet

bunu istemiyorsan length|... olan sey iste

az degisigi dersen
codewordleri 0 1 00 01 vs diye 0->5k 'ya kadar direk vereceksin, tercihen frekans azalan seklinde

ek olarak ikinci bir bantta da ana banttan kac bit okuman gerektigini gosteren veri olacak

0 ise compression yok, direk oku
1+13 bit (=n) ise arrayimdeki n. kod diye okuyacaksin direk

Value = 0 | 1<13bit>

oldugu icin ambiguity yok bunda, ya 1 ya da 14 bit ilerleyeceksin, ilerlerken de ana banti cozeceksin

[SpiderS_DangeR]

Peki bu codewordleri elde etmek için huffmana soktuk diyelim, 5k tane prefix-free codeword elde edebilmek için kaç bite kadar çıkmam gerekiyor acaba? En sonunda 5 bytelık kelimeyi 10 bytle ile encode etmeye çalışırken bulmayayım kendimi?

[Fly]

20-25 bit falan olur sanirim