BBS 1/BBS#1.iso/document/compress.arj/DIPLOMA.TXT

Text File | 1992-05-29 | 33.2 KB | 752 lines

.hm2  .dh1 .ce Input/Output with Embedded Data Compression
.fm64 .df1 .ce -- Page .pa --
.ls1
.pl66
.rm72 .lm0
.tm5  .bm60
.ff1
.tc 72 1 0 0  0 1 4 1 3 1 3 1 3 1
.sh .sf


.ce 伿Γα¿⌐ æ. è«σ¼á¡ε¬


.ce ÉÑ὿ºáµ¿∩ óó«ñá-óδó«ñá ß« ߪáΓ¿Ñ¼ ñá¡¡δσ


.ce Input/Output with Embedded Data Compression



.ce è¿Ñó -- 1992





.ce Abstract


    The data compression techniques became very popular during the
last years. However, most compressors are implemented as standalone
applications which are hard to integrate into programs. This paper
describes input/output library with builtin compression, suitable for
embedding into applications. A quick survey of compression algorithms
is also provided.



.ce Ç¡¡«Γᵿ∩


    é »«ß½Ññ¡ÑÑ óαѼ∩ ¼ÑΓ«ñδ ߪáΓ¿∩ ñá¡¡δσ »«½πτ¿½¿ Φ¿α«¬«Ñ
αáß»α«ßΓαá¡Ñ¡¿Ñ. ÆѼ ¡Ñ ¼Ñ¡ÑÑ, í«½∞Φ¿¡ßΓó« »α«úαá¼¼ ߪáΓ¿∩ αÑ὿º«óá¡δ
ó ó¿ñÑ «Γñѽ∞¡δσ »α¿½«ªÑ¡¿⌐, τΓ« ºáΓαπñ¡∩ÑΓ ¿σ ¿¡ΓÑúαᵿε ó »α«úαá¼¼δ
»«½∞º«óáΓѽ∩. é αáí«ΓÑ «»¿ßδóáÑΓß∩ í¿í½¿«ΓѬá óó«ñá-óδó«ñá ß óßΓα«Ñ¡¡δ¼
ߪáΓ¿Ñ¼ ñá¡¡δσ, πñ«í¡πε ñ½∩ óßΓαá¿óá¡¿∩ ó »α¿¬½áñ¡δÑ »α«úαá¼¼δ. æñѽá¡
Γá¬ªÑ ¬αáΓ¬¿⌐ «íº«α á½ú«α¿Γ¼«ó ߪáΓ¿∩.



.te 1 .ce Äíº«α ¼ÑΓ«ñ«ó ߪáΓ¿∩ ñá¡¡δσ


    îÑΓ«ñδ ߪáΓ¿∩ ñá¡¡δσ ¿¼ÑεΓ ñ«ßΓáΓ«τ¡« ñ½¿¡¡πε ¿ßΓ«α¿ε.
Å«»δΓáѼß∩ ñáΓ∞ ¬αáΓ¬¿⌐ «íº«α «ß¡«ó¡δσ ¿ñÑ⌐ ¿ αÑ὿ºáµ¿⌐, ¡Ñ
»αÑΓÑ¡ñπεΘ¿⌐, «ñ¡á¬«, ¡á »«½¡«Γπ. ü«½ÑÑ »«ñα«í¡δÑ ßóÑñÑ¡¿∩ ¼«ª¡« ¡á⌐Γ¿,
¡á»α¿¼Ñα, ó [èα¿τÑó߬¿⌐], [Witten].

    æπΘÑßΓóπÑΓ α∩ñ "¡á¿ó¡δσ" »«ñσ«ñ«ó ¬ ñá¡¡«⌐ »α«í½Ñ¼Ñ.  ìá¿í«½ÑÑ
¿ºóÑßΓ¡δ⌐ -- φΓ« ¬«ñ¿α«óá¡¿Ñ ñ½¿¡ ßÑα¿⌐ (run length encoding, RLE).
æπΓ∞ ¼ÑΓ«ñá: ºá¼Ñ¡á µÑ»«τѬ »«óΓ«α∩εΘ¿σß∩ ß¿¼ó«½«ó ¡á «ñ¿¡ φΓ«Γ ß¿¼ó«½
¿ ßτÑΓτ¿¬ »«óΓ«αÑ¡¿∩. Åα«í½Ñ¼á ß«ßΓ«¿Γ ó Γ«¼, τΓ«íδ αá߻ᬫóΘ¿¬ ¼«ú
«Γ½¿τ¿Γ∞ ó αѺπ½∞Γ¿απεΘѼ »«Γ«¬Ñ Γá¬πε ¬«ñ¿α«óá¡¡πε ßÑα¿ε «Γ ñαπú¿σ
ß¿¼ó«½«ó. ÉÑΦÑ¡¿Ñ «τÑó¿ñ¡« -- ß¡áíªáΓ∞ óßÑ Γá¬¿Ñ µÑ»«τ¬¿ ¡Ñ¬«Γ«α묨
ºáú«½«ó¬á¼¿ (¡á»α¿¼Ñα, ¿ß»«½∞º«óáΓ∞ »Ñαóδ⌐ í¿Γ ¬á¬ »α¿º¡á¬ ¬«ñ¿α«óá¡¡«⌐
ßÑα¿¿). îÑΓ«ñ ñ«ßΓáΓ«τ¡« φΣΣÑ¬Γ¿óÑ¡ ñ½∩ úαáΣ¿τÑ߬¿σ ¿º«íαáªÑ¡¿⌐ ó
Σ«α¼áΓÑ "íá⌐Γ ¡á »¿¬ßѽ" (¡á»α¿¼Ñα, Σ«α¼áΓ PCX ¿ß»«½∞ºπÑΓ ¬«ñ¿α«óá¡¿Ñ
RLE).

    ìÑñ«ßΓáΓ¬¿ ¼ÑΓ«ñá RLE «τÑó¿ñ¡δ -- ¡¿º¬á∩ ßΓѻѡ∞ ߪáΓ¿∩
(¡á»α¿¼Ñα, ó ΓѬßΓÑ ñá¡¡«⌐ ßΓáΓ∞¿ «¡ ß¼«ªÑΓ π»á¬«óáΓ∞ Γ«½∞¬« µÑ»«τ¬¿
»α«íѽ«ó ó ¡áτá½Ñ ßΓ᫬).

    æñѽáѼ ºñÑß∞ ¡Ñí«½∞Φ«Ñ «ΓßΓπ»½Ñ¡¿Ñ ñ½∩ πΓ«τ¡Ñ¡¿∩ ΓÑନ¡«½«ú¿¿.
é ñá½∞¡Ñ⌐ΦѼ ¼δ íπñѼ αáßß¼áΓα¿óáΓ∞ π»á¬«óΘ¿¬ (compressor) ¬á¬
»α«úαá¼¼π, »αÑ«íαáºπεΘπε ¡Ñ¬«Γ«αδ⌐ ñó«¿τ¡δ⌐ »«Γ«¬ ñá¡¡δσ (»«ñ«í¡δ⌐
Σá⌐½π ó ß¿ßΓÑ¼Ñ UNIX) ó ñαπú«⌐, ªÑ½áΓѽ∞¡« ¼Ñ¡∞ΦÑú« αẼÑαá.
æ««ΓóÑΓßΓóÑ¡¡«, αá߻ᬫóΘ¿¬ (uncompressor) -- »α«úαá¼¼á, «ßπΘÑßΓó½∩εΘá∩
«íαáΓ¡«Ñ »αÑ«íαẫóá¡¿Ñ, »α¿τѼ «ñ¡«º¡áτ¡«. Æᬿ¼ «íαẫ¼, ¼δ ¿ß¬½ετáѼ
¿º αáßß¼«ΓαÑ¡¿∩ ¼ÑΓ«ñδ ߪáΓ¿∩, ΓÑα∩εΘ¿Ñ ¿¡Σ«α¼áµ¿ε (¡á»α¿¼Ñα, ¼ÑΓ«ñ
ߪáΓ¿∩ ¿º«íαáªÑ¡¿⌐ JPEG, «ß¡«óá¡¡δ⌐ ¡á »αÑ«íαẫóá¡¿∩σ µóÑΓ«ó,
»αá¬Γ¿τÑ߬¿ ¡Ñ αẽ¿τáѼδσ τѽ«óÑτÑ߬¿¼ ú½áº«¼).

    Å«ñ ßΓ«¿¼«ßΓ∞ε ¬«ñ¿α«óá¡¿∩ »«¡¿¼áÑΓß∩ ßαÑñ¡∩∩ ñ½¿¡á ¬«ñ«ó«ú«
ß½«óá (ó í¿Γáσ). êºíδΓ«τ¡«ßΓ∞ ¬«ñ¿α«óá¡¿∩ αáó¡á αạ«ßΓ¿ ¼Ñªñπ
ßΓ«¿¼«ßΓ∞ε ¿ φ¡Γα«»¿Ñ⌐ ¬«ñ¿α«óá¡¿∩. ÄτÑó¿ñ¡«, τΓ« σ«α«Φ¿⌐ á½ú«α¿Γ¼
ߪáΓ¿∩ ñ«½ªÑ¡ ¼¿¡¿¼¿º¿α«óáΓ∞ ¿ºíδΓ«τ¡«ßΓ∞.  öπ¡ñá¼Ñ¡Γá½∞¡á∩ ΓÑ«αѼá
ÿÑ¡¡«¡á « ¬«ñ¿α«óá¡¿¿ ¿ßΓ«τ¡¿¬«ó ú«ó«α¿Γ « Γ«¼, τΓ« ßΓ«¿¼«ßΓ∞
¬«ñ¿α«óá¡¿∩ óßÑúñá ¡Ñ ¼Ñ¡∞ΦÑ φ¡Γα«»¿¿ ¿ßΓ«τ¡¿¬á, σ«Γ∩ ¼«ªÑΓ íδΓ∞ ߬«½∞
πú«ñ¡« í½¿º¬á ¬ ¡Ñ⌐ [ÿÑ¡¡«¡].

    äá½∞¡Ñ⌐ΦÑÑ «íßπªñÑ¡¿Ñ φΓ«ú« ¿ ßó∩ºá¡¡δσ ß ¡¿¼ ó«»α«ß«ó ß¼.
[èα¿τÑó߬¿⌐], ßΓα.15-54.

    äá½ÑÑ, »α«µÑßß ßªáΓ¿∩ ñá¡¡δσ αáºí¿óáÑΓß∩ ¡á ñóá -- Γ.¡.
¼«ñѽ¿α«óá¡¿Ñ ¿ ¬«ñ¿α«óá¡¿Ñ (ß¼., ¡á»α¿¼Ñα, [Rissanen]). ¥Γ¿ »α«µÑßßδ
(¿ á½ú«α¿Γ¼δ, ¿σ αÑ὿ºπεΘ¿Ñ) ¼«ª¡« αáßß¼áΓα¿óáΓ∞ ¡Ñºáó¿ß¿¼«.

        é¡áτá½Ñ »«ú«ó«α¿¼ « ΓÑσ¡«½«ú¿∩σ ¬«ñ¿α«óá¡¿∩.



.te 1 .ce îÑΓ«ñδ ¬«ñ¿α«óá¡¿∩


    è«ñ¿α«óá¡¿Ñ (encoding) ¿¼ÑÑΓ ñѽ« ß »«Γ«¬«¼ ß¿¼ó«½«ó ó
¡Ñ¬«Γ«α«¼ á½Σáó¿ΓÑ, »α¿τѼ τáßΓ«Γδ ß¿¼ó«½«ó αẽ¿τ¡δ. ûѽ∞ε ¬«ñ¿α«óá¡¿∩
∩ó½∩ÑΓß∩ »αÑ«íαẫóá¡¿Ñ φΓ«ú« »«Γ«¬á ó »«Γ«¬ í¿Γ ¼¿¡¿¼á½∞¡«⌐ ñ½¿¡δ. ¥Γ«
ñ«ßΓ¿úáÑΓß∩ π¼Ñ¡∞ΦÑ¡¿Ñ¼ φ¡Γα«»¿¿ »«Γ«¬á »πΓѼ πτÑΓá τáßΓ«Γδ ß¿¼ó«½«ó:
ñ½¿¡á ¬«ñá ñ«½ª¡á íδΓ∞ »α«»«αµ¿«¡á½∞¡á ¿¡Σ«α¼áµ¿¿, ß«ñÑαªáΘÑ⌐ß∩ ó«
óσ«ñ¡«¼ »«Γ«¬Ñ. àß½¿ αáß»αÑñѽѡ¿Ñ óÑα«∩Γ¡«ßΓÑ⌐ τáßëà ¿ºóÑßΓ¡«, Γ«
¼«ª¡« »«ßΓα«¿Γ∞ «»Γ¿¼á½∞¡«Ñ ¬«ñ¿α«óá¡¿Ñ.  çáñáτá πß½«ª¡∩ÑΓß∩ ó ß½πτáÑ,
Ñß½¿ αáß»αÑñѽѡ¿Ñ τáßΓ«Γ ß¿¼ó«½«ó ºáαá¡ÑÑ ¡Ñ¿ºóÑßΓ¡«. é φΓ«¼ ß½πτáÑ
ßπΘÑßΓóπÑΓ ñóá αẽ¿τ¡δσ »«ñσ«ñá.

    ÅÑαóδ⌐ »«ñσ«ñ: »α«ß¼«ΓαÑΓ∞ óσ«ñ¡«⌐ »«Γ«¬ ¿ »«ßΓα«¿Γ∞
¬«ñ¿α«óá¡¿Ñ ¡á «ß¡«óá¡¿¿ ß«íαá¡¡«⌐ ßΓáΓ¿ßΓ¿¬¿ (»α¿ φΓ«¼ »«ΓαÑíπεΓß∩ ñóá
»α«σ«ñá »« Σá⌐½π, τΓ« «úαá¡¿τ¿óáÑΓ ßΣÑαπ »α¿¼Ñ¡Ñ¡¿∩ Γᬿσ á½ú«α¿Γ¼«ó).
é óδσ«ñ¡«⌐ »«Γ«¬ ó Γᬫ¼ ß½πτáÑ ñ«½ª¡á íδΓ∞ ºá»¿ßá¡á ßσѼá
¿ß»«½∞º«óá¡¡«ú« ¬«ñ¿α«óá¡¿∩, ¬«Γ«αá∩ íπñÑΓ ¿ß»«½∞º«óá¡á ºáΓѼ
ñѬ«ñÑα«¼. Åα¿¼Ñα -- ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á [Huffman].

        éΓ«α«⌐ »«ñσ«ñ ¿ß»«½∞ºπÑΓ Γᬠ¡áºδóáѼδ⌐ áñá»Γ¿ó¡δ⌐ ¬«ñÑα
(adaptive coder). êñÑ∩ ß«ßΓ«¿Γ ó Γ«¼, τΓ«íδ ¼Ñ¡∩Γ∞ ßσÑ¼π ¬«ñ¿α«óá¡¿∩ ó
ºáó¿ß¿¼«ßΓ¿ «Γ ¿ßσ«ñ¡δσ ñá¡¡δσ. Æᬫ⌐ á½ú«α¿Γ¼ «ñ¡«»α«σ«ñÑ¡ ¿ ¡Ñ
ΓαÑíπÑΓ »ÑαÑñáτ¿ ¿¡Σ«α¼áµ¿¿ «í ¿ß»«½∞º«óá¡¡«¼ ¬«ñ¿α«óá¡¿¿ ó ∩ó¡«¼ ó¿ñÑ.
é¼ÑßΓ« φΓ«ú« ñѬ«ñÑα, ßτ¿Γδóá∩ ¬«ñ¿α«óá¡¡δ⌐ »«Γ«¬, ß¿¡σα«¡¡« ß ¬«ñÑα«¼
¿º¼Ñ¡∩ÑΓ ßσÑ¼π ¬«ñ¿α«óá¡¿∩, ¡áτ¿¡á∩ ß ¡Ñ¬«Γ«α«⌐ »αÑñ«»αÑñѽѡ¡«⌐.
Çñá»Γ¿ó¡«Ñ ¬«ñ¿α«óá¡¿Ñ ¼«ªÑΓ ñáΓ∞ í«½∞Φπε ßΓѻѡ∞ ߪáΓ¿∩, »«ß¬«½∞¬π
¼«úπΓ íδΓ∞ πτΓÑ¡δ ½«¬á½∞¡δÑ ¿º¼Ñ¡Ñ¡¿∩ τáßΓ«Γ.  Åα¿¼Ñα«¼ ∩ó½∩ÑΓß∩
ñ¿¡á¼¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á (ß¼. [Gallager], [Knuth], [Vitter]).

        é ¬áτÑßΓóÑ »α¿¼Ñαá αáßß¼«Γα¿¼ ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.
¥Γ« ¬«ñ¿α«óá¡¿Ñ ß«»«ßΓáó½∩ÑΓ óσ«ñ¡δ¼ ß¿¼ó«½á¼ («íδτ¡« »αÑñßΓáó½∩Ѽδ¼
µÑ»«τ¬á¼¿ í¿Γ«ó αẽ¿τ¡«⌐ ñ½¿¡δ) µÑ»«τ¬¿ í¿Γ«ó »ÑαѼѡ¡«⌐ ñ½¿¡δ.  使¡á
¬«ñá ñ½∩ ß¿¼ó«½á »α«»«αµ¿«¡á½∞¡á ñó«¿τ¡«¼π ½«úáα¿Σ¼π Ñú« τáßΓ«Γδ,
óº∩Γ«¼π ß «íαáΓ¡δ¼ º¡á¬«¼. ¥Γ« ¬«ñ¿α«óá¡¿Ñ ∩ó½∩ÑΓß∩ »αÑΣ¿¬ß¡δ¼, τΓ«
»«ºó«½∩ÑΓ ½Ñú¬« Ñú« ñѬ«ñ¿α«óáΓ∞ (ó »αÑΣ¿¬ß¡«¼ ¬«ñ¿α«óá¡¿¿ ¬«ñ ½εí«ú«
ß¿¼ó«½á ¡Ñ ∩ó½∩ÑΓß∩ »αÑΣ¿¬ß«¼ ¬«ñá ¡¿¬á¬«ú« ñαπú«ú« ß¿¼ó«½á; »«ñα«í¡ÑÑ
ß¼. [èα¿τÑó߬¿⌐], 29-34).

        ÅπßΓ∞ óσ«ñ¡«⌐ á½Σáó¿Γ ß«ßΓ«¿Γ ¿º τÑΓδαÑσ ß¿¼ó«½«ó:  a, b, c, d,
τáßΓ«Γδ ¬«Γ«αδσ αáó¡δ ß««ΓóÑΓßΓóÑ¡¡« 1/2, 1/4, 1/8, 1/8.  è«ñ¿α«óá¡¿Ñ
òáΣΣ¼Ñ¡á ñ½∩ φΓ«ú« á½Σáó¿Γá ñáÑΓß∩ ß½ÑñπεΘÑ⌐ Γáí½¿µÑ⌐:

         ß¿¼ó«½ │ τáßΓ«Γá │    óσ«ñ¡«Ñ   │  óδσ«ñ¡«Ñ
                │         │  ¬«ñ¿α«óá¡¿Ñ │ ¬«ñ¿α«óá¡¿Ñ
        ────────┼─────────┼──────────────┼─────────────
           a    │   1/2   │   00         │   0
           b    │   1/4   │   01         │   10
           c    │   1/8   │   10         │   110
           d    │   1/8   │   11         │   111

        ìá»α¿¼Ñα, ¬«ñ«¼ µÑ»«τ¬¿ abaaacb, »αÑñßΓáó½Ñ¡¡«⌐ ¡á óσ«ñÑ ¬á¬ 00
01 00 00 00 10 01, íπñÑΓ 0 10 0 0 0 110 10 (»α«íѽδ ñ«íáó½Ñ¡δ ñ½∩
πñ«íßΓóá τΓÑ¡¿∩). 14 í¿Γ ¡á óσ«ñÑ ñ὿ 11 í¿Γ ¡á óδσ«ñÑ. è«ñ¿α«óá¡¿Ñ »«
òáΣΣ¼Ñ¡π «íδτ¡« ßΓα«¿Γß∩ ¿ σαá¡¿Γß∩ ó ó¿ñÑ ñó«¿τ¡«ú« ñÑαÑóá, ó ½¿ßΓ∞∩σ
¬«Γ«α«ú« ¡áσ«ñ∩Γß∩ ß¿¼ó«½δ, á ¡á ñπúáσ "¡á»¿ßá¡δ" µ¿Σαδ 0 ¿½¿ 1. è«ñ«¼
ß¿¼ó«½á ∩ó½∩ÑΓß∩ »πΓ∞ «Γ ¬«α¡∩ ñÑαÑóá ¬ φΓ«¼π ß¿¼ó«½π.  Åα¿
¿ß»«½∞º«óá¡¿¿ áñá»Γ¿ó¡«ú« ¬«ñ¿α«óá¡¿∩ òáΣΣ¼Ñ¡á »α«í½Ñ¼á ß«ßΓ«¿Γ ó
¡Ñ«íσ«ñ¿¼«ßΓ¿ »«ßΓ«∩¡¡«⌐ ¬«ααÑ¬Γ¿α«ó¬¿ ñÑαÑóá ó ß««ΓóÑΓßΓó¿¿ ß
¿º¼Ñ¡∩εΘÑ⌐ß∩ ßΓáΓ¿ßΓ¿¬«⌐ óσ«ñ¡«ú« »«Γ«¬á.

        ä«ßΓ«¿¡ßΓóἿ ¼ÑΓ«ñá òáΣΣ¼Ñ¡á ∩ó½∩εΓß∩ Ñú« ñ«ßΓáΓ«τ¡« óδß«¬á∩
߬«α«ßΓ∞ ¿ σ«α«ΦÑÑ ¬áτÑßΓó« ߪáΓ¿∩. ¥Γ«Γ á½ú«α¿Γ¼ ßαáó¡¿Γѽ∞¡« ñáó¡«
¿ºóÑßΓÑ¡ ¿ Φ¿α«¬« »α¿¼Ñ¡∩ÑΓß∩; »α¿¼ÑαἿ ¼«úπΓ ß½πª¿Γ∞ »α«úαá¼¼á
compress Äæ UNIX (»α«úαá¼¼¡á∩ αÑ὿ºáµ¿∩) ¿ ßΓá¡ñáαΓ ¬«ñ¿α«óá¡¿∩ ñ½∩
Σá¬ß«ó [Hunter] (á»»áαáΓ¡á∩ αÑ὿ºáµ¿∩).

    è«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á ¿¼ÑÑΓ ¼¿¡¿¼á½∞¡πε ¿ºíδΓ«τ¡«ßΓ∞ »α¿
πß½«ó¿¿, τΓ« ¬áªñδ⌐ ß¿¼ó«½ ¬«ñ¿απÑΓß∩ «Γñѽ∞¡«⌐ µÑ»«τ¬«⌐ ó á½Σáó¿ΓÑ
{0,1}).

        ìÑñ«ßΓáΓ¬«¼ ¬«ñ¿α«óá¡¿∩ òáΣΣ¼Ñ¡á ∩ó½∩ÑΓß∩ ºáó¿ß¿¼«ßΓ∞ ßΓѻѡ¿
ߪáΓ¿∩ «Γ í½¿º«ßΓ¿ óÑα«∩Γ¡«ßΓÑ⌐ ß¿¼ó«½«ó ¬ «Γα¿µáΓѽ∞¡δ¼ ßΓѻѡ∩¼ 2;
φΓ« ßó∩ºá¡« ß ΓѼ, τΓ« ¬áªñδ⌐ ß¿¼ó«½ ¬«ñ¿απÑΓß∩ *µÑ½δ¼* τ¿ß½«¼ í¿Γ.
ìá¿í«½ÑÑ ∩ᬫ φΓ« »α«∩ó½∩ÑΓß∩ »α¿ ¬«ñ¿α«óá¡¿¿ ñóπσß¿¼ó«½∞¡«ú« á½Σáó¿Γá:
ó φΓ«¼ ß½πτáÑ ßªáΓ¿Ñ *óßÑúñá* «ΓßπΓßΓóπÑΓ, ¡Ñß¼«Γα∩ ¡á αẽ¿τ¿Ñ
óÑα«∩Γ¡«ßΓÑ⌐ ß¿¼ó«½«ó; á½ú«α¿Γ¼ Σá¬Γ¿τÑ߬¿ "«¬απú½∩ÑΓ" ¿σ ñ« 1/2!

        ¥Γá »α«í½Ñ¼á ¼«ªÑΓ íδΓ∞ τáßΓ¿τ¡« αÑΘÑ¡á ºá ßτÑΓ í½«¬¿α«óá¡¿∩
óσ«ñ¡«ú« »«Γ«¬á (Γ.Ñ. óóÑñÑ¡¿∩ ó αáßß¼«ΓαÑ¡¿Ñ ¡«óδσ ß¿¼ó«½«ó ó¿ñá 'ab',
'abc', ... úñÑ a, b, c -- ß¿¼ó«½δ ¿ßσ«ñ¡«ú« á½Σáó¿Γá).  Äñ¡á¬« φΓ« ¡Ñ
»«ºó«½∩ÑΓ »«½¡«ßΓ∞ε ¿ºíáó¿Γ∞ß∩ «Γ »«ΓÑα∞ («¡¿ ½¿Φ∞ π¼Ñ¡∞ΦáεΓß∩
»α«»«αµ¿«¡á½∞¡« αẼÑαπ í½«¬á) ¿ »α¿ó«ñ¿Γ ¬ αѺ¬«¼π α«ßΓ𠬫ñ«ó«ú«
ñÑαÑóá: Ñß½¿, ¡á»α¿¼Ñα, ß¿¼ó«½á¼¿ óσ«ñ¡«ú« á½Σáó¿Γá ∩ó½∩εΓß∩ 8-í¿Γ«óδÑ
íá⌐Γδ ß« º¡áτÑ¡¿∩¼¿ 0 .. 255, Γ« »α¿ í½«¬¿α«óá¡¿¿ »« ñóá ß¿¼ó«½á ¼δ
»«½πτáѼ 65536 ß¿¼ó«½«ó (¿ ßΓ«½∞¬« ªÑ ½¿ßΓ∞Ñó ¬«ñ«ó«ú« ñÑαÑóá), á »α¿
í½«¬¿α«óá¡¿¿ »« Γα¿ -- 16777216!  æ««ΓóÑΓßΓóÑ¡¡« ó«ºαáßΓπΓ ΓαÑí«óá¡¿∩ ¬
»á¼∩Γ¿ ¿ óαѼ∩ »«ßΓα«Ñ¡¿∩ ñÑαÑóá (á »α¿ áñá»Γ¿ó¡«¼ ¬«ñ¿α«óá¡¿¿ -- ¿
óαѼ∩ «í¡«ó½Ñ¡¿∩ ñÑαÑóá, á º¡áτ¿Γ, ¿ óαѼ∩ ߪáΓ¿∩). Å«ΓÑα¿ ªÑ ß«ßΓáó∩Γ
ó ßαÑñ¡Ñ¼ 1/2 í¿Γá ¡á ß¿¼ó«½ »α¿ «ΓßπΓßΓó¿¿ í½«¬¿α«óá¡¿∩, á »α¿ Ñú«
¡á½¿τ¿¿ -- 1/4 ¿ 1/6 í¿Γá ß««ΓóÑΓßΓóÑ¡¡« ñ½∩ í½«¬«ó ñ½¿¡ 2 ¿ 3.
ü«½∞Φπε ßΓѻѡ∞ ߪáΓ¿∩, ¡Ñ ºáó¿ß∩Θπε «Γ í½¿º«ßΓ¿ º¡áτÑ¡¿⌐ óÑα«∩Γ¡«ßΓ¿
ß¿¼ó«½«ó ¬ ßΓѻѡ∩¼ 1/2, ¼«ªÑΓ ñáΓ∞ Γᬠ¡áºδóáѼ«Ñ áα¿Σ¼ÑΓ¿τÑ߬«Ñ
¬«ñ¿α«óá¡¿Ñ.

        Çα¿Σ¼ÑΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ (»«ñα«í¡«Ñ «»¿ßá¡¿Ñ ß¼. [Witten])
∩ó½∩ÑΓß∩ ¼ÑΓ«ñ«¼, »«ºó«½∩εΘ¿¼ π»á¬«óδóáΓ∞ ß¿¼ó«½δ óσ«ñ¡«ú« á½Σáó¿Γá íѺ
»«ΓÑα∞ »α¿ πß½«ó¿¿, τΓ« ¿ºóÑßΓ¡« αáß»αÑñѽѡ¿Ñ τáßëà φΓ¿σ ß¿¼ó«½«ó.
è«¡µÑ»µ¿∩ ¼ÑΓ«ñá ó«ßσ«ñ¿Γ ¬ αáí«Γá¼ ¥½¿áßá ó 60-x ú«ñáσ (ß¼. [Abramson,
60-61]). é ñá½∞¡Ñ⌐ΦѼ ¼ÑΓ«ñ íδ½ αáºó¿Γ ¿ º¡áτ¿Γѽ∞¡« πß«óÑαΦÑ¡ßΓó«óá¡
([Rissanen]).

    Çα¿Σ¼ÑΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ ∩ó½∩ÑΓß∩ «»Γ¿¼á½∞¡δ¼, ñ«ßΓ¿úá∩
ΓÑ«αÑΓ¿τÑ߬«⌐ úαá¡¿µδ ßΓѻѡ¿ ߪáΓ¿∩, -- φ¡Γα«»¿¿ óσ«ñ¡«ú« »«Γ«¬á.

    ÆѬßΓ, ߪáΓδ⌐ áα¿Σ¼ÑΓ¿τÑ߬¿¼ ¬«ñÑα«¼, αáßß¼áΓα¿óáÑΓß∩ ¬á¬
¡Ñ¬«Γ«αá∩ ñó«¿τ¡á∩ ñα«í∞ ¿º ¿¡ΓÑαóá½á [0, 1). ÉѺπ½∞ΓáΓ ßªáΓ¿∩ ¼«ª¡«
»αÑñßΓáó¿Γ∞ ¬á¬ »«ß½Ññ«óáΓѽ∞¡«ßΓ∞ ñó«¿τ¡δσ µ¿Σα ¿º ºá»¿ß¿ φΓ«⌐ ñα«í¿.
êñÑ∩ ¼ÑΓ«ñá ß«ßΓ«¿Γ ó ß½ÑñπεΘѼ: ¿ßσ«ñ¡δ⌐ ΓѬßΓ αáßß¼áΓα¿óáÑΓß∩ ¬á¬
ºá»¿ß∞ φΓ«⌐ ñα«í¿, úñÑ ¬áªñδ⌐ óσ«ñ¡«⌐ ß¿¼ó«½ ∩ó½∩ÑΓß∩ "µ¿Σα«⌐" ß óÑß«¼,
»α«»«αµ¿«¡á½∞¡δ¼ óÑα«∩Γ¡«ßΓ¿ Ñú« »«∩ó½Ñ¡¿∩. Å«∩ß¡¿¼ αáí«Γπ ¼ÑΓ«ñá ¡á
»α¿¼ÑαÑ.

    ÅπßΓ∞ á½Σáó¿Γ ß«ßΓ«¿Γ ¿º ñóπσ ß¿¼ó«½«ó: a ¿ b ß óÑα«∩Γ¡«ßΓ∩¼¿
ß««ΓóÑΓßΓóÑ¡¡« 3/4 ¿ 1/4. èᬠπªÑ ú«ó«α¿½«ß∞ óδΦÑ, ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á
¡Ñ ¼«ªÑΓ π»á¬«óδóáΓ∞ ß½«óá ó ñá¡¡«¼ á½Σáó¿ΓÑ.

    Éáßß¼«Γα¿¼ («Γ¬αδΓδ⌐ ß»αáóá) ¿¡ΓÑαóá½ [0, 1). Éẫí∞Ѽ Ñú« ¡á
τáßΓ¿, ñ½¿¡á ¬«Γ«αδσ »α«»«αµ¿«¡á½∞¡á óÑα«∩Γ¡«ßΓ∩¼ ß¿¼ó«½«ó.  é ¡áΦѼ
ß½πτáÑ φΓ« [0, 3/4) ¿ [3/4, 1).  æπΓ∞ á½ú«α¿Γ¼á ó ß½ÑñπεΘѼ: ¬áªñ«¼π
ß½«óπ ó« óσ«ñ¡«¼ á½Σáó¿ΓÑ ß««ΓóÑΓßΓóπÑΓ ¡Ñ¬«Γ«αδ⌐ »«ñ¿¡ΓÑαóá½ ¿º [0,1).
ÅπßΓ«¼π ß½«óπ ß««ΓóÑΓßΓóπÑΓ óÑß∞ ¿¡ΓÑαóá½ [0, 1). Å«ß½Ñ »«½πτÑ¡¿∩
¬áªñ«ú« »«ß½ÑñπεΘÑú« ß¿¼ó«½á áα¿Σ¼ÑΓ¿τÑ߬¿⌐ ¬«ñÑα π¼Ñ¡∞ΦáÑΓ ¿¡ΓÑαóá½,
óδí¿αá∩ Γπ Ñú« τáßΓ∞, ¬«Γ«αá∩ ß««ΓóÑΓßΓóπÑΓ ó¡«ó∞ »«ßΓπ»¿óΦѼπ ß¿¼ó«½π.
è«ñ«¼ µÑ»«τ¬¿ ∩ó½∩ÑΓß∩ ¿¡ΓÑαóá½, óδñѽѡ¡δ⌐ »«ß½Ñ «íαáí«Γ¬¿ óßÑσ ÑÑ
ß¿¼ó«½«ó, Γ«τ¡ÑÑ, ñó«¿τ¡á∩ ºá»¿ß∞ ½εí«⌐ Γ«τ¬¿ ¿º φΓ«ú« ¿¡ΓÑαóá½á.

    Æᬿ¼ «íαẫ¼, ñ½¿¡á »«½πτÑ¡¡«ú« ¿¡ΓÑαóá½á »α«»«αµ¿«¡á½∞¡á
óÑα«∩Γ¡«ßΓ¿ »«∩ó½Ñ¡¿∩ ¬«ñ¿απѼ«⌐ µÑ»«τ¬¿.

    éδ»«½¡¿¼ á½ú«α¿Γ¼ ñ½∩ µÑ»«τ¬¿ "aaba":

 ÿáú │ Åα«ß¼«ΓαÑ¡¡á∩  │ ê¡ΓÑαóá½
     │    µÑ»«τ¬á     │
─────┼────────────────┼──────────────────────────────────────────────
 0.  │  ""            │ [0, 1) = [0, 1)
 1.  │  "a"           │ [0, 3/4) = [0, 0.11)
 2.  │  "aa"          │ [0, 9/16) = [0, 0.1001)
 3.  │  "aab"         │ [27/64, 36/64) = [0.011011, 0.100100)
 4.  │  "aaba"        │ [108/256, 135/256) = [0.01101100, 0.10000111)

        é ¬áτÑßΓóÑ ¬«ñá ¼«ª¡« óº∩Γ∞ ½εí«Ñ τ¿ß½« ¿º ¿¡ΓÑαóá½á,
»«½πτÑ¡¡«ú« ¡á ΦáúÑ 4, ¡á»α¿¼Ñα, 0.1.

        Çα¿Σ¼ÑΓ¿τÑ߬¿⌐ ñѬ«ñÑα αáí«ΓáÑΓ ß¿¡σα«¡¡« ß ¬«ñÑα«¼: ¡áτáó ß
¿¡ΓÑαóá½á [0, 1), «¡ »«ß½Ññ«óáΓѽ∞¡« «»αÑñѽ∩ÑΓ ß¿¼ó«½δ óσ«ñ¡«⌐
µÑ»«τ¬¿. é τáßΓ¡«ßΓ¿, ó ¡áΦѼ ß½πτáÑ «¡ ó¡áτá½Ñ αáºñѽ¿Γ
(»α«»«αµ¿«¡á½∞¡« τáßΓ«Γá¼ ß¿¼ó«½«ó) ¿¡ΓÑαóá½ [0, 1) ¡á [0, 0.11) ¿
[0.11, 1).  ū߬«½∞¬π τ¿ß½« 0.0111 (»ÑαÑñá¡¡δ⌐ ¬«ñÑα«¼ ¬«ñ µÑ»«τ¬¿
"aaba") ¡áσ«ñ¿Γß∩ ó »Ñαó«¼ ¿º ¡¿σ, ¼«ª¡« »«½πτ¿Γ∞ »Ñαóδ⌐ ß¿¼ó«½: "a".
çáΓѼ ñѽ¿¼ »Ñαóδ⌐ »«ñ¿¡ΓÑαóá½ [0, 0.11) ¡á [0, 0.1001) ¿ [0.1001,
0.1100) (»α«»«αµ¿«¡á½∞¡« τáßΓ«Γá¼ ß¿¼ó«½«ó).  Ä»∩Γ∞ óδí¿αáѼ »Ñαóδ⌐,
Γᬠ¬á¬ 0 < 0.0111 < 0.1001.  Åα«ñ«½ªá∩ φëà »α«µÑßß, ¼δ «ñ¡«º¡áτ¡«
ñѬ«ñ¿απѼ óßÑ τÑΓδαÑ ß¿¼ó«½á.  ä½∩ Γ«ú«, τΓ«íδ ñѬ«ñÑα ¼«ú «»αÑñѽ¿Γ∞
¬«¡Ñµ µÑ»«τ¬¿, ¼δ ¼«ªÑ¼ ½¿í« »ÑαÑñáóáΓ∞ ÑÑ ñ½¿¡π «Γñѽ∞¡«, ½¿í«
ñ«íáó¿Γ∞ ¬ á½Σáó¿Γπ ñ«»«½¡¿Γѽ∞¡δ⌐ ß¿¼ó«½ "¬«¡Ñµ µÑ»«τ¬¿".

        Åα¿ αáßß¼«ΓαÑ¡¿¿ φΓ«ú« ¼ÑΓ«ñá 󫺡¿¬áεΓ ñóÑ »α«í½Ñ¼δ:
ó«-»Ñαóδσ, ¡Ñ«íσ«ñ¿¼á óÑΘÑßΓóÑ¡¡á∩ áα¿Σ¼ÑΓ¿¬á, ó««íΘÑ ú«ó«α∩,
¡Ñ«úαá¡¿τÑ¡¡«⌐ Γ«τ¡«ßΓ¿, ¿ ó«-óΓ«αδσ, αѺπ½∞ΓáΓ ¬«ñ¿α«óá¡¿∩ ßΓá¡«ó¿Γß∩
¿ºóÑßΓÑ¡ ½¿Φ∞ »α¿ «¬«¡τá¡¿¿ óσ«ñ¡«ú« »«Γ«¬á.  äá½∞¡Ñ⌐Φ¿Ñ ¿ßß½Ññ«óá¡¿∩,
«ñ¡á¬«, »«¬áºδóáεΓ [Rubin], τΓ« ¼«ª¡« »αá¬Γ¿τÑ߬¿ íѺ »«ΓÑα∞ «í«⌐Γ¿ß∞
µÑ½«τ¿ß½Ñ¡¡«⌐ áα¿Σ¼ÑΓ¿¬«⌐ ¡Ñí«½∞Φ«⌐ Γ«τ¡«ßΓ¿ (16-32 αáºα∩ñá), á ΓᬪÑ
ñ«í¿Γ∞ß∩ ¿¡¬αѼѡΓá½∞¡«⌐ αáí«Γδ á½ú«α¿Γ¼á: µ¿Σαδ ¬«ñá ¼«úπΓ óδñáóáΓ∞ß∩
»«ß½Ññ«óáΓѽ∞¡« »« ¼ÑαÑ τΓÑ¡¿∩ óσ«ñ¡«ú« »«Γ«¬á.



.te 1 .ce î«ñѽ¿ óσ«ñ¡«ú« »«Γ«¬á


    èᬠú«ó«α¿½«ß∞ óδΦÑ, ¬«ñ¿α«óá¡¿Ñ »αÑñßΓáó½∩ÑΓ ß«í«⌐ ½¿Φ∞ τáßΓ∞
»α«µÑßßá π»á¬«ó¬¿. ìÑ ¼Ñ¡ÑÑ ó᪡« Γ.¡. ¼«ñѽ¿α«óá¡¿Ñ (modelling).  îδ
πªÑ ú«ó«α¿½¿ « Γ«¼, τΓ« áα¿Σ¼ÑΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ ¿¼ÑÑΓ ¼¿¡¿¼á½∞¡πε
¿ºíδΓ«τ¡«ßΓ∞ »α¿ ºáñá¡¡«¼ αáß»αÑñѽѡ¿¿. ùπñÑß¡«! -- ó«ß¬½¿¬¡ÑΓ
τ¿ΓáΓѽ∞. ì« «Γ¬πñá íÑαÑΓß∩ φΓ« αáß»αÑñѽѡ¿Ñ? ê « ¬á¬«¼ á½Σáó¿ΓÑ ¿ñÑΓ
αÑτ∞?

    ÄΓóÑΓδ ¡á φΓ¿ ó«»α«ßδ ñáÑΓ ¼«ñѽ∞ »«Γ«¬á, »αÑñßΓáó½∩εΘá∩ ß«í«⌐
(ß¼. [Rissanen], [Witten]) ¡Ñ¬«Γ«αδ⌐ ß»«ß«í «»αÑñѽѡ¿∩ αáß»αÑñѽѡ¿∩
óÑα«∩Γ¡«ßΓÑ⌐ »α¿ ¬áªñ«¼ »«ßΓπ»½Ñ¡¿¿ «τÑαÑñ¡«ú« ß¿¼ó«½á. ê¼Ñ¡¡« ¬áªñ«¼,
»«ß¬«½∞¬π ßΓáΓ¿τÑ߬¿Ñ ¼«ñѽ¿ (ó ¬«Γ«αδσ αáß»αÑñѽѡ¿Ñ ¡Ñ ¿º¼Ñ¡∩ÑΓß∩) ó
í«½∞Φ¿¡ßΓóÑ ß½πτáÑó ¡Ñ ñáεΓ ¼á¬ß¿¼á½∞¡«ú« ¬áτÑßΓóá ߪáΓ¿∩. â«αáºñ«
í«½∞Φ¿⌐ ¿¡ΓÑαÑß »αÑñßΓáó½∩εΓ Γᬠ¡áºδóáѼδÑ áñá»Γ¿ó¡δÑ ¼«ñѽ¿,
πτ¿ΓδóáεΘ¿Ñ ΓѬπΘ¿⌐ ¬«¡ΓѬßΓ.  Æá¬¿Ñ ¼«ñѽ¿ »«ºó«½∩εΓ ßΓα«¿Γ∞ íδßΓαδÑ
«ñ¡«»α«σ«ñ¡δÑ á½ú«α¿Γ¼δ ߪáΓ¿∩, ¡Ñ ΓαÑíπεΘ¿Ñ á»α¿«α¡δσ º¡á¡¿⌐ « óσ«ñ¡«¼
»«Γ«¬Ñ ñá¡¡δσ ¿ ßΓα«∩Θ¿Ñ αáßαÑñѽѡ¿Ñ "¡á ½ÑΓπ". éδñѽ∩εΓ Γá¬ªÑ ¬½áßß
"½«¬á½∞¡« áñá»Γ¿ó¡δσ" á½ú«α¿Γ¼«ó, «ΓñáεΘ¿σ »α¿ »«ßΓα«Ñ¡¿¿ αáß»αÑñѽѡ¿∩
»αÑñ»«τΓÑ¡¿Ñ »«ß½Ññ¡¿¼ »«ßΓπ»¿óΦ¿¼ ß¿¼ó«½á¼.

    髺¼«ª¡δ αẽ¿τ¡δÑ »«ñσ«ñδ ¬ φΓ«⌐ »α«í½Ñ¼Ñ: »α«ßΓÑ⌐Φ¿⌐ ¿º ¡¿σ
-- ßí«α ßΓáΓ¿ßΓ¿¬¿ »«∩ó½Ñ¡¿∩ ¬áªñ«ú« ß¿¼ó«½á ¡Ñºáó¿ß¿¼« «Γ ñαπú¿σ
(¼«ñѽ¿α«óá¡¿Ñ ¿ßΓ«τ¡¿¬«¼ üÑα¡π½½¿: óÑα«∩Γ¡«ßΓ∞ »«∩ó½Ñ¡¿∩ ß¿¼ó«½á ¡Ñ
ºáó¿ß¿Γ «Γ Γ«ú«, ¬á¬¿Ñ ß¿¼ó«½δ óßΓαÑΓ¿½¿ß∞ »ÑαÑñ ¡¿¼). 髺¼«ª¡« ΓᬪÑ
¿ß»«½∞º«óá¡¿Ñ ¼áᬫó߬«⌐ ¼«ñѽ¿: ßí«α ßΓáΓ¿ßΓ¿¬¿ »«∩ó½Ñ¡¿∩ ¬áªñ«ú«
ß¿¼ó«½á ß πτÑΓ«¼ ¡Ñ¬«Γ«α«ú« ¬«½¿τÑßΓóá »αÑñδñπΘ¿σ ß¿¼ó«½«ó (ó
¼áᬫó߬«¼ ¿ßΓ«τ¡¿¬Ñ »Ñαó«ú« »«α∩ñ¬á óÑα«∩Γ¡«ßΓ∞ »«∩ó½Ñ¡¿∩ ß¿¼ó«½á
ºáó¿ß¿Γ Γ«½∞¬« «Γ «ñ¡«ú« »«ß½Ññ¡Ñú« »«½πτÑ¡¡«ú« ß¿¼ó«½á, ¿ Γ.ñ.).
îáᬫó߬¿Ñ ¼«ñѽ¿ ¼«úπΓ ñáóáΓ∞ í«½ÑÑ Γ«τ¡πε ¬áαΓ¿¡π ¿ßΓ«τ¡¿¬á, «ñ¡á¬«
τ¿ß½« ß«ßΓ«∩¡¿⌐ ó ¡¿σ í«½∞ΦÑ, ß««ΓóÑΓßΓóÑ¡¡« í«½∞ΦÑ «í∞Ѽ σαá¡¿¼δσ
Γáí½¿µ τáßΓ«Γ. èα«¼Ñ Γ«ú«, »α¿ ¿ß»«½∞º«óá¡¿¿ ¬«ñ¿α«óá¡¿∩ òáΣΣ¼Ñ¡á «¡¿
¼«úπΓ ñáªÑ πσπñΦ¿Γ∞ ¬áτÑßΓó« ߪáΓ¿∩, »«ß¬«½∞¬π »«α«ªñáѼδÑ ¿¼¿
óÑα«∩Γ¡«ßΓ¿ «íδτ¡« σπªÑ »α¿í½¿ªáεΓß∩ ßΓѻѡ∩¼¿ 1/2.

    â«ó«α∩ « ¼«ñѽ∩σ óσ«ñ¡«ú« »«Γ«¬á ¿ áñá»Γ¿ó¡δσ á½ú«α¿Γ¼áσ
ߪáΓ¿∩, ¡Ñ½∞º∩ ¡Ñ π»«¼∩¡πΓ∞ »α«ßΓ«⌐ ¿ ñ«ßΓáΓ«τ¡« φΣΣÑ¬Γ¿ó¡δ⌐ ¼ÑΓ«ñ
¬«ñ¿α«óá¡¿∩ ¿ßΓ«τ¡¿¬á ß ¡Ñ¿ºóÑßΓ¡δ¼ αáß»αÑñѽѡ¿Ñ¼ τáßΓ«Γ, ¿ºóÑßΓ¡δ⌐
¬á¬ ߪáΓ¿Ñ »α¿ »«¼«Θ¿ ßΓ«»¬¿ ¬¡¿ú. îÑΓ«ñ íδ½ ó»ÑαóδÑ «Γ¬αδΓ ¿
¿ßß½Ññ«óá¡ É∩í¬« ó 1980 ú. (ß¼. [É∩í¬«]), á ºáΓѼ »ÑαÑ«Γ¬αδΓ üÑ¡Γ½¿,
æ½Ñ⌐ΓÑα«¼, Æáα∞∩¡«¼ ¿ éÑ¿ ó 1986 ú. (ß¼. [Bentley]).

    êñÑ∩ ¼ÑΓ«ñá ß«ßΓ«¿Γ ó ß½ÑñπεΘѼ: »πßΓ∞ á½Σáó¿Γ ¿ßΓ«τ¡¿¬á
ß«ßΓ«¿Γ ¿º N ß¿¼ó«½«ó ß ¡«¼ÑαἿ 1, 2, ..., N. è«ñÑα σαá¡¿Γ ß»¿ß«¬
ß¿¼ó«½«ó, »αÑñßΓáó½∩εΘ¿⌐ ß«í«⌐ ¡Ñ¬«Γ«απε »ÑαÑßΓá¡«ó¬π á½Σáó¿Γá. Åα¿
»«ßΓπ»½Ñ¡¿¿ ¡á óσ«ñ ß¿¼ó«½á c, ¿¼ÑεΘÑú« ó φΓ«ß ß»¿ß¬Ñ ¡«¼Ñα i, ¬«ñÑα
»ÑαÑñáÑΓ ¬«ñ ¡«¼Ñαá i (¡á»α¿¼Ñα, ¼«¡«Γ«¡¡δ⌐ ¬«ñ: [èα¿τÑó߬¿⌐],
ßΓα.69-73). ¥áΓѼ ¬«ñÑα »ÑαÑßΓáó½∩ÑΓ ß¿¼ó«½ c ó ¡áτὫ ß»¿ß¬á,
πóѽ¿τ¿óá∩ ¡á 1 ¡«¼Ñαá óßÑσ ß¿¼ó«½«ó, ßΓ«∩Θ¿σ »ÑαÑñ c. Æᬿ¼ «íαẫ¼,
í«½ÑÑ "»«»π½∩α¡δÑ" ß¿¼ó«½δ íπñπΓ Γ∩ú«ΓÑΓ∞ ¬ ¡áτá½π ß»¿ß¬á ¿ ¿¼ÑΓ∞ í«½ÑÑ
¬«α«Γ¬¿Ñ ¬«ñδ.



.te 1 .ce äóπσßΓπ»Ñ¡τáΓ«Ñ ¬«ñ¿α«óá¡¿Ñ. ǽú«α¿Γ¼ ïѼ»Ñ½∩-ç¿óá


    éßÑ αáßß¼«ΓαÑ¡¡δÑ óδΦÑ ¼ÑΓ«ñδ ¿ ¼«ñѽ¿ ¬«ñ¿α«óá¡¿∩
αáßß¼áΓα¿ó὿ ó ¬áτÑßΓóÑ óσ«ñ¡δσ ñá¡¡δσ µÑ»«τ¬¿ ß¿¼ó«½«ó (ΓѬßΓδ) ó
¡Ñ¬«Γ«α«¼ ¬«¡Ñτ¡«¼ á½Σáó¿ΓÑ. Åα¿ φΓ«¼ «ßΓáóá½ß∩ «Γ¬αδΓδ¼ ó«»α«ß « ßó∩º¿
φΓ«ú« óσ«ñ¡«ú« á½Σáó¿Γá ¬«ñÑαá ß ñá¡¡δ¼¿, »«ñ½ÑªáΘ¿¼¿ π»á¬«ó¬Ñ («íδτ¡«
Γá¬ªÑ »αÑñßΓáó½Ñ¡¡δ¼¿ ó ó¿ñÑ µÑ»«τѬ ó á½Σáó¿ΓÑ, «íδτ¡« ß«ßΓ«∩ΘѼ ¿º
256 ß¿¼ó«½«ó-íá⌐Γ).

    é »α«ßΓÑ⌐ΦѼ ß½πτáÑ ¼«ª¡« ¿ß»«½∞º«óáΓ∞ ó ¬áτÑßΓóÑ óσ«ñ¡«ú«
á½Σáó¿Γá ¬«ñÑαá ¿¼Ñ¡¡« φΓ¿ ß¿¼ó«½δ (íá⌐Γδ) óσ«ñ¡«ú« »«Γ«¬á. ê¼Ñ¡¡« Γá¬
αáí«ΓáÑΓ ¼ÑΓ«ñ squashing »α«úαá¼¼δ PKPAK (¿ß»«½∞º«óá¡« ßΓáΓ¿τÑ߬«Ñ
¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á, ñóπσ»α«σ«ñ¡δ⌐ á½ú«α¿Γ¼). æΓѻѡ∞ ߪáΓ¿∩ »α¿ φΓ«¼
«Γ¡«ß¿Γѽ∞¡« ¡Ñóѽ¿¬á -- »«α∩ñ¬á 50% ñ½∩ ΓѬßΓ«óδσ Σá⌐½«ó.

    â«αáºñ« í«½∞ΦÑ⌐ ßΓѻѡ¿ ߪáΓ¿∩ ¼«ª¡« ñ«í¿Γ∞ß∩ »α¿ óδñѽѡ¿¿ ¿º
óσ«ñ¡«ú« »«Γ«¬á »«óΓ«α∩εΘ¿σß∩ µÑ»«τѬ ¿ ¬«ñ¿α«óá¡¿∩ ßß佫¬ ¡á φΓ¿
µÑ»«τ¬¿.

    ¥Γ«Γ ¼ÑΓ«ñ, « ¬«Γ«α«¼ ¿ »«⌐ñÑΓ ñá½ÑÑ αÑτ∞, »α¿¡áñ½Ñª¿Γ ïѼ»Ñ½ε
¿ ç¿óπ (ß¼. [Lempel), ¿ «íδτ¡« ¡áºδóáÑΓß∩ LZ-compression. æπΓ∞ Ñú« ó
ß½ÑñπεΘѼ: π»á¬«óΘ¿¬ »«ßΓ«∩¡¡« σαá¡¿Γ ¡Ñ¬«Γ«α«Ñ ¬«½¿τÑßΓó« »«ß½Ññ¡¿σ
«íαáí«Γá¡¡δσ ß¿¼ó«½«ó ó íπΣÑαÑ.  Å« ¼ÑαÑ «íαáí«Γ¬¿ óσ«ñ¡«ú« »«Γ«¬á
ó¡«ó∞ »«ßΓπ»¿óΦ¿Ñ ß¿¼ó«½δ »«»áñáεΓ ó ¬«¡Ñµ íπΣÑαá, ßñó¿úá∩
»αÑñΦÑßΓóπεΘ¿Ñ ß¿¼ó«½δ ¿ óδΓÑß¡∩∩ ßá¼δÑ ßΓáαδÑ.  ÉẼÑαδ φΓ«ú« íπΣÑαá,
¡áºδóáѼ«ú« Γá¬ªÑ ß¬«½∞º∩Θ¿¼ ß½«óáαѼ (sliding dictionary), óáα∞¿απεΓß∩
ó αạδσ αÑ὿ºáµ¿∩σ; φ¬ß»Ñα¿¼Ñ¡Γá½∞¡δ¼ »πΓѼ πñὫß∞ πßΓá¡«ó¿Γ∞, τΓ«
»α«úαá¼¼δ LHarc 1.13 ¿ß»«½∞ºπeΓ 4-¬¿½«íá⌐Γ¡δ⌐ íπΣÑα, LHA 2.13 ¿ PKZIP
1.10 -- 8-¬¿½«íá⌐Γ¡δ⌐, á ARJ 2.20 -- 16-¬¿½«íá⌐Γ¡δ⌐.

    ǽú«α¿Γ¼ óδñѽ∩ÑΓ (»πΓѼ »«¿ß¬á ó ß½«óáαÑ) ßá¼πε ñ½¿¡¡πε
¡áτá½∞¡πε »«ñßΓ᫬π óσ«ñ¡«ú« »«Γ«¬á, ß«ó»áñáεΘπε ß «ñ¡«⌐ ¿º »«ñßΓ᫬ ó
ß½«óáαÑ, ¿ óδñáÑΓ ¡á óδσ«ñ »áαπ (length, distance), úñÑ length -- ñ½¿¡á
¡á⌐ñÑ¡¡«⌐ ó ß½«óáαÑ »«ñßΓ᫬¿, á distance -- αáßßΓ«∩¡¿Ñ «Γ ¡ÑÑ ñ«
óσ«ñ¡«⌐ »«ñßΓ᫬¿ (Γ« ÑßΓ∞ Σá¬Γ¿τÑ߬¿ ¿¡ñÑ¬ß »«ñßΓ᫬¿ ó íπΣÑαÑ,
óδτΓÑ¡¡δ⌐ ¿º Ñú« αẼÑαá). é ß½πτáÑ, Ñß½¿ Γá¬á∩ »«ñßΓα«¬á ¡Ñ ¡á⌐ñÑ¡á, ó
óδσ«ñ¡«⌐ »«Γ«¬ »α«ßΓ« ¬«»¿απÑΓß∩ «τÑαÑñ¡«⌐ ß¿¼ó«½ óσ«ñ¡«ú« »«Γ«¬á.

    é »Ñαó«¡áτá½∞¡«⌐ óÑαß¿¿ á½ú«α¿¼á »αÑñ½áúὫß∞ ¿ß»«½∞º«óáΓ∞
»α«ßΓÑ⌐Φ¿⌐ »«¿ß¬ »« óßѼπ ß½«óáαε. éαѼ∩ ߪáΓ¿∩ »α¿ Γᬫ⌐ αÑ὿ºáµ¿¿
í佫 »α«»«αµ¿«¡á½∞¡« »α«¿ºóÑñÑ¡¿ε ñ½¿¡δ óσ«ñ¡«ú« »«Γ«¬á ¡á αẼÑα
íπΣÑαá, τΓ« ¡Ñ»α¿ú«ñ¡« ñ½∩ »αá¬Γ¿τÑ߬«ú« ¿ß»«½∞º«óá¡¿∩. Äñ¡á¬«, ó
ñá½∞¡Ñ⌐ΦѼ í佫 »αÑñ½«ªÑ¡« ¿ß»«½∞φ«óáΓ∞ ñó«¿τ¡«Ñ ñÑαÑó« ñ½∩ íδßΓα«ú«
»«¿ß¬á ó ß½«óáαÑ [Bell], τΓ« »«φ󫽿½« ¡á »«α∩ñ«¬ »«ñ¡∩Γ∞ ߬«α«ßΓ∞
αáí«Γδ á½ú«α¿Γ¼á.

    Æᬿ¼ «íαẫ¼, á½ú«α¿Γ¼ ïѼ»Ñ½∩-ç¿óá »αÑ«íαáºπÑΓ «ñ¿¡ »«Γ«¬
¿ßσ«ñ¡δσ ß¿¼ó«½«ó ó ñóá »áαώѽ∞¡δσ »«Γ«¬á length ¿ distance.
ÄτÑó¿ñ¡«, τΓ« φΓ¿ »«Γ«¬¿ ∩ó½∩εΓß∩ »«Γ«¬á¼¿ ß¿¼ó«½«ó ó ¡«óδσ á½Σáó¿Γáσ L
¿ D, ¿ ¬ ¡¿¼ ¼«ª¡« »α¿¼Ñ¡¿Γ∞ «ñ¿¡ ¿º π»«¼¿¡áóΦ¿σß∩ óδΦÑ ¼ÑΓ«ñ«ó (RLE,
¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á, áα¿Σ¼ÑΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ).  Æᬠ¼δ »α¿σ«ñ¿¼ ¬
ßσÑ¼Ñ ñóπσßΓπ»Ñ¡τáΓ«ú« ¬«ñ¿α«óá¡¿∩, ¡á¿í«½ÑÑ φΣΣÑ¬Γ¿ó¡«⌐ ¿º »αá¬Γ¿τÑ߬¿
¿ß»«½∞ºπѼδσ ó ¡áßΓ«∩ΘÑÑ óαѼ∩ (¿, ó τáßΓ¡«ßΓ¿, ¿ß»«½∞º«óá¡¡«⌐
áóΓ«α«¼). Åα¿ αÑ὿ºáµ¿¿ φΓ«ú« ¼ÑΓ«ñá ¡Ñ«íσ«ñ¿¼« ñ«í¿Γ∞ß∩
ß«ú½áß«óá¡¡«ú« óδó«ñá «í«¿σ »«Γ«¬«ó ó «ñ¿¡ Σá⌐½. ¥Γá »α«í½Ñ¼á «íδτ¡«
αÑΦáÑΓß∩ »πΓѼ »««τÑαÑñ¡«⌐ φỿ߿ ¬«ñ«ó ß¿¼ó«½«ó ¿º «í«¿σ »«Γ«¬«ó.

    æ½ÑñπÑΓ Γá¬ªÑ «Γ¼ÑΓ¿Γ∞ Φ¿α«¬« ¿ºóÑßΓ¡δ⌐ á½ú«α¿Γ¼
ïѼ»Ñ½∩-ç¿óá-éѽτá (Lempel-Ziv-Welch compression, LZW).  ǽú«α¿Γ¼
«Γ½¿τáεΓ óδß«¬á∩ ߬«α«ßΓ∞ αáí«Γδ ¬á¬ »α¿ π»á¬«ó¬Ñ, Γᬠ¿ »α¿
αá߻ᬫó¬Ñ, ñ«ßΓáΓ«τ¡« ß¬α«¼¡δÑ ΓαÑí«óá¡¿∩ ¬ »á¼∩Γ¿ ¿ »α«ßΓá∩
á»»áαáΓ¡á∩ αÑ὿ºáµ¿∩. ìÑñ«ßΓáΓ«¬ -- ¡¿º¬á∩ ßΓѻѡ∞ ߪáΓ¿∩ »« ßαáó¡Ñ¡¿ε
ß« ßσѼ«⌐ ñóπσßΓπ»Ñ¡τáΓ«ú« ¬«ñ¿α«óá¡¿∩. èαáΓ¬« «»¿ΦѼ á½ú«α¿Γ¼. ü«½ÑÑ
»«ñα«í¡δÑ ßóÑñÑ¡¿∩ ß¼. [Welch].

    櫺ñáñ¿¼ ß½«óáα∞, σαá¡∩Θ¿⌐ ßΓ᫬¿ ΓѬßΓá ¿ ß«ñÑαªáΘ¿⌐ »«α∩ñ¬á
2-4-8 Γδß∩τ »α«¡π¼Ñα«óá¡¡δσ ú¡Ñºñ. çỿΦѼ ó »ÑαóδÑ 256 ú¡Ñºñ ßΓ᫬¿,
ß«ßΓ«∩Θ¿Ñ ¿º «ñ¡«ú« ß¿¼ó«½á, ¡«¼Ñα ¬«Γ«α«ú« αáóÑ¡ ¡«¼Ñαπ ú¡Ñºñá.
ǽú«α¿Γ¼ »α«ß¼áΓα¿óáÑΓ óσ«ñ¡«⌐ »«Γ«¬, αáºí¿óá∩ Ñú« ¡á »«ñßΓ᫬¿ ¿
ñ«íáó½∩∩ ¡«óδÑ ú¡Ñºñá ó ¬«¡Ñµ ß½«óáα∩.

    Åα«τ¿ΓáѼ ¡Ñ߬«½∞¬« ß¿¼ó«½«ó ó ßΓ᫬π s ¿ ¡á⌐ñѼ ó ß½«óáαÑ
ßΓ᫬π t -- ßá¼δ⌐ ñ½¿¡¡δ⌐ »αÑΣ¿¬ß s. ÅπßΓ∞ «¡ ¡á⌐ñÑ¡ ó ú¡ÑºñÑ ß ¡«¼Ñα«¼
n.  éδóÑñѼ τ¿ß½« n ó óδσ«ñ¡«⌐ »«Γ«¬, »ÑαѼÑßΓ¿¼ π¬áºáΓѽ∞ óσ«ñ¡«ú«
»«Γ«¬á ¡á length (t) ß¿¼ó«½«ó ó»ÑαÑñ ¿ ñ«íáó¿¼ ó ß½«óáα∞ ¡«ó«Ñ ú¡Ñºñ«,
ß«ñÑαªáΘÑÑ ßΓ᫬π t+c, úñÑ ß -- «τÑαÑñ¡«⌐ ß¿¼ó«½ ¡á óσ«ñÑ (ßαáºπ »«ß½Ñ
t). ǽú«α¿Γ¼ »αÑ«íαáºπÑΓ »«Γ«¬ ß¿¼ó«½«ó ¡á óσ«ñÑ ó »«Γ«¬ ¿¡ñѬ߫ó ∩τÑѬ
ß½«óáα∩ ¡á óδσ«ñÑ. Åα¿ αẼÑαÑ ß½«óáα∩ ó 4096 ú¡Ñºñ ¼«ª¡« »ÑαÑñáóáΓ∞ 12
í¿Γ ¡á ¬áªñδ⌐ ¿¡ñѬß.

    èáªñá∩ αáß»«º¡á¡¡á∩ µÑ»«τ¬á ñ«íáó½∩ÑΓ ó ß½«óáα∞ «ñ¡« ú¡Ñºñ«.
Åα¿ »ÑαÑ»«½¡Ñ¡¿¿ ß½«óáα∩ π»á¬«óΘ¿¬ ¼«ªÑΓ ½¿í« »αѬαáΓ¿Γ∞ Ñú«
ºá»«½¡Ñ¡¿Ñ, ½¿í« «τ¿ßΓ¿Γ∞ (»«½¡«ßΓ∞ε ¿½¿ τáßΓ¿τ¡«).

    Åα¿ »αá¬Γ¿τÑ߬«⌐ αÑ὿ºáµ¿¿ φΓ«ú« á½ú«α¿Γ¼á ß½ÑñπÑΓ πτÑßΓ∞, τΓ«
½εí«Ñ ú¡Ñºñ« ß½«óáα∩, ¬α«¼Ñ ßá¼δσ »Ñαóδσ, ß«ñÑαªáΘ¿σ «ñ¡«ß¿¼ó«½∞¡δÑ
µÑ»«τ¬¿, σαá¡¿Γ ¬«»¿ε ¡Ñ¬«Γ«α«ú« ñ¡πú«ú« ú¡Ñºñá, ¬ ¬«Γ«α«⌐ ó ¬«¡Ñµ
»α¿»¿ßá¡ «ñ¿¡ ß¿¼ó«½. éß½ÑñßΓó¿Ñ φΓ«ú« ¼«ª¡« «í«⌐Γ¿ß∞ »α«ßΓ«⌐ ß»¿ß«τ¡«⌐
ßΓαπ¬Γπα«⌐ ß «ñ¡«⌐ ßó∩º∞ε.



.te 1 .ce Åα«Ñ¬Γ¿α«óá¡¿Ñ. êß»«½∞º«óá¡¡δÑ á½ú«α¿Γ¼δ


    ÅÑαÑ⌐ñѼ ΓÑ»Ñα∞ ¬ «»¿ßá¡¿ε á½ú«α¿Γ¼«ó, ¿ß»«½∞º«óá¡¡δσ ó ¡áΦÑ⌐
αÑ὿ºáµ¿¿. ì« ß¡áτá½á -- ¡Ñ߬«½∞¬« ß½«ó « µÑ½∩σ, »«ßΓáó½Ñ¡¡δσ »α¿
αáºαáí«Γ¬Ñ ¿ «»αÑñѽ¿óΦ¿σ »α¿¡∩ΓδÑ αÑΦÑ¡¿∩.

    ÅαѪñÑ óßÑú«, π»á¬«óΦ¿¬ αáºαáíáΓδóá½ß∩ ß µÑ½∞ε óßΓαá¿óá¡¿∩ Ñú«
ó »α«úαá¼¼δ »«½∞º«óáΓѽ∩. Å«φΓ«¼π ¡Ñ »«ΓαÑí«óá½áß∞ αáºαáí«Γ¬á
߻ѵ¿á½∞¡«ú« Σ«α¼áΓá áασ¿ó¡«ú« Σá⌐½á. ä«ßΓáΓ«τ¡« ½¿Φ∞ »αÑíαẫóáΓѽ∩
"Σá⌐½ ó Σá⌐½" (á¡á½«ú¿τ¡« »α«úαá¼¼Ñ compress ó ß¿ßΓÑ¼Ñ UNIX). äá½ÑÑ,
¡á¬½áñδó὿ß∞ ñ«ßΓáΓ«τ¡« ªÑßΓ¬¿Ñ «úαá¡¿τÑ¡¿∩ ¡á ¿ß»«½∞ºπѼπε »á¼∩Γ∞:
αÑ὿º«óá¡¡δ⌐ á½ú«α¿Γ¼ ¿ß»«½∞ºπÑΓ 44K ñ½∩ π»á¬«ó¬¿ ¿ óßÑú« 12K ñ½∩
αáß»á¬«ó¬¿ (¡Ñ ßτ¿Γá∩ «í∞Ñ¼á ¬«ñá, «ñ¡á¬« «¡ Γ«ªÑ ¡Ñº¡áτ¿Γѽѡ), ó Γ«
óαѼ∩ ¬á¬ PKZIP ΓαÑíπÑΓ 90K ¿ 70K ß««ΓóÑΓßΓóÑ¡¡«, ARJ -- 275K ¿ 160K).
äá½ÑÑ, ¡Ñ«íσ«ñ¿¼á óδß«¬á∩ ߬«α«ßΓ∞ αá߻ᬫó¬¿; ¡á ߬«α«ßΓ∞ ªÑ π»á¬«ó¬¿
¡á¬½áñδóáεΓß∩ í«½ÑÑ ¼∩ú¬¿Ñ «úαá¡¿τÑ¡¿∩.

    êßσ«ñ∩ ¿º φΓ«ú«, íδ½ ¿ß»«½∞º«óá¡ á½ú«α¿Γ¼ ïѼ»Ñ½∩-ç¿óá ß
αẼÑα«¼ ߬«½∞º∩ΘÑú« ß½«óáα∩ 4 ¬¿½«íá⌐Γá, τΓ« »«ºó«½¿½« ¼¿¡¿¼¿º¿α«óáΓ∞
ΓαÑí«óá¡¿∩ ¬ »á¼∩Γ¿ íѺ ßπΘÑßΓóÑ¡¡δσ »«ΓÑα∞ ¡á ßΓѻѡ¿ ߪáΓ¿∩.  ä½∩
¬«ñ¿α«óá¡¿∩ ñ½¿¡ ¿ αáßßΓ«∩¡¿⌐ ¿ß»«½∞º«óὫß∞ ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ
òáΣΣ¼Ñ¡á ß« ߻ѵ¿á½∞¡« »«ñ«íαá¡¡δ¼ ¬«ñ«óδ¼ ñÑαÑó«¼, «»Γ¿¼¿º¿α«óá¡¡δ¼
ñ½∩ ΓѬßΓ«óδσ Σá⌐½«ó.  èα«¼Ñ Γ«ú«, íδ½ ¿ß»«½∞º«óá¡ íδßΓαδ⌐
íá⌐Γ-«α¿Ñ¡Γ¿α«óá¡¡δ⌐ á½ú«α¿Γ¼ αá߻ᬫó¬¿, »«ºó«½∩εΘ¿⌐ π¼Ñ¡∞Φ¿Γ∞ τ¿ß½«
»«í¿Γ«óδσ »ÑαÑß佫¬ ¿ ß««ΓóÑΓßΓóÑ¡¡« πóѽ¿τ¿Γ∞ ߬«α«ßΓ∞ αáí«Γδ.

    æΓáΓ¿ßΓ¿¬á, ß«íαá¡¡á∩ »α¿ αáºαáí«Γ¬Ñ »α«úαá¼¼δ, »«¬áºá½á, τΓ«
í«½ÑÑ 97% óßÑσ «í¡áαπªÑ¡¡δσ µÑ»«τѬ ¿¼ÑεΓ ñ½¿¡π, ¡Ñ »αÑó«ßσ«ñ∩Θπε 16
ß¿¼ó«½«ó. ¥Γ« »«ºó«½¿½« íѺ ßπΘÑßΓóÑ¡¡δσ »«ΓÑα∞ ßΓѻѡ¿ ߪáΓ¿∩ «í«⌐Γ¿ß∞
íδßΓαδ¼ ñÑαÑó«¼ ß 16 ½¿ßΓ∞∩¼¿. ûÑ»«τ¬¿ ß ñ½¿¡«⌐ len, úñÑ len >= 16,
¬«ñ¿α«ó὿ß∞ ¬á¬ µÑ»«τ¬¿ ñ½¿¡δ 16 ß »«ß½ÑñπεΘ¿¼ ñ«»«½¡¿Γѽ∞¡δ¼ íá⌐Γ«¼
"αáßΦ¿αÑ¡¿∩ ñ½¿¡δ" ß« º¡áτÑ¡¿Ñ¼ (len - 16).

    äá½ÑÑ, ñ½∩ αáßßΓ«∩¡¿⌐ (distances) µÑ»«τѬ ¬«ñ¿α«ó὿ß∞ ¿σ
ßΓáαΦ¿Ñ íá⌐Γδ, º¡áτÑ¡¿∩ ¬«Γ«αδσ ¡áσ«ñ¿½¿ß∞ ó ñ¿á»áº«¡Ñ [0..15] (óó¿ñπ
αẼÑαá íπΣÑαá 4096 íá⌐Γ). î½áñΦ¿Ñ íá⌐Γδ ¡Ñ ¬«ñ¿α«ó὿ß∞ óó¿ñπ
ßαáó¡¿Γѽ∞¡« ¡Ñí«½∞Φ«ú« "𬽫¡á" αáß»αÑñѽѡ¿∩ τáßΓ«Γ.

    Äñ¿¡«τ¡δÑ ß¿¼ó«½δ (µÑ»«τ¬¿ ñ½¿¡δ 1) ¬«ñ¿α«ó὿ß∞ ¬á¬ µÑ»«τ¬¿
ñ½¿¡δ 1 ß »«ß½ÑñπεΘ¿¼ íá⌐Γ«¼, ß«ñÑαªáΘ¿¼ ßá¼ ß¿¼ó«½. æ½ÑñπÑΓ «Γ¼ÑΓ¿Γ∞,
τΓ« µÑ»«τ¬¿ ñ½¿¡δ 2 ¬«ñ¿α«ó὿ß∞ ¿¼Ñ¡¡« ¬á¬ µÑ»«τ¬¿, á ¡Ñ ¬á¬ ñóÑ
«Γñѽ∞¡δÑ ½¿ΓÑαδ. ¥Γ« ñáóὫ ßαÑñ¡¿⌐ óδ¿úαδΦ ó 3 í¿Γá ¡á ß¿¼ó«½: (2 + 8
+ 2 + 8) = 20 í¿Γ »α¿ 2 µÑ»«τ¬áσ »« 2 ß¿¼ó«½á ¿ (2 + 4 + 8) = 14 í¿Γ
»α¿ «ñ¡«⌐ ñδπσß¿¼ó«½∞¡«⌐ µÑ»«τ¬Ñ. äá½ÑÑ, ¡Ñí«½∞Φá∩ ¼«ñ¿Σ¿¬áµ¿∩
á½ú«α¿Γ¼á »«¿ß¬á ß«ó»áñáεΘ¿σ »«ñßΓ᫬ »«ºó«½¿½á φΣΣÑ¬Γ¿ó¡« π»á¬«óδóáΓ∞
ßÑα¿¿ »«óΓ«α∩εΘ¿σß∩ µÑ»«τѬ ß¿¼ó«½«ó:  »α¿ »«¿ß¬Ñ ß¿¼ó«½«ó ó íπΣÑαÑ
¿ß¬«¼á∩ µÑ»«τ¬á ¡Ñ∩ó¡« ñ«óáó½∩½áß∞ ó ¬«¡Ñµ íπΣÑαá:  ¡á»α¿¼Ñα, µÑ»«τ¬á
"abcabcabcabcabc" ¬«ñ¿α«óá½áß∞ ¬á¬ (1, "a"), (1, "b"), (1, "c"), (12,
3) -- Σá¬Γ¿τÑ߬¿ τÑαѺ «íαáΘÑ¡¿Ñ ¬ ßἫ⌐ ßÑíÑ ß« ßñó¿ú«¼ ¡á 3 ß¿¼ó«½á.



.te 1 .ce ÉÑ὿ºáµ¿∩ ¿ ßΓαπ¬Γπαá »α«úαá¼¼δ


    æªáΓ¿Ñ óσ«ñ¡«ú« »«Γ«¬á «ßπΘÑßΓó½∩ÑΓß∩ Σπ¡¬µ¿Ñ⌐ SquoPack(),
»«½πτáεΘÑ⌐ ¡á óσ«ñÑ áñαÑßá »«½∞º«óáΓѽ∞߬¿σ Σπ¡¬µ¿⌐ óó«ñá-óδó«ñá.
Äß¡«ó¡«⌐ µ¿¬½ »α«úαá¼¼δ ¼«ªÑΓ íδΓ∞ »αÑñßΓáó½Ñ¡ ß½ÑñπεΘ¿¼ «íαẫ¼:


SquoPack()    {
    Init (); // init dictionary, trees, and output bit buffer

    while (not EOF)    {
        int    length;
        int    distance;

        FindMatch (&length, &distance);
        // scan input and find longest string in dictionary
        // which matches with it; record its length and distance
        // from the end of dictionary.

        EncodeLength (length);
        EncodeDistance (distance);

        UpdateDictionary (length);
        // this discards first 'length' chars
        // from the beginning of dictionary
        // and reads next characters from input
    }

    Done (); // output EOF marker and flush output buffers.
}


    潫óáα∞ (dictionary) «íÑß»Ñτ¿óáÑΓ σαá¡Ñ¡¿Ñ 4096 »«ß½Ññ¡¿σ
ßτ¿Γá¡¡δσ ß¿¼ó«½«ó, ñ« 271(=16+255) ó¡«ó∞ »«ßΓπ»¿óΦ¿σ ¡á óσ«ñ ß¿¼ó«½«ó
¿ íδßΓαδ⌐ »«¿ß¬ »«ñßΓ᫬¿, ß«ó»áñáεΘÑ⌐ ß óσ«ñ¡«⌐. Åα¿ αÑ὿ºáµ¿¿ í佫
¿ß»«½∞º«óá¡« σÑΦ¿α«óá¡¿Ñ ß αáºαÑΦÑ¡¿Ñ¼ ¬«¡Σ½¿¬Γ«ó »πΓѼ σαá¡Ñ¡¿∩
«ñ¡«ßó∩º¡δσ ß»¿ß¬«ó.

    äÑ⌐ßΓó¿Ñ FindMatch αÑ὿º«óá¡« ¡Ñ»«ßαÑñßΓóÑ¡¡« ó Σπ¡¬µ¿¿
SquoPack(); ñÑ⌐ßΓó¿Ñ UpdateDictionary αÑ὿º«óá¡« Σπ¡¬µ¿Ñ⌐ MoveBuf().
è«ñ¿α«óá¡¿Ñ ñ½¿¡ ¿ αáßßΓ«∩¡¿⌐ ¿ óδó«ñ »«½πτÑ¡¡δσ ¬«ñ«ó «ßπΘÑßΓó½∩εΓ
ß««ΓóÑΓßΓóÑ¡¡« Σπ¡¬µ¿¿ PutLen() ¿ PutDist(). Ä¡¿, ó ßó«ε «τÑαÑñ∞,
«íαáΘáεΓß∩ ¬ Σπ¡¬µ¿∩¼ PutBits() ¿ PutByte() ñ½∩ »«íá⌐Γ¡«⌐ íπΣÑα¿ºáµ¿¿
óδó«ñ¿¼δσ µÑ»«τѬ í¿Γ. Åα¿¼Ñ¡Ñ¡á ñ¿¡á¼¿τÑ߬á∩ »ÑαÑßΓá¡«ó¬á óÑαΦ¿¡
ñÑαÑóá òáΣΣ¼Ñ¡á »« ¼«ñ¿Σ¿µ¿α«óá¡¡«¼π á½ú«α¿Γ¼π "ßΓ«»¬¿ ¬¡¿ú" (ß¼.
[É∩í¬«]).

    Éá߻ᬫóΘ¿¬ »αá¬Γ¿τÑ߬¿ »«½¡«ßΓ∞ε αÑ὿º«óá¡ ¡á
ó ó¿ñÑ «ñ¡«⌐ áßßѼí½Ñα¡«⌐ Σπ¡¬µ¿¿ _SquoUnpack.



.te 1 .ce Åα«Σ¿½¿α«óá¡¿Ñ ¿ «»Γ¿¼¿ºáµ¿∩


    ÅÑαó«¡áτá½∞¡á∩ óÑαß¿∩ π»á¬«óΘ¿¬á íδ½á ¡á»¿ßá¡á ¿ «Γ½áªÑ¡á
»αá¬Γ¿τÑ߬¿ »«½¡«ßΓ∞ε ¡á ß¿ (αá߻ᬫóΘ¿¬ íδ½ ß ßἫú« ¡áτá½á íδ½
αÑ὿º«óá¡ ¡á áßßѼí½ÑαÑ). ǡ὿º αѺπ½∞ΓáΓ«ó »α«Σ¿½¿α«óá¡¿∩ »«ºó«½¿½
ºá ßτÑΓ «»Γ¿¼¿ºáµ¿¿ Σπ¡¬µ¿⌐ PutLen() ¿ PutDist() ¿ »ÑαÑñѽ¬¿ Σπ¡¬µ¿¿
UpdateHash() ó ¼á¬α«ß π¼Ñ¡∞Φ¿Γ∞ óαѼ∩ ߪáΓ¿∩ »α¿¼Ñα¡« ¡á 18%.  äá½ÑÑ,
ßΓáΓ¿ßΓ¿¬á »«¬áºá½á, τΓ« ßΓ᫬¿ ñ½¿¡«⌐ 2, 3 ¿ 4 ß¿¼ó«½á ß«ßΓáó½∩εΓ
«¬«½« 75% «íΘÑú« ¬«½¿τÑßΓóá (¡Ñ ßτ¿Γá∩ ßΓ᫬ ñ½¿¡δ 1, Γ.Ñ.  «ñ¿¡«τ¡δσ
ß¿¼ó«½«ó).  ÅÑαÑσ«ñ ¬ ñαπú«¼π ¼ÑΓ«ñπ σÑΦ¿α«óá¡¿∩ (»« τÑΓδαѼ »Ñαóδ¼
ß¿¼ó«½á¼) »«ºó«½¿½ ñ«»«½¡¿Γѽ∞¡« πóѽ¿τ¿Γ∞ ߬«α«ßΓ∞ αáí«Γδ »α«úαá¼¼δ ¿
π¼Ñ¡∞Φ¿Γ∞ ΓαÑí«óá¡¿∩ ¬ »á¼∩Γ¿.  äá½∞¡Ñ⌐Φá∩ «»Γ¿¼¿ºáµ¿∩ ßó∩ºá¡á ß
»ÑαÑ»¿ßδó᡿Ѽ ¬α¿Γ¿τ¡δσ »« óαѼѡ¿ πτáßΓ¬«ó ¬«ñá ¡á ∩ºδ¬ áßßѼí½Ñαá
(¼«ñπ½∞ αáß»á¬«ó¬¿ íδ½ ¡á»¿ßá¡ ¡á áßßѼí½ÑαÑ ¿º¡áτá½∞¡«).

    Åα«Γ«¬«½, ß«ñÑαªáΘ¿⌐ αѺπ½∞ΓáΓδ »α«í¡δσ ºá»π߬«ó »α«úαá¼¼δ,
á Γá¬ªÑ á Γá¬ªÑ «ΓτÑΓ »α«Σ¿½¿α«óΘ¿¬á, »α¿óÑñÑ¡ ó τáßΓ¿ 2.



.te 1 .ce Éπ¬«ó«ñßΓó« »«½∞º«óáΓѽ∩


諼»¿½∩µ¿∩ ¿ ßí«α¬á:
====================

    Å«½∞º«óáΓÑ½ε »αÑñ½áúáεΓß∩ ñóÑ Σπ¡¬µ¿¿, »«ºó«½∩εΘ¿Ñ αÑ὿º«óáΓ∞
ß««ΓóÑΓßΓóÑ¡¡« π»á¬«ó¬π ¿ αá߻ᬫó¬π ñó«¿τ¡δσ »«Γ«¬«ó ñá¡¡δσ (Γ.Ñ.,
ߪáΓ¿Ñ »α¿ ¿ß»«½∞º«óá¡¿¿ »«ß½Ññ«óáΓѽ∞¡«ú« óó«ñá-óδó«ñá). Ä»¿ßá¡¿∩
Σπ¡¬µ¿⌐ ¡áσ«ñ∩Γß∩ ó Σá⌐½Ñ squo.h, «»αÑñѽѡ¿∩ -- ó Σá⌐½áσ squo.c,
lzp.asm, lzu.asm. ä½∩ ßí«α¬¿ »α«úαá¼¼δ »½∞º«óáΓѽ∩ ¡Ñ«íσ«ñ¿¼«
á«ñ¬½ετ¿Γ∞ ß««ΓóÑΓßΓóπεΘ¿Ñ «í∞Ñ¬Γ¡δÑ ¼«ñ㫨 (squo.obj, lzp.obj,
lzu.obj).  ä½∩ ¬«¼»¿½∩µ¿¿ φΓ¿σ «í∞Ñ¬Γ¡δσ ¼«ñπ½Ñ⌐ ¡Ñ«íσ«ñ¿¼δ Σá⌐½δ
style.h, squo.h, squo.c, lz.asi, lzp.asm, lzu.asm.  ÆÑßΓ«óá∩ »α«úαá¼¼á
(»α«ßΓÑ⌐Φ¿⌐ π»áÑ«óΘ¿¬ ñ½∩ Σá⌐½«ó, á¡á½«ú¿τ¡δ⌐ compress) ¡áσ«ñ¿Γß∩ ó
Σá⌐½Ñ squotest.c.

    Åα¿ αáºαáí«Γ¬Ñ, «Γ½áñ¬Ñ ¿ ΓÑßΓ¿α«óá¡¿¿ ¿ß»«½∞º«óá½ß∩ ¬«¼»¿½∩Γ«α
Turbo C 2.01, ¼«ñѽ∞ »á¼∩Γ¿ compact. ÅÑαÑ¡«ß »α«úαá¼¼δ ¡á ñαπú«⌐
ß¿-¬«¼»¿½∩Γ«α ñ½∩ MS-DOS ¡Ñ ñ«½ªÑ¡ »αÑñßΓáó½∩Γ∞ ß½«ª¡«ßΓÑ⌐; ñ½∩ ñαπú¿σ
áασ¿ΓѬΓπα, «τÑó¿ñ¡«, »«¡áñ«í¿Γß∩ »ÑαÑ»¿ßδóá¡¿Ñ ¼«ñπ½Ñ⌐ ¡á ∩ºδ¬Ñ
áßßѼí½Ñαá. ū߬«½∞¬π ¿σ «íΩѼ ¡Ñóѽ¿¬, á Σπ¡¬µ¿¿ Γα¿ó¿á½∞¡δ, φΓ« ΓᬪÑ
¡Ñ ñ«½ª¡« óδºδóáΓ∞ í«½∞Φ¿σ Γαπñ¡«ßΓÑ⌐. é ¡áßΓ«∩ΘÑÑ óαѼ∩ áóΓ«α αáí«ΓáÑΓ
¡áñ UNIX-¼«í¿½∞¡«⌐ óÑαß¿Ñ⌐ »α«úαá¼¼δ.


ê¡ΓÑαΣÑ⌐ß ó맮óá:
=================

#include "squo.h"

extern    int    SquoPack (ReadFunc *reader, WriteFunc *writer);

extern    int    SquoUnpack (ReadFunc *reader, WriteFunc *writer);


髺óαáΘáѼ«Ñ º¡áτÑ¡¿Ñ:
======================

    ¥¡áτÑ¡¿Ñ 0 «í«º¡áτáÑΓ πß»ÑΦ¡«Ñ ºáóÑαΦÑ¡¿Ñ, 1 -- ¡Ñπß»ÑΦ¡«Ñ.


Åáαá¼ÑΓαδ:
==========

    Åáαá¼ÑΓαδ reader ¿ writer -- ß««ΓóÑΓßΓóÑ¡¡« π¬áºáΓѽ¿ ¡á
Σπ¡¬µ¿¿ óó«ñá ¿ óδó«ñá, «»αÑñѽ∩ѼδÑ »«½∞º«óáΓѽѼ. ä½∩ Σπ¡¬µ¿¿
SquoPack, ¡á»α¿¼Ñα, reader ñ«½ªÑ¡ »«ßΓáó½∩Γ∞ ¡Ñπ»á¬«óá¡¡δÑ ñá¡¡δÑ
(߬áªÑ¼, »ÑαÑñáóáΓ∞ ¿σ ¿º ¼áßß¿óá ó »á¼∩Γ¿), á Σπ¡¬µ¿¿ writer φΓ¿
ñá¡¡δÑ íπñπΓ »ÑαÑñá¡δ πªÑ π»á¬«óá¡¡δ¼¿ (¡á»α¿¼Ñα, ñ½∩ ºá»¿ß¿ ó Σá⌐½).
Å«ñα«í¡«ßΓ¿ -- ó ñѼ«¡ßΓαᵿ«¡¡«¼ »α¿¼ÑαÑ squotest.c.

    Æ¿»δ ReadFunc ¿ WriteFunc «»¿ßá¡δ ó ºáú«½«ó«τ¡«¼ Σá⌐½Ñ squo.h:

typedef    size_t    ReadFunc (void * buffer, size_t size);
typedef    size_t    WriteFunc (void * buffer, size_t size);

    ReadFunc τ¿ΓáÑΓ (WriteFunc ß««ΓóÑΓßΓóÑ¡¡« ºá»¿ßδóáÑΓ) size íá⌐Γ
(size <= 65535) »« áñαÑßπ buffer. 髺óαáΘáѼ«Ñ º¡áτÑ¡¿Ñ -- τ¿ß½«
»α«τ¿Γá¡¡δσ (ºá»¿ßá¡¡δσ) íá⌐Γ.


ÄΦ¿í¬¿:
=======

    é ¡áßΓ«∩ΘÑ⌐ óÑαß¿¿ ¿ú¡«α¿απεΓß∩ «Φ¿í¬¿ óδó«ñá »α¿ π»á¬«ó¬Ñ ¿
αá߻ᬫó¬Ñ. é»α«τѼ, »«ñ«í¡δÑ ßαÑñßΓóá ¼«úπΓ íδΓ∞ αÑ὿º«óá¡δ ó
»α«úαá¼¼Ñ »«½∞º«óáΓѽ∩. Éá߻ᬫóΘ¿¬ ¡Ñ ¬«¡Γα«½¿απÑΓ »αáó¿½∞¡«ßΓ∞
óσ«ñ¡δσ ñá¡¡δσ (¡Ñ«ª¿ñá¡¡«Ñ «¬«¡τá¡¿Ñ óó«ñá).




.te 1 .ce êß»«½∞º«óá¡¡δÑ ¿ßΓ«τ¡¿¬¿


èα¿τÑó߬¿⌐, É.à. æªáΓ¿Ñ ¿ »«¿ß¬ ¿¡Σ«α¼áµ¿¿. - î.: Éáñ¿« ¿ ßó∩º∞, 1989.
ÆÑ«αÑΓ¿τÑ߬á∩ αáí«Γá, »«ßó∩ΘÑ¡¡á∩ ΓÑ«α¿¿ ¬«ñ¿α«óá¡¿∩ ¿ßΓ«τ¡¿¬á.
æ«ñÑαª¿Γ ¼¡«ú¿Ñ ó᪡δÑ αѺπ½∞ΓáΓδ, ó Γ«¼ τ¿ß½Ñ «µÑ¡¬¿ ß½«ª¡«ßΓ¿
á½ú«α¿Γ¼«ó ¬«ñ¿α«óá¡¿∩. ü«½∞Φ«Ñ ó¡¿¼á¡¿Ñ πñѽѡ« π¡¿óÑαßá½∞¡δ¼ ¬«ñá¼.

É∩í¬« ü.ƒ. æªáΓ¿Ñ ¿¡Σ«α¼áµ¿¿ ß »«¼«Θ∞ε ßΓ«»¬¿ ¬¡¿ú // Åα«í½Ñ¼δ »ÑαÑñáτ¿
¿¡Σ«α¼áµ¿¿. - 1980. - Æ.16, N.4. - æ. 16-21. ÅÑαó«Ñ «»¿ßá¡¿Ñ ½«¬á½∞¡«
áñá»Γ¿ó¡«ú« ¼ÑΓ«ñá ßΓ«»¬¿ ¬¡¿ú.

ÿÑ¡¡«¡ è. Éáí«Γδ »« ΓÑ«α¿¿ ¿¡Σ«α¼áµ¿¿ ¿ ¬¿íÑα¡ÑΓ¿¬Ñ. - î.: êï, 1963.
꺽«ªÑ¡δ ¬½áßß¿τÑ߬¿Ñ αѺπ½∞ΓáΓδ ΓÑ«α¿¿ ¿¡Σ«α¼áµ¿¿.

Abramson, N. Information Theory and Coding. McGraw-Hill, New York,
1963. ÅÑαóá∩ ßßδ½¬á ¡á ¼ÑΓ«ñ, »«ºªÑ ¡áºóá¡¡δ⌐ áα¿Σ¼ÑΓ¿τÑ߬¿¼
¬«ñ¿α«ó᡿Ѽ (ßΓα. 61-62).

Bell, T.C. IEEE Trans. COM-34, pp. 1176-1182 (1986).
Åα¿¼Ñ¡Ñ¡¿Ñ ñó«¿τ¡«ú« ñÑαÑóá »«¿ß¬á ¬ á½ú«α¿Γ¼π ïѼ»Ñ½∩-ç¿óá.

Bentley, J.L., Sleator, D.D., Tarjan, R.E., Wei, V.K. A locally
adaptive data compression scheme. Commun. ACM 29, 4 (Apr. 1986),
320-330. Ä»¿ßá¡ ½«¬á½∞¡« áñá»Γ¿ó¡δ⌐ á½ú«α¿Γ¼ ߪáΓ¿∩, ¿ß»«½∞ºπεΘ¿⌐
φóα¿ßΓ¿¬π "ñó¿úá⌐ óóÑασ" (á½ú«α¿Γ¼ ßΓ«»¬¿ ¬¡¿ú É∩í¬«).

Gallager, R.G. Variations on the theme by Huffman. IEEE Trans. Inf.
Theory IT-24, 6 (Nov. 1978), 668-674. ¥ΣΣÑ¬Γ¿ó¡δ⌐ á½ú«α¿Γ¼ áñá»Γ¿ó¡«ú«
¬«ñ¿α«óá¡¿∩ òáΣΣ¼Ñ¡á.

Huffman, D.A. A method for the construction of minimum-redundancy
codes. Proc. Inst. Electr. Radio Eng. 40, 9 (Sept. 1952), 1098-1101.
è½áßß¿τÑ߬á∩ αáí«Γá, ó»ÑαóδÑ «»¿ßδóáεΘá∩ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

Hunter, R. and Robinson, A.H. International digital fscsimile coding
standarts. Proc. Inst. Electr. Electron. Eng, 68, 7 (July 1980),
854-867. Ä»¿ßá¡« »α¿½«ªÑ¡¿Ñ ¬«ñ¿α«óá¡¿∩ òáΣΣ¼Ñ¡á ¬ ߪáΓ¿ε ñ½¿¡ ßÑα¿⌐ ó
τÑα¡«-íѽδσ ¿º«íαáªÑ¡¿∩σ.

Knuth, D.E. Dynamic Huffman coding. J. Algorithms 6, 2 (Feb. 1985),
163-180. Åαá¬Γ¿τÑ߬á∩ αÑ὿ºáµ¿∩ ½«¬á½∞¡« áñá»Γ¿ó¡«ú« ¬«ñ¿α«óá¡¿∩
òáΣΣ¼Ñ¡á.

Rissanen, J.J. Arithmetic codings as number representations. Acta
Polytech. Scand. Math. 31 (Dec. 1979), 44-51. äá½∞¡Ñ⌐ΦÑÑ αáºó¿Γ¿Ñ ¿ñÑ⌐
áα¿Σ¼ÑΓ¿τÑ߬«ú« ¬«ñ¿α«óá¡¿∩.

Rissanen, J., and Langdon, G.G. Universal modelling and coding. IEEE
Trans. Inf. Theory IT-27, 1 (Jan 1981), 12-23. Å«¬áºá¡á 󫺼«ª¡«ßΓ∞
αáºñѽѡ¿∩ ߪáΓ¿∩ ñá¡¡δσ ¡á ¼«ñѽ¿α«óá¡¿Ñ ¿ ¬«ñ¿α«óá¡¿Ñ.

Rubin, F. Arithmetic stream coding using fixed precision registers.
IEEE Trans. Inf. Theory IT-25, 6 (Nov. 1979), 672-675. Äñ¡á ¿º »Ñαóδσ
αáí«Γ, ó¬½ετáεΘá∩ óßÑ ¡Ñ«íσ«ñ¿¼δÑ φ½Ñ¼Ñ¡Γδ áα¿Σ¼ÑΓ¿τÑ߬«ú« ¬«ñ¿α«óá¡¿∩:
óδτ¿ß½Ñ¡¿∩ ß Σ¿¬ß¿α«óá¡¡«⌐ Γ«τ¬«⌐ ¿ ¿¡¬αѼѡΓá½∞¡á∩ αáí«Γá á½ú«α¿Γ¼á.

Vitter, J.S. Two papers on dynamic Huffman codes. Tech. Rep. CS- 85-13.
Brown University Computer Science. Providence, R.I. Revised Dec. 1986.
Ä»Γ¿¼á½∞¡«Ñ áñá»Γ¿ó¡«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

Welch, T.E. A technique for high-perfomance data compression.  IEEE
Comput. 17, 6 (June 1984), 8-19. Ä»¿ßá¡ íδßΓαδ⌐ á½ú«α¿Γ¼ ߪáΓ¿∩ ñá¡¡δσ,
¡Ñ «Γ½¿τáεΘ¿⌐ß∩, «ñ¡á¬«, óδß«¬¿¼ ¬áτÑßΓó«¼ ßªáΓ¿∩. ǽú«α¿Γ¼ ¿ºóÑßΓÑ¡
¬á¬ LZW (Lempel-Ziv-Welch compression) ¿ ñ«ßΓáΓ«τ¡« »«»π½∩αÑ¡
(úαáΣ¿τÑ߬¿⌐ Σ«α¼áΓ GIF, ¼ÑΓ«ñ shrinking »α«úαá¼¼δ PKZIP).

Witten, I.H., Neal, R.M., and Cleary, J.G. Arithmetic coding for data
compression. Commun. ACM 30, 6 (June 1987), 520-540. è½áßß¿τÑ߬á∩
αáí«Γá »« áα¿Σ¼ÑΓ¿τÑ߬«¼π ¬«ñ¿α«óá¡¿ε.

Ziv, J., and Lempel, A. Compression of individual sequences via
variable-rate coding. IEEE Trans. Inf. Theory IT-24, 5 (Sept. 1978),
530-536. Ä»¿ßá¡ ¼ÑΓ«ñ ߪáΓ¿∩, ºá¼Ñ¡∩εΘ¿⌐ »«ñßΓ᫬π ΓѬßΓá π¬áºáΓѽѼ ¡á
ÑÑ í«½ÑÑ αá¡¡ÑÑ óσ«ªñÑ¡¿Ñ. ìá φΓ¿σ ¿ñÑ∩σ «ß¡«óá¡« í«½∞Φ¿¡ßΓó«
»αá¬Γ¿τÑ߬¿ ¿ß»«½∞ºπѼδσ »α«úαá¼¼ ߪáΓ¿∩ ñá¡¡δσ.



.te 1 .ce Åα¿½«ªÑ¡¿Ñ Ç. Äíº«α »α«úαá¼¼ ߪáΓ¿∩ ñ½∩ MS-DOS.


    é ß½ÑñπεΘÑ⌐ Γáí½¿µÑ ß«ñÑαªáΓß∩ αѺπ½∞ΓáΓδ ΓÑßΓ¿α«óá¡¿∩
»α«úαá¼¼δ ¡á ¡Ñ߬«½∞¬¿σ Σá⌐½áσ. ä½∩ ßαáó¡Ñ¡¿∩ »α¿óÑñÑ¡δ αѺπ½∞ΓáΓδ
ñ½∩ ΓαÑσ »«»π½∩α¡δσ áασ¿óáΓ«α«ó ñ½∩ MS-DOS. ïÑóá∩ ¬«½«¡¬á ß«ñÑনΓ
ñ½¿¡π ߪáΓ«ú« Σá⌐½á, »αáóá∩ -- «Γ¡«ΦÑ¡¿Ñ αẼÑαá ߪáΓ«ú« Σá⌐½á ¬
αẼÑαπ «α¿ú¿¡á½∞¡«ú« Σá⌐½á. öá⌐½ squo.c »αÑñßΓáó½∩ÑΓ ß«í«⌐
¿ßσ«ñ¡δ⌐ ΓѬßΓ «ñ¡«ú« ¿º ¼«ñπ½Ñ⌐ «»¿ßδóáѼ«⌐ »α«úαá¼¼δ, Σá⌐½ mawk.doc
-- ΓѬßΓ ¡á á¡ú½¿⌐߬«¼ ∩ºδ¬Ñ, Σá⌐½ sos.doc -- ΓѬßΓ ¡á απß߬«¼ ∩ºδ¬Ñ.
é ¬«½«¡¬Ñ 'Original' »α¿óÑñÑ¡δ αẼÑαδ ¡Ñπ»á¬«óá¡¡δσ Σá⌐½«ó.


Filename   Original SquoTest 1.5 PKZIP 1.0   LHA 2.13     ARJ 2.30
---------  -------- ------------ ----------- ------------ -----------
SQUO.C        17821    5876  33%   5371  30%   5148  29%    5089  29%
MAWK.DOC      42961   17108  40%  15359  35%  15122  35%   14713  34%
SOS.DOC       28525   14373  50%  14356  50%  12957  45%   12500  44%


    äá½ÑÑ »α¿ó«ñ¿Γß∩ »ÑαÑτÑ¡∞ (φáóÑñ«¼« ¡Ñ»«½¡δ⌐) »α«úαá¼¼ ߪáΓ¿∩
ñ½∩ MS-DOS ß ¬αáΓ¬¿¼ π¬áºá¡¿Ñ¼ á½ú«α¿Γ¼«ó ¿σ αáí«Γδ ¿ ñá½∞¡Ñ⌐Φ¿¼¿
ßßδ½¬á¼¿.  ÇóΓ«α óδαáªáÑΓ í½áú«ñáα¡«ßΓ¿ Haruhiko Okumura ('Data
Compression Algorithms of LARC and LHarc'), Robert K Jung (ARJ archiver
documentation), PKWARE Inc. (PKZIP archiver documentation) φá
»αÑñ«ßΓáó½Ñ¡¡πε ¿¡Σ«α¼áµ¿ε.


PKPAK 3.61:

îÑΓ«ñ Packed -- á½ú«α¿Γ¼ RLE.
îÑΓ«ñ Crunched-- á½ú«α¿Γ¼ LZW.
îÑΓ«ñ Squashed -- ñóπσ»α«σ«ñ¡«Ñ ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

PKZIP 1.10:

îÑΓ«ñ Shrinked -- ¼«ñ¿Σ¿µ¿α«óá¡¡δ⌐ á½ú«α¿Γ¼ LZW ß τáßΓ¿τ¡«⌐ «τ¿ßΓ¬«⌐
ß½«óáα∩ ¿ »ÑαѼѡ¡«⌐ ñ½¿¡«⌐ ¬«ñá.

îÑΓ«ñ Imploded -- ¼«ñ¿Σ¿µ¿α«óá¡¡δ⌐ á½ú«α¿Γ¼ ïѼ»Ñ½∩-ç¿óá ¿
ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

LHArc:
ǽú«α¿Γ¼ ïѼ»Ññ∩-ç¿óá ¿ ñ¿¡á¼¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

LHA:
ǽú«α¿Γ¼ ïѼ»Ññ∩-ç¿óá ¿ ßΓáΓ¿τÑ߬«Ñ ¬«ñ¿α«óá¡¿Ñ òáΣΣ¼Ñ¡á.

ARJ:
ǽú«α¿Γ¼ ïѼ»Ñ½∩-ç¿óá ¿ «α¿ú¿¡á½∞¡δ⌐ ¼ÑΓ«ñ ¬«ñ¿α«óá¡¿∩ (¿ßΓ«τ¡¿¬:
áóΓ«α߬á∩ ñ«¬π¼Ñ¡Γᵿ∩).