정보이론, 알고리즘 조사

소개글

"정보이론, 알고리즘 조사"에 대한 내용입니다.

목차

없음

본문내용

(1) LZW(Lempel – Ziv – Welch)는 아브라함 렘펠, 제콥 지브가 1977년도에 만든 LZ77의 변형 알고리즘이다. LZ77은 무손실 압축 방법으로 가장 널리 알려져 있다. LZ77의 알고리즘은 압축하고자 하는 문자열이 이미 출현한 문자열에 대한 포인터의 위치와 일치하는 길이를 저장함으로써 압축하고자 하는 데이터의 중복을 제거해 데이터의 압축을 진행하는 알고리즘이다. LZ77은 복호화시에 매우 간단하고 빠르다는 장점을 가지고 있다. 하지만 이 LZ77은 search buffer size 내에서만 압축을 진행하기 떄문에 반복되는 문자열이 비교적 가까운 곳에 위치해야 합니다. 즉, 반복되는 주기가 search buffer size보다 크게될 경우 문자열이 반복되는 것을 인지하지 못하고 압축이 되지 않는 경우가 발생하게 됩니다[1].

참고 자료

Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on information theory, 23(3), 337-343.
Ziv, J., & Lempel, A. (1978). Compression of individual sequences via variable-rate coding. IEEE transactions on Information Theory, 24(5), 530-536.
Kreft, S., & Navarro, G. (2010, March). LZ77-like compression with fast random access. In 2010 Data Compression Conference (pp. 239-248). IEEE.
공명식, 권범, 김진우, & 이상훈. (2016). LZ78 압축 데이터의 구조적 패턴에 기반한 새로운 오류 검출 알고리즘. 한국통신학회논문지, 41(11), 1356-1363.