Gaon12: 시작

2024-03-12T03:42:47Z

시작

새 문서

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

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

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

== 압축 방식 예시 ==
예시 문자열: '''"ABABABABABABABAB"'''

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

=== LZ77 알고리즘 단계 ===
# 초기에 '''"A"'''와 '''"B"'''가 나타나므로, 이들은 직접 데이터로 기록한다.
# 이후 '''"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)"'''에는 가장 짧은 코드를 할당할 수 있다. 가장 빈번한 패턴에 가장 짧은 코드를 할당하는 것은 허프만 코딩의 기본 원리이다.

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

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

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

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

== 최대 압축율 및 압축 레벨 ==
Deflate 알고리즘의 최대 압축율은 압축하는 데이터의 내용에 크게 의존한다. 압축 레벨은 1부터 9까지 설정할 수 있으며, 1은 가장 빠른 압축 속도를, 9는 최대 압축률을 의미한다. 압축 레벨이 높아질수록 더 많은 시간과 계산 리소스를 소모하지만, 결과적으로 파일 크기는 더 작아진다.<ref>무조건 작아진다는 것은 아니다. 압축하는 데이터의 내용이 규칙이 없이 랜덤하다면 압축 레벨이 높으면 CPU의 자원만 더 사용할 뿐 용량은 같을 수도 있다.</ref>

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

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

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

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

== 각주 ==

Deflate - 편집 역사

Gaon12: 시작