Olen ohjelmoimassa ihan kokeilumielessä tekstinpakkaus ohjelmaa. Sen pitäisi pakata tavallista suomenkielistä tekstiä. Saan pakattua tekstin kyllä 50% alkuperäisestä, joka ei ole kovin vaikeaa: Yhteen merkkiin 2 kirjainta.
Mutta juurikaan tästä tehokkaampaa pakkausta en, kiusallista kyllä, saa tehtyä.
Olen kokeillut sanan "mutta" korvaamista sanalla "mtt" jne. Niin olen päässyt korkeintaan 45%:iin. Mutta yleiset sanat ovat lyhyitä, eikä niitä esiinny yleensä paljoa.
Onko kenelläkään ideoita?
Mutta juurikaan tästä tehokkaampaa pakkausta en, kiusallista kyllä, saa tehtyä.
Olen kokeillut sanan "mutta" korvaamista sanalla "mtt" jne. Niin olen päässyt korkeintaan 45%:iin. Mutta yleiset sanat ovat lyhyitä, eikä niitä esiinny yleensä paljoa.
Onko kenelläkään ideoita?
Vastaukset 5
Vanhimmat
Mitenkäs sinä pakkaat yhteen merkkiin kaksi kirjainta niin, että saat ne siitä myös palautettua? 31 x 31 vaihtoehtoista kahden kirjaimen yhdistelmää ei pysty yksiselitteisesti 31 merkillä esittämään. Ellet sitten tarkoittanut jonkinlaista Huffman-koodausta, joka taitaa näin äkkiä ajateltuna olla tehokkain yksinkertaisesti toteutettavissa oleva tekstinpakkausmenetelmä.
No oikeastaan tuokin on vähän kesken. Käytän välilyöntiä ja 14 kirjainta. Muut kirjaimet, kuten vierasperäiset ja isot, esiintyvät paljon harvemmin. Niitä varten jätin \-merkin, tyyliin ö="\o". Pisteen koodasin kahdella välillä ja kolme väliä on piste kappalevaihto. Pilkku tulee jos sana loppuu j:hin. "jj" voisi tarkoittaa vaikka numeroa 8. Eli vähän kökösti...
Niin, tuohan on siis eräänlainen Huffmann-koodaus. Sen periaatteena on tallentaa useiten esiintyvät merkit hyvin pieneen tilaan (esim yksi bitti) ja harvinaisemmat merkit sitten useammalla bitillä. Tämä tapa sopii hyvin kaikenlaisen ei-satunnaisen datan häviättömään pakkaukseen, mutta jos lähdemateriaalista ei pystytä eroittelemaan tiettyjä merkkejä selvästi yleisemmiksi kuin muut, ei tämä tapa oikein toimi. Tähän perustuu myös se, että kertaalleen pakattua dataa ei yleensä uudelleen pakkaamisella pienemmäksi saada.
Kokeilin alkuperäistä huffmania ja se pakkasi 50-54 prosenttiin alkuperäisestä, joten ei varmaan kannata alkaa huffman-puita kokoamaan, kun omalla tekniikallani pääsin samaan yksinkertaisemmin.
Tavallinen huffman ei ota kantaa, missä järjestyksessä nuo kirjaimet ovat. Kokeilin myös niin, että tehdään monta huffman-puuta pakattavaa kirjainta edeltävän kirjaimen mukaan. Esim "j":tä ei todennäköisesti seuraa ainakaan "p" vaan yleensä "a" tai "i". Mutta näinkään ei varmaan pääse kun johonkin 40% kieppeille. Jos lasketaan todennäköisyys kahden edeltävän kirjaimen mukaan, voitaisiin päästä johonkin 35% ehkä. Mutta puut pitäisi säilyttää silloin pakkausohjelmassa, jo jos tuo ohjelma vahingossa katoaisi, olisi tiedot aika hyvin kryptattuja itseltäkin.
Näyttää olevan matemaattinen tosiasia, ettei suomen kieli pakkaudu kun johonkin 35-40 prosenttiin...
No, tasan 50% on kai ihan hyvä minun projektilleni...