6. 과제-압축 프로그래밍
16강. 과제-정수 데이터를 컴팩트하게 가져가기
정수 데이터를 컴팩트하게 가져가기
[과제]정수열이 기록된 CSV를 바이너리로 해서 컴팩트하게 가져가기
정수의 부호화를 연구해서 텍스트로 152MB인 CSV 데이터를 절반 이하의 크기로 해서 처리할 수 있도록 해야 합니다. 물론 원본을 복원할 수 있어야 합니다.
출제의도
큰 데이터를 압축해서 컴팩트하게 만들면 제2장에서 설명한 대로 우선 디스크 I/O를 줄일 수 있습니다. 큰 데이터를 다룰 때 압축한다는 생각을 항상 염두에 두어야 합니다.
또한 RDBMS에서는 보통 정수를 고정길이로 가져가기 때문에 아무래도 크기가 늘어나게 되는데, 이를 적당히 작은 크기로 줄여서 처리하는 방법을 알 수 있게 됩니다.
그리고 지금까지 속도에 대해 여러 번 이야기했는데, 실제로 빠른 프로그램이나 빠른 알고리즘이라는 게 어느 정도의 레벨이 빠른 것인지에 대해서는 논란의 여지가 있습니다. 이번에는 VB Code라는 알고리즘을 소개하는데, 이것이 웬만큼 속도가 나옵니다.
17강. VB Code와 속도감각
VB Code
정수열을 압축하는 알고리즘을 설명하겠습니다. 여기에는 VB Code(Variable Byte Code, 가변길이 바이트 부호)가 사용됩니다. VB Code는 구현 면에서는 간단하고 속도가 빨라 손쉽게 사용할 수 있습니다. 압축률이나 속도 면에서는 더 뛰어난 알고리즘도 있지만, 그 정도까지는 사용하지 않으므로 이번에는 VB Code를 사용합니다.
VB Code는 압축 알고리즘이라기보다는 정수의 부호화 방법 중 하나입니다. 보통의 컴퓨터에서는 5라는 숫자를 고정길이 32비트로 0...0000 0101이라고 표현합니다. 이는 정수를 바이너리 부호라는 부호화 방법으로 부호화한 것입니다. 마찬가지로 VB Code는 또 다른 규칙에 따라 정수를 부호화합니다.
그림 6.1을 보기 바랍니다. 그림 6.1은 ❶ 수치란의 5, 130이라는 숫자를 바이너리 부호, VB Code로 각각 부호화한 경우의 비트열을 나타낸 것입니다. ❷ 고정길이 바이너리 부호에서는 32비트가 4바이트나 되지만, 5와 130은 모두 하위 1바이트 외에는 사용하지 않습니다. 보통 정수 int형으로서 사용하고 있는 것은 이 고정길이 바이너리 부호이지만, 작은 숫자인 경우는 앞부분은 모두 0이고 뒤의 1바이트만 사용한다는 것을 잘 알고 있을 것입니다.
여기서 앞부분에 사용하지 않는 바이트를 제거하고 최소한의 바이트로 정보를 표현하는 것이 ❸ VB Code입니다.
그림 6.1 VB Code
❸ VB Code는 첫 1비트가 플래그(continuation 비트)로 되어 있으며, 남은 7비트로 바이너리 부호를 표현합니다. 5의 부호를 보면 첫 비트인 1이 이 정수의 비트열은 이 바이트에서 끝이라는 플래그로 되어 있습니다. 5는 1바이트로 표현할 수 있습니다.
VB Code로 부호화하면 5와 같은 작은 숫자의 경우는 1바이트만 사용해도 됩니다. 4바이트였던 것이 1바이트가 됩니다. 130에서도 2바이트만 사용해도 됩니다. 이렇게 해서 값이 작으면 작을수록 적은 바이트로 정수를 표현할 수 있는 것이 가변길이인 VB Code입니다.
이상으로 작은 숫자를 작은 바이트 수로 표현할 수 있다는 점을 알 수 있습니다. 단, 4바이트가 아닌 더 작은 바이트 수로 부호화하는 방법을 정수 열에 적용해 압축할 경우는 조금 더 연구할 필요가 있습니다.
정렬 완료된 정수를 Gap으로 가져가기
그것이 바로 정수 간 차분(差分, difference)을 구해서 작은 정수로 표현되도록 바꾸는 것입니다. 정수로 정렬 완료되었다면 그 수는 반드시 단순 증가한다는 것을 보장할 수 있습니다. 단순 증가하게 되면 처음부터 차분을 구하더라도, 역으로 복원할 때 처음부터 더해가면 원래 정수열로 복원할 수 있습니다.
[3, 5, 20, 21, 23, 76, 77, 78]
-> [3, 2, 15, 1, 2, 53, 1, 1]
VB Code로 압축할 때 위의 열과 같은 상태로 압축하기보다 아래 열과 같은 상태로 만든 후에 압축하는 편이 압축률이 높아질 것이라는 점은 직감적으로 알 수 있습니다.
Wrap Up
이 과제의 핵심은 정수를 고정길이로 다루지 않고, 더 작은 표현으로 바꾸어 디스크 I/O와 저장 공간을 줄이는 감각을 익히는 데 있습니다. 특히 VB Code와 Gap 변환은 대규모 데이터에서 복원 가능성을 유지하면서도 압축률과 처리 속도를 함께 고려하는 실전적인 출발점이 됩니다.
Summary
정수열 CSV를 바이너리로 압축하는 과제는 단순히 파일 크기를 줄이는 문제가 아니라, 대규모 데이터를 다룰 때 디스크 I/O를 줄이고 메모리 활용을 높이는 사고방식을 익히기 위한 것입니다. VB Code는 정수를 고정 4바이트가 아니라 값의 크기에 따라 1바이트, 2바이트처럼 가변길이로 표현하는 부호화 방식이어서 작은 숫자에 특히 효과적입니다. 여기에 정렬된 정수열의 차분을 구하는 Gap 방식까지 결합하면 더 작은 수들로 바뀌므로 압축률을 더 높일 수 있습니다. 중요한 점은 압축뿐 아니라 원본 복원이 가능해야 하며, 이를 위해서는 차분값을 다시 누적합으로 복원하는 구조를 이해해야 합니다. 결국 이 장은 압축률, 속도, 복원 가능성을 함께 고려하는 프로그래밍 감각을 요구합니다.