블로그 이미지
이태원에서 사는 다섯식구의 무직 가장. 흰둥에미

카테고리

분류 전체보기 (184)
Itaewon (2)
ryu's?? (1)
20121210이전 (20)
20130827이전 (147)
soo'study (13)
Total39,468
Today11
Yesterday4

'LZ77'에 해당되는 글 1건

  1. 2013.01.31 압축 알고리즘

압축 알고리즘이란

 - 수학적인 원리를 이용해 자료의 크기를 축소하여, 공간 절약 및 전송기간 단축.

   압축 시간, 복원 시간, 압축률 등이 중요 이슈


분류

 - 무손실 기법 : 복원시 원래의 데이터를 그대로 재현할 수 있지만, 좋은 압축 효과를 얻기 힘듦

   손실 기법 : 복원한 자료가 압축 전의 자료와 일치하지 않음. 연속 매체(음향, 비디오, 동영상)에 적합


종류

 - RunLengthCoding : 반복되는 픽셀 블록을 하나의 값과 그 값의 반복 회수로 나타내는 기법.

                               반복억제 - 한 자료에서 자주 반복되는 코드들의 사용을 최대한 억제

                               통계적 인코딩 - 한 자료의 코드들을 통계를 내어 통계적 수치에 따라 코드를 새로 작성.

   HuffmannCoding : 통계적인 부호화 방식. 빈번히 발생하는 데이터 코드는 적은 수의 비트로 표현,

                             빈번하지 않은 데이터는 상대적으로 많은 비트로 표현

   ColorLookUpTable : 색 참조표의 인덱스 값을 픽셀의 값으로 이용함으로써

                                실제 하드웨어에서 사용하는 픽셀당 비트수보다 적은 비트수를 사용하는 기법

   Interpolation : 픽셀들을 띄엄띄엄 전송하고, 그 사이 픽셀은 보간법을 이용해 복구.

   Prediction : 새로 부호화할 정보가 이전 정보로부터 쉽게 도출 가능하다면 그것을 사용하는 기법.

   변환 : 대상 기반 기법의 하나로서, 정보를 바라보는 관점을 바꾸는 기법

   벡터 양자화 : 데이터 스트림을 '벡터'라고 부르는 블록으로 나누어 처리하는 기법

   동작 보상(Motion Compensation) : 동화상에서 배경은 고정되어 있고, 움직이는 물체의 이동 위치만 기술하는 방법.


허프만 코딩

 - 허프만 트리를 사용하여 코드 체계 구축

   코드화 순서 : 1. 데이터 코드의 출현 빈도수 측정

                      2. 빈도에 따라 순서대로 정렬 후, 가장 적은 문자 두개로 트리 생성, 트리의 부모는 두 문자의 출현 빈도의 합.

                      3. 2번의 방법으로 모든 데이터 코드들에 대해 트리 생성 후, 각 트리들로 반복하여 하나의 트리 구축

                      4. 트리의 왼쪽은 0, 오른쪽은 1을 붙임.

   해당 데이터 코드를 나타낼 때, 트리에서 데이터 코드가 위치한 곳까지 찾아가면서 나오는 0과 1을 조합하여 나타냄.

   압축된 파일에 참조한 트리 정보가 포함되어야 함.


LZ77 알고리즘

 - 문자열 내에서 자주 반복되는 문자열 패턴을 찾아 나타나는 처음 한번 저장후, 이후에는 해당 코드로 대치해 주는 방법.

   스스로 문자열과 코드 매핑 테이블을 늘려가며, 압축을 풀 수 있도록 고안

   장.단점

   - 파일을 한 번만 읽고도 처리 가능.

     압축 파일 내에 트리 정보를 기록할 필요가 없어(허프만 코딩과 달리), 파일의 크기가 클수록 압축 효율 증가

     파일의 크기가 작을 때 오히려 압축된 파일의 크기가 더욱 클 수 있음.

     연속된 두 개의 문자열이 파일의 다른 부분에 존재하지 않을 때는 압축 불가능.



'20130827이전 > 알고리즘' 카테고리의 다른 글

병렬 알고리즘  (0) 2013.01.31
암호 알고리즘  (1) 2013.01.31
압축 알고리즘  (0) 2013.01.31
수치 해석 알고리즘  (1) 2013.01.31
검색 알고리즘  (1) 2013.01.31
정렬 알고리즘  (0) 2013.01.31
Posted by 흰둥에미

최근에 달린 댓글

최근에 받은 트랙백

글 보관함