Run Length Encoding , 압축 알고리즘

리눅스 실습 시간에 배운 Run-Length Encoding 알고리즘 간단하게 복습

기본적인 개념은 "중복되는 문자를 한 문자로 치환시키는 것" 이다.

예를들면 텍스트 파일의 내용이

" AAABCDDDDDOS " 로 되어있다고 하면

" A3BCD5OS " 로 이렇게 중복되는 문자를 숫자로 치환하는것이다.

하지만 압축을 했으면 복호화의 과정이 필요한데

만약 저렇게 되어있을경우 3이 실제로 입력된 문자인지 치환된 문자인지 구별하기 어렵다는점이

있다.

따라서 치환된부분을 탈출문자 (Escape) 문자를 이용하여 나타낼 수 있다.

" *3ABC*5DOS " 이렇게 *로 나타내는것이다.

그래서 탈출문자로 문자이기때문에 거의 쓰이지않는문자를 쓰는게 중요하다.

코드 예시

int f(int n) { i#include <stdio.h> int main(int ac, char **av) { FILE *fp, *cfp // 파일 포인터 fp, cfp int c,d; char buf[200]; // 입력받는것이 2 개가 아니면 if ( ac != 2 ) { printf("Usage : %s filename",av[0]); return 1; } // 파일 열기 (read, binary) if( (fp = fopen(av[1],"rb")) == NULL ) { printf("Can't open %s \n",av[1]); return 2; } // buf 변수에 av[1].cmp 형태로 저장 후 파일 열기 spirntf(buf,"%s.cmp",av[1]); if ( (cfp = fopen(buf,"wb")) == NULL ) { printf("Can't open %s \n",buf); return 3; } // 인코딩 // 파일로부터 한 문자 읽음 while ( (c=fgetc(fp)) != EOF ) { unsigned char ccnt = 0; // 256까지 표현 가능한 unsigned 선언 while( (d=fgetc(fp)) != EOF ) // 다음 문자를 읽어들임 { if ( c == d ) // 이전 읽은문자와 다음 읽은문자가 일치 => 중복 { if( ++ccnt == 255 ) // ccnt 하나 증가시킨다 -> 만약 255 최대치까지 올라갔을경우 중단 break; } else // 다르다면 { ungetc(d,fp); // 지금 읽어들인문자 취소한다 break; } } putc(ccnt,cfp); // 그리고 ccnt 먼저 파일에 삽입 ( 중복아닐경우 10진수 0 char형 escape문자 '^@' 문자 삽입됨) putc(c,cfp); } fclose(fp); fclose(cfp); return 0; } }

그런데 리눅스로 파일크기를 계산해보니

오히려 원본파일보다 크기가 커졌다...

복호화를 하니까 원래크기로 돌아왔긴 하지만 압축의 의미가 없는것같다..