LZW

A Wikipédiából, a szabad lexikonból.

Az LZW (Lempel-Ziv-Welch) egy veszteségmentes tömörítési algoritmus. Az informatikában széles körben használt eljárást Terry Welch publikálta 1984-ben az Abraham Lempel és Jacob Ziv által 1978-ban közzétett LZ78 algoritmus továbbfejlesztéseként.^[1]

[szerkesztés] Működése

A tömörítés alapja, hogy a kódoló csak egy szótárbeli indexet küld át. A szótár dinamikusan bővül, kiinduló állapotban az összes egybetűs szimbólumot tartalmazza. A kódolás elve igen egyszerű: az aktuális pozíciótól kezdve addig kell a szimbólumokat kiolvasni, amíg a sorozat szerepel a szótárban. Ezután elküldjük ezen sorozat indexét, a szótárba felvesszük kiegészítve a következő szimbólummal, és az algoritmust ettől a szimbólumtól folytatjuk.

[szerkesztés] Alkalmazása

A gyakorlatban fix szóhosszúságú szótárral használják, a szótár betelése után egyszerű fix szótáras tömörítést végeznek. Az LZW széles körben a Unix operációs rendszer compress segédprogramjának algoritmusaként terjedt el; ma leginkább a GIF képformátum részeként ismert. A GIF-hez használt implementációban a szótár maximális mérete 512, vagyis maximum 9 bit hosszú kódszavakat használ. Amikor a szótár betelik, 10 bites kódszavakra kell áttérni, vagyis a szótár mérete megduplázódik, és így tovább.

A TIFF képformátum és a PDF dokumentumformátum tömörítési eljárásai között is szerepel.

[szerkesztés] Hivatkozások

1. ^ Welch, T. A. (June 1984). A technique for high-performance data compression." Computer. Vol. 17, pp. 8-19.