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]]

====== LZW ======

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu
===== Az LZW kódolásról =====

Az LZ77, majd az LZ78 továbbfejlesztett verziója.
Abraham Lempel, Jacob Ziv és Terry Welch munkája. 1984-ben publikálta Terry Welch.

A Unix compress parancsa ezzel az algoritmussal tömörít, de használjuk a GIF képekben is.

Szemben az LZ78 kódolással, az LZW kódoló szótára induláskor nem üres.
Tartalmaz minden egyedi karaktert, ami a kódolandó szövegben megtalálható.
Ugyanakkor a kibontáshoz nem szükséges tárolni a szótárt, mert az újból felépíthető
a kód alapján. Az alapszótár, azonban egységes kell legyen a kibontás és tömörítés során egyaránt. 
Mivel minden karakter benne van kezdéskor a szótárban, ezért a kódolás
minden lépése egy prefix karakterrel történik. Így az első keresés után
két karakterünk van.


===== Működés =====

Induláskor, a könyvtár tartalmaz minden lehetséges karaktert, az S pedig üres.

<code>
s <- üres
ciklus amíg van adat
	ch <- adat[következő]
	ha szotar.tartalmazza(s + ch) akkor
		s <- s + ch
	ellenben
		kimenet.hozzáfűz(lekerIndex(s))
		szotar.hozzáfűz(s + ch)
		s <- ch
	ha vége
ciklus vége
kimenet.hozzáfűz(lekerIndex(s)
</code>

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

^  A kódolandó karakterfolyam  ^^^^^^^^^^
^  Pozíció  ^  1  ^  2  ^  3  ^  4  ^  5  ^  6  ^  7  ^  8  ^  9  ^
^  Karakter  |  A | B | B | A | B | A | B | A | C |


^  Kezdőszótár  ^
|  (1) A  |
|  (2) B  |
|  (3) C  |


^  A kódolás folyamat  ^^^^
^  Lépés  ^  Pozíció  ^  Szótár  ^  Kimenet  ^
|  1  |  1  | (4) A B  |  1  |
|  2  |  2  | (5) B B  |  2  |
|  3  |  3  | (6) B A  |  2  |
|  4  |  4  | (7) A B A  |  4  |
|  5  |  5  | (8) A B A C  |  7  |
|  6  |  --  |  --  |  3  |



===== Java megvalósítás =====

<code java>
static String lzwCompress(String text, ArrayList<String> dic) {
	StringBuilder output= new StringBuilder();			
	String s = "";
	for(int i= 0; i<text.length(); i++) {
		Character ch = text.charAt(i);			
		if( dic.contains(s+ch.toString())) {
			s = s + ch.toString();
		}else {
			output.append(dic.indexOf(s) + " ");
			dic.add(s + ch.toString());
			s = ch.toString();
		}
	}
	output.append(dic.indexOf(s));
	return output.toString();
}
</code>


A metódust meglehet úgy is írni, hogy egy byte összes variációja eleve szerepel a szótárban, ekkor 
nem szükséges második paraméter.