압축원리에 관한 질문입니다.
글쓴이: phs38 / 작성시간: 금, 2003/05/02 - 12:28오전
압축방법중 크런칭의 원리가 아래와 같은데 제 머리로는 잘 이해가 안되네요.
제 머리로 이해한 사실은 두개의 연속된 문자열을 4,096개로 지정하고 문자열대신 그 지정된 주소를 적는 것 같은데 출력파일 즉 압축되서 나올 거에는 주소만이 적혀 나오는데 그 주소에 어떤 문자열이 지정되어 있는지 모르잖아요. 그리고 연속된 두 문자열만 따지면 65,536의 경우의 수가 생기는데 4,096개로 지정하면 65,536-4,096개는 어떻게 하나요. 뭐가 뭔지 제가 아무래도 뭔가 잘못 이해하고 있는 것 같은데 제 수준에 맞게 설명해주세요. 부탁합니다.
Quote:
크런칭의 원리는, 파일을 읽어들이면서 연속된 문자열에 대한 표를 만들어두었다가 나중에 같은 문자열이 발견되면 이 표를 참조하는 방식이다.
크런칭이 시작되면 맨 먼저 기억 장소 내에 4,096개의 문자열에 대한 표를 만들게 되며, 각 기억 장소는 2바이트 선두 포인터(Prefix)와 1바이트의 후위 포인터(Suffix)로 이루어진다. 이 중에서 0∼255번의 후위 바이트에는 표준 ASCII 코드가 지정되며, 선두 포인터는 모두 빈 공간(Null)으로 남게 되고, 256번도 시스템에서 특수한 용도로 사용하기 위해서 남겨둔다.
이러한 과정을 거친 후에야 실제로 파일에서 문자를 읽어들여서 압축을 하게 된다. 즉, 파일에서 연속된 두 문자를 읽어들이고 이 문자열이 기억 장소 내의 표에 존재하는지 여부를 검사한 후에, 만일 존재하지 않는다면 표의 257번 이상의 위치에 문자열들을 보관하고, 출력 파일에는 그 문자의 아스키 코드값을 기록하게 된다. 문자열이 기억 장소 내에 존재한다면, 이 문자열의 주소(Address)를 선두 포인터에 기록하고, 다음에 오는 문자열의 아스키 코드값을 후위 바이트에 보관하여, 출력 파일에는 그 문자열의 주소를 기록하게 된다. 4,096개의 항목이 나열된 표를 사용한다면 출력 파일에 기록하는 주소를 표시하기 위해서는 12비트가 필요하다.
작성된 압축 파일을 풀 때에도 동일한 과정을 거쳐 기억 장소 내에 표를 만들면서 원래의 파일을 생성하게 된다.
Forums:
간단하게 설명합니다.
제가 알고 있는 범위에서는 이렇게 하는걸로 알고 있습니다.
즉, 자주 쓰이는 표현의 문자열(문자가 아닌 문자열이라는 것에 주목을 해야합니다.)
을 추려서 4096개를 하나의 표로 만들고 그에 해당하는 문자열이 나오면 문자열대신에
표에있는값을 쓴다.
만일 표에 있는 문자열에 해당하는 값이 아닌경우에는 그것을 따로 표를 만들어 순번을
메긴다.
이것은 이미지 압축에서도 많이 사용되는 방법인데 가장 기초적인 PCX파일의 형식을
보자면 일단 한줄에 연속된 색상을 찾아서 그 색상값을 쓰고 연속된 숫자값을 써줌으로써
압축의 효과를 냈었죠.
원문에서도 표현했듯이 '문자열'('A'라는 단어가 아닌 'abcd'라는 문자열)을 기준으로
생각하면 어느정도 이해가 가능하리라고 생각됩니다.
압축 알고리즘을 자세하게 공부하진 않았지만 포함된 원문의 내용은 위와 같은 뜻인걸로
생각이 되는군요.
------------------------------
좋은 하루 되세요.
음 -_-
그 인용문 상당히 어렵게 설명을 해놨네요 -_-
압축기법에 관심도 없었고 처음 읽어봐서 잘 모르겠지만 대충 이런거 같네요
[2바이트 ][1바이트] 이게 4096개로 만들 표의 각각 entry란 거죠
그리고 표의 0~255번 까지는 ASCII코드로 쫙 적어넣습니다
(근데 왜 255까지나 필요할까요 글쎼요 -_-)
그러면 표에서 주소의 번호랑 아스키 코드값이랑 같겠죠?
이제 여기서부터 시작입니다
파일을 읽지요
처음은 문자 두개씩 읽어서 표를 채워나가겠죠
그러다가 표에 있는 두 문자가 검색이 되면
예를 들어 'BC' 가 표에 들어가 있는데
또 'BC'가 나왔다 그러면 그 다음 문자 까지 읽는거죠
만일 'BCD'다 그러면 앞 2바이트에는 BC가 저장된 주소를, 마지막 바이트에는
D가 저장된 주소를(이건 아스키코드랑 같겠죠?) 적습니다
이제 감이 오시나요?
이런식으로 동일한 문자열이 존재하면 문자를 하나씩 추가해 나가는거죠
근데 제 생각이 맞는지 모르겠네요
단지 그 설명보고 해석한 것일 뿐이니 너무 믿진 마시구요
그럼~
ps
두 문자를 65536개의 표로 만들면
그건 압축이 전혀 안되는 것이지요 ^^
ps2
어렵게 설명했다는 말이 글 올리시는 분의 인용문을 보고 한 얘기였는데
오해가 있었나보네요 수정했습니다
codebank님의 글이 훨씬 이해하기 좋네요.
codebank님의 글이 훨씬 이해하기 좋네요.
압축 알고리즘..
프세에 강대명님께서 연재하고 계십니다. 찾아보셔도 좋을듯..^^
가이: 리여.. 확실히 너는 네지와는 다르다
록리: 위로라면 집어치세요..
가이: 위로같은게 아니다 ! 너는 네지와는 다르게 천재도 아니고 재능도 없다 하지만 너는 노력의 천재다..
- 나루토 <키시모토마사시>
반복해서 나오는 글자나 패턴을
반복되는 글자나 패턴을 간단한 기호로 바꿔버리는게 압축원리 아닐까요.
물론 종류별로 그 방식이 틀리죠.
1. RLE -> 반복되는 글자를 적당한 기호로 바꾼다.
2. 호프만 -> 자주 나오는 글자는 짧은 기호로 표현하고 덜 나오는 글자는
긴 기호로 표현
3. LZW -> 자주 반복되는 패턴을 찾아서 그 패턴을 특정 기호로 바꾼다.
(패턴길이는 가변입니다)
Written By the Black Knight of Destruction
프세의 강대명님이 누구죠? 어느 사이트에 있나요?
위에위에님께서 프세의 강대명님이 알축알고리즘을 연재 하신다고 하셨는데
어디가서 찾죠? 알려주세요.
제가 아는 게 부족한 자라 질문 밖에 글을 올리지 못할거 같네요. 부디 많은 답변 바랍니다.
서점에 있을것 같네요;;
서점에 있을것 같네요;;
대명님은..
데브피아에 자주 들르시는데.. 지난 2월부터 5회분에 걸쳐 압축
알고리즘에 대해 연재하고 있습니다.
프세란.. 프로그램 세계란 개발자 월간지를 말합니다. ㅡ.ㅡ;
가이: 리여.. 확실히 너는 네지와는 다르다
록리: 위로라면 집어치세요..
가이: 위로같은게 아니다 ! 너는 네지와는 다르게 천재도 아니고 재능도 없다 하지만 너는 노력의 천재다..
- 나루토 <키시모토마사시>
LZW알고리즘이군요
제가 10여년전에 보았던 LZW알고리즘과 흡사한 것같습니다.(똑같은걸로 보이지만 기억이 가물가물해서요 --;)
그당시 GIF파일을 분석한 적이 있었는데, GIF파일의 구조가 바로 이와 같습니다. GIF파일 디코더를 보시면 보탬이 되실겁니다. 구지 GIF89a를 보실 필요도 없이 GIF87만 보셔도 그 중 디코더 부분만 보셔도 되겠습니다.
LZW는 3명의 수학자(전산?)이름의 약자인데요, 스펠링은 모르고, 렘펠, 집, 웰츠일겁니다. 1970년대말에 시작해서 1980년대 중반경에 완성된 알고리즘으로 알고있습니다. IEEE Computer에서 연재되었던것으로 기억합니다.
------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.
사전 기반 압축 알고리즘은 LZ77과 LZ78의 두 계열이 가장 유명합니
사전 기반 압축 알고리즘은 LZ77과 LZ78의 두 계열이 가장 유명합니다.
LZ77은 자기보다 앞에 나타난 문자열을 바탕으로 압축을 하죠.
입력으로 들어온 문자열을
라고 합시다 (| 앞은 이미 처리된 문자열) 이 때 다음에 들어오는 babc란 문자열을 (2, 3, c)라고 encoding할 수 있습니다. "현재보다 두 글자 앞부터 3글자가 반복되어 나타나고, 그 뒤에 c 자를 덧붙인다"는 뜻으로요. gzip에서 쓰이는 기본 알고리즘도 이 LZ77의 변형입니다.
LZ78은 위에서도 언급된 것처럼 두 글자씩 묶어서 계속 사전에 넣는 방식입니다.
aaaababaabaaabab이 입력을 처리할 때, 처음엔 사전에 아무 것도 없으니 (0, a)를 출력하며 "a"를 처리합니다. (사전의 첫번째엔 "a"가 들어갑니다.) 그 다음엔 사전의 첫번째에 "a"가 있으니 (1, a)를 출력하며 "aa"를 처리합니다. (사전 두번째엔 "aa"가..) 그 다음엔 "ab"를 처리할 차례죠? (1,b)가 답이 됩니다. (사전 세번째엔 "ab"가..) 다음엔 "aba"를 (3,a)로 압축할 수 있죠. (사전 네번째엔 "aba"가...). GIF에 쓰이는 LZW는 이 LZ78의 변형입니다.
LZ77/LZ78과는 다른 계열의 압축 알고리즘도 있습니다. bzip2 등에서 쓰이는 block sorting을 기반으로 하는 알고리즘 등이 그런 예죠.
댓글 달기