"Pahastutteko siellä MeliaVolumessa jos Claude E Shannon ehti kommentoida jo 58 vuotta sitten? "

Ei pahastuta. Toivon mukaan et itse pahastu kun huomaat olevasi väärässä ja tukeutuvasi Claude Shanonin kehittämiin laskelmiin. Huvittavaa lienee tässä se, että jo herra Huffman, jonka professori oli mukana Shannon Fanon tutkimusryhmässä osoitti että on olemassa parempikin algoritmi. Tämä tunnetaan nykyisin nimellä Huffmanin koodauksena.

Ei tässä olla kusettamassa tai riidanhakusia. Olen tehnyt keksinnön, ja sillä sipuli.

Pidämme lehdistötilaisuuden asiasta ja voin olla varma että se tulee olemaan ikimuistoinen. Lupaan todistaa väitteeni todeksi sielä ja for the regord:

Todistan
- kaikki data on pakattavissa TEOREETTISEEN rajaan asti
- kieroksien suorittmaninen jo pakatulle tiedolle
- häviötön tekniikka. MITÄÄN EI KADOTETA

----------------------------------------------------------
MeliaVolume Oy
IT-ja mainostoimistopäällikkö

Sebastian de Mel
Vanha-Juvankatu 2 E 41
33710 TAMPERE
FINLAND

e-mail: sebastian.de.mel@meliavolume.fi

www.meliavolume.fi
mainostoimisto.meliavolume.fi

Huffman-koodaus on lähteen koodauslauseen (source coding theorem) mielessä ns. optimaalinen koodi. Se juuri niin hyvä kuin koodaus voi tuon lauseen nojalla olla, ei parempi. Jokaiselle jakaumaltaan tunnetulle tietolähteelle (kaikki oikeasti pakattavaksi annettava data luonnollisesti on tällaista) voidaan konstruoida tällainen koodi, joka minimoi sanapituuden, eli pakkaa parhaalla mahdollisella tavalla.

Toki kaikki data on pakattavissa teoreettiseen rajaan saakka. Onko joku väittänyt, ettei olisi? Se teoreettinen raja on tunnettu jo pitkään, joten on sumutusta puhua tämän hetken teoreettisesta rajasta.

Pakkauksen iterointi (kerran pakattu pakkautuu lisää) kertoo siitä, että algoritmi on hidas. Kompleksisuudeksi tulee vähintään O(n^[iterointimäärä]).

Häviötön tekniikka kertoo siitä, että pakkaus on ns. yksikäsitteisesti purkautuva koodi. Se on koodaukselta varsin miellyttävä ja tavoiteltava ominaisuus.

En minä riitaa haasta, vaan harmittelen noloa tapausta.

mikäs olis sun mielestä se max. raja minkä alle ei mennä esim. 500 tavun tekstitiedostossa?

Tunnetko softaa joka pakkaa tollasta, ilman että koko kasvaa?

Teoreettinen minimi on 0, mikäli lähdettä ei spesifioida. Tällaisessa tapauksessa lähde voidaan valita siten, että entropia on nolla, joten triviaalisti koodatun lähteen alarajakin putoaa nollaan.

Eikö mikä tahansa pakkaussofta osaa pakata redundanttia dataa? Sehän on vähän niinkuin niiden olemassa olon tarkoitus. Vastaavasti mikään pakkausohjelma ei saa yksikäsitteisesti pakattua täysin satunnaista dataa. Tämä on suora seuraus lähteen koodauslauseesta.

Demonstraatio

terotil@tavi:~/tmp$ dd if=/dev/urandom of=testi-rand bs=1c count=500
500+0 tietuetta sisään
500+0 tietuetta ulos
500 bytes transferred in 0,011933 seconds (41901 bytes/sec)
terotil@tavi:~/tmp$ dd if=/dev/zero of=testi-redu bs=1c count=500
500+0 tietuetta sisään
500+0 tietuetta ulos
500 bytes transferred in 0,008555 seconds (58445 bytes/sec)
terotil@tavi:~/tmp$ ls -l testi-*
-rw-r--r-- 1 terotil terotil 500 2006-08-08 13:04 testi-rand
-rw-r--r-- 1 terotil terotil 500 2006-08-08 13:04 testi-redu
terotil@tavi:~/tmp$ bzip2 testi-*
terotil@tavi:~/tmp$ ls -l testi-*
-rw-r--r-- 1 terotil terotil 665 2006-08-08 13:04 testi-rand.bz2
-rw-r--r-- 1 terotil terotil 41 2006-08-08 13:04 testi-redu.bz2

En jatka typeryyksistä inttämistä. Jos TODELLA olet pyyhkinyt "Shannonin kehittämillä laskelmilla" rektaaliasi, kirjoita toki siitä artikkeli. Communications of the ACM tai IEEE Transactions on Information Theory tappelevat saadakseen julkaista sen.

Sanoiko joku Riot-entertainment?

Väärin, täysin randomaalistakin dataa pystytään pakkaamaan. Täysin randomaalisestakin merkki/lukujoukosta löytyy yhtäläisyyksiä, joita voidaan pakata. Esimerkiksi piin arvossakin toistuu samoja pieniä lukusarjoja jotka voidaan merkitä pakkausmetodin alkuun ja korvata yhdellä yhtäläisyydellä.

Ja väärin, pakkauksella ei oo teoreettista minimiä. Aina voidaan tehdä monimutkaisempi ohjelma joka etsii pakattavasta datasta yhtäläisyyksiä matemaattisin kaavoin (sin, cos ym), Esimerkiksi monimutkainen muutaman merkin pitkä sin+cos tms. kaava voi korvata satoja lähes randomaalisia merkkijonoja.

Jos otetaan pala satunnaista dataa, sieltä tietysti _voi_ löytyä redundanssia, joka saadaan puristettua pois tai _voi_ löytyä tapa ilmaista osa datasta analyyttisessä muodossa kaavana. Ei kuitenkaan voi luvata, että sitä redundanssia tai kaavaa löytyy. Siinä on ero.

Yksittäisen tunnetun bittijonon pakkaukselle ei olekaan minimiä. Mutta emme kai me siitä olleet kiinnostuneita, vaan universaalista pakkauksesta?

Todistus: Oletetaan algoritmi joka pakkaa kaikki n bitin jonot k < n bittiin. Nyt jokaista n bitin jonoa vasta (injektiivisesti) vähintään yksi k bitin jono (purkamisen yksikäsitteisyys). n bitin jonoja on 2^n kappaletta ja k bitin jonoja on 2^k kappaletta. Injektiivisyysvaatimuksesta seuraa 2^k >= 2^n. Alun oletuksen (k

Nykyaikana kai JACM on se arvostetuin ACM:n lehti. CACM on lähempänä Mikrobittiä nykyisin.

Totta, kuvitelkaa toiseen kommenttiini s/CACM/JACM.

Tosin ei se CACM nyt ehkä ihan Mikrobitti ole, kun AISin MIS Journal Rankins http://www.isworld.org/csaunders/rankings.htm pistää sen kuitenkin alansa kärkiryhmään. :)

Heh, MeliaVolumen PDF-läyskässä tosiaan väitetään: "[T]äysin arvotussa datassa (satunnaisesti ykkösiä ja nollia) päästiin tasaisesti 70 - 80% alkuperäiskoosta."

Kun pakataan satunnaisia binäärimerkkijonoja, joissa ykkösen todennäköisyys on muista merkeistä riippumattomasti 50 %, niin kuten Shannon mm. osoitti, minkään häviöttömän pakkausalgoritmin keskimääräinen pakkaussuhde ei voi olla alle 100 %.

MeliaVolumen väite ei siis ole "väärä" vain siinä mielessä, että kukaan ei vain ole vielä keksinyt tällaista pakkausalgoritmia, vaan väite voidaan matemaattisesti todistaa vääräksi.

Melkein luulisi kyseessä olevan mainostoimiston julkisuusstuntin, mutta toisaalta - kuten Teron blogiartikkelissa linkkaamasta FAQistakin näkyy - onhan näitä yrittäjiä aikaisemminkin ollut.

FAQin mukaan mm. Byte-tietokonelehti uutisoi 1992 Web Technoligiesin vähän vastaavanlaisesta muka kaikenlaista dataa kompressoivasta keksinnöstä, joka edes "ei ollut informaatioteorian lakien alainen". Ohjelmasta ei kuitenkaan saatu jostain kumman syystä aikaiseksi lopullista versiota ja lopulta Byten kysellessä asian perään firman toimitusjohtajakin katosi julkisuudesta. :I

Eikö tämä jo kerro kaiken tuolla MeliaVolumen sivulla:
"Meidän Teknologia osastomme on kehittämässä parhaillaan mekaniikan keksintöä pitkien tutkimusten tuloksena. Keksintö on niin mullistava, että se tulee vaikuttamaan mekaniikan alaan vähintään yhtä paljon kuin Melia Mini IT-alaa."

Hieman epäilyttää että mekaniikassa enää mitään "alaa mullistavaa" keksittäisiin. Ja tämä kehitetty vähän tuossa it-alan mullistuksen ohella? Ei hullummin...

Kauppalehteen veijarit ehtivät vasta 22.8.2006, sivun 17 ("Digi") oikeaan reunaan kahden palstan leveydelle: "MeliaVolumelta huipputehokas tiedon pakkaustuote". Hälytyskellot alkoivat soida viimeistään kolmannen kappaleen kohdalla: "Pakkaustekniikka on häviötön. Kaikki tiedostot voidaan siis purkaa ilman että dataa häviää." Viides kappale on kuin suoraan comp.compression-keskusteluryhmän FAQ:ista: "Pakkauskierroksia voi tehdä useita." jne.

Ja lisäksi sfnet.atk.ohjelmointi ryhmään ketjun avausviesti kirjoitettiin samasta DNA-Internetin IP-osoitteesta, täysin samanlaisella selaimella kuin millä "Sebastian de Mel":in nimellä kirjoitetut vastineet. Muropaketin avausviestin kirjoittanut tunnus oli rekisteröity samana päivänä ketjun aloituksen kanssa.

9.8.2006 esitetyssä kommentissa on todistus, jossa todetaan, että jos meillä on n:n bitin jono, niin sitä ei voi pakata k < n bittiin.

Tämä todistus ei ole täysin riittävä. Siinä nimittäin oletetaan pakkauksen tapahtuvan aina yhdelle tietyn mittaiselle tiedostolle kun väite on, että n:n bitin jonon voidaan pakata jollekin k:n bitin jonolle k < n.

Todistus pienellä muutoksella on tietysti melkein yhtä yksinkertainen ja sopisi lukiomatikan harjoitukseksi.

Keskustelussa myös on todettu, että satunnaistakin dataa voidaan pakata ja viitattiin mm. piin desimaaleihin. Hieman ehkä yllättäen piin desimaaleissa on erittäin vähän satunnaisuutta! Merkkijonon satunnaisuus määritellään yleensä suhteena lyhimpään ohjelmaan, joka tulostaa merkkijonon. Koska pii voidaan tulostaa hyvin lyhyellä ohjelmanpätkällä ei siinä juuri ole satunnaisuutta. Piihän on pakattu jo siihen lyhyeen ohjelmaan, joka sen desimaaleja luettelee. Jos tulostamiseen tarvitaan vähintään yhtä pitkä ohjelma kuin merkkijono on, niin merkkijono on satunnainen.

Todistuksessa _ei_ todeta "että jos meillä on n:n bitin jono, niin sitä ei voi pakata k < n bittiin", vaan että _kaikkia_ n bitin jonoja ei saa pakattua k bittiin millekään k

"Todistuksessa _ei_ todeta "että jos meillä on n:n bitin jono, niin sitä ei voi pakata k < n bittiin", vaan että _kaikkia_ n bitin jonoja ei saa pakattua k bittiin millekään k

Kas. Hoksasin, mitä tarkoitit. Valitsemani esimerkki oli liian yksinkertainen. 2^(k+1)-2 = 2^k, kun k=1.

Käyttämälläsi määritelmällä piin desimaalikehitelmä ei ole satunnainen. Olen informaatioteoreettisessa kontekstissa tottunut ajattelemaan satunnaisuuden entropian käsitteen kautta. Kutsukaamme näitä näkökulmia vaikka puuroksi ja velliksi. :-)

Jostain syystä mietin juuri äsken, olisikohan yrityksen lupaama mekaniikan alan keksintö (ikiliikkuja?) jo valmistunut. http://www.meliavolume.fi näyttää tyhjältä, ja MeliaVolume Oy on YTJ:n (http://www.ytj.fi) mukaan siirtynyt 14.5.2007 turkulaisen tilitoimiston haltuun. Yrityshän oli alun perin tamperelainen (Vanha-Juvankatu 2 E 41, 33710 TAMPERE). Kumma kyllä, en ole lainkaan yllättynyt tällaisesta vähin äänin katoamisesta.