3814
edycji
LZP: Różnice pomiędzy wersjami
Przejdź do nawigacji
Przejdź do wyszukiwania
m
→Algorytm kompresji: dt.
m (→Zobacz też: lnkfix.) |
m (→Algorytm kompresji: dt.) |
||
|
Algorytm przebiega następująco:
# Inicjalizacja:
#* '''
#* '''
#* '''i''' := 0 - bieżąca pozycja
#* Wyzeruj tablicę '''L''' przechowującą ostatnie wystąpienia kontekstu
# Wypisz '''N''' pierwszych liter
# '''i''' := '''N''' - przesuń okno o '''N''' pozycji w lewo
#* Jeśli '''P''' nie istnieje (nie było jeszcze takiego kontekstu) wypisz na wyjście pierwszy niezakodowany znak i przesuń okno w lewo o jedną pozycję; '''i''' := '''i''' + 1.
#* Jeśli '''P''' istnieje znajdź najdłuższy podciąg, tzn. '''s'''['''P''', '''P''' + '''k'''] = '''s'''['''i''', '''i''' + '''k'''], gdzie '''k''' to długość dopasowania:
#*
#*
===Przykładowy krok kompresji - przypadek znalezienie prefiksu===
| |||