'Compression'에 해당되는 글 2건
- 2007/08/11 압축 알고리즘에 대해 (2) Lempel-Ziv
- 2007/08/09 압축 알고리즘에 대해 (1) RLE
현재 상용 압축 프로그램에 가장 많이 쓰이는 알고리즘들은, 바로 이 Lempel-Ziv 알고리즘의 변형들이다. Lempel과 Ziv는 이 알고리즘을 처음 고안한 사람들의 이름이다. 이들의 머릿글자를 따서 LZ 알고리즘이라고도 부르며, 만든 연도, 또는 사용한 기법에 따라 LZ77, LZ78, LZW, LZSS 등으로 부른다.
압축의 철학은, 반복하는 데이터는 축약해서 표현할 수 있다는 것이다. 예를 들어서, RLE의 경우는 aaaa -> a4 와 같이 반복되는 '문자'를 축약한다. 반면, LZ는 반복되는 '패턴'을 축약한다.
다음의 문자열이 입력으로 들어오면, RLE는 전혀 압축이 되지 않는다.
abababcabc
그러나 기본적인 LZ방법에서는, 다음과 같은 방식으로 표현된다.
ab(2,2)(4,2)c(3,3)
(n,m)은 n만큼 앞에서부터 m개의 문자를 반복하라는 의미이다. 그러나, 최적의 압축률을 보이는 대입을 찾기란 쉬운 일이 아니다. 이 패턴을 찾는 방법에 따라서 LZ 알고리즘의 압축률과 소요 시간이 좌우된다. 이를 위해서 suffix tree 등을 이용하는데, 이게 은근히 난제다. 구현이 꽤 까다롭기 때문이다.
압축의 철학은, 반복하는 데이터는 축약해서 표현할 수 있다는 것이다. 예를 들어서, RLE의 경우는 aaaa -> a4 와 같이 반복되는 '문자'를 축약한다. 반면, LZ는 반복되는 '패턴'을 축약한다.
다음의 문자열이 입력으로 들어오면, RLE는 전혀 압축이 되지 않는다.
abababcabc
그러나 기본적인 LZ방법에서는, 다음과 같은 방식으로 표현된다.
ab(2,2)(4,2)c(3,3)
(n,m)은 n만큼 앞에서부터 m개의 문자를 반복하라는 의미이다. 그러나, 최적의 압축률을 보이는 대입을 찾기란 쉬운 일이 아니다. 이 패턴을 찾는 방법에 따라서 LZ 알고리즘의 압축률과 소요 시간이 좌우된다. 이를 위해서 suffix tree 등을 이용하는데, 이게 은근히 난제다. 구현이 꽤 까다롭기 때문이다.
이올린에 북마크하기
이올린에 추천하기
RLE
압축 알고리즘을 배우고자 할 때, 아마도 가장 처음 접하게 되는 알고리즘이 아닐까 생각한다. 기본적인 개념은 이렇다. 여러 개의 중복된 문자를 다음처럼 치환하는 것이다.
원문 : aaabbccccddddd
압축문 : a3bbc4d5
보다시피, 여러 개의 문자가 반복되면, 그 문자가 몇번이나 반복되었는지만 저장하는 것이다. 방법은 간단하지만, 압축률은 그다지 좋지 않다. 한 문자가 계속 반복되는 데이터가 얼마나 있겠는가?
의문을 가진 독자도 있을 것 같다. 숫자가 데이터로 들어오면 어찌할 것인가? 그래서 데이터와 반복 회수를 구분할 방도가 필요하다. 이는 LZ등의 알고리즘에서도 마찬가지인데, 주로 탈출 문자를 사용한다. C/C++의 '\'을 생각하면 이해가 갈 것이다.
압축 알고리즘을 배우고자 할 때, 아마도 가장 처음 접하게 되는 알고리즘이 아닐까 생각한다. 기본적인 개념은 이렇다. 여러 개의 중복된 문자를 다음처럼 치환하는 것이다.
원문 : aaabbccccddddd
압축문 : a3bbc4d5
보다시피, 여러 개의 문자가 반복되면, 그 문자가 몇번이나 반복되었는지만 저장하는 것이다. 방법은 간단하지만, 압축률은 그다지 좋지 않다. 한 문자가 계속 반복되는 데이터가 얼마나 있겠는가?
의문을 가진 독자도 있을 것 같다. 숫자가 데이터로 들어오면 어찌할 것인가? 그래서 데이터와 반복 회수를 구분할 방도가 필요하다. 이는 LZ등의 알고리즘에서도 마찬가지인데, 주로 탈출 문자를 사용한다. C/C++의 '\'을 생각하면 이해가 갈 것이다.
Prev
Rss Feed