„LZ77” változatai közötti eltérés

1 231 bájt hozzáadva ,  7 hónappal ezelőtt
a
formázás, bővítés, példa
(0 forrás archiválása és 1 megjelölése halott linkként. #IABot (v2.0beta10))
a (formázás, bővítés, példa)
 
Az '''LZ77''' [[veszteségmentes tömörítés|veszteségmentes tömörítőalgoritmus]], amit [[Abraham Lempel]] és [[JakobJacob Ziv]] publikált [[1977]]-ben (ezt jelöli a névben szereplő 77-es szám). Az algoritmusalgoritmust továbbfejlesztetta változataiszerzőpáros azegy [[LZ78]]évvel éskésőbb továbbfejlesztette [[LZWLZ78]] algoritmusoknéven.
 
Az algoritmustidők sokanfolyamán módosították,többen javítottákkészítettek aennek jobbaz tömörítéseljárásnak érdekében,az ezekalapján közültömörítő aalgoritmusokat, legismertebbmint megvalósításpéldául a [[James Storer]] és [[Thomas Szymanski]] nevéhez fűződikfűződő [[LZSS]], akika [[LZSSTerry Welch]] tömörítésáltal névenbemutatott dolgozták[[LZW]] kiés az [[Igor Pavlov]] jegyezte [[LZMA]] algoritmusukatalgoritmus.
 
== Az algoritmus működése ==
Az '''LZ77''' egy szótár alapú tömörítő eljárás, amely egy meghatározott méretű (4-64 [[kilobyte]]) úgynevezett csúszó ablakon keresztül vizsgálja a kódolandó adatfolyamot. A tömörítési folyamat során egy kereső[[Adatpuffer|pufferben]] letárolja az n db utolsó [[byte]]-ot, és amikor egy olyan byte-csoportot talál, mely szerepel ebben a pufferben, akkor a byte-csoport helyett annak a pufferben lévő helyét és hosszát tárolja le.
 
== Példa ==
Az '''LZ77''' alapú tömörítők letárolják az n db utolsó [[byte]]-ot, és amikor egy olyan byte-csoportot találnak, mely szerepel ebben a [[Adatpuffer|puffer]]ben, akkor a byte-csoport helyett annak a pufferben lévő helyét és hosszát tárolják le.
 
{| class="wikitable"
|+ Bemeneti adatfolyam
|-
! pozíció !! 1 !! 2 !! 3 !! 4 !! 5 !! 5 !! 7 !! 8 !! 9
|-
| karakter || A || A || B || C || B || B || A || B || C
|}
 
A kódolási folyamat menete:
# A pozíció beállítása az adatfolyam elejére;
# megkeresi a leghosszabb korábbi előfordulást;
# kimenetre írja a <code>(B, L) C</code> formulát, ahol <code>B</code> a megtalált karakter távolsága az előretekintő puffertől, az <code>L</code> az egyező karakterek legnagyobb hosszúsága, a <code>C</code> pedig az első nem egyező karakter az előretekintő pufferben;
# ha az előretekintő puffer nem üres, akkor eltolja a pozíciót (ablakot) az <code>L+1</code>-el, majd visszaugrik a 2. lépésre.
 
{| class="wikitable"
|+ Kódolási folyamat
|-
! lépés !! pozíció !! találat !! karakter !! kimenet
|-
| 1. || 1 || - || A || (0,0) A
|-
| 2. || 2 || A || B || (1,1) B
|-
| 3. || 4 || - || C || (0,0) C
|-
| 4. || 5 || B || B || (2,1) B
|-
| 5. || 7 || A B || C || (5,2) C
|}
 
== Források ==
*[http://users.iit.uni-miskolc.hu/~lippai/ Miskolci Egyetem Gépészmérnöki és Informatikai Kar Informatikai és villamosmérnöki tanszékcsoport]
*[https://vik.wiki/InfElmTetel44 A VIK Wikiből: InfElmTetel44]
*[https://wiki.sch.bme.hu/bin/view/Infoalap/InfElmTetel44?CGISESSID=910e9f341d2c9693b50026c738e44555 SCH BME wiki]{{Halott link|url=https://wiki.sch.bme.hu/bin/view/Infoalap/InfElmTetel44?CGISESSID=910e9f341d2c9693b50026c738e44555 |date=2018-11 }}
*[https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.8921 A Universal Algorithm for Sequential Data Compression (1977) by Jacob Ziv , Abraham Lempel]
 
{{Portál|Informatika|i }}
{{csonk-info}}
[[Kategória:Tömörítő algoritmusok]]
529

szerkesztés