2014-04-15 6 views
0

대부분의 압축 방법은 효과적이기 위해 일부 데이터 반복에 의존한다는 것을 알고 있습니다. 예를 들어, "AAAAAaaaQWERTY"는 무손실의 경우 "5A3aQWERTY"로, 손실의 경우 "8aqwerty"와 같이 나타낼 수 있습니다 (이는 실제 작업 방법이 아닌 예입니다). 내가 아는 한, 모든 압축 알고리즘은 -> constant < - 문자열의 반복에 의거합니다.압축 방법

문자열 "abcdefghijklmnopqrstuvwxyz"에 문제가 있습니다. 여기서는 아무 것도 반복하지 않지만, 문자열의 정보가 훨씬 더 짧은 방식으로 표현 될 수 있습니다. regex-like str에서. "[a-z]"또는 "for (x = 0; x < 25; ++) {ascii (97 + x)}"일 수 있습니다.

"0149162536496481100121"문자열도 고려하십시오. "for (x = 0; x < 11; ++) {x * x}"로 표시 할 수 있습니다.

문자열 "ABEJQZer"로 표현 될 수있다 "를위한 (X = 0; 8; ++) {ASCII (64 + X * X)}"

마지막 두 알고리즘을 알고로서는 있었다 원래의 문자열을 재생할 수 있습니다. 일반 알고리즘 (효율적인 경우)에서 생성 할 수있는 데이터보다 훨씬 적은 공간을 차지한다는 것을 알고 있습니다.

svg 이미지 (파일의 알고리즘 만 사용함)에서와 같이 크기가 jpeg보다 작습니다.

제 질문은 데이터를 가져 와서 tryes가 그것을 나타낼 수있는 효율적인 알고리즘을 찾는 압축 방법입니다. 다른 데이터와도 작동하는 래스터 이미지 (예 : http://vectormagic.com/)를 벡터화하는 것과 같습니다.

일부 오디오 편집기 (예 : 대담성) 프로젝트 파일에는 "시간 0에서 시간 2 분 45.6 초까지 120 진폭의 120Hz 고정 주파수 생성"과 같은 정보가 포함되어 있습니다 (대담성 저장 xml 형식의 정보). 이 메타 데이터는 메모리를 거의 사용하지 않으며 프로젝트를 wav 또는 mp3로 내보낼 때 프로그램이 정보를 내 보낸 형식의 실제 샘플로 "렌더링"합니다.

그런 경우 압축기는 렌더링 프로세스를 취소해야합니다. 그것은 wav 또는 mp3 파일을 취해야하며 알고리즘이 샘플을 나타낼 수있는 알고리즘을 파악해야합니다 (알고리즘이 손실되면 샘플의 근사값을 생성해야합니다 (예 : vectormagic.com이 이미지를 추정 함) 압축 파일을 생성합니다.

나는 압축 시간이 엄청나게 길다는 것을 알고 있지만 그러한 (또는 유사한) 압축 알고리즘이 있습니까?

+0

[ "PAQ"] (http://en.wikipedia.org/wiki/PAQ) 일련의 무손실 압축 알고리즘이 당신이 찾고있는 것이라고 생각합니다. –

답변

0

모든 압축 방법은 다음과 같습니다. 출력은 입력을 렌더링하는 세트 알고리즘 또는 입력과 비슷한 것으로 설정된 매개 변수 세트입니다.

예를 들어 MP3 오디오 코덱은 입력을 576 개의 샘플 블록으로 나누고 각 블록을 주파수 진폭 공간으로 변환하고 인간이들을 수없는 것을 정리합니다. 출력은 "진폭 a, b, c를 갖는 다음 13 밀리 초 재생 주파수 x, y, z 동안"과 동일합니다. 이것은 오디오 데이터에 잘 맞으며, JPEG에서 사용 된 유사한 접근법은 사진 이미지에 적합합니다.

비슷한 방법을 언급 할 수 있습니다. 예를 들어 987654 또는 010409162536과 같은 시퀀스는 다항식의 연속 값에 의해 생성되며 다항식의 계수로 표현 될 수 있습니다. 첫 번째는 9-x에 대해 (9, -1)로, 두 번째 것은 (1, 2,1)에 대해 1 + 2x + x².

입력을 생성하는 데 사용되는 알고리즘의 선택은 단순성을 위해 고정되어 사용 사례에 맞게 조정되는 경향이 있습니다. 예를 들어 디지털 카메라로 촬영 한 사진 이미지를 처리하는 경우 벡터 출력을 생성하려고 시도하는 경우조차 거의 없습니다.

0

일부 데이터를 무손실로 압축하려고하면 모델을 만드는 것으로 시작합니다. 예를 들어 인간의 언어로 일부 텍스트를 압축하는 경우 실제로 반복되는 단어가 실제로는 많지 않다는 것을 가정합니다. 그러나 많은 알고리즘이 이동 중에도 모델의 매개 변수를 배우려고합니다. 이 단어가 실제로 무엇인지에 의존하지 않는 것처럼, 그것은 주어진 입력을 위해 그것들을 찾으려고합니다. 따라서 알고리즘은 실제 사용 된 언어에 의존하지는 않지만 실제로는 인간 언어이며 일부 패턴을 따르는 것이 사실입니다.

일반적으로 완벽한 알고리즘은 없으며 무손실로 압축 할 수 있습니다. 수학적으로 입증되었습니다. 어떤 알고리즘이라도 데이터 자체보다 압축 결과가 더 큰 데이터가 있습니다.