szit

Ez az oldal csak olvasható. Megtekintheted a forrását, de nem változtathatod meg. Ha úgy gondolod, hogy ez helytelen, kérdezd az Adminisztrátorokat!
[[oktatas:programozás:algoritmusok|< Algoritmusok]]
====== LZ77 ======

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Szerkesztve: 2014, 2019, 2020
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu

===== Az LZ77-ről =====

**Abraham Lempel** és **Jakob Ziv** publikálta 1977-ben. Innen a neve, bár LZ1 néven is használták.


Toló- vagy csúszóablakos tömörítés.

Egy k hosszúságú ablakot használunk, amelyet végigcsúsztatunk a tömörítendő karaktersorozaton.
A k ablak két részből áll. Egy h<sub>k</sub> hosszúságú keresőablakból és egy h<sub>e</sub> hosszúságú előremutató ablakból. 




===== Példa =====

  TONINITONINIT


^ lépés ^  kimenet  ^
|  1  | 0, 0, T |
|  2  | 0, 0, O |
|  3  | 0, 0, N |
|  4  | 0, 0, I |
|  5  | 2, 2 ,T |
|  6  | 6, 6, * |

===== Példa részletesen =====

Legyen egy karaktersorozat a példa kedvéért:

  TONINITONINIT

A kódolása:

Legyenek a következő ablak méretek:
  * h = 16
  * h<sub>k</sub> = 8
  * h<sub>e</sub> = 8


          TONINITONINIT
  ^              ^
     teljes ablak

A kereső és az előremutató ablak ekkor:
          TONINITONINIT
  ^      ^^      ^
  |      ||      |
   kereső  előrem.


Vegyük az előremutató ablak első karakterét:


          TONINITONINIT
          ^
  |      ||      |
   kereső  előrem.

Ez "T" betű. Megkeressük a keresőablakban van-e ilyen karakter, a keresőablakban visszafele haladva.
A keresőablak üres, így csak lekódoljuk magát a T betűt. A kód kimenete három érték. Általánosan felírva:
  index, hossz, karakter

  * Az index, ha a keresőablakban volt ilyen karakter, akkor annak helye, ellenben 0
  * A hossz, ha a keresőablakban volt ilyen karakter, akkor hány további karakter egyezik az előremutató és a keresőablakban.
  * Ha nem volt egyezés felírjuk a karaktert, ha volt felírjuk az első nemegyező karaktert


Az első kódkimenet ezek alapján:
  <0, 0, T>

Az egész ablakot eltoljuk jobbra eggyel:

          TONINITONINIT
           ^
   |      ||      |
    kereső  előrem.

A következő az "O" betű. A keresőablakban nincs ilyen betű, ezért ezt is csak felírjuk:
  <0, 0, T>
  <0, 0, O>


Az egész ablakot eltoljuk jobbra eggyel:

          TONINITONINIT
            ^
    |      ||      |
     kereső  előrem.

Az "N" betűvel az előbbiekhez hasonlóan járok el:

  <0, 0, T>
  <0, 0, O>
  <0, 0, N>


Az "I" betűvel is:
  <0, 0, T>
  <0, 0, O>
  <0, 0, N>
  <0, 0, I>


A keresőablakunk, most egy olyan betűhöz ért, ami szerepel a keresőablakban.
          TONINITONINIT
              ^
      |      ||      |
       kereső  előrem.

Felírjuk, a keresőablakban visszafele hányadik helyen van az "N" betű.
A számozást eggyel kezdem. Így a második helyet kell felírnunk.
Felírjuk a kettőt:
  <2, . , .>
A másik két érték még kérdéses.

Megnézzük, hogy hány karakter egyezik N-től a kereső és az előremutató ablakban.
Egyezés "NI":

  TONINITONINIT
    ^^^^
Amit kimenetként felírunk:
  <2, 2 , T>

A harmadik helyre felírjuk az előremutató ablakban a következő nem egyező karaktert:

  TONINITONINIT
        ^
A kódunk most így néz ki:
  <0, 0, T>
  <0, 0, O>
  <0, 0, N>
  <0, 0, I>
  <2, 2 ,T>

A következő karaktert vesszük ez egy "O" betű:

  TONINITONINIT
         ^

Nézzük, hol tart az ablak:

          TONINITONINIT
                 ^
         |      ||      |
          kereső  előrem.

Az "O" betű szerepel a keresőablakban, visszafele a 6-s helyen. Hat egyezés van. 
Elfogytak a karakterek, így vége van.

A kódunk most így néz ki:
  <0, 0, T>
  <0, 0, O>
  <0, 0, N>
  <0, 0, I>
  <2, 2 ,T>
  <6, 6, *>


===== Segédeszköz =====

  * https://szit.hu/lz

===== Gyakorlat =====

==== Feladat 001 ====

Dekódolja a következő kódot:
<code>
0,0,p
0,0,a
0,0,r
0,0,k
0,0,o
0,0,l
0,0,á
0,0,s
0,0,_
0,0,a
2,1,p
3,1,r
0,0,k
0,0,b
4,1,n
0,0,_
0,0,p
4,1,t
2,1,k
6,1m
0,0,e
0,0,l
1,1,e
0,0,t
1,1,null
</code>