LZW(Lempel-Ziv-Welch) 알고리즘

Jun 24, 2025

LZW(Lempel-Ziv-Welch) 알고리즘

Contents

🧠 작동 원리 요약 🔧 예시 📚 장점 vs 단점 💡 활용 예시

💡

무손실 압축 알고리즘 중 하나

데이터를 반복되는 문자열 단위로 압축

사전(dictionary)을 활용해 문자열을 코드로 치환

🧠 작동 원리 요약

1. 초기 사전 생성

입력에 나오는 모든 단일 문자를 포함한 사전 생성

예: A~Z까지 포함한 256개 문자 (ASCII 기준)

2. 문자열 분석 및 사전 확장

현재 문자열 w와 다음 문자 c를 붙인 w+c가

사전에 존재하면 → 계속 확장

존재하지 않으면

w의 코드 출력
w+c를 사전에 추가
w ← c로 갱신하여 계속 진행

3. 압축된 결과 출력

문자열을 숫자 코드로 치환하여 출력

압축 효율이 좋은 이유:

자주 나오는 패턴은 짧은 코드로 대체됨

🔧 예시

입력 문자열: ABABABA

처리 과정 요약:

단계	w	c	w+c	사전에 존재?	출력	사전 추가
1	A	B	AB	❌	A (0)	AB (256)
2	B	A	BA	❌	B (1)	BA (257)
3	A	B	AB	✅	—	—
4	AB	A	ABA	❌	AB (256)	ABA (258)
5	A	—	—	—	A (0)	—

최종 출력


0, 1, 256, 0

📚 장점 vs 단점

장점	단점
무손실 압축 가능	처음엔 압축 효율 낮음
텍스트에 특히 효율적	사전 크기 제한 필요
구현이 상대적으로 단순	바이너리 파일에선 비효율적일 수 있음

💡 활용 예시

GIF 이미지 포맷

UNIX 압축 명령어 compress

팩스, 모뎀 통신 등에서 활용

Share article

More articles

[JAVA 문제 풀이] 338. 뒤에 있는 큰 수 찾기

[JAVA 문제 풀이] 338. 뒤에 있는 큰 수 찾기

[JAVA 문제 풀이] 337. k진수에서 소수 개수 구하기

[JAVA 문제 풀이] 337. k진수에서 소수 개수 구하기

[SQL 문제 풀이] Find Consistently Improving Employees (지속적으로 개선되는 직원 찾기)

[SQL 문제 풀이] Find Consistently Improving Employees (지속적으로 개선되는 직원 찾기)

[SQL 문제 풀이] Monthly Transactions I (월간 트랜잭션 I)

[SQL 문제 풀이] Monthly Transactions I (월간 트랜잭션 I)

stupefyee

RSS·Powered by Inblog