T
he first
href="module.php?name=Lexikon&file=search&eid=1&query=algorithm">algorithm to use t
he
href="module.php?name=Lexikon&file=search&eid=1&query=Lempel-Ziv">Lempel-Ziv {substitutional compression} sc
hemes, proposed in 1977. LZ77 compression keeps track of t
he last n bytes of data seen, and w
hen a p
hrase is encountered t
hat
has already been seen, it outputs a pair of values corresponding to t
he position of t
he p
hrase in t
he previously-seen buffer of data, and t
he lengt
h of t
he p
hrase. In effect t
he compressor moves a fixed-size "window" over t
he data (generally referred to as a "sliding window"), wit
h t
he position part of t
he (position, lengt
h) pair referring to t
he position of t
he p
hrase wit
hin t
he window. T
he most commonly used
href="module.php?name=Lexikon&file=search&eid=1&query=algorithm">algorithms are derived from t
he
href="module.php?name=Lexikon&file=search&eid=1&query=LZSS">LZSS sc
heme described by James Storer and T
homas Szymanski in 1982. In t
his t
he compressor maintains a window of size N bytes and a "looka
head buffer", t
he contents of w
hic
h it tries to find a matc
h for in t
he window: w
hile (lookA
headBuffer not empty) { get a pointer (position, matc
h) to t
he longest matc
h in t
he window for t
he looka
head buffer if (lengt
h > MINIMUM_MATC
h_LENGT
h) { output a (position, lengt
h) pair s
hift t
he window lengt
h c
haracters along } else { output t
he first c
haracter in t
he looka
head buffer s
hift t
he window 1 c
haracter along } } Decompression is simple and fast: w
henever a (POSITION, LENGT
h) pair is encountered, go to t
hat POSITION in t
he window and copy LENGT
h bytes to t
he output. Sliding-window-based sc
hemes can be simplified by numbering t
he input text c
haracters mod N, in effect creating a circular buffer. T
he sliding window approac
h automatically creates t
he
href="module.php?name=Lexikon&file=search&eid=1&query=LRU">LRU effect w
hic
h must be done explicitly in
href="module.php?name=Lexikon&file=search&eid=1&query=LZ78">LZ78 sc
hemes. Variants of t
his met
hod apply additional compression to t
he output of t
he LZSS compressor, w
hic
h include a simple variable-lengt
h code (
href="module.php?name=Lexikon&file=search&eid=1&query=LZB">LZB), dynamic
href="module.php?name=Lexikon&file=search&eid=1&query=huffman">huffman coding (
href="module.php?name=Lexikon&file=search&eid=1&query=LZh">LZh), and
href="module.php?name=Lexikon&file=search&eid=1&query=Shannon-Fano">Shannon-Fano coding (
href="module.php?name=Lexikon&file=search&eid=1&query=ZIP">ZIP 1.x), all of w
hic
h result in a certain degree of improvement over t
he basic sc
heme, especially w
hen t
he data are rat
her random and t
he LZSS compressor
has little effect. An algorit
hm was developed w
hic
h combines t
he ideas be
hind LZ77 and LZ78 to produce a
hybrid called
href="module.php?name=Lexikon&file=search&eid=1&query=LZFG">LZFG. LZFG uses t
he standard sliding window, but stores t
he data in a modified
href="module.php?name=Lexikon&file=search&eid=1&query=trie">trie data structure and produces as output t
he position of t
he text in t
he trie. Since LZFG only inserts complete *p
hrases* into t
he dictionary, it s
hould run faster t
han ot
her LZ77-based compressors. All popular arc
hivers (
href="module.php?name=Lexikon&file=search&eid=1&query=arj">arj,
href="module.php?name=Lexikon&file=search&eid=1&query=lha">lha,
href="module.php?name=Lexikon&file=search&eid=1&query=zip">zip,
href="module.php?name=Lexikon&file=search&eid=1&query=zoo">zoo) are variations on LZ77. [comp.compression
href="module.php?name=Lexikon&file=search&eid=1&query=FAQ">FAQ]. (1995-04-07)
In addition suitable contents:
[ href="module.php?name=Lexikon&op=content&tid=31">2 ] [ href="module.php?name=Lexikon&op=content&tid=134">= ] [ href="module.php?name=Lexikon&op=content&tid=262">ad ] [ href="module.php?name=Lexikon&op=content&tid=411">ai ] [ href="module.php?name=Lexikon&op=content&tid=433">al ] [ href="module.php?name=Lexikon&op=content&tid=492">algorithm ] [ href="module.php?name=Lexikon&op=content&tid=544">am ] [ href="module.php?name=Lexikon&op=content&tid=592">an ] [ href="module.php?name=Lexikon&op=content&tid=683">app ] [ href="module.php?name=Lexikon&op=content&tid=740">ar ] [ href="module.php?name=Lexikon&op=content&tid=743">arc ] [ href="module.php?name=Lexikon&op=content&tid=750">archive ] [ href="module.php?name=Lexikon&op=content&tid=767">arj ] [ href="module.php?name=Lexikon&op=content&tid=800">as ] [ href="module.php?name=Lexikon&op=content&tid=893">AT ] [ href="module.php?name=Lexikon&op=content&tid=894">at ] [ href="module.php?name=Lexikon&op=content&tid=935">au ] [ href="module.php?name=Lexikon&op=content&tid=1025">B ] [ href="module.php?name=Lexikon&op=content&tid=1026">b ] [ href="module.php?name=Lexikon&op=content&tid=1034">ba ] [ href="module.php?name=Lexikon&op=content&tid=1120">base ] [ href="module.php?name=Lexikon&op=content&tid=1181">be ] [ href="module.php?name=Lexikon&op=content&tid=1269">bi ] [ href="module.php?name=Lexikon&op=content&tid=1535">br ] [ href="module.php?name=Lexikon&op=content&tid=1606">bs ] [ href="module.php?name=Lexikon&op=content&tid=1640">buffer ] [ href="module.php?name=Lexikon&op=content&tid=1695">by ] [ href="module.php?name=Lexikon&op=content&tid=1699">byte ] [ href="module.php?name=Lexikon&op=content&tid=1708">C ] [ href="module.php?name=Lexikon&op=content&tid=1724">ca ] [ href="module.php?name=Lexikon&op=content&tid=2001">ch ] [ href="module.php?name=Lexikon&op=content&tid=2018">char ] [ href="module.php?name=Lexikon&op=content&tid=2019">character ] [ href="module.php?name=Lexikon&op=content&tid=2099">ci ] [ href="module.php?name=Lexikon&op=content&tid=2125">circular buffer ] [ href="module.php?name=Lexikon&op=content&tid=2136">ck ] [ href="module.php?name=Lexikon&op=content&tid=2138">cl ] [ href="module.php?name=Lexikon&op=content&tid=2247">co ] [ href="module.php?name=Lexikon&op=content&tid=2273">code ] [ href="module.php?name=Lexikon&op=content&tid=2330">com ] [ href="module.php?name=Lexikon&op=content&tid=2441">complete ] [ href="module.php?name=Lexikon&op=content&tid=2471">compress ] [ href="module.php?name=Lexikon&op=content&tid=2474">compression ] [ href="module.php?name=Lexikon&op=content&tid=2545">con ] [ href="module.php?name=Lexikon&op=content&tid=2791">cr ] [ href="module.php?name=Lexikon&op=content&tid=2900">cu ] [ href="module.php?name=Lexikon&op=content&tid=2976">D ] [ href="module.php?name=Lexikon&op=content&tid=3006">data ] [ href="module.php?name=Lexikon&op=content&tid=3084">data structure ] [ href="module.php?name=Lexikon&op=content&tid=3136">dd ] [ href="module.php?name=Lexikon&op=content&tid=3151">de ] [ href="module.php?name=Lexikon&op=content&tid=3240">degree ] [ href="module.php?name=Lexikon&op=content&tid=3436">ding ] [ href="module.php?name=Lexikon&op=content&tid=3565">do ] [ href="module.php?name=Lexikon&op=content&tid=3752">du ] [ href="module.php?name=Lexikon&op=content&tid=3834">E ] [ href="module.php?name=Lexikon&op=content&tid=3865">ec ] [ href="module.php?name=Lexikon&op=content&tid=3896">ed ] [ href="module.php?name=Lexikon&op=content&tid=3929">ee ] [ href="module.php?name=Lexikon&op=content&tid=3946">eg ] [ href="module.php?name=Lexikon&op=content&tid=3953">eh ] [ href="module.php?name=Lexikon&op=content&tid=4148">er ] [ href="module.php?name=Lexikon&op=content&tid=4150">era ] [ href="module.php?name=Lexikon&op=content&tid=4171">es ] [ href="module.php?name=Lexikon&op=content&tid=4199">et ] [ href="module.php?name=Lexikon&op=content&tid=4396">FAQ ] [ href="module.php?name=Lexikon&op=content&tid=4404">fas ] [ href="module.php?name=Lexikon&op=content&tid=4497">fi ] [ href="module.php?name=Lexikon&op=content&tid=4520">file ] [ href="module.php?name=Lexikon&op=content&tid=4595">fix ] [ href="module.php?name=Lexikon&op=content&tid=4691">fm ] [ href="module.php?name=Lexikon&op=content&tid=4700">fo ] [ href="module.php?name=Lexikon&op=content&tid=4727">for ] [ href="module.php?name=Lexikon&op=content&tid=4828">fr ] [ href="module.php?name=Lexikon&op=content&tid=4983">G ] [ href="module.php?name=Lexikon&op=content&tid=5057">ge ] [ href="module.php?name=Lexikon&op=content&tid=5070">gen ] [ href="module.php?name=Lexikon&op=content&tid=5291">gr ] [ href="module.php?name=Lexikon&op=content&tid=5398">gt ] [ href="module.php?name=Lexikon&op=content&tid=5434">h ] [ href="module.php?name=Lexikon&op=content&tid=5540">hat ] [ href="module.php?name=Lexikon&op=content&tid=5675">hm ] [ href="module.php?name=Lexikon&op=content&tid=5768">hr ] [ href="module.php?name=Lexikon&op=content&tid=5931">id ] [ href="module.php?name=Lexikon&op=content&tid=5956">ie ] [ href="module.php?name=Lexikon&op=content&tid=6013">il ] [ href="module.php?name=Lexikon&op=content&tid=6064">in ] [ href="module.php?name=Lexikon&op=content&tid=6068">inc ] [ href="module.php?name=Lexikon&op=content&tid=6070">include ] [ href="module.php?name=Lexikon&op=content&tid=6165">input ] [ href="module.php?name=Lexikon&op=content&tid=6194">int ] [ href="module.php?name=Lexikon&op=content&tid=6412">IO ] [ href="module.php?name=Lexikon&op=content&tid=6413">io ] [ href="module.php?name=Lexikon&op=content&tid=6423">IP ] [ href="module.php?name=Lexikon&op=content&tid=6449">ir ] [ href="module.php?name=Lexikon&op=content&tid=6482">is ] [ href="module.php?name=Lexikon&op=content&tid=6557">IT ] [ href="module.php?name=Lexikon&op=content&tid=6558">it ] [ href="module.php?name=Lexikon&op=content&tid=6589">J ] [ href="module.php?name=Lexikon&op=content&tid=6789">ke ] [ href="module.php?name=Lexikon&op=content&tid=6822">ki ] [ href="module.php?name=Lexikon&op=content&tid=6918">la ] [ href="module.php?name=Lexikon&op=content&tid=7023">ld ] [ href="module.php?name=Lexikon&op=content&tid=7091">Lex ] [ href="module.php?name=Lexikon&op=content&tid=7104">lha ] [ href="module.php?name=Lexikon&op=content&tid=7107">li ] [ href="module.php?name=Lexikon&op=content&tid=7395">lr ] [ href="module.php?name=Lexikon&op=content&tid=7398">LRU ] [ href="module.php?name=Lexikon&op=content&tid=7399">ls ] [ href="module.php?name=Lexikon&op=content&tid=7410">lt ] [ href="module.php?name=Lexikon&op=content&tid=7415">lu ] [ href="module.php?name=Lexikon&op=content&tid=7441">ly ] [ href="module.php?name=Lexikon&op=content&tid=7457">M ] [ href="module.php?name=Lexikon&op=content&tid=7463">ma ] [ href="module.php?name=Lexikon&op=content&tid=7582">man ] [ href="module.php?name=Lexikon&op=content&tid=7817">method ] [ href="module.php?name=Lexikon&op=content&tid=8019">mm ] [ href="module.php?name=Lexikon&op=content&tid=8032">mo ] [ href="module.php?name=Lexikon&op=content&tid=8040">mod ] [ href="module.php?name=Lexikon&op=content&tid=8079">module ] [ href="module.php?name=Lexikon&op=content&tid=8167">mp ] [ href="module.php?name=Lexikon&op=content&tid=8258">mu ] [ href="module.php?name=Lexikon&op=content&tid=8384">N ] [ href="module.php?name=Lexikon&op=content&tid=8386">na ] [ href="module.php?name=Lexikon&op=content&tid=8460">nc ] [ href="module.php?name=Lexikon&op=content&tid=8472">ne ] [ href="module.php?name=Lexikon&op=content&tid=8627">ng ] [ href="module.php?name=Lexikon&op=content&tid=8660">nl ] [ href="module.php?name=Lexikon&op=content&tid=8672">nn ] [ href="module.php?name=Lexikon&op=content&tid=8675">no ] [ href="module.php?name=Lexikon&op=content&tid=8745">np ] [ href="module.php?name=Lexikon&op=content&tid=8760">ns ] [ href="module.php?name=Lexikon&op=content&tid=8787">nu ] [ href="module.php?name=Lexikon&op=content&tid=8820">O ] [ href="module.php?name=Lexikon&op=content&tid=8964">om ] [ href="module.php?name=Lexikon&op=content&tid=9014">op ] [ href="module.php?name=Lexikon&op=content&tid=9132">OS ] [ href="module.php?name=Lexikon&op=content&tid=9145">OSI ] [ href="module.php?name=Lexikon&op=content&tid=9176">output ] [ href="module.php?name=Lexikon&op=content&tid=9204">pa ] [ href="module.php?name=Lexikon&op=content&tid=9457">pe ] [ href="module.php?name=Lexikon&op=content&tid=9550">ph ] [ href="module.php?name=Lexikon&op=content&tid=9651">pl ] [ href="module.php?name=Lexikon&op=content&tid=9738">ply ] [ href="module.php?name=Lexikon&op=content&tid=9762">point ] [ href="module.php?name=Lexikon&op=content&tid=9766">pointer ] [ href="module.php?name=Lexikon&op=content&tid=9801">pop ] [ href="module.php?name=Lexikon&op=content&tid=9845">POS ] [ href="module.php?name=Lexikon&op=content&tid=9908">pr ] [ href="module.php?name=Lexikon&op=content&tid=10144">pt ] [ href="module.php?name=Lexikon&op=content&tid=10194">py ] [ href="module.php?name=Lexikon&op=content&tid=10198">Q ] [ href="module.php?name=Lexikon&op=content&tid=10253">query ] [ href="module.php?name=Lexikon&op=content&tid=10313">random ] [ href="module.php?name=Lexikon&op=content&tid=10364">rc ] [ href="module.php?name=Lexikon&op=content&tid=10385">re ] [ href="module.php?name=Lexikon&op=content&tid=10767">ro ] [ href="module.php?name=Lexikon&op=content&tid=10768">roach ] [ href="module.php?name=Lexikon&op=content&tid=10887">ru ] [ href="module.php?name=Lexikon&op=content&tid=10892">run ] [ href="module.php?name=Lexikon&op=content&tid=10918">S ] [ href="module.php?name=Lexikon&op=content&tid=11010">sc ] [ href="module.php?name=Lexikon&op=content&tid=11150">se ] [ href="module.php?name=Lexikon&op=content&tid=11314">sh ] [ href="module.php?name=Lexikon&op=content&tid=11375">SI ] [ href="module.php?name=Lexikon&op=content&tid=11376">si ] [ href="module.php?name=Lexikon&op=content&tid=11506">sit ] [ href="module.php?name=Lexikon&op=content&tid=11510">sk ] [ href="module.php?name=Lexikon&op=content&tid=11525">sl ] [ href="module.php?name=Lexikon&op=content&tid=11651">so ] [ href="module.php?name=Lexikon&op=content&tid=11790">spec ] [ href="module.php?name=Lexikon&op=content&tid=11934">st ] [ href="module.php?name=Lexikon&op=content&tid=11956">standard ] [ href="module.php?name=Lexikon&op=content&tid=12068">store ] [ href="module.php?name=Lexikon&op=content&tid=12109">struct ] [ href="module.php?name=Lexikon&op=content&tid=12133">su ] [ href="module.php?name=Lexikon&op=content&tid=12359">T ] [ href="module.php?name=Lexikon&op=content&tid=12440">tc ] [ href="module.php?name=Lexikon&op=content&tid=12567">text ] [ href="module.php?name=Lexikon&op=content&tid=12588">th ] [ href="module.php?name=Lexikon&op=content&tid=12627">Thomas ] [ href="module.php?name=Lexikon&op=content&tid=12721">to ] [ href="module.php?name=Lexikon&op=content&tid=12777">tp ] [ href="module.php?name=Lexikon&op=content&tid=12787">tr ] [ href="module.php?name=Lexikon&op=content&tid=12791">track ] [ href="module.php?name=Lexikon&op=content&tid=12896">tt ] [ href="module.php?name=Lexikon&op=content&tid=13030">um ] [ href="module.php?name=Lexikon&op=content&tid=13175">us ] [ href="module.php?name=Lexikon&op=content&tid=13229">V ] [ href="module.php?name=Lexikon&op=content&tid=13252">va ] [ href="module.php?name=Lexikon&op=content&tid=13260">value ] [ href="module.php?name=Lexikon&op=content&tid=13274">var ] [ href="module.php?name=Lexikon&op=content&tid=13275">variable ] [ href="module.php?name=Lexikon&op=content&tid=13310">ve ] [ href="module.php?name=Lexikon&op=content&tid=13366">vi ] [ href="module.php?name=Lexikon&op=content&tid=13694">while ] [ href="module.php?name=Lexikon&op=content&tid=13725">win ] [ href="module.php?name=Lexikon&op=content&tid=14075">yt ] [ href="module.php?name=Lexikon&op=content&tid=14079">Z ] [ href="module.php?name=Lexikon&op=content&tid=14125">zip ] [ href="module.php?name=Lexikon&op=content&tid=14138">zoo ]