Vstup:: Sekvencia symbolov Výstup:: Kratšia sekvencia symbolov, ktorá vyjadruje pôvodnú sekvenciu
[https://www.asciiart.eu/animals/aardvarks](Art by Horroroso)
_,,......_
,-' `'--.
,-' _ '-.
(`. ,' , `-. `.
\ \ - / ) \ \
`\`-^^^, )/ | / :
)^ ^ ^V/ / '.
| ) | `.
9 9 /,--,\ |._:` .._`.
| / / `. \ `. ( `.`.
| / \ \ \ \ `--\ ) `.`.___
-hrr- .;;./ ' ) ' ) ///' `-"'
`--' 7//\ ///\
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
12W1B12W3B24W1B14W
http://www.stringology.org/DataCompression/lz77/index_en.html
Podľa wiki:
Prebieha v plávajúcom okne, ktoré je rozdelené na minulosť a budúcnosť.
begin
naplň nezakódovanou část okna ze vstupu
while (nezakódovaná část není prázdná) do
begin
najdi v okně předponu p nezakódované části začínající v zakódované části
i := pozice předpony p v okně
j := délka předpony p
X := první znak za p v nezakódované části
output(i,j,X)
přidej do okna zprava i+1 znaků
end
end
Prebieha v plávajúcom okne.
Kombinácia LZ 77 a Huffman Encoding.
http://www.stringology.org/DataCompression/lz78/index_en.html
Jeho upravená verzia sa nazýva Lempel-Ziv-Welch
[quote,Wikipedia]
V každom kroku sa vstupné bajty zhromaždia do postupnosti, pokiaľ nasledujúci znak nevytvorí postupnosť ktorá sa nenachádza v slovníku. Kód postupnosti bez nového znaku sa pridá do výstupu a postupnosť spolu s novým znakom sa pridá do slovníka.
číslo záznamu v slovníku + symbol
begin
inicializace slovníku
buffer := ""
while (!konecVstupu()) do
begin
symbol := další nezpracovaný znak ze vstupu
if ( ( buffer.symbol ) je ve slovníku ) then
buffer := buffer.symbol;
else
begin
output(indexDoSlovníku(buffer),symbol)
přidej do slovníku ( buffer.symbol )
buffer := ""
end
end
if ( !prázdný(buffer) ) then
output(indexDoSlovníku(buffer));
end
Podľa blogu: