Duomenų suspaudimas leidžia taupyti vietą, bei laiką persiunčiant duomenis. Spartėjant internetui, bei pingant vietai diske vis rečiau tenka susidurti su *.rar ir *zip, bet reikia nepamiršti, jog duomenų suspaudimas egzistuoja ir nuotraukų, video, garso įrašų failuose.
Deflate yra duomenų suspaudimo algoritmas naudojamas gzip, png, zip failų formatuose. Duomenys jame suspaudžiami naudojant Huffman kodą, bei žodyną.
Huffman kodas
Kodo esmė, jog kuo dažniau pasikartojantys simboliai koduojami trumpesniu kodu. Pavyzdys iš Huffman kodo generatoriaus:
Kaip matote, dažniausiai pasikartojantys simboliai N ir A yra koduojami 2 bitais, o rečiausiai sutinkami 5 bitais. Koduojant įprastu būdu visi simboliai turėtų 4 bitų kodą, tad užkoduoti frazę pakaktų 4 *25 = 100 bitų. Huffman kodo atveju – 2*9 + 3*4 + 4 *6 + 5*6 = 84 bitai.
Kaip parenkamas kodas simboliams galite pasiskaityti plačiau, naudojant medį ne tik dažniems simboliams parenkamas trumpesnis kodas, bet ir pats simbolio kodas yra ypatingas, nes nei vienas kodas nesutampa su kito kodo pradžia.
Žodynas
Deflate naudoja LZ77 žodyno algoritmą dar vadinama slankiojančiu langu. Algoritmo esmė, jog duomenų eilutės pakeičiamos nuorodomis į žodyną.
Langą sudaro du laukeliai, kairėje esantis paieškos buferis(search buffer), kuriame saugomi rasti pasikartojantys simbolių deriniai ir dešinėje esantis peržiūros buferis(look-ahead buffer). Langui slenkant iš kairės į dešinę peržiūros buferyje juda nesuspausti duomenys.
Suspaudimas vyksta ieškant ilgiausios sutampančios sekos tarp paieškos ir peržiūros buferio, tokią radus išvedamas atstumas iki sekos pradžios paieškos buferyje, sekos ilgis, bei sekantis(nežinomas) simbolis peržiūros buferyje(pvz.: 7,4,d). Tas simbolis taip pat perkeliamas į paieškos buferį. Langas persislenka ik dar nesuspaustų duomenų ir viskas kartojama per naują.
Pažangesnis LZSS algoritmas kilęs iš LZ77 skiriasi nuo pastarojo tuo, jog duomenų eilutė nėra keičiama nuorodomis, jei nuorodos užima daugiau vietos. Taip nutiko su pavyzdyje aukščiau adr nuorodomis.
