Unix 압축

Unix의compress와most 뒤에 있는 압축 알고리즘을 보여 줍니다.gif 압축.
Lempel-Ziv-Welch[LZW] 알고리즘은 공간을 절약하기 위해 반복되는 패턴을 비교적 짧은 코드로 대체하는 탐욕스러운 무손실 압축 알고리즘이다.

Lossless is a form of compression where no data is lost.

우리는 알고리즘을 검사하고 파이톤의 실현을 볼 것이다.

For simplicity sake, we’ll limit the discussion to encoding ASCII characters.

부호화

기본적으로 만약에 우리가 텍스트 파일을 처리할 때 중복된 단어를 식별할 수 있다면 우리는 원시 텍스트보다 짧은 코드로 이 단어들을 대체할 수 있다.전체 문서에서 이 동작을 실행하면 우리가 추구하는 압축을 실현할 수 있습니다.
LZW는 하나의 단어를 고유한 코드에 매핑하는 사전을 사용합니다.사전의 처음 256개 항목은 숫자 코드에 매핑되는 단일 ASCII 문자입니다.

예를 들어, 사전은 처음에 다음과 같습니다.

{
  "A": "65",
  "B": "66",
  ....
  "a": "97",
  "b": "98"
}

현재, 우리는 텍스트의 나머지 부분을 한 글자씩 훑어보고, 짧은 단어/문자 서열을 만들 것이다.새 문자를 포함하면 현재 사전에 존재하지 않는 짧은 단어를 만들 것입니다. 이 인터럽트 문자를 무시하고 문자열의 이전 상태와 일치하는 코드를 출력합니다.
그리고 이 새 단어를 사전에 추가해서 새 코드를 분배합니다.
예를 들어, 입력한 텍스트가 다음과 같다고 가정합니다.

... app [cursor] appl ....

우리 사전은 아마도 다음과 같다.

{
  ...
  "app": 324,
  ....
}

우리가 만난 다음 텍스트는 'appl' 입니다. 현재 사전에 없습니다.
따라서, 우리는 기존 단어가 'app' 와 일치하는 코드를 출력하고, 새로운 코드를 사용하여 'app' 를 사전에 추가할 것입니다.
이터레이션된 출력은 다음과 같습니다.

Dictionary: { … “app”: 324, “appl”: 325 …}

Output: … 324 …

사전에 없는 새 단어를 만났을 때만 코드를 출력할 수 있으니 주의하십시오.이것은 우리에게 더 큰 단어를 세우고 더 큰 압축을 실현할 수 있는 기회를 주었다.
프로그램 처리 입력과 사전이 증가함에 따라, 우리는 최종적으로 점점 더 큰 문자열을 저장할 것이다.문자열이 길수록 우리는 더 작은 코드로 그것을 바꾸어 더 큰 압축을 얻을 수 있다.
하프만 인코딩과 달리 LZW는 압축된 데이터에 이 사전을 포함하도록 요구하지 않습니다.이 알고리즘의 독특한 특징은 데이터를 풀면서 사전을 재구성할 수 있다는 것이다.이 알고리즘의 문자별 방법을 감안하면 데이터 흐름을 압축하기에 매우 적합하다.
압축의 원본을 완전히 이해하기 위해 더 큰 예를 살펴보자.

34832 : 'Harry'
34833 : 'Potter'
34834 : 'Hogwarts'
34835 : 'magic'

예를 들어, 만약 우리가 코드 34833을 기호가 없는 짧은 코드로 저장한다면, 그것은 16자리가 걸릴 것이다.그러나 6자 * 8자리 = 48자리의 정보를 표시합니다.일반적으로 코드가 높게 올라갈수록 우리가 얻는 압축은 더욱 많아진다.

디코딩

디코딩 과정은 사실상 인코딩 과정과 정반대이다.유일한 변화는 256개의 ASCII 코드로 사전을 다시 만들어서 다른 압축 해제를 시작하기 전의 초보적인 절차로 삼아야 한다는 것이다.
그리고 우리는 압축 데이터를 통독하고 코드 사전을 사용하여 코드를 원시 텍스트로 번역한다.

가변 길이 인코딩

이 알고리즘의 대다수 실현은 가변 너비 코드를 사용하는 사상을 사용한다.
이것은 코드의 최대 길이에 상한선을 정의하여 이 알고리즘이 메모리를 차지하는 것을 방지한다.예를 들어 만약에 우리가 8자리 코드를 너비로 선택한다면 우리의 최대 코드 수는 256(2)이 될 것이다.⁸).
만약 우리가 12개의 코드를 너비로 선택한다면, 우리는 최대 4096개의 코드를 가지고 있을 수 있다.
만약 우리의 사전이 4096개의 코드를 포함하는 것으로 확장된다면, 문서의 나머지 부분은 기존 사전으로 인코딩되지만, 새 코드는 추가되지 않을 것입니다.

비밀 번호

압축 알고리즘은 실현하기에 상당히 간단하다.
다음은 A Tale of Two Cities에서 실행할 때 532KB의 압축 파일을 생성하여 원래의 777KB보다 32% 작다.
다음은 this code의 개편 버전이다.

Wrapping Up

이런 알고리즘은 쉽게 이해하고 실현되지만 항상 정확한 선택은 아니다.텍스트가 짧고 유일할 때 성능이 떨어진다.이 알고리즘은 중복 데이터를 지원합니다

현대 알고리즘에 대한 이런 기술적 탐색을 좋아하신다면 언제든지 저를 주목하시거나 제personal website를 보셔서 더 많은 댓글을 얻으세요