8-1. 데이터 압축과 암호화 : 데이터 압축

데이터 압축

송신자가 원래의 데이터를 압축하여 크기를 줄인 후 전송하거나 저장하는 기술

전송속도를 줄이거나 저장공간을 절약할 수 있음

 

허프만 코드

- 가장 많이 쓰이는 압축방법

- 문자가 나타나는 빈도수에 따라 그 크기를 다르게 하는 것 : 빈도수 의존 코드

- 모음(a, e, i, o, u) 과 L, R, S, N, T 등과 같이 자주 나타나는 문자들은 더 작은 비트를 할당

 

허프만 알고리즘

1. 단 하나의 노드만을 가지고 있는 이진 트리와 각 문자랠 매핑, 각 트리에 문자들의 빈도수를 할당 : 트리의 가중치

2. 가장 작은 가중치를 가지고 있는 트리 두개를 찾아 하나의 트리로 합치고 새로운 루트 노드를 만들어냄

3. 마지막으로 하나의 트리가 남을 때까지 이 과정을 반복

- 원래 노드 각각은 마지막 이진트리의 말단노드가 되고 루트로부터 말단 노드에 이르는 유일한 경로가 있게 되는데 이 경로가 허프만 코드, 즉 각 노드의 왼쪽 자식 포인터에 0을 할당하고 오른쪽 자식 포인터에 1을 할당해서 결정

 

길이 인코딩(Run Length Encoding)

- 허프만 코드는 알려져 있는 문자의 빈도수를 알아야 함

- 데이터에는 이진 파일, 팩스 데이터, 비디오 신호 등도 포함되어 있어 허프만 코드로 압축하기에는 어려운 부분이 있음

- ex) 팩스는 종이의 밝은 부분과 어두운 부분에 해당하는 비트를 전송

- 팩시밀리 신호를 부호화하고 압축하는데 사용되는 간단하면서도 효율적인 데이터 압축 알고리즘

- 팩시밀리 사용 예 : 팩시밀리는 연속된 모든 0또는 1을 전송하는 대신에 연속적인 0또는 1의 개수를 나타내는 숫자를 보냄, 팩시밀리 전송을 위해 페이지를 줄단위로 주사하고 각 줄을 따라 일정 간격의 점들에 의해 반사되는 빛의 밝기를 측정

- 입력받는 문자열이 어떤 속성을 가지느냐에 따라서 압축률이 달라짐. 항상 효율적인 것은 아님

 

상대적 인코딩(Relative Encoding)

- 하나의 비디오 이미지는 거의 반복을 가지고 있지 않지만 이미지들에 대해서는 많은 반복이 있음 

- 이전 소개된 방법은 이미지 압축에 도움이 안 됨

- 각각의 프레임을 개별적인 단위로서 다루고 압축하려고 시도하지 않고 각 프레임 이전의 것보다 얼마나 다른지를 고려

- 정보를 압축하고 보내는 것은 프레임들 간의 차이가 아주 작을 때 효과적

 

상대적 인코딩 원리

1. 송신측은 첫 번째 프레임을 수신측에 보내고 이 프레임은 수신측의 버퍼에 저장

2. 송신측은 두 번째 프레임을 처음 것과 비교하고 그 차이를 인코드, 그리고 차이를 인코드한 데이터를 프레임 형식으로 수신측에 보냄

3. 수신측은 프레임을 받아 프레임이 갖고 있는 차이를 적용해서 송신측이 가졌던 두 번째 프레임을 만들어냄 

4. 송신측은 그 다음 프레임에 대하여 위의 과정 반복

 

Lampel-Zic 인코딩

- 최근에 나온 방법

- 흔하게 되풀이되어지는 문자열을 찾아 단지 한번만 저장

- 여러 번 나타나는 단어나 문장은 원래의 것을 가리키는 위치 또는 인덱스를 나타내는 값으로 대치

- 데이터베이스 관리 정책의 기본 원리

- 반복되는 문자열의 길이가 길수록 이 알고리즘의 효율은 증가