LZ77LZ78dekodning

LZ77LZ78dekodning refererar till avkodning av två nära relaterade förlustfria kompressionssystem: LZ77 och LZ78. Båda metoderna bygger på att använda tidigare data för att beskriva komprimerad information, men de gör det på olika sätt. Dekodningen måste kunna återuppbygga exakt samma ursprungstext som originalet från det mottagna komprimerade flödet.

LZ77-avkodning används tillsammans med en flyttbar fönsterstruktur och ofta en look-ahead-buffer. Den komprimerade strömmen består vanligtvis av tripletter (offset, längd, nästa symbol) eller liknande representationer. Vid avkodning läses varje triplet: kopiera längden tecken från positionen som ligger offset tecken bakom den aktuella slutpositionen i den redan avkodade strängen, och avsluta med nästa symbol. Om längden är noll kopieras inga tecken från fönstret utan nästa symbol läggs till direkt. När tecken avkodas uppdateras fönstret kontinuerligt med de nya tecknen. Överlappning används naturligt i processen, vilket kräver tecken-för-tecken-kopiering tills längden är uppnådd.

LZ78-avkodning bygger istället en ordlista (frasier). Den avkodade strömmen består av par (index, symbol), där index refererar till en tidigare fras i ordlistan. Vid varje kodsteg hämtas frasen som motsvarar dictionary[index], man lägger till symbolen för att bilda en ny fras, skriver ut den nya frasen och lägger till den i ordlistan. Många varianter har ett startvärde där index kan vara 0 (tom fras). Denna process gör att varje ny fras byggs av en befintlig fras plus ett nytt tecken. Skillnaderna mellan LZ77 och LZ78 ligger i hur historiken används: fönsterbaserad rekonstruk respektive byggandet av en växande ordlista.

Båda metoderna är grunden för senare varianter som LZW och påverkar moderna komprimeringar där avkodningens korrekthet är beroende av exakt överensstämt kodningsschema.