• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • LZ77



    Podstrony: 1 [2] [3] [4] [5]
    Przeczytaj także...
    Kodowanie Huffmana (ang. Huffman coding) – jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.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”.

    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”.

    Abraham Lempel (hebr. אברהם למפל, urodzony 10 lutego 1936 we Lwowie) - izraelski naukowiec, informatyk, najbardziej znany ze współautorstwa (z Jacobem Zivem) algorytmów bezstratnej kompresji danych Lempel-Ziv (LZ77 i LZ78). Autor ponad 70 prac, właściciel 8 patentów.PNG (ang. Portable Network Graphics) – rastrowy format plików graficznych oraz system bezstratnej kompresji danych graficznych.

    Algorytm LZ77 jest wolny od wszelkich patentów, co w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia. Doczekał się wielu ulepszeń i modyfikacji, dających lepsze współczynniki kompresji albo dużą szybkość działania. Na LZ77 opiera się m.in. algorytm deflate, używany jest również w formatach ZIP, gzip, ARJ, RAR, PKZIP, a także PNG.

    ZIP – jeden z najczęściej używanych formatów kompresji i archiwizacji danych na platformie PC, zwłaszcza w środowisku Microsoft Windows.Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca - służy do lokalizowania w tekście określonego podciągu. Został stworzony w 1987 roku przez Michaela O. Rabina i Richarda Karpa.

    Algorytm został opracowany w 1977 przez Abrahama Lempela i Jacoba Ziv i opisany w artykule A universal algorithm for sequential data compression opublikowanym w IEEE Transactions on Information Theory (s. 8–19). Rok później autorzy opublikowali ulepszoną wersję metody, znaną pod nazwą LZ78.

    Organizacja IEEE uznała algorytm Lempel-Ziv za kamień milowy w rozwoju elektroniki i informatyki.

    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).Jacob Ziv (hebr. יעקב זיו, ur. 27 października 1931 w Tyberiadzie, w Palestynie) – izraelski informatyk, najbardziej znany ze współautorstwa (wspólnie z Abrahamem Lempelem) algorytmu bezstratnej kompresji danych Lempel-Ziv (LZ77 i LZ78).

    Zasada działania[ | edytuj kod]

    W LZ77 zapamiętywana jest w słowniku pewna liczba ostatnio kodowanych danych – przeciętnie kilka do kilkudziesięciu kilobajtów. Jeśli jakiś ciąg powtórzy się, to zostanie zastąpiony przez liczby określające jego pozycję w słowniku oraz długość ciągu; do zapamiętania tych dwóch liczb trzeba przeznaczyć zazwyczaj o wiele mniej bitów niż do zapamiętania zastępowanego ciągu.

    LZP (P od predykacja) - metoda kompresji opracowana w 1996 roku przez Charlesa Blooma, będąca modyfikacją algorytmu LZ77, wykorzystująca kontekstowość danych - pewne ciągi występują z większym prawdopodobieństwem w sąsiedztwie innych. Mówiąc obrazowo, jeśli wcześniej po ciągu abc wystąpił ciąg def, i znów pojawił się ciąg abc, to jest szansa, że następnym ciągiem będzie def.W informatyce tablica mieszająca lub tablica z haszowaniem (ang. hash table, niekiedy błędnie tłumaczone jako "tablica haszująca") to struktura danych, która jest jednym ze sposobów realizacji tablicy asocjacyjnej, tj. abstrakcyjnego typu danych służącego do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp. Tablica mieszająca umożliwia również szybkie porównywanie danych, np. fragmentów tekstów, plików.

    Metoda LZ77 zakłada, że ciągi powtarzają się w miarę często, tzn. na tyle często, żeby wcześniejsze wystąpienia można było zlokalizować w słowniku – ciągi powtarzające się zbyt rzadko nie są brane pod uwagę. Wady tej pozbawiona jest metoda LZ78, w której – przynajmniej teoretycznie – słownik rozszerza się w nieskończoność.

    Instytut Inżynierów Elektryków i Elektroników, IEEE (od ang. Institute of Electrical and Electronics Engineers) – organizacja typu non-profit skupiająca osoby zawodowo związane z elektrycznością i elektroniką, a także pokrewnymi dziedzinami. Powstała w 1963 roku, w wyniku konsolidacji Amerykańskiego Instytutu Inżynierów Elektryków (American Institute of Electrical Engineers, AIEE) oraz Instytutu Inżynierów Radiowych (Institute of Radio Engineers, IRE). Jednym z podstawowych jej zadań jest ustalanie standardów dla urządzeń elektronicznych, w tym standardów dla urządzeń i formatów komputerowych. Kilobajt (KB, rzadziej kB, ang. Kbyte, kbyte, kilobyte) – jednostka używana w informatyce do określenia ilości informacji lub wielkości pamięci.

    Bardzo dużą zaletą kodowania LZ77 (a także innych metod słownikowych z rodziny LZ, tj. LZSS, LZ78, LZW itp.) jest to, że słownika nie trzeba zapamiętywać i przesyłać wraz z komunikatem – zawartość słownika będzie na bieżąco odtwarzana przez dekoder.

    Algorytm kompresji jest bardziej złożony i trudniejszy w realizacji niż algorytm dekompresji. W metodzie LZ77 można wpływać na prędkość kompresji oraz zapotrzebowania pamięciowe, regulując parametry kodera (rozmiar słownika i bufora kodowania).

    Algorytm kompresji[ | edytuj kod]

    Metoda LZ77 korzysta z bufora (okna), który logicznie podzielony jest na dwie części:

    Lempel-Ziv-Welch (skracane zwykle do LZW) – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.RAR (skrótowiec od Roshal ARchive) – format bezstratnej kompresji danych, stworzony przez Rosjanina Jewgienija Roszała. Używa odmiany kompresji LZSS, może być szyfrowany za pomocą AES-128. RAR posiada wolniejszy rodzaj kompresji niż ZIP, ale w większości przypadków skuteczniejszy.
  • bufor słownikowy (słownik), przechowujący ostatnio przetwarzanych symboli (sufiks);
  • bufor wejściowy (lub bufor kodowania), przechowujący symboli do zakodowania.
  • Bufor słownikowy obejmuje indeksy bufor wejściowy

    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.Bufor to obszar pamięci służący do przechowywania danych do komunikacji pomiędzy dwoma systemami, np. bufor karty sieciowej przechowuje pakiety, które mają zostać wysłane, a bufor karty graficznej – to co ma zostać wyświetlone na ekranie.

    Rozmiary i mogą być dowolne, w praktyce dobiera się je tak, aby były całkowitą potęgą dwójki, dzięki czemu w pełni wykorzystywane są słowa bitowe przeznaczone do ich zapamiętania. Rozmiar bufora słownikowego wynosi w praktyce kilka-kilkadziesiąt kilobajtów, bufor kodowania jest dużo mniejszy. Na przykład w programie gzip słownik ma 32 kB, bufor kodowania natomiast 258 bajtów.

    Bufor cykliczny - w informatyce bufor zorganizowany w ten sposób, że dane są przechowywane w tablicy, a dodatkowo przechowywane są dwa wskaźniki lub indeksy tablicy pokazujące pierwszy i ostatni element (albo pierwszy i puste miejsce za ostatnim). Dopisywanie nowych danych wymaga inkrementacji wskaźnika na ostatni element. W przypadku dojścia do końca tablicy jest on przemieszczany na początek. Podobnie wskaźnik odczytu po dojściu do końca tablicy przemieszcza się na początek. Bufor na ogół reprezentuje kolejkę FIFO, można też zaimplementować na nim bufor, w którym dane mogą być dopisywane i czytane z obydwu stron.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.

    Algorytm przebiega następująco:

  • Bufor słownikowy jest wypełniany pierwszym symbolem wejściowym i ten symbol jest zapisywany na wyjście.
  • Do bufora wejściowego wstawiane jest pierwszych symboli wejściowych.
  • Dopóki w buforze wejściowym są jakieś dane:
    1. W obrębie bufora słownikowego wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego (najdłuższy prefiks bufora kodowania). Wynikiem wyszukiwania jest indeks początku wyszukanego podciągu oraz jego długość ograniczona z góry przez Część podciągu może być wspólna z buforem wejściowym!
      Jeśli podciągu nie uda się znaleźć, to może mieć dowolną wartość, natomiast
    2. Na wyjście wyprowadzana jest trójka ( symbol z bufora wejściowego następujący po dopasowanym podciągu).
    3. Okno (bufor słownikowy + bufor wejściowy) przesuwane jest w lewo o pozycji i na koniec bufora dopisywane jest tyleż kolejnych symboli wejściowych (o ile jeszcze są jakieś).
  • Stopień kompresji LZ77 w dużej mierze zależy od długości słownika oraz długości bufora wejściowego (bufora kodowania). Programy wykorzystujące tę metodę mają zwykle możliwość ustalania rozmiaru słownika, istnieją również programy dynamicznie zmieniające rozmiar słownika.

    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.LZMA (ang. Lempel-Ziv-Markov chain-Algorithm) – algorytm kompresji bezstratnej opracowany przez Igora Pawłowa w latach 1999-2001.

    Prędkość kompresji natomiast jest uzależniona głównie od efektywności procedury wyszukującej najdłuższy prefiks. Używane są tutaj różne rozwiązania. Np. w programie gzip używa się tablicy haszującej adresowanej pierwszymi trzema literami z bufora kodowania. Stosowane są również zwykłe tablice, a do lokalizacji prefiksu używa się algorytmów wyszukiwania wzorca, np. algorytmu Karpa-Rabina.

    Bajt (dop. bajtu lub bajta) – najmniejsza adresowalna jednostka informacji pamięci komputerowej, składająca się z bitów.

    Jeśli słownik jest realizowany jako tablica, to aby uniknąć fizycznego, czasochłonnego przesuwania danych w oknie (punkt 3. algorytmu), używa się buforów cyklicznych.

    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 | c | 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)
    S = b (symbol z bufora wejściowego następujący po dopasowanym podciągu)
    

    3. Przesunięcie bufora o 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 |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
    | c | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
    


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




    Reklama

    Czas generowania strony: 0.077 sek.