				⨥ .

PreScriptum:	    饭 ଥ,  ⢮
  ଥ⢮ 易, ⮬  楫 ᥮饣 襭 ஢ 
 ࠧ ।⠢   ⥩ :)

 饬,    稭 ଥ⢮,  㬠   ࠡ
娢.  㬠  祣 㬭  ਤ㬠  㯨  
 "ଠ ᪨ ".   ࠭ ⠬  
筮   LZW,䬠,RLE  䬥᪮ ᦠ.
⮬ 㢨 Win32.LZSlow (SMT/SMF)  㢨  ⠬  LZW,  ⮨
LZ :)
 饬 訫 ࠧ.     襫  ,祬   
.

 
	1. ⨥ ᭮  ᫮
		a. LZ77
		b. LZSS
		c. LZ78
		d. LZW
	2.  ࠧ筮  
		a. ॢ -
		b. ॢ 䬠
	4. ⨥  稭 (RLE)
		a. Basic RLE
		b. PackBits

  䬥᪮ ᦠ⨥   ᬠਢ ⠪  쭮 ᫮ 
,  祭 㤭 ॠ㥬  ࠪ⨪.

	1. ⨥ ᭮  ᫮ 
  ⨯ ᦠ ᯮ     ᫮. 騩 ਭ樯
  ᫥⥫쭮   ⪨ 稭. 

	A. LZ77
 ਭ樯 ᦠ
  騪    (ன ࠭祭 )   
  ᫥⥫쭮 ᮢ  묨 㯠뢠묨  ⥪饩 樨
     室 㪠⥫   ᫥⥫쭮    
  ᮤঠ騩 - ᮢ .       ⠪ 
  ᫥⥫쭮,   ᫠  室 ⮪ 㫥 㪠⥫ 
   㫥 . LZ77 蠥  : ᫥  㪠⥫  뤠 
   ᨬ   ᫥ ᮢ襩 ᫥⥫쭮   뤠 
  㫥 㪠⥫  ᨬ  ⥪饩 樨. 饬  室  
  㪠⥫  ᫥⥫쭮, ᫥⥫쭮  . ᨬ.

  ᦠ:
    1. ⠭  ᦠ  室 ⮪
    2.    ᫥⥫쭮   ᦠ
    3. 뫠  뢮  (P,C)  ᫥騬 祭ﬨ
	 P - 㪠⥫  ᫥⥫쭮  ᮢ
	 C -  ᨬ   ᮢ
    4. ᫨     ।  ᦠ  1 ।  
	룠  2.
 ਬ ᦠ:
   Pos	123456789
   Char AABCBBABC
   
					뢮
	1	1	--		A	(0,0)A
	2	2	A		B	(1,1)B
	3	4	--		C	(0,0)C
	4	5	B		B	(2,1)B
	5	7	AB		C	(5,2)C

 ᯠ:
  ⠥  (P,C) 訬 ᫥⥫쭮  P  ᨬ C.
 
 ࠪ᪨ 砭:
  ஢ ᦠ 祭 宩   ⨯ ,  ᦠ⨥ 쭮
 ॡ⥫쭮  ᠬ ⥬,    ६.  㣮 ஭
 ᯠ 祭   祭 . ᯮ짮  .

	B. LZSS
   LZ77
  LZ77   室 ᫥⥫쭮  㤮⢮ ᫮,
  뫠 ᠬ ᨬ ᫥  㪠⥫.  襭 ᮤন
  筮  譨 ᨬ  ᯮ짮  ᫥. ࠢ.
  LZSS 蠥  ஡  - 㪠⥫ 뫠  室 ⮪ ᫨
   ᮢ襩 ᫥⥫쭮 > 祬  ᠬ 㪠⥫. ⢥
  ਩ ᯮ짮 .   ।   㪠⥫  

  ᦠ
	1. ⠭   砫 ᦨ 
	2.    ᫥⥫쭮    ᮢ
		 묨  ⥪饩 樨
		* P := 㪠⥫   ᫥⥫쭮
		* L :=  ᫥⥫쭮
	3. L >= MIN_LENGTH ?
		* . 뤠  室 (P,L)  ᤢ ⥪ 
		ᦠ  L ᨬ
		* . 뫠  室 ⥪騩 ᨬ  ᤢ 
		ᦠ  1.
	4. ᫨   ,   2

 ਬ
 
	Pos	1234567890
	Char	AABBCBBAAB

					室
	1	1		--		A
	2	2		A		A
	3	3		--		B
	4	4		B		B
	5	5		--		C
	6	6		BB		(3,2)
	7	8		AAB		(7,3)
	
 ᯠ
     ᦠ  ⠪    㯠,஢  ᥩ
  - ᨬ  㪠⥫  ᨬ   ᮮ⢥⢨   ଠ樥
 ᯠ뢠 .

 ࠢ  LZ77
   ᦨ   祬 LZ77 ਬ୮  묨 ॡﬨ 
   . ᯠ ⠪       LZ77. 
 
 樨
   ਭ樯 ᯮ     娢 (PkZip,ARJ,
 LHArc,ZOO, ). 筮  娢 ॠ ⮤  ᢮. 

  LZSS  㤠筮 ᪮஢  ⮤ ᦠ ᭮묨  ६
   (䬠,-),ਬ PkZip v.1.0 ᯮ짮 LZSS 
 樨  ᦠ⨥ -, ARJ  䬠 (᫥ ᨨ PkZip
  䬠)
 
	C. LZ78

 ⨥
   砫 ᦠ ᫮ .  ⮣   ᭨ ਭ樯 ᦠ,
 ।⠢  ᫮ 㦥 ᮤন  ப. 
     ப 㫥 .  ६ ᨬ  室 ⮪ 塞
   ப. 饬  ப  襬 ᫮. ᫨ ப 㦥 , 
 塞  ப ᫥騩 ᨬ  . ।  ⨣ ⮣ 
  ப . ᪠ P - ப  ᫥  ᨬ,
 C - ᫥  ᨬ.   뫠  室 ⮪ 
 ᮮ⢥騩 ப P  ᨬ C, 塞 P+C  ᫮.
 
 ᫨ ᫮    室 뫠 0  ᨬ C. 

   ᦠ
	1.  ᫮ , P -  ப
	2. C := ᫥騩 ᨬ  ⮪
	3. P+C   ᫮ ?
		a. . P := P+C
		b. 
			i.   뫠  쥪  室
			   *  ⢥騩 ப P  ᫮  0
			   *  , ⠪      室 ⮪
			ii.  塞 ப P+C  ᫮
			iii. 頥 P
	4.   ᨬ  ᦠ ?
		a. . 릮  2
		b. 
			i. ᫨ P -   ப,뫠  室
				P
			ii. 

 ᯠ
  砫 ᫮ . ⠥  - (K)  ᨬ(C). P := ப  ᫮
 ᮮ⢥ (K). 모뢠  室 P+C  塞  ᫮ P+C.

   ᯠ
	1.  
	2. W := ᫥騩 
	3. C := ᨬ ᫥騩  
	4. 뫠  室 ப.W (  ⮩)  ᨬ C
	5. 塞 ப.W+C  ᫮
	6.    ?
		i. .  2
		ii. . 

 ਬ
	Pos	123456789
	Char	ABBCBCABA

						室
	1	1		A		(0,A)
	2	2		B		(0,B)
	3	3		BC		(2,C)
	4	5		BCA		(3,A)
	5	8		BA		(2,A)

 祭
  襥 २⢮ । LZ77 - 㬥訫 - ࠢ ப 
  蠣 ᦠ. ⥯ ᦠ ਬ୮ 筠 LZ77.

	D. LZW
  ⮬ ⬥ ᯮ  ਭ樯 LZ78  ᫥騬 
	*  砫쭮 ᫮ ᮤঠ  ᨬ  0-255 (8)

 ⫨  ᦠ⨨
	* 쪮  ᫮   室.   ᫮  
    砫묨 祭ﬨ.
	*     ᨬ ப 㦥  ᫮,  
 横 ᦠ ᯮ ⮢ 䨪.ப    ᫮
   2 .
	*  ᤥ ⠪, ᫮  ᯠ ४  
 譨   ⮪.

  ᦠ
	1.  砫 ᫮ ᮤন   ୨ (256 ᨬ)  ப
		P - 
	2. C := ᫥騩 ᨬ  室 ⮪
	3. ப P+C 室  ᫮ ?
		a. ᫨ , P := P+C
		b. 
			i.   뤠  室  ᮮ⢥騩 ப P
			ii.  塞 P+C  ᫮
			iii. P := C (P ᮤন  ᨬ C)
	4.    ?
		a. .  2
		b. . 
			i.   뤠  室   P
			ii.  The End

 ਭ樯 ᯠ
   砫 ᫮ ᮤন ⥦ 256 ᨬ. 
  ।  ᫮ ᮤন ⥫쭮 ᪮쪮  ⮢ 
 ப.   ।饥  ᫮ (pW)  ⠥ ⥪饥
  ᫮(cW), 뫠  室 ப ᮮ⢥ cW. ⮬
   ᫮ ப.pW+ ᨬ ப.cW. ⢥   
 ⥫ ᨬ  LZ78.  ਭ樯, ᮧ ᫮  ᯠ
 ᥣ   蠣 ࠭ 祬 ᮧ ᫮  㯠.
  ᮡ 砩 ந室  cW  ᮤন  ᫮.   
  ⮬  ᮧ ᫮  ᯠ  ⠫  ᫮
  㯠,稭 -   ᦠ ⠥ ப  ⮫쪮-
 뫠   ᫮.  ६ ᯠ  ப   
  ᫮. 襭 ⮥: ᫨ ப  ,  ६  ᨬ
 ।饩 ப  塞    ᨬ,뢠 稢訥 
 ᫮   室.
  
  ᯠ:
	1.  砫 ᫮ ᮤন  ୨ (256 ᨬ)
	2. cW :=    ⮪
	3. 뫠  室 ப.cW
	4. pW := cW
	5. cW := ᫥.   ⮪
	6. ப.cW   ᫮ ?
		* .
			i.    뫠  室 ப.cW
			ii.   P := ப.pW
			iii.  C :=  ᨬ ப cW
			iv.   訬 ப P+C  ᫮
		* 
			i.    P := ப.pW
			ii.   C :=  ᨬ ப.pW
			ii.     室 ப P+C  塞 
				 ᫮
	7.    ?
		* .  4
		* . The End

 ਬ

	⨥
	
	Pos	123456789
	Char	ABBABABAC

	砫 ᫮:	123
				ABC

						室
	1	1		(4)AB		(1)
	2	2		(5)BB		(2)
	3	3		(6)BA		(2)
	4	4		(7)ABA		(4)
	5	6		(8)ABAC		(7)
	6	--		--		(3)

	ᯠ

				室		
	1	(1)		A		--
	2	(2)		B		(4)AB
	3	(2)		B		(5)BB
	4	(4)		AB		(6)BA
	5	(7)		ABA		(7)ABA
	6	(3)		C		(8)ABAC

	᫥㥬 蠣 4. ।騩  (2) ࠭  pW  cW ᮤন 4.
	ப.cW ᮤন "AB". ப.pW ᮤন "B". ७ 
 	ᨬ ப.cW  ᫮  "BA"  ᮬ (6).
	  5 蠣. ন cW = (4)   pW   祭
	cW   ⮪.  ᫮ 7-   ,  ६
	ப.pW ("AB"),塞    ᨬ  ப ("A") 
	砥 "ABA"  ᮡ⢥  ࠭塞  ᫮   
	室.

 ࠪ᪨ 砭
   ⮤ 祭 ७  ࠪ⨪. २⢥ । ᥬ 
 LZ-᭮묨 ⬠  ᪮,⠪    ந ⢮
 ࠢ ப. 㣨 襭,⠪  ࠧ筠    ᨬ
  ࠧ ᫮,㤠 譨 ப  ,⮫쪮  ᦠ⨥.
 
  ⮤ ⥭஢  Unisys,   ࠧ蠥 ᢮
 ᯮ짮 ⬠  ᪨ 楫. ⭮ .蠫 ᯮ짮
 LZW :) ?
 
	2. ⨥ ᭮  ࠧ筮  
	
 ᭮  ᦠ -    ᨬ 襬  ⪨
        . ⮪  ⮤-
  室 ࠭ ॢ   㯠, १ 祣
   䠫 ⠭  .
	
	a. ⨥ -

	:

		I.  㥬 ᨬ  浪 ⠭
		II.     
		III.ࢮ  ᢠ 0  ன  1
		IV.   蠣 II,४ᨢ  稢訥   
			,     ⠭  1 

	ਬ: (ᨬ ஢  浪 뢠)

	ॢ			
	a-\_____/-0		00
	b-/  0  \-1		01
	c-\      ______/-0	100
	d-|     /  0   \-1	101
	e-\____/   ____/-0	1100
	f-/  1 \__/  0 \-1	1101
	g-|     1 \____/-0	1110
	h-/          1 \-1	1111

	ᯠ . ६ . ਬ  ॢ 㤠 .  塞
	  ⢨. 뢠 ᨬ ᮮ⢥騩  ⢨.  ⠪
	᭮   ⨣  ᯠ뢠 .

	b. ⨥ 䬠
	饬 祭 宦  ᦠ⨥  -,  ⨢
	ࠧ.
	
	ਭ樯 ᦠ:
	1. 砥 ଠ  ⥯ 砥 ⮣   ᨬ.
	2. ਬ ॢ  ᮮ⢥⢨  祭 ଠ樥
	3.   ᨬ  室 ⮪ 訬 ᮮ⢥騩 
		
	
	ਬ
	abbbcccddeeeeeeeeef
	
	 :	a:1,b:3,c:3,d:2,e:9,f:1
	ॢ:

		0/\1
	       /  (e)
	     /\1
	  0/   \
	 /    0/\1
       /     (b) (c)
    0/\1
   /   \
 (d)  0/\1
     (a) (f)  
	⢥ ᠬ 㯠 :
	a		=	0010
	b		=	010
	c		=	011
	d		=	000
	e		=	1
	f		=	0011
	
	ᯠ 筮 ॢ -.

	4. ⨥  稭 (RLE)
  ਭ樯 ᦠ ᭮  筮 :  aaaa 
 4a :)
	1. Basic RLE
	 ஢ ⮤. -  ᯮ  䨪.
  ਬ  = 0.  ᫥ ⮣    ᫮ . ᨬ,
  ᫥ ᫠ ᠬ ᨬ.      = 0, ᮡ⢥ ᫮
 () = 0  ।,᫥.  ᯮ짮   饭 ᠬ 0.
	ਬ:
	abbcbaaaaacb(0)(0)(0)(0)a(0)a
	(x) -   x- 祭
	:	a (0)(2)b cb (0)(5)a cb (0)(4)(0) a (0)(0) a

	2. PackBits
	⢥  ਭ樯 RLE ਤ Apple  198? .
	
	     ᮤন X. ᫨ X>127 ( 7 ⠭),   
  ⮬ ᫥ 1    X-128 ࠧ. ᫨   ⠭
    ⮬ ᫥ X , 묨 祣 ᤥ .

	ਬ:
	aaabcbdfaaabbbccc
	
	(128+3)a (5)bcbdf (128+3)a (128+3)b (128+3)c

 祭 ⮫-⮬ :)
  1. 祬 ᪨뢠 譨 ⠬ ?  室 ⮪ 訬  - 
      ஥   ⥪騩  室.
  2. 䬠  -    䠩 ( ⠪   ਤ㬠  
   ॢ -  砥 쭮 쥬,   ࠭
 㦭.)
  3.    ⠫ 䬠 ᤥ, ᦠ     室 :(  )
 䠩 業⮢  5 ⠭ .  ॢ ࠢ쭮 .
  -  ⨬ ஥ ?

  ⠪ . 砭  ।   xdeviator@yahoo.com

P.S.  ਫ  ਬ  ମ⮣ LZ78,  ࠡ饣 
     PackBits 㯠騪/ᯠ騪.

Deviator/HAZARD.
