[Overview] 01. Data Storage - (4) Data Compression

데이터 압축

---

01. 일반적인 데이터 압축 기법 (Generic Data Compression Techniques)

RLE(Run Length Encoding)

빈도 종속 인코딩(Frequency-dependent Encoding)

차등 인코딩(Differential Encoding)

사전 기반 인코딩(Dictionary Encoding)

LZW 압축 알고리즘(Lempel-Ziv-Welsh Compression Algorithm)

 

 

 데이터의 저장이나 전송을 위해 원래 정보를 유지하면서 데이터의 크기를 줄이는 것이 필수적이다. 각 분야에 맞게 고안된 압축 기법들이 있다.

---

01. 일반적인 데이터 압축 기법 (Generic Data Compression Techniques)

데이터 압축 방법은 무손실(lossless) 압축 방법과 손실(loss) 압축 방법으로 나뉜다.

 

 무손실 압축 방법은 압축 과정에서 정보를 잃지 않는 방법이며, 손실 압축 방법은 정보를 잃을 수도 있는 방법이다. 손실 압축 방법은 무손실 압축 방법보다 높은 압축률을 제공하지만 정보를 잃을 수도 있으므로 이미지나 비디오처럼 작은 오차들에 크게 구애받지 않는 환경에서 널리 사용된다.

 

RLE(Run Length Encoding, 런 길이 부호화)

매우 간단한 비손실 압축 방법으로, 데이터에서 같은 값이 연속해서 나타나는 것을 개수와 반복되는 값으로 줄여서 표현하는 방법이다.

 예를 들어 아래와 같은 이미지를 RLE로 압축한다고 하자.

smile

 위 이미지는 흑백 이미지로, 흰색 바탕이 대부분을 차지하고 있고 오브젝트가 검정색으로 그려져 있다. 이를 PIL라이브러리의 Image 모듈을 이용해 numpy 배열로 간단하게 나타내면 다음과 같다.

 

[[255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255]
 [255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255]
 [255 255 255 255 255 255   0   0   0   0 253 255 255 255 255 255]
 [255 255 255 255   0   0 255 255 255 255   0   0 255 255 255 255]
 [255 255 255   0 255 255 255 255 255 255 255 255   0 255 255 255]
 [255 255 255   0 255 255   0 255 255   0 255 255   0 255 255 255]
 [255 255   0 255 255   0   0 255 255   0   0 255 255   0 255 255]
 [255 255   0 255 255 255 255 255 255 255 255 255 255   0 255 255]
 [255 255   0 255 255 255 255 255 255 255 255 255 255   0 255 255]
 [255 255   0 255 255 255 255 255 255 255 255 255 255   0 255 255]
 [255 255 251   0 255   0 255 255 255 255   0 255   0 253 255 255]
 [255 255 255   0 255 255 255   0   0 255 255 255   0 255 255 255]
 [255 255 255 255   0   0 255 255 255 255   0   0 255 255 255 255]
 [255 255 255 255 255 255   0   0   0   0 253 255 255 255 255 255]
 [255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255]
 [255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255]]

 결과를 간단하게 나타내기 위해 스마일 이미지를 임의로 16x16 크기로 변환해 출력한 것이다. 보다시피 오브젝트 주변의 픽셀들은 대부분 255라는 white값으로 나타낼 수 있다. 따라서 각각의 픽셀에 '255라는 값을 갖고 있다'라는 정보를 주는 것보다 '0번부터 22개가 255라는 값을 갖고 있다'라는 의미로 (22, 255)로 표현하도록 하면 같은 정보를 더 짧게 표현할 수 있다.

 

 지금은 16x16크기라서 22번 밖에 반복되지 않았지만 만약 1920x1920처럼 더 큰 이미지나 반복되는 색이 많을 경우 RLE를 이용한 압축 효율이 더 좋을 것으로 예상할 수 있다.

 

이제 실제로 얼마나 절약되는지 궁금하다. 위 이미지를 RLE로 압축해 원본 크기와 비교해보도록 하자.

 

from PIL import Image
import numpy as np
import os
import pickle


def rle_compressing(data):
    """ RLE 압축 """
    data = data.flatten()
    encode = []

    i = 0

    while i < len(data):
        count = 1
        while i + 1 < len(data) and data[i] == data[i + 1]:
            i += 1
            count += 1

        encode.append((count, data[i]))
        i += 1

    return encode


# PIL 라이브러리로 이미지 불러오기
img = Image.open("img/smile.jpg")

# numpy array로 변환
img_array = np.array(img)

img_array_list = img_array.tolist()


# RLE를 이용한 압축 과정
compressed_data = rle_compressing(img_array)


# 각각을 bin형식으로 저장
with open('data_original.bin', 'wb') as f:
    pickle.dump(img_array_list, f)

with open('data.bin', 'wb') as f:
    pickle.dump(compressed_data, f)

# 파일 크기 확인
file_size = os.path.getsize('data_original.bin')
print(f"원본: {file_size}bytes")

file_size = os.path.getsize('data.bin')
print(f"RLE 압축: {file_size}bytes")

원본: 7385346bytes
RLE 압축: 1300860bytes

 

 1920x1920 크기의 이미지를 RLE를 저장할 때 원본과 비교해서 약 6배 작은 크기로 출력되었다. 단순하게 각각을 리스트로 나타내고 바이너리 파일로 저장해 크기를 비교한 것 뿐이지만 어쨌든 대략적인 크기 비교가 가능했다.

 그렇다면 이제 압축시킨 데이터가 제대로 동작할 수 있는지가 궁금하다. 

 

def rle_decompressing(data):
    """ RLE로 압축한 data를 다시 해제 """
    decode = []
    for count, num in data:
        decode += [num] * count
    return decode
    
# 압축 해제 과정
decompressed_data = rle_decompressing(compressed_data)

# 1차원 데이터를 다시 2차원으로 변환
decompressed_array = np.array(decompressed_data).reshape(img_array.shape)

# PIL라이브러리의 Image모듈을 이용해 다시 이미지화
decompressed_img = Image.fromarray(decompressed_array)

# 비트맵 파일로 저장
decompressed_img.save("img/smile_compressed.bmp")

 위 코드에 추가적으로 RLE로 압축한 데이터를 decompressing하는 코드를 집어넣고 실행했다. 결과는 같은 이미지를 생성해냈다.

 

RLE로 압축한 데이터를 이용해 다시 만들어 낸 이미지

 

 

빈도 종속 인코딩(Frequency-dependent Encoding)

압축하고자 하는 정보에서 자주 등장하는 정보는 짧은 비트로 표현하고 거의 등장하지 않는 정보는 긴 비트로 표현하는 가변 길이 코드를 이용한 무손실 데이터 압축 기법

 

 빈도 종속 코드 개발에 널리 사용되는 알고리즘을 개발한 허프만(David Huffman)의 이름을 따서 그 알고리즘을 사용해 개발된 코드들을 일반적으로 허프만 코드(Huffman Code)라고 부른다.

 

 간단한 예로 주로 영문 텍스트에서는 e, t, a, i 같은 문자들이 z, q, x, w같은 문자들보다 자주 등장한다. 따라서 영문 텍스트를 위한 코드를 만들 때, 빈도가 높은 문자의 경우에는 10, 11과 같은 짧은 비트 패턴을 부여하고 빈도가 낮은 문자의 경우에는 1101, 0111과 같은 긴 비트 패턴을 부여해 공간을 절약하는 것이다.

 

허프만 코드

 

 

차등 인코딩(Differential Encoding)

전체 단위들 대신 인접 단위들 사이의 차이를 기록한다.

 

 각 단위는 앞 단위와의 관계로서 인코딩된다. 상대적 인코딩은 연속 데이터 단위 사이의 차이를 정확히 인코딩할지 근사 값을 인코딩할지에 따라 손실 압축이 될 수도 있고 무손실 압축이 될 수도 있다.

 

 

 

사전 기반 인코딩(Dictionary Encoding)

압축될 정보를 인덱스 등의 참조 방식으로 가리켜 인코딩하는 방식

 

 워드 프로세서에서 텍스트 문서를 압축할 때 사전 인코딩을 사용할 수 있다. 사전에는 이미 약 25,000개의 단어가 있으므로 이 단어 자체를 인코딩하는 것보다 각 단어를 0~24,999 범위의 인덱스로 가리키도록 하면 15bit의 패턴으로 모든 단어를 표현할 수 있다.

  

 

LZW 압축 알고리즘(Lempel-Ziv-Welsh Compression Algorithm)

아프라함 렘펠, 제콥 지브, 테리 웰치가 만든 알고리즘으로 압축할 정보에 포함되어 있는 개별 문자로 구성된 사전에서 시작해 검색 과정에서 개별 문자로 이루어진 더 큰 단위의 항목이 발견되면 그 항목을 사전에 추가하고 단 한번의 참조를 통해 인코딩할 수 있게 한다.

 

LZW Compression Algorithm

 

 위 그림에서 보다시피 BABAABAAA를 LZW 알고리즘으로 압축해보자. 테이블 왼쪽 열은 압축을 수행하는 Encoder, 오른쪽은 문자 정보가 저장되어 있는 dictionary인 점을 기억하고, B, A까지는 처음 등장하는 개별 문자이므로 유니코드 66, 65를 차례대로 저장하고 이때 발견되는 BA라는 패턴을 256로 저장한다. 다시 AB라는 패턴이 발견되므로 이는 257로 저장한다. 그다음 문자로 넘어갔을 때 우리가 사전에 이미 저장한 BA라는 패턴이 발견됐으므로 66, 65라는 개별적인 인덱스 대신 256이라는 하나의 인덱스로 표현해줄 수 있다.

 이렇게 마지막까지 표현하고 나면 9개의 유니코드로 표현해야 했던 영문자 BABAABAAA가 [66, 65, 256, 257, 65, 260] 길이 6으로 압축된 것을 확인할 수 있다.