Deflate

개요

Deflate 압축 알고리즘은 필립 카츠가 1993년에 개발한 압축 알고리즘이다. 이 알고리즘은 LZ77 (Lempel-Ziv 1977) 및 허프만 코딩이라는 두 가지 주요 기술을 결합하여 구현된다. Deflate는 효율적인 데이터 압축을 제공하는 것으로 널리 알려져 있으며, ZIP 파일 포맷과 PNG 이미지 포맷 등 다양한 파일 형식에서 사용된다.

LZ77 알고리즘

LZ77 알고리즘은 '슬라이딩 윈도우'라는 개념을 사용하여 데이터를 압축한다. 이 윈도우는 최근에 처리된 데이터의 일부를 유지하며, 알고리즘은 현재 처리 중인 데이터 조각이 이전에 이미 윈도우에 나타났는지 검사한다. 만약 발견된다면, 데이터 조각은 그 위치와 길이를 나타내는 포인터로 대체된다. 이는 반복되는 문자열을 효과적으로 압축할 수 있게 한다.

허프만 코딩

허프만 코딩은 빈도가 높은 데이터에 더 짧은 코드를, 빈도가 낮은 데이터에는 더 긴 코드를 할당하는 방식으로 작동한다. 이는 불균등한 코드 할당을 통해 데이터를 더 효율적으로 표현할 수 있게 한다. Deflate에서는 LZ77로 처리된 데이터를 더욱 압축하기 위해 허프만 코딩이 사용된다.

압축 방식 예시

예시 문자열: "ABABABABABABABAB"

예시 문자열은 "AB"라는 패턴이 반복되고 있다.

LZ77 알고리즘 단계

1. 초기에 "A"와 "B"가 나타나므로, 이들은 직접 데이터로 기록한다.
2. 이후 "AB" 패턴이 반복되므로, 첫 번째 "AB" 이후에 나타나는 모든 "AB" 패턴은 이전에 나타난 위치를 찾아 그 위치와 길이를 나타내는 포인터로 대체한다. 첫 번째 "AB"는 직접 기록하고, 나머지는 "(2,2)"와 같이 참조한다.

이 단계의 결과, 문자열은 "AB(2,2)(2,2)(2,2)(2,2)(2,2)(2,2)"와 같이 표현할 수 있다.

허프만 코딩 단계

LZ77로 압축된 데이터는 "A", "B", "(2,2)"와 같은 3개 요소로 구성되어 있고, 허프만 코딩 단계에서는 이러한 각 데이터 요소의 빈도를 기반으로 최적의 코드를 할당한다.

예를 들어, 가장 간단한 형태로 설명하면:

• "A"와 "B"는 동일한 빈도(각각 1번)로 나타난다.
• "(2,2)"는 6번 반복되므로 가장 빈번한 요소이다.

이 정보를 바탕으로, "A"와 "B"에는 비교적 긴 코드를, "(2,2)"에는 가장 짧은 코드를 할당할 수 있다. 가장 빈번한 패턴에 가장 짧은 코드를 할당하는 것은 허프만 코딩의 기본 원리이다.

실제 허프만 트리를 구성하고 코드를 할당하는 과정은 다음과 같이 진행됩니다:

1. 데이터 요소와 그 빈도를 바탕으로 허프만 트리를 구성한다.
2. 트리의 각 노드에 이진 코드를 할당하여, 빈도가 높은 요소에 짧은 경로(즉, 짧은 코드)를, 빈도가 낮은 요소에는 긴 경로(즉, 긴 코드)를 할당한다.

결과적으로, "(2,2)"에는 가장 짧은 이진 코드가 할당되고, "A"와 "B"에는 조금 더 긴 이진 코드가 할당될 것이다. 이 과정을 통해 데이터의 표현을 최적화하고, 전체적인 데이터 크기를 줄일 수 있다.

실제 허프만 코딩의 결과는 입력 데이터의 빈도 분포와 할당된 코드에 따라 달라지며, 이를 통해 최종적으로 압축된 데이터가 생성된다.

최대 압축율 및 압축 레벨

Deflate 알고리즘의 최대 압축율은 압축하는 데이터의 내용에 크게 의존한다. 압축 레벨은 1부터 9까지 설정할 수 있으며, 1은 가장 빠른 압축 속도를, 9는 최대 압축률을 의미한다. 압축 레벨이 높아질수록 더 많은 시간과 계산 리소스를 소모하지만, 결과적으로 파일 크기는 더 작아진다.

ZIP 압축의 경우 압축 프로그램에 따라 압축 레벨 0이 있을 수도 있는데, 0은 압축하지 않고 .tar와 같이 파일을 묶는것이다.

사용 사례

Deflate 알고리즘은 압축 기술의 중요한 부분으로, 많은 파일 형식과 애플리케이션에서 사용된다.

• ZIP 압축: ZIP 파일 형식은 가장 널리 알려진 압축 형식 중 하나로, Deflate 알고리즘을 사용하여 파일 크기를 줄인다. 이는 다양한 종류의 데이터와 파일을 효율적으로 압축하고 보관할 수 있게 해준다.
• PNG 이미지: PNG (Portable Network Graphics) 형식은 투명성을 지원하는 무손실 압축 이미지 형식이다. PNG는 이미지 데이터를 압축하기 위해 Deflate 알고리즘을 사용하며, 이는 고화질의 이미지를 저장할 때 우수한 압축률을 제공한다.
• 네트워크 통신: 웹 페이지와 서버 간의 데이터 전송에 있어서는 과거에는 Deflate를 사용했지만, 요즘은 더 좋은 압축율을 가진 알고리즘들(예: Brotli이나 Gzip)이 널리 사용된다. 이러한 알고리즘은 웹 콘텐츠의 로딩 시간을 단축하고, 대역폭 사용을 최소화하여 더 빠른 인터넷 서핑 경험을 제공할 수 있습니다. 현재는 Brotli와 Gzip에 비해 상대적으로 덜 사용된다.

Deflate 알고리즘의 압축 레벨 설정은 사용자가 데이터 압축 시 속도와 압축률 사이에서 원하는 균형을 찾을 수 있게 해준다. 낮은 압축 레벨(예: 1)은 빠른 압축을 제공하지만, 압축률이 낮을 수 있으며, 높은 압축 레벨(예: 9)은 더 나은 압축률을 제공하지만, 더 많은 시간과 처리 능력을 요구한다. 이러한 설정은 특정 사용 사례에 따라 최적화할 수 있으며, 사용자는 압축하는 데이터의 특성과 요구 사항에 맞춰 적절한 레벨을 선택해야 한다.