문자열 압축

문자열

문자열 압축

• 기본 아이디어: 압축한 쪽과 압축을 푸는 쪽이 공통의 ‘사전’을 가지고 있다면, 텍스트에서 나오는 단어를 사전의 단어 인덱스로 바꾸면 압축할 수 있다.
• 양쪽이 어떻게 사전을 공유? (Lempel-Zive Data Compression)
  • 별도로 사전을 공유하지 않는다.
  • 압축하는 과정에서 사전을 만들고, 압축을 해제하는 과정에서 동일한 사전을 만들어낸다.
  • 즉, 양쪽이 동일한 사전을 만들어나갈 수 있다는 것만 확인하면 된다.

LZ77

• 사전은 이미 압축한 부분, 즉 이미 읽은 부분 전체
• [몇 번째 위치, 이후부터 몇 글자]의 형태로 읽은 부분의 단어 표현
• 최근 N 글자만 한정할 수 있다. (전체를 모두 사전으로 표현하면 구현 복잡)

문제 제시

• 총 N 글자 고려, 현재 위치부터 최대 F 글자까지 단어로 본다고 가정
  1. 처음 F 글자를 읽는다.
  2. 이미 읽은 글자에서 겹치는 문자열을 찾는다.
  3. 만약 j 글자가 겹친다면, (i,j,a)를 출력한다. i만큼 왼쪽으로 이동하고, j만큼 글자를 복사한 후, 다음 글자 a가 온다는 뜻
• N = 11, F = 4, T = abcabcbacbab
  1. 처음 a,b,c는 이전에 나온 적이 없고, 복사해 올 수 있는 글자도 없다.: [,0,a], [,0,b], [,0,c]
  2. F = 4이므로 4 글자 abcb 읽으면, abc는 현재 위치에서 왼쪽으로 3칸 이동해서 3글자를 읽으면 일치하고, 마지막 글자 b를 추가 : [3,3,b]
  3. acba에 대해서는, 현재 위치 왼쪽으로 4칸 이동하면 문자 a 일치, 다음 c 추가: [4,1,c]
  4. bab에 대해서는, 현재 위치 왼쪽으로 3칸 이동하면 문자 ba 일치, 다음 b 추가: [3,2,b]
  5. [,0,a],[,0,b],[,0,c],[3,3,b],[4,1,c],[3,2,b]
• 압축 해제: 위의 결과를 하나씩 이용하면, abc가 되고, [3,3,b]는 현재 위치에서 3칸 왼쪽으로 이동하고 3글자를 따오라는 의미로 abc를 가져와 b를 추가하고, [4,1,c]는 현재 위치에서 4칸 왼쪽으로 이동하여 1글자를 따오라는 의미로 a를 가져와 c를 추가하는 식으로 반복하여 해제하면 된다.

LZ78

• 사전을 명시적으로 만들어 나간다.

RLE (run-length encoding)

• 주어진 문자열에서 같은 문자가 반복해서 나오면 [문자, 반복된 순서]로 표현
• 그림 파일 등의 압축에 유용 (같은 색깔의 픽셀이 연속적으로 나옴)
• 주어진 문자열을 압축하기 좋은 형태의 문자열로 변형한 후 압축한다.

  BWT (Burrows-Wheeler Transform)

• 압축방법
  1. 주어진 문자열을 각각의 위치부터 시작하여 순환하여 쓴다.
     

1. 이 문자열을 사전 순서대로 정렬한다. 그 후, 마지막 문자들과 원래 문자열이 있던 순서를 저장한다. (NNBAAA, 3): 표에서 3번째 문자열이 원래 문자열이다.
   

2. NNBAAA

   • [N, 2], [B, 1], [A ,3] 으로 압축된다.

• 해제방법
  1. BWT된 문자열을 정렬하면 첫 번재 글자들을 복원할 수 있고, (NNBAAA, 3)에서 3번째가 원래 문자열(B…A)임을 알 수 있다.
     

1. 글자를 순환하면서 썼기 때문에 B가 가장 마지막 문자인 단어의 첫 글자가 B 다음 글자이다. 즉 A
   

2. 이 과정 반복