[아홉가지 알고리즘] 07. 데이터 압축 - 무손실
데이터 압축은 뭐... 정말 많은 곳에서 쓰인다. 단순하게 텍스트 파일을 압축할 수도 있고.. 인터넷에 돌아다니는 대부분의 이미지들도 압축된 파일이다. 영상 역시 어떻게 압축하느냐에 따라 화질이 많이 달라지지!
일단 오늘은 무손실 압축에 대해 적어보자.
제목에서부터 알 수 있지만 무손실 압축은 말 그대로, 데이터 압축 - 압축 해제 전과 후의 데이터가 동일하여, 전혀! 손실이 없음을 의미한다. 게슈탈트 붕괴현상이 오고있다. 압축, 압축.
무손실 압축을 구현하는 방법(?!.. 책에서는 주로 트릭.. 이라고 표현함.)에는 여러가지가 있다.
1. Run-Length 인코딩
BOMBOMBOMBOMBOMNANANANALLLLLLL
책에서 런-렝스 ..... 인코딩이라고 표현한 이 트릭은 사실 매~우 특정한 유형의 데이터에만 유용하다. 단독으로 쓰이는 경우는 별로 없고 다른 압축 알고리즘과 함께 쓰인다.
자, 위 박스처럼 텍스트가 나열되있다. 이 .. 어느정도의 규칙성을 가지고 있는 텍스트는, 아래처럼 의미는 같지만 간소화되게 표현할 수 있다.
BOM5 NA4 L7
BOM 이 5번 반복. 그 다음 NA 가 4번 반복, L이 7번 반복되는구나! ... 총 30글자에 달하는 텍스트가 9자로! 거의 1/3 정도 줄여진 것이다.
하지만, 매우 특정한 유형의 데이터만 유용한 이유가 바로 이것이다. 이런 트릭으로 ASDFEWQQF-LJ-ASDFEWQQFEBD-LASDFEWQQF-RFWWO 같이 규칙성이 별로 없어보이는 텍스트는 어쩌려고?
하지만 이런 인코딩 방법도 쓸모 있는 곳이 있다는데?!
2. '이전과 같음' 트릭
뭐야 이 트릭 이름은 왜 이런거야.. 아무튼.
아까 Run-length 인코딩에서, 왜 Run-Length 인코딩이 특정 유형의 데이터에만 유용한지 설명하기 위해 예시로 나온 텍스트를 다시 예로 들어보자. 물론 대시 기호는 가독성을 위한 것이니 실제 스트링 계산에서는 무시!
ASDFEWQQF-LJ-ASDFEWQQFEBD-LASDFEWQQF-RFWWO
알고보면 의외로 반복되는 부분이 많다.
먼저 처음 11글자는, 그 이전에 반복된 것이 아무것도 없기 때문에 그대로 써야한다.
ASDFEWQQF-LJ
하지만 12번째 글자부터는 반복된 부분이 있다! 그렇다면 우리는 이렇게 말할 수 있다.
11글자 뒤로 돌아가서(back) 9글자를 복사(copy)!
이걸 줄여서 기호로 표현하면
ASDFEWQQF-LJ-11b9c
그렇다면 위 스트링은 아래 처럼 표현할 수 있다.
ASDFEWQQF-LJ-11b9cEBD-L13b9c-RFWWO
원래 38자였는데! 30자로 줄... 줄어들었.... 다. 예시를 잘 못 든 것 같다만! 이 트릭의 경우에는 반복되는 부분이 많으면 많을수록 효율이 좋아진다는 점이다.
3. 더 짧은 심벌 트릭
으아아... 지금 당장 하고싶지 않지만 이걸 또 잘라먹을 수는 없으니까 마저 해야지ㅠ.ㅠ
책 자체의 .. 취지가 일단은 프로그래머가 아닌 '대중서' 이기 때문에 (이에 별로 동의하지는 않지만) 아스키코드가 아니라 임의의 번호를 매칭해줬다. (이 책은 절대 대중서가 될 수 없어!!ㅠㅠ)
이 트릭을 일단 문자열 하나당 일정한 자리의 숫자 하나 를 매칭해준다. 가령 빈칸은 00 A는 01 a는 27 같은 규칙으로. 그렇다면 우리는 이 규칙을 이용해 아래 문장을 숫자화 할 수 있다.
Meet your fiancé there.
13 31 31 46 00 51 41 47 44 00 32 35 27 40 29 82 00 46 34 31 44 31 66
예시 3-1
물론... 여기는 가독성을 위해서 띄어쓰기를 해놓았지만, 컴퓨터는 그런거 없당. 얄짤없다. 여기까지는 그래, 압축을 하기 위한 전 단계라고 생각하면 된다. 이제 이 문제의 '더 짧은 심벌 트릭'을 살펴보자.
'압축'의 기본은 항상 반복되는 것에 주목하는 것! 예시 안에서라면 e 나 t 같은, 영어에서 정말 빈번하게 쓰이는 문자들! 요거를 우리는 한글자로 더 압축해보자.
e 는 31 이고 t 는 46 이지만, 우리는 이 두 글자를 한 글자씩으로 압축한다. 일단 무작정 압축해보자. 이제부터 e 는 8 이고, t 는 9 다. 어차피 우리의 문자열은 두자리 숫자와 매칭되기 때문에 중복이 될 염려는 일단 없다.
그렇게 나타낸 저 문장은
13 8 8 9 00 51 41 47 44 00 32 35 27 40 29 82 00 9 34 8 44 8 66
예시 3-2
사실 예시 3-1 에서 우리가 숫자에서 문자로 다시 이해할 수 있었던 이유는 숫자 2개당 문자 한개를 의미하고 있다는 걸 알고 있어서이지만, 여기서는 .. 음?
13-8-8-9 가 Meet 이기도 하지만... 13-88-9 로 해석해버린다거나 13-8-89 로 해석해버린다면 ?
13-88-9 mùt
13-8-89 meù
....이런 처참한 결과가 벌어진다. 그래서 약간의 희생을 통해, 잘 안쓰는 녀석들은 3자리 코드를 부여함으로서 이러한 문제를 해소하도록 한다.
자주 쓰이지 않는 문자(ù, é)를 비롯한 기호(ex. ＜, ø)는 7로 시작하는 3자리 코드로 표현하고, 자주 쓰이는 기호는 69까지로 제한한다. 이렇게 하면
13-8-8-9
으로 해석 할 수 있다. 음. 그러니까 축약하지 않은, 일반적인 기호들은 2자리 씩이기 때문에 홀수번 째 자리가 제 아무리 커봐야 6이다. 그런데 홀수번 째 자리에 오는 숫자가 7 이면, 이 숫자는 2개가 아니라 3개를 묶어서 해석해야 하고, 8 혹은 9 가 온다면 우리가 사전에 약속한 e 혹은 t 가 되는 것이다.
고로... !
We ate meat.
2380027980013827966
처럼 표현할 수 있다.
-> 사실 굉장히 미미해보이는 압축이지만 '무손실' 이라는 점에서.. 메세지가 길어지면 길어질 수록 유의미해지는 트릭.. 이라고 한다.