알고리즘 ) lzw

 
 
 
압축률 계산 eof (압축 전후 둘다 포함인가 
 
압축 , 복원 원리 똑같
 
DA만 저장하고, DAB는 저장하지 않습니다. 말씀하신 대로 딱 새로운 것 하나(DA)만 등록하는 것이 맞습니다.
 
 ab rb올때(복원)

 

89다음 90아니고 8a임 

 

 

 

 
 

기존 압축 알고리즘의 한계와 비교

• 런레Length 압축 (RLE - Run-Length Encoding):
  • 동일한 문자나 데이터(예: 0 또는 1)가 연속적으로 길게 나타날 때 매우 효과적입니다.
  • 그러나 일반적인 텍스트 파일(아스키 코드가 산발적으로 나타나는 파일)에서는 문자가 무작위로 섞여 있어 연속적인 반복이 드물기 때문에 압축률이 현저히 떨어지거나 오히려 파일 크기가 커집니다.
• 허프만 압축 (Huffman Coding):
  • 문자의 출현 빈도수(Frequency)를 기반으로 압축을 수행합니다. 자주 등장하는 문자에는 짧은 비트의 코드를, 드물게 등장하는 문자에는 긴 비트의 코드를 할당하는 가변 길이 코드 방식입니다.
  • 단점: 압축 파일의 앞부분에 압축을 풀기 위한 '허프만 트리(Huffman Tree)' 또는 '코드 테이블' 메타데이터를 반드시 포함해야 합니다. 이 메타데이터가 파일 용량의 일정 부분을 차지하므로, 파일 크기가 작을 때는 오히려 허프만 압축 후의 파일 크기가 더 커지는 오버헤드가 발생합니다.
• LZW 압축 (Lempel-Ziv-Welch Coding):
  • 압축 단위의 확장: 문자 하나가 아닌, **여러 개의 문자열(집합)**을 단일 코드로 압축합니다. 자주 반복되는 문자열 패턴(예: abc, abcdef)을 하나의 W -비트 고정 길이 코드로 매핑합니다.
  • 메타데이터 배제: 압축 파일 내에 코드 테이블이나 트리를 저장할 필요가 없습니다. 압축을 진행하면서 코드 테이블을 동적으로 생성하고, 복원(Decompression)할 때도 압축 파일에 저장된 데이터 흐름을 읽으며 동일한 규칙으로 테이블을 실시간 복원하기 때문입니다.