Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

Proste algorytmy kompresji tekstu. Program w języku C lub sam algorytm.

02 Dec 2004 12:30 14852 30
  • Level 22  
    Czy zan ktos jakies proste algorytmy do kompresji plikow tekstowych, a moze ktos robil cos takiego i moglby podzielic sie doswiadczeniami.
    Chodzi mi o jakis program w jezyku C++ lub sam algorytm.
    Jak nie na forum to podaje mail krzysiek400(malpa)op.pl
    [30.03.2021, webinar elektroda] Nowoczesna diagnostyka maszyn, monitorowanie i przewidywanie awarii. Zarejestruj się
  • Level 23  
    Oj dużo możliwości mamy, można np.
    1. wyszukiwać powtarzające się frazy i wstawiać jakiś znacznik (zmienna) np. podczas podarunku pod podwalem podawane były... ;) == $Pczas $Parunku $P $Pwalem... itd.
    2. wielokrotne spacje np. " " == 6xS itd.
    itd.

    oczywiście to najprostsze przekształcenie.
  • Admin of Design group
    Mysle ze tutaj moze sie sprawdzic np. kompresja Hufmana.
    Prosta a dostosuje sie do ilosci powtorzen liter aby zoptymalizowac ich zakodowanie.
  • Level 22  
    wielkie dzieki to juz cos!!! a moze cos po polsku by sie znalazlo??
  • Level 29  
    Podałem wcześniej link, polecam, sprawdziłem, jeszcze nie widziałem lepszego wytłumaczenia LZW, można go zrobić dokładnie tak jak było w książce. Jedyna operacja wymagająca szczyptę pracy to w czasie kompresji - „znajdź (napis)” w słowniku, tu warto dla kodów > 255 zrobić binarne drzewo- dramatycznie przyśpiesza w porównaniu z prostym liniowym przeszukiwaniem.
  • Level 29  
    Zaimplementowałem dwa algorytmy, LZW i kodowanie Huffmana. Pobawiłem się 195.186 bajtowym polskim tekstem (PKZIP zamienił go na 69.652 bajty).
    Kompresja LZW przy 16 bitach na kod, zmniejszyła tekst do 94.806 bajtów (słownik urósł do 47.657 pozycji), przy krótszych tekstach (mniej więcej do 20kB) kody mogą być 12 bitowe (mniejsze o 25%, z dwu kodów łatwo złożyć 3 bajty i odwrotnie). Trzeba by jeszcze sprawdzić zachowanie LZW przy kodowaniu 12 bitowym kiedy przy przepełnieniu słownika przekazujemy maksymalny kod jako sygnał o budowaniu słownika od nowa, proste a może być dobre! ;-( sprawdziłem, słabo wychodzi, 77.530 kodów, czyli 116.295 bajtów, myślałem że będzie lepiej ale i tak nie jest źle bo....
    Huffman dla tego samego tekstu dał 122.362 bajty, w tekście było 25.295 spacji, spacja kodowana 3 bitami, „e” „a” „i” „o” „n” 4 bity, ........, „ś” „ć” 8 bitów, ... aż do 17 bitów dla pojedynczo występujących „Ą” „Ś” „Ź”. Do tego jakoś trzeba dodać jeszcze „drzewo” kodów (prosty sposób to sam histogram 256*2 bajty)
    To co powstało z LZW ściśnięte Huffmanem dało 91.234 bajty (kody od 5 do 10 bitów) czyli raczej skromny wynik, co dobrze świadczy o LZW.
    LZW dla krótkich tekstów zachowuje się źle (może dodać nawet 50% przy 12 bitach na kod). Przy wielu tekstach, wspólnym drzewie kodów, myślę że Huffman daje raczej gwarancję na zysk (a przynajmniej brak strat), trudniejszy w zaprogramowaniu (kody zmiennej długości, „zyglowanie” bitami, łażenie po drzewach, dwuprzebiegowa kompresja), i wolniejszy - dekompresja LZW to błysk.
    Mnie jakoś bardziej „leży” LZW.
  • VIP Meritorious for electroda.pl
    Kompresja dyfuzyjna:

    Pewna narwana Natasza szastała łagodnie nieswoimi milionami.

    Pewnarwanataszastałagodnieswoimilionami.

    Objętość końcowa:

    (39/60)*100%=65%


    PS Jak na razie opracowano tylko metodę kompresji niektórych zdań. Prace nad innymi i dekompresorem trwają.

    Inne opracowania:

    Kompresja skracania ułamków

    $$\frac{16}{64}$$ skracamy skreślając 6 w liczniku i mianowniku

    Kompresja stłuczeń przy pomocy gazy nasączonej środkiem z apteki.

    Kompresja głowy w za małym cylindrze.
    i inne. :wink:
  • Level 29  
    Kompresja palindomiczna
    Kobyłama
    8/18=44%
  • Level 22  
    a czy mozna cos blizej o tych ostatnich rodzajach kompresji. LZW, palindoniczna i ta z ulamkami bo narazie to za bardzo nie wiem o co chodzi
    tak naprawde to chodzi mi o cos prostego
    musze zaliczyc przedmiot i tyle
    jakis przykladzik tez by byl mile widziany
    wielkie dzieki z gory i pozdrawiam!!!
  • VIP Meritorious for electroda.pl
    Na poważnie, to te ostanie to sobie odpuść, bo to żarty słowne w temacie.
    (to skracanie ułamków i kompresja dyfuzyjna nie istnieje poza rozrywką).
  • Level 27  
    polecam książkę "Metody kompresji danych", autor: Krzysztof Heim, wydawnictwo Mikom.
  • Level 22  
    A moze lepiej i wydajniej kompresowac obraz np jakies zdjecie??? Jak to sie robi???
  • Level 27  
    Najczęściej stosuje się transformację dct, są też algorytmy oparte na transformacji falkowej. Potem tylko kwantyzacja i gotowe. A na przykład taki GIF to korzysta z LZW.
  • Level 22  
    no a na czym polega to LZW
  • Level 22  
    Naprwade nikt nie ma programiku do kompresji tekstu napisanego w c++. Jesli juz to prosze na meila krzysiek400(malpa)op.pl
  • Level 22  
    Aczy ktos wie moze jak w c++ odczytywac i zapisywac plik bit opo bicie a nie bajt po bajcie???
  • Level 35  
    No po bicie to się nie da :D

    Najprościej jest stworzyć sobie bufor bitów do zapisu i zapisywać cały bajt np. tak:

    Code:

       static unsigned char bpoz=0x80;  /*zmienna inicjalizowana tylko raz, przy starcie programu!*/
       unsigned char bajt;   /* te zmienne są globalne ze względu na drugą procedurę, ale w C++ można je wrzucić do jakiejś klasy i będzie ładnie i elegancko */


    /* jeżeli chcemy zapisać bit o wartości 1 to parametr bit podajemy różny od zera, jak chcemy zero - to 0 */
    void zapisz_bit(char bit)
    {
       if (bit)
          bajt |=bpoz;  /* ustawia bit stosownie do bpoz */
       else
          bajt &=~bpoz;  /* czyści bit */

       bpoz >>=1;   /* przesuwamy się 1 bit "niżej" */

       if(bpoz==0) {   /* zapisano wszystkie 8 bitów w bajcie */
          zapisz_bajt(bajt);
          bpoz = 0x80;   /* i hop na początek bajtu */
       }
    }

    /* i tutaj bardzo ważna funkcja! funkcja zapiszz_bit() zapisuje dopiero gdy bajt zostanie wypełniony. A co się stanie, gdy zechcemy zapisać np. 45 bitów? - Zapisane zostanie tylo tyle bitów, ile zmieści się w pełnych bajtach (czyli 45/8 = 5 :D matematyka dyskretna), reszta 45-5*8 = 5) będzie sobie czekała w buforze. efekt - niepoprawna zawartość pliku.
    A co z tym zrobić?
    po zakończeniu wszystkich operacji zapisu bitów (a przed zamknięciem pliku) wywołujemy poniższą funkcję, wypełni ona brakujące bity zerami i zapisze ostatni bajt, jeżeli nie będzie co zapisywać - nie zrobi nic
    */

    void bit_flush()
    {
       while(bpoz!=0x80)
           zapisz_bit(0);
    }

    oczywiście ta metoda jest super-mało wydajna, w praktyce dobrze było by zapisywać bufor większy niż jeden bajt :D

    A co do kompresji, to książeczka, którą poleca h-doc, też ją mam, droga nie jest, tylko nie wiem, czy jeszcze jest w księgarniach, ja kupowałem kilka lat temu i nie żałuję, warto było.
    Tam masz sporo rodzajów kompresji opisanych bardzo dokładni wraz z kodami źródłowymi
  • Level 22  
    Znalazlem jakis sposob na kompresje - algorytm byterun. Nie wiem tylko jak to dokladnie dziala.

    Na przykład, jeżeli chcemy poddać kompresji ciąg bajtów:

    3 4 5 1 1 1 1 1 1 1 3 9 A A

    postępowanie będzie następujące:
    -- pierwsze trzy bajty są różne, w buforze zapisujemy, ile ich jest wraz z nimi;

    zawartość bufora: 3 3 4 5
    -- kolejne siedem bajtów jest identyczne, do bufora dopisujemy zanegowaną liczbę powtórzeń zmniejszoną o jeden oraz bajt, który się powtarza;

    zawartość bufora: 3 3 4 5 -7
    -- następne dwa bajty są różne -- postępujemy jak w pierwszym kroku:

    zawartość bufora: 3 3 4 5 -7 1 2 3 9
    -- ostatnie dwa bajty są identyczne, więc ostateczna zawartość bufora będzie następująca:

    3 3 4 5 -7 1 2 3 9 -2 A

    Z powyższego przykładu można wyciągnąć następujące wnioski: -- zysku nie ma, jeśli sąsiadują ze sobą tylko dwa identyczne bajty; -- jeżeli w danych poddawanych kompresji nie wystąpią ciągi jednakowych bajtów (więcej niż dwa), to długość danych po kompresji będzie w najgorszym wypadku większa od oryginału o rozmiar oryginału podzielony przez 127 bajtów (bo na każde kolejne 127 różnych bajtów trzeba dopisać jeden bajt z ich licznikiem).

    No bo jak taki plik dekompresowac???? Z kad mam wiedziac gdzie jest poczatek powtarzajacych sie znakow. Nie widze tu zadnego znacznika.
    Spotkal sie ktos z czyms takim i moglby cos napisac na ten temat??
  • Level 35  
    krzysiek40 wrote:
    Znalazlem jakis sposob na kompresje - algorytm byterun. Nie wiem tylko jak to dokladnie dziala.

    Przecież sam napisałeś, jak działa :D

    krzysiek40 wrote:
    zawartość bufora: 3 3 4 5 -7 1

    Brakło jedynki

    A w ogóle to trochę pokręciłeś.
    krzysiek40 wrote:
    -- pierwsze trzy bajty są różne, w buforze zapisujemy, ile ich jest wraz z nimi;

    W algorytmie byterun zapisuje się ilość pomniejszoną o 1, czyli na początku bufora będzie 2 3 4 5....

    krzysiek40 wrote:
    -- kolejne siedem bajtów jest identyczne, do bufora dopisujemy zanegowaną liczbę powtórzeń zmniejszoną o jeden oraz bajt, który się powtarza;

    czyli zamiast - 7 powinno do bufora trafić -8.

    ostatecznie bufor wygląda tak:
    Code:

    WE:   3 4 5        1 1 1 1 1 1 1    3 9       A A
    WY:   2 3 4 5     -8 1              1 3 9    -3 A

    końcówkę bufora można też zapisać: 3 3 9 A A , zajmuje tyle samo miejsca, a dekompresja przebiega szybciej, ale to już takie tam meandrowanie... :D

    krzysiek40 wrote:
    No bo jak taki plik dekompresowac???? Z kad mam wiedziac gdzie jest poczatek powtarzajacych się znakow. Nie widze tu zadnego znacznika.
    Spotkal się ktos z czyms takim i moglby cos napisac na ten temat??


    Jak to, nie ma znacznika? A czymże jest w takim razie zapisywana ilość bajtów? Na niebiesko masz znaczniki:

    2 3 4 5 -8 1 1 3 9 -3 A

    Algorytm dekompresji:

    1. mamy dwa strumienie: wejściowy (WE) i wyjściowy (WY)
    2. pobieramy z WE jeden bajt (n=WE)
    2.1 Jeżeli n dodatnie, to pobieramy z WE n+1 bajtów i wstawiamy je do WY
    2.2 Jeżeli n ujemne, to pobieramy 1 bajt z WE i kopiujemy go (-(n+1) ) razy do WY
    3. skocz do 2.


    Ten rodzaj kompresji jest wykorzystywany w amigowych plikach graficznych (IFF ILBM)


    Na początku pliku trzeba sobie zapisać ile mamy bajtów skompresowanych danych, albo ile ma być bajtów zdekompresowanych.
    Można też ewentualnie wprowadzić dodatkowy znacznik, określający koneic danych.
    W formacie IFF ILBM jest taki wolny znacznik (-128), który wprawdzie oznacza "rób nic" :D , ale na własne potrzeby możesz go użyć do oznaczenia końca danych.
    W takim wypadku do powyższego algorytmu należało by dodać jeszcze jedną linię (pomiędzy punkatami 2. i 2.1): JEŻELI n=-128, to KONIEC

    Do kompresji tekstu najlepsze są metody słownikowe (jak np. LZW)

    Ogólnie kompresję za pomocą metod słownikowych przeprowadza się w dwóch etapach:
    1. Właściwa kompresja słownikowa (tzn. utworzenie słownika i strumienia kodów)
    2. Post-kompresja powstałego strumienia (w szczególności) i słownika (ewentualnie) za pomocą metody probabilistycznej (np. algorytmem Huffmana)

    Najważniejsze jest stworzenie odpowiedniego słownika.
    ogólnie tworzenie słownika polega na znalezieniu powtarzających się ciągów znaków, niekoniecznie bajtów, równie dobrze można operować na pojedynczych bitach, albo na słowach 16 bitowych, wszystko zależy od charakteru kompresowanych danych. Procedura tworząca słownik jast najbardziej skomplikowaną częścią całego algorytmu kompresji słownikowej, bo to od niej zależy jakość i szybkość kompresji.
    Przykładowo popularne archiwizery jak RAR, czy ZIP umożliwiają wybór stopnia kompresji, co w praktyce realizowane jest przez wybór odpowiedniej procedury przeszukiwania strumienia.
    Najlepsza kompresja znajduje zazwyczaj (nie zawsze!) najwięcej powtarzających się ciągów, ale kosztem wydłużenia czasu kompresji.
    Co ciekawe: W archiwizerach ZIP i RAR, niezależnie od tego, która procedura kompresji była użyta, procedura dekompresji jest zawsze ta sama! :D




    Przykład kompresji metodą słownikową:
    "Joja lojalna, Jola nielojalna"
    Można skompresować tak (ale jaki jest algorytm to już nie powiem, bo może być różny :D ):
    słownik:
    [0]: "Jola "
    [1]: "lojalna"

    strumień:
    0 1 -2", " 0 -4" nie" 1

    w tym przypadku z 29 bajtów zrobiło się 24 (12 słownik + 12 strumień)

    dekompresujemy tak:
    pobieramy ze strumienia wejściowego (WE) liczbę n
    jeżeli n >=0 do do strumienia WY wstawiamy pozycję ze słownika o indeksie n
    jeżeli n ujemne, to do strumienia WY kopiujemy -n znaków ze strumienia WE

    czyli naszą Jolę zdekompresujemy tak:
    0 - wstawiamy ciąg o indeksie 0 w słowniku:
    "Jola "
    1 - wstawiamy ciąg o indeksie 1 w słowniku:
    "Jola lojalna"
    -2", " - wstawiamy 2 następne bajty ze strumienia wejściowego (przecinek i spacja):
    "Jola lojalna, "
    0 - wstawiamy ciąg o indeksie 0 w słowniku:
    "Jola lojalna, Jola"
    -4" nie" - wstawiamy 4 następne bajty ze strumienia WE:
    "Jola lojalna, Jola nie"
    1 - wstawiamy ciąg o indeksie 1 w słowniku:
    "Jola lojalna, Jola nielojalna"

    Słownik można wpleść w strumień wejściowy, tak, że będzie tworzony wraz z dekodowaniem strumienia, albo zapisywać na początku pliku.

    A w ogóle to www.google.pl , np. tak:
    http://www.google.pl/search?num=50&hl=pl&q=ko...listyczna+%7C+s%C5%82ownikowa&btnG=Szukaj&lr=

    Poza tymi rodzajami kompresji jest jeszcze kodowanie arytmetyczne (też rodzaj kompresji probabilistycznej), które zapewnia większą wydajność niż algorytm Huffmana, ale sam proces kompresji przebiega dużo wolniej.
  • Level 22  
    Nadal nie rozumiem przeciez program nie odrozni kolorow bo ich nie ma to z kad.
    No ale moze jakos sobie z tym poradze. Mam jeszcze pytanie bo chyba WORD, EXEL to w piku liczby ujemne tez zapisuja czy sie myle??

    Czy w ogole algorytm ByteRun nadaje sie do tego typu plikow??
  • Level 34  
    krzysiek40 wrote:
    Nadal nie rozumiem przeciez program nie odrozni kolorow bo ich nie ma to z kad

    do plików niezapisuje sie kolorów tylko ich składowe.. w pliku np. bmp który jest niekompresowany 24-bitowym kolor biały zostanie zapisany jako FFFFFF czerwony-FF0000 zielony-00FF00 niebieski-0000FF itd.. na każdy piksel przypadają 3 bajty. każdy bajt opisuje jedną składową piksela.. kompresowanie pliku o jednolitym kolorze jest oczywiście bardziej skuteczne niż jakiegoś krajobrazu.. jeśli mamy 4 pixele o tym samym kolorze np szarym to mamy strumień danych 808080808080808080808080... algorytm hufmana skróci to w najlepszym wypadku do 20 bitów: 8 na generator drzewa i na 12 dane.. (1 bit zamiast 1 bajtu...)

    ciekawostka:
    plik o rozmiarze 256 bajtów, posiadający każdy bajt o innej wartości, po spakowaniu do pliku rar niestraci ani bitu na swoim rozmiarze, a zakładając nazwy, atrybuty, crc32 plik rar będzie o wiele większy..
    plik o rozmiarze 300MB (na takim testowałem) w którym wszystkie bajty mają taką samą wartość pakując dwukrotnie rarem otrzymujemy plik o rozmiarze 2KB
  • Level 35  
    eeeech....
    Dekompresor nie musi wiedzieć, gdzie znajdują się wszystkie znaczniki.

    To nie jest tak, że procedura widzi (dosłownie :D ) cały skompresowany plik na raz.

    Strumień danych do dekompresji w byterun zaczyna się ZAWSZE od znacznika i w algorytmie dekompresji masz jasno napisane co trzeba z nim zrobić. Czyli, albo zostanie pobrane ze strumienia WE ileś tam bajtów, albo jeden, to zależy od znacznika. Po tych pobranych bajtach ZAWSZE znajduje się następny znacznik itd...

    Strumień danych: mniej więcej to samo, co kolejka wsuper markecie :D . Pobieranie danych ze strumienia wygląda tak:
    Pobierasz jeden bajt - indeks strumienia przesuwa się o 1
    Pobierasz milyjon bajtów - indeks strumienia przesówa się o milion.

    Przykład:
    Zawartość strumienia: "Satan was zezre"
    na początku indeks strumienia wynosi 0 , czyli wskazyje na pierwszy kod w strumieniu ("S")

    pobierasz ze strumienia 1 kod (bajt, znak, czy jak to sobie nazwiesz), dostajesz "S", a indeks strumienia przesuwa się o jedną pozycję dalej, czyli wskazyje na "a"
    Pobierasz 7 kodów ze strumienia - dostajesz 7 kodów zaczynając od tego, na który wskazuje indeks, czyli dostaniesz "atan wa", a indeks strumienia przesunie się o 7 pozycji dalej, czyli będzie wskazywał na "s".

    I w byterun jest to samo masz ciąg:
    2 3 4 5 -8 1 1 3 9 -3 A

    Czyli zgodnie z opisanym wcześniej algorytmem:

    na początku indeks strumienia (i) = 0, czyli wskazuje na pierwszy kod, który jest znacznikiem.

    pobieramy kod (k=2), indeks przesuwa się o 1 czyli i=1. k=2 oznacza, że mamy pobrać ze strumienia 3 kody, co też czynimy, mamy 3 kody, które kopiujenmy do strumienia WY, a indeks przesuwa się o 3 pozycje dalej, czyli teraz i=4. na pozycji 4 mamy (NIESPODZIANKA!) znowu znacznik. pobieramy znacznik (i=5) pobieramy jeden bajt (i=6) i co? znowu znacznik.

    Ogóleni efekt kompresji byteryun wygląda tak:
    znacznik dane znacznik dane znacznik dane...
    dane - 1 albo więcej bajtów, a ile - to sobie określamy na podstawie zawartości znacznika, po pobraniu odpowiedniej ilości danych, zawsze napotykamy na znacznik!!!


    byterun nadaje się do kompresji danych, w których występują ciągi takich samych kodów następujących bezpośrednio po sobie.

    np. plik graficzny o rozmiarach 64x64 pixele cały biały, z jednym czarnym pixelem o współrzędnych 32x32 zakodujemy tak:
    -65 biały
    -65 biały
    (...)
    -33 biały 0 czarny -32 biały
    -65 biały
    (...)

    W standardzie IFF ILBM (i nie tylko) pakuje się osobne linie, tzn nie można zrobić czegoś takiego:
    -97 biały, co miało by oznaczać 64 pixele w pierwszej linii i 32 w następnej białe. Robi się tak z pewnego powodu, ale to nie czas i miejsce. :D

    Do kompresji tekstu, dźwięku i nie wiem czego jeszcze byterun się nie nadaje
  • Level 22  
    Ok wielkie dzieki za wyjasnienia. Chce jeszcze sprawdzic czy dobrze mysle. Tym sposobem mozna kompresowac cokolwiek byleby plik byl mniejszy po niz przed???
  • Level 22  
    Od 3 dni proboke napisac kompresje z uzyciem ByteRun. Nie idzie mi za bardzo i prosze o pomoc. Moze ktos juz robil tego typu kompresje i moglby sie podzielic doswiadczeniami albo programikiem na krzysiek400(malpa)op.pl. Ja musze to napisac w c++ zorientowane obiektowo. Narazie proboje to nieobiektowo zrobic i pozniej poprzerabiac no ale jest jak juz napisalem. Same problemy. Narazie mojego programu nie moge zamiescic bo mam go w laptoku i nie mam jak skopiowac.
    Wielkie dzieki za dotychczasowa pomoc i pozdrawiam wszystkich.
  • Level 2  
    mam za zadanie napisac kompresor i dekompresor w pascalu. Nie wiem zabardzo jak sie za to zabrac, niezdecydowalem sie jakia metode wybrac. ten kompresor musi byc bardzo wydajny. Kompresja musi byc jak najlepsza. Jaka metode wybrac? Shannona?? Huffmana?? moze inna ??