LZW
Z Wikipedii
Lempel-Ziv-Welch (skracane zwykle do LZW) to metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.
Algorytm bardzo prosty, ale dający dobre rezultaty. Wykorzystywany jest m.in. w formacie zapisu grafiki GIF oraz w modemach (V.32bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia prac nad nowym algorytmem zapisu grafiki o nazwie PNG.
Schemat kompresji:
- Wypełnij słownik alfabetem źródła informacji.
- Dopóki są dane na wejściu
- Wczytaj znak
- Jeżeli wczytany znak w połączeniu z wcześniej wczytanym ciągiem nie znajduje się w słowniku, wypisz kod poprzedniego ciągu i wstaw nowy do słownika, w przeciwnym razie dodaj wczytany znak do ciągu.
fragment kodu w C++:
int main() { char znak; string str, tmp; int numer=1; map<string, int> slownik; zainicjujSlownik(slownik); while (cin.get(znak)) { tmp=str+znak; if (slownik.find(tmp)!=slownik.end()) str=tmp; else { wypisz(slownik[str]); slownik[tmp]=numer++; str=znak; } } wypisz(slownik[str]); }