목차
6장 압축 프로그래밍
[과제] 정수 데이터를 컴팩트하게 가져가기
정수열이 기록된 CSV를 바이너리로 하여 컴팩트하게 가져가기
정수의 부호화를 연구해서 텍스트로 152MB인
CSV데이터를 절반 이하의 크기로 해서 처리할 수 있도록 하라. 물론 원본을 복원할 수 있어야 합니다.
교수님도 아니고 책에서 무슨 과제를...
출제 의도
큰 데이터를 압축해서 컴팩트하게 만들면 디스크의 I/O를 줄일 수 있습니다. 따라 큰 데이터를 다룰 때는 항상 압축한다는 생각을 염두해야 합니다.
잡담 : 블로그 글을 적는 필자의 잡담
개발자보다 메모리가 더 싸다. 라는 말이 있듯이 네이버라는 대기업에 다니면서 느낀 점은 큰 데이터를 저장하기 위해 압축하고 효율을 생각하는 것보다, 모자란 만큼
DB를 증설하여 활용하고 있다는 것입니다. 개발자가 알고리즘을 서치하고 적용하는 시간 및 코스트보다 그냥DB를 증설하는 것이 더 싸기 때문이지 않을까 싶습니다. 그래서 책이 쓰여진 2009년도에서의 상황에서의 경험을 이해하고 과거 고전적인 해결방법을 알아 가는 것이 좋은 것 같습니다.
디스크 압축을 통해 다음과 같은 효과를 얻을 수 있습니다.
- 디스크 공간 절약: 압축된 데이터는 일반적으로 압축되지 않은 데이터보다 적은 공간을 차지합니다.
- 디스크 I/O 감소: 압축된 데이터를 디스크에 읽거나 쓸 때 더 적은 I/O가 필요하므로 성능이 향상될 수 있습니다.
그러나 이게 기반한 단점도 존재합니다.
- 압축 및 해제 오버헤드: 데이터를 읽고 쓸 때 압축 및 해제 오버헤드가 발생할 수 있습니다. 이로 인해 압축 및 해제 작업이 느려질 수 있습니다.
- 압축률에 따른 효과: 데이터의 종류에 따라 압축률이 다를 수 있습니다. 효과적으로 압축할 수 있는 데이터와 그렇지 않은 데이터를 구분하여 적용해야 합니다.
또한 일반적인 RDBMS는 압축된 데이터를 압축 해제하고 조회하는 기능을 제공하지 않습니다. 따라서 압축된 데이터를 조회하려면 먼저 압축을 해제해야 합니다. 그리고 압축 해제된 데이터에 대해 쿼리를 사용하여 필요한 조회 또는 조작을 수행해야 합니다.
VB Code와 속도감각
VB Code를 활용해 정수를 컴팩트하게 저장하자.
정수열 압축에는 수많은 알고리즘이 있는데 이 중 VB Code를 활용한 압축을 진행합니다.
VB Code는 압축 알고리즘이라기보다는 정수의 부호화 방법 중 하나압니다. 현대의 컴퓨터에서는 5라는 숫자를 고정길이 32비트로
0..0 0000 0101으로 표현합니다. 이는 정수를 바이너리 부호라는 부호화 방법으로 부호화한 것 입니다. 마찬가지로 VB Code는 또다른 규칙에 따라 정수를 부호화합니다.
VB Code는 바이너리 부호화 방식에서 사용하지 않는 앞자리의 0을 최소화함으로써 정보를 표현합니다.
| 수치 | 고정길이 바이너리 부호 | VB Code |
|---|---|---|
| 5 | 00000000 00000000 00000000 00000101 | 10000101 |
| 130 | 00000000 00000000 00000000 10000010 | 00000001 1000010 |
5의 부호를 보면 첫 비트인 1이 이 정수의 비트열은 이 바이트에서 끝이라는 플래그로 사용됩니다.
130의 경우는 2바이트가 필요합니다. 이 2바이트의 비트열을 복호화할 때는 먼저 첫비트부터 살펴나갑니다. 첫 비트가 0임으로 이 바이트에서는 끝나지 않는 것을 의미합니다.
즉 00000001의 하위 7비트가 128을, 10000010의 하위 7비트가 2를 나타내므로 128+3=130을 나타나게 됩니다.
VB Code의 경우 각 바이트 8비트의 첫 1비트는 플래그이므로 정수를 표현하는 부분으로는 127까지 나타낼 수 있습니다. 따라 최대 표현할 수 있는 수의 범위는 줄지만, 5를 표현하기 위해 4바이트를 사용하는 일은 사라지게 됩니다.
코틀린을 활용해 직접 구현해보기
fun encodeVariableByteCode(value: Int): ByteArray {
val result = mutableListOf<Byte>()
var num = value
while (num >= 128) {
val byte: Byte = ((num and 127) or 128).toByte()
result.add(byte)
num = num ushr 7
}
result.add(num.toByte())
// 최상위 바이트의 최상위 비트를 0으로 설정
if (result.isNotEmpty()) {
val lastIndex = result.size - 1
result[lastIndex] = (result[lastIndex].toInt() and 127).toByte()
}
return result.toByteArray()
}
fun decodeVariableByteCode(encodedBytes: ByteArray): Int {
var result = 0
var shift = 0
for (byte in encodedBytes) {
val value = byte.toInt() and 0xFF // unsigned byte로 변환
result = result or ((value and 0x7F) shl shift)
if (value and 0x80 == 0) {
// 왼쪽 비트가 0이라면 이건 마지막 비트
return result
}
shift += 7
}
throw IllegalArgumentException("Invalid Variable Byte Code")
}
fun main() {
val value = 130
val variableByteCode = encodeVariableByteCode(value)
println("Variable Byte Code 인코딩 결과: ${variableByteCode.joinToString(", ") { it.toString() }}")
val decodedValue = decodeVariableByteCode(variableByteCode)
println("Variable Byte Code 디코딩 결과 $decodedValue")
}출력 결과는 다음과 같습니다.
Variable Byte Code 인코딩 결과: -126, 1
Variable Byte Code 디코딩 결과 130130 인코딩이
-126, 1로 출력된 이유는VB Code가 00000001 1000010 로 표현되기에 이를 바이너리 부호로 바꾸면 1과, -126이 되기 때문입니다.
이렇게 압축을 통해 정수형 데이터를 압축할 수 있습니다.
정렬 완료된 정수를 GAP으로 가져가기
또한 데이터를 압축하는 것도 좋지만 데이터의 량 자체를 줄이는 방법도 있습니다. 바로 정렬된 정수들을 차분을 이용해 표현하는 것 입니다.
-
실제 데이터
- 3, 5, 20, 21, 23, 76, 77, 78
-
차분을 이용한 표현
- 3, 2, 15, 1, 2, 53, 1, 1
눈대중으로 보아도 수의 크기가 크게 줄은 것을 확인할 수 있습니다. 따라 VB Code로 압축을 진행할 때 위의 열과 같은 상태로 압축하기보다 아래와 같은 숫자로 압축하는 것이 더 효율이 좋다는 걸 바로 알 수 있을 것입니다.
보충 + 압축의 기초
압축에 대한 약간의 보충 설명을 하자면 출현빈도에 따라 빈번하게 출현하는 기호에는 짧은 부호를, 그렇지 않은 기호에는 긴 부호를 부여하여 압축할 수 있습니다.
- 모스 부호의 예
모스부호에서는 e와 t등 자주 출현되는 부호에 대해서는 짧게 전달하고, z와 q등 별로 출현하지 않는 부호에 대해서는 긴 부호가 할당되어 있습니다.
- JPG 압축의 예
JPEG 압축의 경우 8X8 단위로 영상을 DCT 변환해서 압축을 진행합니다.
이는 64개의 기저들의 선형결합, 계수들을 곱하고 더하는 것을 통해서 8X8로 표현할 수 있는 어떤 영상이든지 다 나타낼 수 있도록 표현하는 것입니다.
해당 기저들 또한 빈번하게 쓰이는 기저들이 있을 것이고 이미지 압축을 진행할 때 많이 사용되지 않은 기저들을 짜부시켜 용량을 줄일 수 있습니다.
자세한 내용은
JPEG는 왜 디지털 풍화가 생길까?를 참고할 수 있습니다.
참고자료
