Post

압축 알고리즘

Posted Updated
By 10 min read

학교에서 배운 RLE, LZW 알고리즘 등에 대해 다룹니다.

RLE

Run-Length Encoding 이란 뜻으로, 문자열의 연속되는 부분을 길이로 나타내서 압축하는 알고리즘입니다. 예를 들어,
AAAABBBBBAABABBBBABBBBB
라는 문자열은
A4B5A2B1A1B4A1B5
라고 압축할 수 있습니다. A가 4개, B가 5개, A가 2개, … 이런 식으로 연속해 있다는 것을 숫자로 나타내면 됩니다.

사용 예

문자열을 이루는 문자의 수가 적고 연속하는 길이가 긴, 예를 들어 검은색과 흰색으로 이루어지는 팩스 문서 등을 압춧할 때 효율적이나, “A tensor is an object that transforms like a tensor.” 같은 문장을 압축하기에는 별로 좋은 방법이 아닙니다.

구현

왼쪽에서 문자를 하나씩 보면서, 연속한 글자수를 세다가 다른 문자가 나오면 이전까지 연속하던 알파벳과 카운팅한 수를 출력하고 카운트는 다시 1로 줄이면 됩니다.

1
2
3
4
5
6
7
8

cin>>str;
for(int i=0;i<n-1;i++){
    if(str[i]!=str[i+1]){
        cout<<str[i]<<cnt;
        cnt=1;
    } else cnt++;
}
cout<<str[n-1]<<cnt;

과제 해결하기

E. RLE 준비

위 구현 코드에서 출력 부분을 지우고 cnt를 초기화할 때마다 max를 업데이트해주면 됩니다.

F. RLE 압축

위 구현 코드와 같습니다.

G. RLE 압축률 구하기

위 구현 코드에서 출력 부분을 지우고 cnt를 초기화할 때마다 출력 문자열의 길이를 늘리면 됩니다. 문자가 10개 이상 연속하면 문자열의 길이가 세 글자 이상 한 번에 늘 수 있으니 주의합니다. (이걸 고려하지 않으면 13틀을 하게 되는 거다)
기약분수는 유클리드 호제법을 통해 최대공약수를 구하는 함수 등을 만들면 됩니다.

H. RLE 압축 해제

문자열 내의 각 문자가 숫자인지 알파벳인지 구분해야 합니다. 숫자가 나오면 string 형태의 십진수를 int로 바꿔주는 코드를 짜고(역시나 수가 두 자리 이상의 수인 상황을 고려해야 합니다)문자가 나오면 그 횟수만큼 문자를 출력하면 됩니다.

LZW

Lempel-Ziv-Welch의 약자입니다. 많이 나오는 단어로 사전을 만들어서 사전에 따라 문자를 압축합니다. 예를 들어,
ABABBABCABABBA
라는 문자열이 있으면 단어사전에 A, B, C, AB, BA, ABB, BAB, BC, CA, ABA, ABBA
와 같이 단어를 추가해
1 2 4 5 2 3 4 6 1
과 같은 길이로 압축할 수 있습니다. RLE에 비해 더 사용 범위가 넓고 효율적입니다.

STL map 자료구조

LZW를 사용하기 위해 필요합니다. 간략하게 다루어보자면,
std::map<key, value> 형태로 선언합니다. key와 value에는 각각의 자료형을 넣으면 됩니다. 이때 map에 key를 넣으면 value값을 찾아서 바로 뱉어내 줍니다. key가 정수인 기본 배열과 다르게 key를 문자열 등의 자료형으로 사용할 수도 있고, 특정 value값을 찾고 싶을 때 O(logn)에 찾아준다는 것도 장점입니다.

작동 방법

  1. 길이 1인 문자열을 모두 사전에 추가합니다.

  2. 왼쪽부터 문자를 하나하나씩 읽어나갑니다. \

    1) 만약 현재의 문자열이 사전에 있다면? 현재 문자열 뒤에 다음 문자를 붙여 줍니다.
    2) 만약 없다면? 제일 뒤 한 글자를 뺀 문자열은 사전에 존재합니다. 따라서 그 문자열에 해당하는 번호를 추가하고 현재 문자열은 가장 오른쪽 문자 하나로 깎습니다. 이때, 아까 사전에 없던 그 단어를 사전에 추가합니다.

구현

  1. 인코딩을 위해 map<string, int> 를 하나 선언합니다. 우리의 단어 사전이 될 것입니다.
  2. 모든 한 글자 문자열을 map에 추가합니다. 문자열이 없을 경우 추가하는데, 위에 서술한 바와 같이 map은 자료가 있는지 logn 시간에 찾을 수 있으므로 그리 오래 걸리지 않습니다.

  3. 왼쪽부터 한 글자씩 읽습니다.\

    1) 현재 문자열의 뒤에 읽은 문자를 추가합니다.
    2) 만약 map에 현재 문자열이 있다면 3. 1)로 돌아가면 됩니다.
    3) 아니라면 아까 추가한 문자를 제거하고 그 문자열의 value를 출력하면 됩니다. map에는 현재 문자열(마지막 문자가 포함된 문자열)을 추가하고, 현재 문자열은 현재 문자로 초기화합니다.

  4. map의 모든 원소를 출력하면 이가 단어 사전이 됩니다.
  5. 아까 출력한 value가 압축한 문자열이 됩니다. 여기서부터는 디코딩하는 방법을 알아봅시다.
  6. 단어사전을 이번에는 map<int, string>으로 만듭니다. 아까 그 map의 원소를 그대로 가져오면 됩니다.
  7. 압축한 문자열의 각 수에 대해, map에서 그 문자열을 꺼내 오면 됩니다. 코드는 생략합니다.

과제 해결하기

I. LZW 사전 만들기

위 구현의 4.까지 하면 됩니다.

J. LZW 압축하기

위 구현을 하면서, 3. 3)의 출력을 vector 등의 자료형에 넣는 것으로 대체하고 나중에 크기와 함께 한꺼번에 출력하면 됩니다.

기타 과제 해결하기

A. 문자열

A나 B가 나올 때마다 A.B를 출력하고, 나머지는 해당 문자를 출력하면 됩니다.

tag: implementation

B. 문자열 계산식의 총합

재귀함수 구현 문제입니다. 저는 (현재까지의 합, 남은 수) 2-변수로 구현했습니다. 재귀가 아닌 다른 풀이도 존재합니다.

tag: implementation, math

C. 문자열 출력 1

재귀함수 구현 문제입니다. 저는 (현재까지 문자열, 남은 문자열, 선택해야 할 남은 문자의 수) 3-변수로 구현했습니다. 재귀가 아닌 다른 풀이도 존재합니다만, 재귀가 더 잭관적인 것 같습니다.

tag: implementation, string

D. IOI 문자열 출력

BOJ에 있는 문제입니다. (IOIOI) 코이스터디에도 IOIOI라는 이름으로 중복 업로드된 문제입니다. DP 배열을 만들어서, IO라는 부분문자열이 나오면 두 칸 전의 값에 +1, 아니면 0으로 각 칸에 값을 저장한 후 문자열에서 I라는 문자를 찾으면 그 전 칸의 수만큼의 길이를 가진 IOI 수열이 존재하는 것입니다.

tag: dp, string

K. Huffman encoding

문제에서 제시해 주는 것을 구현하기만 하면 되는 문제입니다. 트리의 각 정점을 {번호, 대응 문자열, 나타나는 횟수, 부여된 코드값, 부모 노드의 번호}의 구조체로 저장하고, 나타나는 횟수에 의한 priority_queue로 정점을 관리하면 됩니다. 자세한 구현 방법은 생략합니다. iamcoder 11솔이 더 나오면 안되니까요

tag: implementation, data_structures, trees

GSHS, InfoII
gshs infoii algorithms
This post is licensed under CC BY 4.0 by the author.