웹 개발과 압축 알고리즘

브라우저의 개발자도구를 열심히 보다보면 네트워크 탭에서 accept-encoding 이라는 헤더를 볼 수 있다.

이 헤더에 대부분 HTTP 응답 내용의 압축 알고리즘이 명시된다. 요청을 보낼 때 클라이언트가 어떤 압축 알고리즘을 수용할 수 있는지 나타내면서 서버에서 이러한 방식으로 압축해달라고 요청하는 의미가 될 것이다.

요청을 받으면 서버에서는 클라이언트가 원하는 압축 방식중에서 가능한 알고리즘으로 압축한 뒤에 응답을 보내주면서 사용된 압축 알고리즘을 content-encoding 헤더에 명시한다.

이 헤더들의 값으로 gzip, compress, br, deflate 와 같은 알고리즘들이 많이 사용되는데 어떤 방식으로 압축하는지 알아보자.

deflate

https://datatracker.ietf.org/doc/html/rfc1951

deflate 알고리즘은 LZ77과 Huffman Coding 알고리즘을 함께 적용하는 알고리즘이다.

앞으로 LZ로 시작하는 알고리즘이 자주 등장할텐데 대부분의 압축 알고리즘은 LZ77, LZ78에서 파생된 알고리즘을 기반으로 하기 때문이다.

deflate 알고리즘은 RFC에서는 LZ77을 사용한다고 하는데, 다른 자료에서는 LZSS를 사용한다고 하는것을 보아 여러 종류가 있는 듯 하다.

둘 다 간략하게 알아보자.

LZ77

https://en.wikipedia.org/wiki/LZ77_and_LZ78

입력 문자열을 순회하면서 이전에 등장했었던 반복되는 부분문자열을 압축하는 방식

• 압축 결과로 LLD블록(literal, length, distance) 시퀀스를 생성
• 사전(dictionary)압축방식 : 이전에 나왔던 단어를 찾는 방식
• 간단한 알고리즘으로 꽤 괜찮은 압축률를 보여준다

예를 들어 ababc라는 문자열을 압축하면

<0,0,a> <0,0,b> <2,2,c> 이렇게 3개의 LLD블록으로 압축된다.

LZSS

https://en.wikipedia.org/wiki/Lempel–Ziv–Storer–Szymanski

LZ77 알고리즘의 단점을 보완한 알고리즘

위의 LZ77의 예에서 볼 수 있듯이 문자 a를 압축한 결과가 <0,0,a>로 되면 오히려 압축결과의 크기가 더 커지게 된다.

이런 경우를 방지하기위해 일정 길이 이하의 반복문자는 아예 압축하지 않는 방식으로 최적화한 알고리즘이 LZSS이다.

그래서 LZ77과 똑같이 ababc라는 문자열을 압축하고 길이 1은 압축하지 않는것으로 설정하면

ab<2,2,c>로 압축될 것이다

Huffman Coding

https://en.wikipedia.org/wiki/Huffman_coding

허프만이라는 사람이 만든 가변길이 코딩을 만들기 위한 알고리즘이다.

가변 길이 코드란 문자를 표현하는 비트를 최대한 짧게 사용해서 길이를 압축시키는 아이디어다.

반대로 고정 길이 코드는 모든 문자가 똑같은 길이의 코드를 가지는 것을 말한다.

예를 들어, 보통 아스키 코드는 고정 길이 코드로, 8비트로 표현된다.

A=0000 0001

B=0000 0010

C=0000 0011

반면 가변 길이 코드로는 다음처럼 표현할 수 있다.

A=0

B=1

C=01

이제 여기서 중요한 점이 2가지 있다.

1. 최대한 압축률을 높이기 위해서 가장 많이 등장하는 심볼에 짧은 코드를 할당해야 한다는 점
   • 실제로 모스부호에서도 가장 많이 등장하는 알파벳 E가 가장 짧다
2. 다른 코드로 시작하는 코드의 경우, 어떤 코드인지 디코딩하기 어렵다는 점
   • 위의 예에서 코드 01은 AB일 수도 있고, C일 수도 있다

허프만 코딩 알고리즘은 이진트리를 만드는 방시그로 이 문제들을 효율적으로 해결한다.

실제로 최적의 코드를 만들 수 있는 것으로 알려져 있다.

허프만 트리를 만드는 과정은 간단하다.

1. 심볼(문자)를 등장 빈도순으로 정렬한다
2. 빈도가 가장 낮은 두 심볼을 자식노드로 가지는 트리를 만든다. 해당 트리의 빈도는 합쳐진 자식노드의 빈도의 합이 된다.

위 과정을 반복하면 된다.

예를 들어 각 심볼의 등장빈도가 다음과 같다고 하자

A=40

B=20

C=67

D=23

정렬하면 다음과 같다

C(67), A(40), D(23), B(20)

D와 B를 자식 노드로 가지는 트리를 만든다

C(67), A(40), DB(43)

다시 정렬

C(67), DB(43), A(40)

DB와 A를 트리로 만든다

C(67), DB-A(83)

다시 정렬하고

DB-A(83), C(67)

최종적으로 만든 트리는 다음처럼 된다

      []
    []  C
   [] A
  D  B

루트노드에서 각 단말노드로 가면서 왼쪽 경로는 0, 오른쪽 경로는 1을 붙이면

A=01

B=001

C=1

D=000

이 된다.

다시 deflate 알고리즘을 살펴보면, LZ77알고리즘으로 압축해서 나온 LLD블록들을 다시 허프만코딩으로 압축하면 deflate 알고리즘이 된다.

gzip

https://datatracker.ietf.org/doc/html/rfc1952

https://stackoverflow.com/questions/7243705/what-is-the-advantage-of-gzip-vs-deflate-compression

gzip의 압축 알고리즘은 deflate 알고리즘과 같다.

deflate와 비교해서 차이점은 gzip 포맷은 추가적인 헤더와 체크섬을 사용하여 오류검출에 더 강점이 있다는 점이다.

그래서인지 웹사이트에서 deflate보다 gzip이 더 권장되는 것으로 보인다.

compress

compress는 LZW 알고리즘을 의미한다.

LZW도 간단한데, 원래 문자를 표현하는데 사용하는 8비트를 9~12비트까지 확장한다.

그리고 확장한 공간에 반복되는 부분문자열을 그룹화하여 할당하는 방식을 취한다.

만약에 ABAB라는 입력이 들어오면, 앞에서부터 읽으면서 테이블을 만든다.

이 때 두 번째 AB는 앞에서 반복되었으므로 사전 테이블에 256으로 추가한다

A=65, B=66, AB=256

압축 결과는 65 66 256이 된다.

이런 방식으로 압축하는 알고리즘이 compress(LZW)이다.

br

https://datatracker.ietf.org/doc/html/rfc7932

구글에서 2015년에 발표한 압축 알고리즘으로 웹사이트의 정적 컨텐츠를 압축할 떄 gzip보다 빠르고, 압축률이 더 좋다고 한다. 성능을 위해선 이제 가능한 brotli를 우선적으로 사용하는 것이 좋을 것이다.