Home > Zib library에서 사용하는 알고리즘 > Lempel-Ziv 알고리즘 > TABLES

 

 

<표1: 압축 알고리즘의 실행 결과>

 

루프패스

버퍼

C

전송

테이블

새 값

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

B

A

AB

A

AB

C

B

BA

B

BA

BAB

A

AB

ABC

B

BA

BAB

BABA

B

A

B

A

B

C

B

A

B

A

B

A

B

C

B

A

B

A

B

0(A에 대한 코드)

1(B에 대한 코드)

 

3(AB에 대한 코드)

 

3(AB에 대한 코드)

2(C에 대한 코드)

 

4(BA에 대한 코드)

 

 

8(BAB에 대한 코드)

 

 

6(ABC에 대한 코드)

 

 

 

9(BABA에 대한 코드)

AB(code=3)

BA(code=4)

 

ABA(code=5)

 

ABC(code=6)

CB(code=7)

 

BAB(code=8)

 

 

BABA(code=9)

 

 

ABCB(code=10)

 

 

 

BABAB(code=11)

B

A

AB

A

AB

C

B

BA

B

BA

BAB

A

AB

ABC

B

BA

BAB

BABA

B

 

 

< 표 2: 압축 알고리즘에 의해 생성되는 테이블 >

스트링

A

B

C

AB

BA

ABA

ABC

CB

BAB

BABA

ABCB

BABAB

BABC

CBA

코트

0

1

2

3

4

5

6

7

8

9

10

11

12

13

                     입력 문자열:  ‘ABABABCBABABABCBABABABCBA’
                     전송되는 코드: 0 1 3 3 2 4 8 6 9 8 7 0

 

 

< 표 3: 복원 알고리즘의 런타임 결과 >

 

루프 패스

Prior(스트링)

현재

(스트링)

테이블의

현재 코드

C

임시 스트링

/ 코드 쌍

인쇄 (현재 또는 임시 스트링)

1

2

3

4

5

6

7

8

9

10

11

0(A)

1(B)

2(AB)

3(AB)

2(C)

4(BA)

8(BAB)

6(ABC)

9(BABA)

8(BAB)

7(CB)

1(B)

3(AB)

3(AB)

2(C)

4(BA)

8

6(ABC)

9(BABA)

8(BAB)

7(CB)

0(A)

YES

YES

YES

YES

YES

NO

YES

YES

YES

YES

YES

B

A

A

C

B

B

A

B

B

C

A

AB/2

BA/4

ABA/5

ABC/6

CB/7

BAB/8

BABA/9

ABCB/10

BABAB/11

BABC/12

CBA/13

B (current)

AB (current)

AB (current)

C (current)

BA (current)

BAB (temp string)

ABC (current)

BABA (current)

BAB (current)

CB (current)

A (current)