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

[ellenőrzött változat]

Tartalom törölve Tartalom hozzáadva

Sorban

A lap jelenlegi, 2021. január 30., 00:30-kori változata

Az LZ77 veszteségmentes tömörítőalgoritmus, amit Abraham Lempel és Jacob Ziv publikált 1977-ben (ezt jelöli a névben szereplő 77-es szám). Az algoritmust a szerzőpáros egy évvel később továbbfejlesztette LZ78 néven.

Az idők folyamán többen készítettek ennek az eljárásnak az alapján tömörítő algoritmusokat, mint például a James Storer és Thomas Szymanski nevéhez fűződő LZSS, a Terry Welch által bemutatott LZW és az Igor Pavlov jegyezte LZMA algoritmus.

Az algoritmus működése[szerkesztés]

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ő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[szerkesztés]

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 (B, L) C formulát, ahol B a megtalált karakter távolsága az előretekintő puffertől, az L az egyező karakterek legnagyobb hosszúsága, a C 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 L+1-el, majd visszaugrik a 2. lépésre.

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[szerkesztés]

Informatikaiportál • összefoglaló, színes tartalomajánló lap

Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!

@@ 1. sor: / 1. sor: @@
-Az '''LZ77''' [[veszteségmentes tömörítés|veszteségmentes tömörítőalgoritmus]], amit [[Abraham Lempel]] és [[Jakob Ziv]] publikált [[1977]]-ben (ezt jelöli a névben szereplő 77-es szám). Az algoritmus továbbfejlesztett változatai az [[LZ78]] és [[LZW]] algoritmusok.
+Az '''LZ77''' [[veszteségmentes tömörítés|veszteségmentes tömörítőalgoritmus]], amit [[Abraham Lempel]] és [[Jacob Ziv]] publikált [[1977]]-ben (ezt jelöli a névben szereplő 77-es szám). Az algoritmust a szerzőpáros egy évvel később továbbfejlesztette [[LZ78]] néven.
-Az algoritmust sokan módosították, javították a jobb tömörítés érdekében, ezek közül a legismertebb megvalósítás [[James Storer]] és [[Thomas Szymanski]] nevéhez fűződik, akik [[LZSS]] tömörítés néven dolgozták ki algoritmusukat.
+Az idők folyamán többen készítettek ennek az eljárásnak az alapján tömörítő algoritmusokat, mint például a [[James Storer]] és [[Thomas Szymanski]] nevéhez fűződő [[LZSS]], a [[Terry Welch]] által bemutatott [[LZW]] és az [[Igor Pavlov]] jegyezte [[LZMA]] algoritmus.
 == 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 }}
+{{Portál|Informatika|i}}
 {{csonk-info}}
 [[Kategória:Tömörítő algoritmusok]]