• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • LZSS



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    ARJ jest jednym z formatów kompresji danych oraz programem do kompresji i dekompresji tego typu plików. Został stworzony przez Roberta K. Junga. Wersja 1.0 powstała w lutym 1991 roku. Nazwa wywodzi się od angielskiego: Archived by Robert Jung (skompresowane przez Roberta Junga). Pliki spakowane ARJ mają zwykle rozszerzenie „.arj”.Kompresja bezstratna (ang. lossless compression) – ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem, że metoda ta gwarantuje możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.

    LZSS – nazwa słownikowej metody bezstratnej kompresji danych. LZSS jest ulepszonym wariantem metody LZ77.

    Nazwa metody pochodzi od nazwisk: Lempel-Ziv-Storer-Szymanski, została opracowana przez Jamesa A. Storera i Thomasa G. Szymanskiego i opisana w 1982 roku w Journal of the ACM, w artykule pt. Data compression via textual substitution (s. 928–951).

    Algorytm LZSS jest używany między innymi w programach PKZIP i ARJ.

    LZ78 – słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Jacoba Ziva i Abrahama Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536).Kilobajt (KB, rzadziej kB, ang. Kbyte, kbyte, kilobyte) – jednostka używana w informatyce do określenia ilości informacji lub wielkości pamięci.

    Algorytm kompresji[ | edytuj kod]

    Metoda LZSS, tak samo jak LZ77, używa bufora, podzielonego na dwie części:

  • słownik (bufor słownikowy) – przechowującą ostatnio przetwarzanych symboli, obejmujący indeksy
  • bufor wejściowy (bufor kodowania) – przechowujący symboli, które mają zostać zakodowane, obejmujący indeksy
  • Wartości i są dobierane tak, aby były potęgami dwójki. Rozmiar słownika jest dużo większy niż bufora wejściowego, w praktyce ma kilka-kilkadziesiąt kilobajtów.

    Lempel-Ziv-Welch (skracane zwykle do LZW) – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.PKZIP – program do kompresji danych napisany przez amerykańskiego programistę Phila Katza, wykorzystujący do kompresji danych algorytm ZIP. PKZIP jest akronimem od Phil Katz ZIP.

    W każdym kroku algorytmu w słowniku wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego, charakteryzowany parą ( ), gdzie – indeks początku podciągu, – jego długość. Symbol w buforze następujący po dopasowanym ciągu oznaczmy jako

    Bit (w ang. kawałek, skrót od binary digit, czyli cyfra dwójkowa) – najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ. Jednostka logiczna.Kodowanie słownikowe - kodowanie danych, w którym podciągi komunikatu występujące w słowniku (tj. zbiorze słów) są zastępowane symbolami jednoznacznie opisującym ich pozycję w słowniku, zwykle indeksami (liczbami). Takie metody dobrze kompresują dane, w których podciągi powtarzają się, np. w przypadku tekstów naturalnych (teksty książek, czasopism itp.) wiele słów a nawet całych fraz występuje wielokrotnie.

    Algorytm LZ77 wypisuje na wyjście trójki nawet wtedy, gdy trójka ma większą długość niż opisywaną przez nią ciąg. Algorytm LZSS wypisuje na wyjście tylko pary ale bierze przy tym pod uwagę fakt, czy para nie zajmuje więcej bitów niż opisywany przez nią ciąg symboli. Jeśli kodowany ciąg jest dłuższy niż para, wówczas opłaca się wypisać na wyjście parę, w przeciwnym razie na wyjście wypisywany jest tylko pierwszy symbol z bufora wejściowego W celu odróżnienia symbolu od pary, poprzedza się je pojedynczym bitem:

    Lempel-Ziv 77, skracane zwykle do LZ77 (algorytm LZ77) – metoda strumieniowej słownikowej kompresji danych. Metoda LZ77 wykorzystuje fakt, że w danych powtarzają się ciągi bajtów (np. w tekstach naturalnych będą to słowa, frazy lub całe zdania) – kompresja polega na zastępowaniu powtórzonych ciągów o wiele krótszymi liczbami wskazującymi, kiedy wcześniej wystąpił ciąg i z ilu bajtów się składał; z punktu widzenia człowieka jest to informacja postaci "taki sam ciąg o długości 15 znaków wystąpił 213 znaków wcześniej".Bajt (dop. bajtu lub bajta) – najmniejsza adresowalna jednostka informacji pamięci komputerowej, składająca się z bitów.
  • (0, ),
  • (1, ).
  • Formalnie algorytm kompresji przebiega następująco:

    1. Wypełnij słownik pierwszym symbolem, wypisz ten symbol na wyjście; wypełnij bufor wejściowy pierwszymi symbolami wejściowymi.
    2. Dopóki w buforze wejściowym są dane:
      1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi bufora wejściowego – wynikiem są liczby i
      2. Jeśli rozmiar pary ( ) jest mniejszy od rozmiaru znalezionego podciągu, zapisz na wyjście trójkę (1,), przesuń cały bufor o pozycji w lewo i wprowadź do bufora wejściowego tyle samo kolejnych symboli.
      3. W przeciwnym razie wypisz na wyjście parę (0, ), przesuń cały bufor o 1 pozycję w lewo i wprowadź do bufora wejściowego kolejny symbol wejściowy.

    Uwaga: ponieważ w przypadku wypisywania pary liczba nigdy nie będzie miała wartości 0 ani 1, toteż można zmniejszyć liczbę bitów wymaganą do zapisania poprzez przypisanie wartości binarnej 0 liczby 2, wartości binarnej 1 liczby 3 itd. Np. dla do zapisania należałoby przeznaczyć 3 bity, a przy takim przyporządkowaniu wystarczą 2 bity.

    Przykładowy krok algorytmu[ | edytuj kod]

    1. Wyszukanie najdłuższego podciągu równego początkowi bufora wejściowego (tutaj: aac).

              słownik               |  bufor wejściowy  | nieprzetworzone symbole
      0   1   2   3   4   5   6   7 | 0   1   2   3   4 |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
    | a | a | a | a | a | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
    |                      okno                         |
    

    2. Wynik wyszukiwania:

    P = 2 (pozycja w słowniku)
    C = 3 (długość podciągu)
    

    3. Przyjmując, że para (P,C) zajmuje mniej niż ciąg aac - przesunięcie bufora o C pozycji, dopisanie do bufora wejściowego nieprzetworzonych symboli.

              słownik               |  bufor wejściowy  | nieprzetworzone symbole
      0   1   2   3   4   5   6   7 | 0   1   2   3   4 |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
    | a | a | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
    

    4. Przyjmując, że para (P,C) zajmuje więcej bitów niż kodowany ciąg - przesunięcie bufora o 1 pozycję, wprowadzenie do bufora wejściowego jednego symbolu.

              słownik               |  bufor wejściowy  | nieprzetworzone symbole
      0   1   2   3   4   5   6   7 | 0   1   2   3   4 |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
    | a | a | a | a | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
    


    Podstrony: 1 [2] [3] [4]




    Reklama

    Czas generowania strony: 0.026 sek.