Java: Korta ner sträng med hjälp av omkodning kodning

2011-09-12 13:30

Permalänk

MrMadMan

Medlem

Plats: Umeå
Registrerad: Maj 2003

●

Java: Korta ner sträng med hjälp av omkodning kodning

Jag håller på med en applikation där jag behöver lagra en given textsträng i en kortare textsträng.

ASCII använder ju som bekant 1 byte per tecken (UTF-8 ibland 2) där varje byte kan vara en av 256 möjliga tecken.
I mitt fall är alfabetet begränsat till 39 olika tecken: ([a-z][0-9]-:.) och jag behöver därför bara 6 bits för varje tecken. Det innebär att jag skulle kunna rymma 4 tecken i 3 bytes och därför representera en 16 tecken lång sträng med bara 12 tecken!

Jag är ute efter något i stil med följande:

public static String shortenString(String longString) {
    byte[] encodedBytes = magic(longString); //Kodar om strängen till en förkortad byte-array
    String shorterString = new String(encodedBytes, "UTF-8") //Kodar om byte-arrayen till en UTF-8 sträng som bör vara kortare än ursprungssträngen.
    return shorterString;
}

Och sedan förstås en metod för att göra det hela baklänges, vilket bör vara trivialt.

Men hur bär jag mig åt?

Rapportera Redigera

Citera flera Citera

2011-09-12 16:49

Permalänk

Gnejs

Medlem

Plats: Stockholm
Registrerad: Apr 2006

●

Du får nog ta och använda dig av bitvisa operationer. t.ex.
http://www.janeg.ca/scjp/oper/bitwise.html
Så att du bestämmer att t.ex. de 6 första bitarna är ett tecken, så får du översätta dessa bitar till det tecken du nu är ute efter.
Du kan ju använda AND operatorn för att maska bort alla ointressanta bitar, så du maskar fram 6 bitar i taget från t.ex. en 32 bitars int lr liknande. Översätter bitarna var för sig till det tecken osv. Hoppas du förstod ^^

Visa signatur

Rapportera Redigera

Citera flera Citera

2011-09-12 18:28

Permalänk

mounte

Medlem

Plats: Sandviken
Registrerad: Mar 2005

●

Hej,
vill bara belysa frågan från en annan vinkel:
vad är det som gör att du vill spara dessa 2bitar per symbol? Kommer det vara många/långa strängar?
Jag skulle tipsa dig att undersöka först vad snittstorleken på en av dina strängar kommer vara(n symboler) samt profilera och ta reda på hur många strängar som kommer lagras (k st).
Först då kan du skatta de faktiska vinsterna med din kodning som 2*n*k bitar eller n*k/4 bytes. Det är först med ca 1000000 strängar med snittstorlek på 1000symboler som du når vinster över 100MB.
I gengäld så måste du räkna på den cputid du lägger på varje kodning och avkodning samt ev. framtidssäkring om ditt teckensätt utökas.

Så till ytterligare ett lösningsförslag, skapa en ordlista med 4tecken --> 1tal, 4 tecken ==> 39^4 = 2 313 441 ~ 2.3 milj element. Du kan nu ta din sträng, skanna fyra tecken åt gången och välja det tal som du ska koda med direkt. En par MB kommer krävas på disken, men det är inte så mycket i sammanhanget. En optimering kan vara att dela upp ordlistan i 39 delar på första bokstaven, så att du bygger ett enkelt träd över dina ord.

Annars kan du alltid koda med Ziv Lempel eller valfri teckenkodare Huffman kanske kan bli din vän
Lycka till

Senast redigerat 2011-09-12 18:56

Visa signatur

weeeee

Rapportera Redigera

Citera flera Citera

2011-09-12 21:21

Permalänk

MrMadMan

Medlem

Plats: Umeå
Registrerad: Maj 2003

●

Anledningen till att jag vill spara så mkt som möjligt är att strängarna eventuellt ska skickas som sms, eller genom tal (IRL ^^).

Det är alltså inte lagringsutrymmet som jag vill spara på.
Att lagra i den där tabellen är lite olämplig eftersom jag vill hålla ner storleken på programmet.

Jag håller på att lösat det genom att koda strängen med bas 40. Finns att läsa här: http://stackoverflow.com/questions/7389252/shorten-an-already...

Rapportera Redigera

Citera flera Citera

2011-09-13 00:40

Permalänk

mounte

Medlem

Plats: Sandviken
Registrerad: Mar 2005

●

Om du ska skicka datat på det sätt du beskriver så skulle jag tipsa att du kikar på antingen huffmankodning eller Lempel–Ziv–Welch algoritmen. Enkla att implementera och bör ge bättre resultat.

Visa signatur

weeeee

Rapportera Redigera

Citera flera Citera

2011-09-13 00:45

Permalänk

MrMadMan

Medlem

Plats: Umeå
Registrerad: Maj 2003

●

Skrivet av mounte:

Om du ska skicka datat på det sätt du beskriver så skulle jag tipsa att du kikar på antingen huffmankodning eller Lempel–Ziv–Welch algoritmen. Enkla att implementera och bör ge bättre resultat.

Gå till inlägget

Nu vet jag inte riktigt hur dessa fungerar. Men de flesta komprimeringsalgoritmer fungerar bara bra när man har större mängder data. Här rör det sig om ett 20-tal tecken. Hur mycket kan man tänkas tjäna?

Rapportera Redigera

Citera flera Citera

2011-09-13 01:01

Permalänk

Oggelito

Medlem ★

Plats: Stockholm
Registrerad: Nov 2005

●

Skrivet av MrMadMan:

Nu vet jag inte riktigt hur dessa fungerar. Men de flesta komprimeringsalgoritmer fungerar bara bra när man har större mängder data. Här rör det sig om ett 20-tal tecken. Hur mycket kan man tänkas tjäna?

Gå till inlägget

Han bad dig kika först, du kan nog bäst räkna ut vilken metod du tjänar mest på. Allt är inte ZIP/dictionary-kompression..

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

http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

Visa signatur

Rapportera Redigera

Citera flera Citera

2011-09-13 01:38

Permalänk

MrMadMan

Medlem

Plats: Umeå
Registrerad: Maj 2003

●

Skrivet av Oggelito:

Han bad dig kika först, du kan nog bäst räkna ut vilken metod du tjänar mest på. Allt är inte ZIP/dictionary-kompression..

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

http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

Gå till inlägget

Jag körde ett snabbt test med LZW och det gav negativ kompression (pga den korta inputsträngen).
Huffmankodning kräver att man även skickar med tabellen/trädet vilket ger enorm overhead.

Den lösning jag hittade och har valt att köra på har gett mycket goda resultat så jag kommer fortsätta köra med den.

Rapportera Redigera

Citera flera Citera

2011-09-13 09:22

Permalänk

Gi][Gurra

Hedersmedlem

Plats: East side
Registrerad: Maj 2002

●

Kanske en idé att ta en titt på nio-buffers. Ett kul projekt vore att implementera en bit-buffert :). Tex som en wrapper av bytebuffer

Visa signatur

Every time you create an iterator: God kills a kitten.

Rapportera Redigera

Citera flera Citera

2011-09-13 10:02

Permalänk

mounte

Medlem

Plats: Sandviken
Registrerad: Mar 2005

●

Skrivet av MrMadMan:

Jag körde ett snabbt test med LZW och det gav negativ kompression (pga den korta inputsträngen).
Huffmankodning kräver att man även skickar med tabellen/trädet vilket ger enorm overhead.

Den lösning jag hittade och har valt att köra på har gett mycket goda resultat så jag kommer fortsätta köra med den.

Gå till inlägget

Om du tänker ett steg till så kan du med enkla medel ta reda på statistik över de meddelanden som ska skickas, utifrån dessa kan du generera ett statiskt träd för huffmankodning som är optimalt med avseende på den kontext det ska användas inom, därmed så behöver du inte skicka tabellen någon gång alls.

Men det kan vara så att denna metod hamnar nära den kodning du redan fått tips om på SO.

Visa signatur

weeeee

Rapportera Redigera

Citera flera Citera

Java: Korta ner sträng med hjälp av omkodning kodning

Java: Korta ner sträng med hjälp av omkodning kodning

Externa nyheter

Spelnyheter från FZ