Komprimere tekst matematisk?

[Newklear]

Hei! : )

 

Først: Hadde egentlig ikke peil på hvor jeg skulle poste denne tråden og tenkte at det er god kunnskap om dette blandt de som driver med programmering, så da ble det her. Men om noen moderator føler at den passer bedre inn et annet sted så flytt i vei! : )

 

Så til problemet;

Lurer på hvordan man mest mulig effektivt kan komprimere en string med tall + bokstaver. Da tenker jeg ikke på sånt som fjerne mellomrom\vokaler og andre enkle tiltak, men mer matematisk.

 

Lengden på det som skal komprimeres kan variere fra 30-100+ tegn og består utelukkende av tall\bokstaver.

 

Er også visse krav som må innfris: (Men bare å poste forslag selv om de faller litt utenfor)

- Dekomprimeringen må kunne utføres på noen få minutter manuelt. (om nødvendig med kalkulator) Til komprimeringen er det greit å bruke PC.

- Dekomprimeringen kan ikke være avhengig av databaser eller tabeller som ikke kan læres utenatt.

- Komprimeringsteknikken må forkorte teksten i sin helhet og ikke hvert tegn (som er vanlig med datamaskiner der ett tegn blir representert v/8-tegns binærstring)

 

- jeg kan konvertere mellom tall\bokstaver, så aritmetikk er fullt mulig : ) Men dette øker lengden på teksten med 18,8%. (det betyr at teksten igjen må reduseres med 15,25% for at d skal være vits å gjøre den om til tall)

 

Til nå har jeg kommet frem til primtallsfaktorisering, men det er ikke spesielt effektivt og i enkelte tilfeller (ganske så ofte faktisk) ender jeg opp med at den "komprimerte" teksten er lengre enn råteksten.

 

Edit: Lagd en kopi av tråden på matematikk.net:

http://www.matematikk.net/ressurser/mattep...pic.php?p=94905

Endret 5. januar 2009 av Newklear

[NevroMance]

Ville nok sett på huffmankoding for dette. Hvertfall hvis det er 100++ tegn, ikke like effektivt hvis det er 20. Kan hvertfall dekomprimere koden din veldig raskt etterpå, og om det ikke er sinnssykt mange forskjellige tegn kan du enkelt memorisere tabellen din. Hvis du derimot skal skrive en fil med huffmannkoding vil selve koden bli lenger, men hvis du får lagret det ved at hvert tegn tar 1 byte (siden du bare bruker 0 og 1) vil selve størelsen bli mye mindre. Blir vel fort ASCII hvis du lager den manuelt, og da tar den plutselig mye større plass.

 

Hadde det vært en enda større fil ville jeg anbefallt differensekoding. Der lar du første sifferet være det samme, og resten er differansen mellom sifferet du er på og det forrige, f. eks. vil

 

7 4 5 8 9 5 4 7 bli

7 -3 1 3 1 -4 -1 3

 

http://en.wikipedia.org/wiki/Huffman_coding

http://www.uio.no/studier/emner/matnat/ifi...ompresjon-I.pdf

http://www.uio.no/studier/emner/matnat/ifi...mpresjon-II.pdf

 

Første er om huffmankoding. De to andre er litt generelle komprimeringsteknikker.

[Newklear]

Takk for godt svar! Var litt komplisert lesning, men kommer meg vel gjennom det! Men vil jeg ikke få problemer med å huske frekvenser om jeg f. eks. kommer opp i så mye som f. eks. 20 forskjellige tegn? (Er vel lite sannsynelig på 100 tegn med mindre det er en den tall inne i bildet, men likevel!)

 

Okei, skjønte endelig hvordan huffmankodingen fungerte : D Problemet blir at jeg skal gjøre dette med penn og papir, og da vil huffmankodingen ha motsatt effekt siden jeg ikke er ute etter å komprimere selve tegnet, men teksten i sin helhet.

 

Og de andre metodene gikk visst rundt samme prinsippet : ( (Satte meg ikke inn i hver eneste, men så da sånn un i hvertfall :[ )

 

EDIT; Har fått en ide nå! Skal se om jeg får til noe ved hjelp av regresjon på kalkulatoren! Tviler vel egentlig på om det kommer til å funke, men prøver for det! : D (*HINT* Post flere lure tips!! : D)

Endret 4. januar 2009 av Newklear

[NevroMance]

Ok. Skal du gjøre det manuelt blir det litt vanskeligere ja. Helt uten videre kommer jeg ikke på noe, hvis det ikke er sekvenser som går igjen og tegn som ikke brukes som disse sekvensene kan erstattes med. Men dette blir ikke veldig matematisk slik sett da. Skal poste nye ideer hvis de dukker opp.

[Newklear]

Det du sier med sekvenser der er jo lurt da : p Spesielt om det er lange ord som går igjen!

 

Edit: Men hvordan går det fort(les:få tegn) å definere en variabel?

Endret 4. januar 2009 av Newklear

[teflonpanne]

For veldig enkel dekomprimering kan du bruke RLE (run length encoding). Altså hvis du har strengen AAABBBBCCDDDDD så blir det A3B5C2D5 f.eks, men det egner seg kanskje ikke så bra for vanlig tekst så huffman er nok det beste alternativet.

Endret 4. januar 2009 av teflonpanne

[Newklear]

For veldig enkel dekomprimering kan du bruke RLE (run length encoding). Altså hvis du har strengen AAABBBBCCDDDDD så blir det A3B5C2D5 f.eks, men det egner seg kanskje ikke så bra for vanlig tekst så huffman er nok det beste alternativet.

Huffman egner seg overhodet ikke for vanlig tekst på papir! (Det går ut på å minske antall bits for mye brukte bokstaver på bekostning av de mindre brukte)

 

Som du selv påpeket så er problemet med RLE at det ikke finnes trippeltkonsonanter på norsk ;\ er jo greit å bruke det når jeg får dobbeltkonsonant i slutten av et ord og neste ord starter på samme bokstav da. Men d er nokså sjeldent ;\ Men takk for forslaget! : D

Endret 4. januar 2009 av Newklear

[GeirGrusom]

LZH/LZW komprimering er vel veldig egnet til å komprimere tekst. Den vil psee bedre fordi den tar hensyn til at mange ord og setinger går igjen i teksten, og ideelt kan en komprimere tekst opp til 90%

 

edit: Ikke så lete å dekomprimere manuelt dog... så da er vel huffman beste metoden

Endret 5. januar 2009 av GeirGrusom

[Newklear]

LZH/LZW komprimering er vel veldig egnet til å komprimere tekst. Den vil psee bedre fordi den tar hensyn til at mange ord og setinger går igjen i teksten, og ideelt kan en komprimere tekst opp til 90%

 

edit: Ikke så lete å dekomprimere manuelt dog... så da er vel huffman beste metoden

Hvordan blir det i forhold til faste variabler jeg legger til i tegnsettet mitt som jeg kan definere og bruke kun v/ett tegn?

 

Edit: Leste litt om det da : ) Er beste til nå, men spesielt effektivt blir det vel ikke når jeg har en metode for å fjerne alt som kalles sekvenser i utgangspunktet?

Endret 5. januar 2009 av Newklear

[NoPain74]

Hei,

 

jeg programmerer cobol til vanlig, og der kan man "pakke" de numeriske feltene.

 

Det vil si at hvis du skal lagre f.eks tallet 1234, så vil dette ta 4 tegn hvis det ikke er pakket og vil ha hex verdien x'F1' for 1-tallet og x'F2' for 2-tallet osv...

1234
----
FFFF
1234

 

i ascii så er det vel

1234
----
4555
9012

 

Hvis du "pakker" feltet, lagrer du kun x'1234'.

13
24

 

Vet ikke om dette var forståelig eller om du kan bruke det, men da bruker du ihvertfall bare halve plassen og du kan lese det i klartekst hvis du kan skrive det ut i hex.

 

Marvin

[Newklear]

Det der virket utrolig lovende! Det var noe sånt jeg hadde håpet på! : ) Skal prøve å se om jeg greire å sette meg inn i hex nå : ) Eneste jeg vet er at det betyr 16 : p

 

Edit: Vet ikke hvor vanskelig det blir å dekomprimere jeg? Det og konvertere til en større base er jo en genial ide, problemet er jo bare at skal dette fungere effektivt må jeg lære meg til å bruke det aktuelle tallsystemet ;\ Men som sagt beste ide hittil! : )

 

Fortsett og kom med forslag! : )

Endret 5. januar 2009 av Newklear

[GeirGrusom]

LZH/LZW komprimering er vel veldig egnet til å komprimere tekst. Den vil psee bedre fordi den tar hensyn til at mange ord og setinger går igjen i teksten, og ideelt kan en komprimere tekst opp til 90%

 

edit: Ikke så lete å dekomprimere manuelt dog... så da er vel huffman beste metoden

Hvordan blir det i forhold til faste variabler jeg legger til i tegnsettet mitt som jeg kan definere og bruke kun v/ett tegn?

 

Edit: Leste litt om det da : ) Er beste til nå, men spesielt effektivt blir det vel ikke når jeg har en metode for å fjerne alt som kalles sekvenser i utgangspunktet?

 

Tja, hvis det ikke er noen sekvenser forsvinner også fordelen med denne metoden.

Det er dog verdt å merke seg at dette er metoden som blir brukt av programmer som winrar og winzip.

deflate er også en metode som er en blanding av lzw og huffman.

[Newklear]

Men det betyr vel at da er vi tilbake på bit-sekvenser igjen? : (

[GeirGrusom]

Men det betyr vel at da er vi tilbake på bit-sekvenser igjen? : (

Ja, for det kan løses enkelt med penn og papir.

[Newklear]

Men det betyr vel at da er vi tilbake på bit-sekvenser igjen? : (

Ja, for det kan løses enkelt med penn og papir.

Men.. Da blir teksten 8 ganger så lang? : p (5 hvis du driter i de 3 første bitsene som er like for alfabetet uansett) Eller er det noe jeg overser her? ; o

Endret 6. januar 2009 av Newklear

[Dj_Offset]

Siden du skal gjøre dette for hånd (og siden ingen har nevnt dette før):

Er teksten lang, så går det kanskje an å indeksere hele ord i stedet for bokstaver, og følgelig bruke ordlisten samt en sekvens av indekser som komprimert tekst. Dette forutsetter at en har en viss lengde på teksten, samt at mange ord i teksten er like, ellers oppnår man ingenting. Har man lyst kan man også se på gramatikk og hvordan man dele opp ord i sekvenser.

 

Hvis en forenkler vekk huffman, kan en se på:

* LZW - fungerer omtrendt som beskrevet over, men "ordlisten" bygges opp dynamisk på kompresjon og dekompresjonssiden ettersom man prosesserer.

* LZ77 - opererer ved å lage oppslagsreferanser av kjente sekvenser i de til en hver tid siste 32 kilobytes.

 

Ellers hadde teflonpanne et godt poeng med RLE. En kan omdefinere problemstillingen til å sortere alle bokstaver i teksten, deretter gjøre f.eks. RLE. Da blir problemstillingen å finne en måte å revertere sorteringen på.

En variant av dette blir utnyttet i BZip2 algoritmen hvor en setter opp teksten i en matrise og bruker Burrows-Wheeler transformasjon på matrisen (denne er revertibel), før man sorterer radene i matrisen og deretter bruker klassiske komprimeringsteknikker til slutt.

[Newklear]

Dette virket bra! : D Skal se på det med Burrows-Wheeler transformasjon nå : D

 

Har nå brukt ganske lang tid på wiki for å forstå Bruuows-wheeler (greide d ikke før jeg tok meg tid til å se på pseudokoden, og det tok en stund x] ) Men så ut som dekomprimeringen var noe sinnsykt stress å få til der? ; o

Endret 9. januar 2009 av Newklear