moze to pomoze http://atariarea.krap.pl/artykuly.php?a … &id=38

To zalezy mocno od danych, jezeli masz powtarzajace sie mocno znaki (pisales o 70% dla najczesciej wystepujacego), to skompresowane RLE (bo to wlasciwie robisz) bedzie niezle. Ale chyba jednak mozna duzo lepiej. Zalozmy, ze masz 4 znaki: A-70%, B-15%, C-10%, D-6%. Popatrz, ze statystycznie szanse, ze sekwencja 2 znakow to jest BB 0.15 jest 0.025, dla pozostalych jeszcze nizej. A i tak kompresujesz ten znak dodajac 6 bitow licznika. Tracisz. Jezeli masz naprawde 1 znak dominujacy tak mocno jak A, sproboj zrobic RLE tylko dla takiego znaku, i moze nawet z licznikiem nie 6-bitowym a 2- lub 4- bitowym. Na oko 2 moze byc dobre - szanse, ze sekwencja 5 znakow jest AAAAA to ca. 0.17 a ze 16 to juz 0.003. Innymi slowy, sekwencje AABAACAAADBA spakowalbys tak (kazdy znak to 2 bity): A2BA2CA3DBA1. Ofkorz zamiast cyferek 1-2-3 uzywasz 0-1-2 w prawdziwych danych.
W ta strone bym radzil kombinowac.
Oczywiscie, pojawia sie pytanie, czy kompresujesz na tyle duzo danych, zeby komplikowac depacker :D
Aha, no i ofkorz Huffman tez moze tu byc ciekawy...

Ostatnio edytowany przez eru (2006-02-12 13:25:16)

przyklad1:
111111111111111112222222222222211222222222222221122222222222222112222322223222211222222222222221
122224444442222112222222222222211222222222222221122222222222222112222222222222211111111111111111

przyklad2:
212222222222221221222222222222122122222222222212212223222232221221222221122222122122222442222212
212222222222221221222322223222122122222222222212212222222222221221222222222222122122222222222212

@Magnus - to moze byc dobre, prosta i szybka metoda dekompresji (krotki program depakera).

niema co szalec danych wyjsciowych bedzie w sumie ok 3 kb glownie zalezalo mi na krotkiej procedurze dekompresji.

jesli chodzi o kompresje tylko jednego obrazka - rle (w twoim wykonaniu) powinno byc wystarczajace
jesli bedziesz kombinowal z tego animacje - huffmana raczej nic nie zastapi
polecam poczytac o lz77 lub o jego nieco efektywniejszej wersji - lzss (np. przykladowy kod w zalaczniku do arta wspomnianego przez tebe), albo o ponoc szybszy przy dekompresji - lzo

btw. skad mozna pobrac ten zalacznik?

Ostatnio edytowany przez jellonek (2006-02-12 15:44:07)

hej!

nie wiem jak bardzo krytyczna jest prędkość dekompresji... jednak możnaby się pokusić o kompresję bitową... jeżeli to jest dla twojego zastosowania odpowiednie można podejsc do problemu nieco inaczej... w przypadku takiego rozkladu danych wejściowych, należałoby zastosować jakiś kod, w którym długość słowa okreslajacego dany znak, nie jest stała. Najbardziej logicznym wydaje się zastosowanie bardzo prostego kodowania bitowego, np. możemy zastosować taki algorytm...

potrzebujeby procedury get_bit, która umożliwia pobranie jednego bitu danych ze wejścia.

1. zerujemy "index"
2. pobieramy jeden bit
3. zwiekszamy index o 1
4. sprawdzamy czy pobrany bit=1, jeżeli nie wracamy do kroku #2
5. wartość index określa jednoznacznie daną ktory pobralismy, mozemy go wykorzystac do pobrania odpowiedniej wartosci z tablicy konwersji.

reasumujac, kodowanie bedzie wygladalo mniej wiecej tak:

1: kod oznaczajacy dana #1
01: kod oznaczajacy dana #2
001: kod oznaczajacy dana #3
0001: kod oznaczajacy dana #4
itd.

jak widac ilosc bitów przeznaczonych na zakodowania kolejnego symbolu rośnie dość szybko... jednak w przypadku twojego rozkładu danych (70% będzie reprezentowane przez pojedynczy bit). Ma to szanse sporej kompresji. Musisz sprobowac w praktyce. Zreszta istnieje bardzo duzko koów o zmiennej dlugosci slowa... mozesz sprobowac poczytac troche tu:

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

i tu:

http://en.wikipedia.org/wiki/Universal_ … ression%29

procka dekompresji moze byc dosc krotka i przy dobrej implementacji get_bit, powinna byc szybka:

get_one_byte:

 ldx #$00
loop:
 jsr get_bit ; get bit w znaczniku "C" zwraca wartosc pobranego bitu
 inx
 bcc lopp
 lda tab_cnv,x
 rts

; tutaj tablica konwersj, najczesciej wystepujace elementy powinny byc kodowane najmniejsza iloscia bitów :)
; czyli będą się znajdowały na początk u tablicy... im dalej w tablicy tym wiecej bitów potrzeba :)

tab_cnv:
 dta b($04),b($03),b($02),b($01)

get_bit:

 ; tutaj w/g twojego uznania... jest sporo sposobów :) 
 ; a implementacja zalzey od tego czy uzyjesz rejestrow, lokacji na stronie zerowej... itd.

jest to jedno z prymitywniejszych kodowań o zmiennej długości słowa... i nie wiem czy to bedzie przydatne ze wzgledu na szybkosc, jednak kompresja powinna byc efektywna dla twoich danych :)

pozdrawiam
Seban/SLIGHT

Ostatnio edytowany przez seban (2006-02-12 20:51:31)

Pare rzeczy mi sie tu nasuwa:

1. Jak danych wejsciowych jest 3k to z samego Huffmana nawet jakbys wszystko zakodowal
1 bitem to wyjdzie ci 50% ;) czyli 1,5k a nie 200 bajtów ;)

2. Wedlug mnie takie normalne RLE jest tu bez sensu jezeli dlugości powtarzania sie
nie sa wieksze niz 4-5 bajtow, a srednie powtarzanie masz w tych granicach. Czemu ?
Bo jak dodasz 3 bity na licznik chocby to juz masz  1 bit symbolu + 3 bity licznika
co daje 4 bity tyle samo by wyszlo gdybys po prostu zakodowal 4 x 1 bit danych
czyli skrocenie wystepuje dopiero przy 5 powtorzeniach o 1 bit, oczywiscie jeżeli
stosujemy RLE tylko do tego 70% znaku a reszte normalnie. Natomiast przy
powtorzeniach krotszych (2-3) bedzie to wydluzac zamiast skracac.

3. Można by to poprawic stosując też huffmana do licznika czyli biorąc pod uwage
czestość okreslonych powtorzen, ale tez bym nie liczyl ze osiagniesz 200 bajtow ;),
no chyba że miales na mysli 3k danych wejsciowych w bajtach, a nie juz w symbolach
2bitowych, wtedy faktycznie wejsciowych bedzie 3k/4 czyli  jakies 768 bajtow czego
i tak samym huffmanem do 200 nie zmniejszysz. Z RLE jakas tam szansa jest, ale
trzeba by chyba przeanalizowac dane i zastosowac wbudowane w procedurke
dekompresji na stale dlugosci. Np. jezeli najczestsze powtorzenia beda x5 x4 i x6
(przykladowo) i ich kody beda np. 00 01 10  no to masz tam jakis skrot typu 1-3 bitow
(np. 010 oznacza 0 - kod znaku 70%ego +10 x6 czyli zastepuje 000000 itd.).
Czyli cuś jak w deflate tylko w wersji uproszczonej i zastosowane tylko do tego 70%.
Oczywiscie nadal np. wystapienia pojedyncze czy x2 , x3 nawet jeżeli beda rzadziej
wystepowac beda wydluzac zamiast skracac, wiec to zalezy jak duzo ktorych powtorzen
bedzie, ale wlasnie dlatego huffman do licznika tez. Jeszcze analiza czy np. nie oplaci
sie np. powtorzen x8 przerabiac na x4 + x4 czy x9 na x4 + x5 itp. Tak czy siak
te < 256 bajtow to dosc mizernie widze chyba ze masz tak fantastyczne dane ;).
W każdym razie bym je przeanalizowal (te wszystkie dane) i od tego bym uzależnil
jaka metode sobie wybrac.

Jutro wkleje tu kilka zagwózdek z mojego 3d z falcona. A co tam, niech ktoś za mnie zrobi ;)

LZSS - ofset i długość na 5 bitach:
przykład 1 -> 14 bajtów,
przykład 2 -> 23 bajty.

...o ile się nie walnąłem w liczeniu :)

Ostatnio edytowany przez Magnus (2006-02-13 22:29:21)

zielony: piszesz o tym co ja napisalem? ;)
btw. jak napisalem - to sie da jeszcze o pare bajtow skrocic
ale przy obecnym zapisie - jest holernie proste do dekompresji...

Ostatnio edytowany przez jellonek (2006-02-13 21:56:17)

Właśnie, jellonek, co to dla Was :P

dziekuje wszystkim za pomoc, otworzyly mi sie oczy :-)

zrobilem odrobine zmodyfikowany rle (jako ze dane sa bardzo specyficzne) i tak:
przyklad1: 27 bajtów
przyklad2: 25 bajtów

---

poprawka:

przyklad1: 29 bajtow
przyklad2: 21 bajtow

Ostatnio edytowany przez xxl (2006-02-14 09:18:24)