이 시나리오의 좋은 (DE) 압축 루틴은 무엇입니까?

Question

다음 특성이있는 바이너리 (HEX Data)의 임베디드 시스템과 같은 제한된 자원 환경에 최적화 된 빠른 감압 루틴이 필요합니다.

1. 데이터는 8 비트 (바이트) 지향 (데이터 버스 폭이 8 비트)입니다.
2. 바이트 값은 0-0xff에서 균일하게 범위를 차지하지 않지만 각 데이터 세트에 Poisson 분포 (벨 곡선)가 있습니다.
3. 데이터 세트는 고급 (플래시로 불 태워서)으로 고정되어 있으며 각 세트는 거의> 1-2MB입니다.

압축은 필요한 시간만큼 걸릴 수 있지만, 바이트의 감압은 임베디드 시스템 (3MHz -12MHz 코어, 2K 바이트 RAM)과 같은 제한된 자원 환경에서 수행 될 수있는 최소한의 메모리 풋 프린트로 최악의 시나리오에서 23US를 취해야합니다. .

좋은 감압 루틴은 무엇입니까?

기본 런 길이 인코딩은 너무 낭비되는 것처럼 보입니다. 압축 데이터에 헤더 설정을 추가하여 사용하지 않은 바이트 값을 사용하여 종종 반복 된 패턴을 나타냅니다.

몇 분만 투자 한 나와 함께,이 물건을 좋아하는 사람들의 알고리즘이 이미 존재해야합니까?

기본 RLE에 대한 성능을 비교할 수 있도록 PC에서 시험해 볼 수있는 "준비"예제를 갖고 싶습니다.

Answer 1

성능이 유일한 관심사 일 때 내가 사용하는 두 가지 솔루션은 다음과 같습니다.

• lzo GPL 라이센스가 있습니다.
• liblzf BSD 라이센스가 있습니다.
• Minilzo.tar.gz 이것은 LZO, 방금 내장 개발에 더 적합한 '미니딩 된'버전으로 다시 포장되었습니다.

둘 다 극도로 압축 압축 할 때 빠릅니다. 나는 그것을 발견했다 LZO 보다 약간 작은 압축 데이터를 생성합니다 liblzf 대부분의 경우에. 속도를 위해 자신의 벤치 마크를해야하지만, 나는 그것들이 "본질적으로 같다"고 생각합니다. 둘 다 빛보다 빠릅니다 zlib, 아직 압축하지는 않지만 (예상대로).

LZO, 특히 miniLZO, 그리고 liblzf 둘 다 내장 대상에 탁월합니다.

Answer 2

각 값의 제안 가능성이 모든 데이터 세트에 고정되어 있음을 의미하는 사전 설정된 값 분포가있는 경우 고정 코드로 허프 만 인코딩을 만들 수 있습니다 (코드 트리가 데이터에 포함되지 않아야 함).

데이터에 따라 고정 코드 또는 LZ77을 사용하여 Huffman을 사용해 보겠습니다 (Brian 링크 참조).

Answer 3

글쎄, 떠오르는 두 가지 알고리즘은 허프만 그리고 LZ.

첫 번째는 기본적으로 사전을 만듭니다. 사전의 크기를 충분히 제한하면 매우 빠르야하지만 압축이 좋지는 않습니다.

후자는 출력 파일의 반복 부분에 역 참조를 추가하여 작동합니다. 백사록을 읽거나 최근에 읽은 데이터의 덩어리를 RAM으로 저장하기 위해 파일 I/O를 사용해야한다는 점을 제외하고는 실행해야 할 메모리가 거의 필요하지 않을 것입니다.

반복되는 섹션이 서로 가까이있는 경향이 있다면 LZ가 최선의 선택이라고 생각합니다. Huffman은 당신이 언급했듯이 종종 반복되는 요소의 사전을 가지고 작동합니다.

Answer 4

이것은 오디오 인 것처럼 보이므로 차동 PCM 또는 ADPCM 또는 이와 유사한 것을 살펴보면 품질이 크게 손실되지 않고 4 비트/샘플로 줄입니다.

가장 기본적인 차등 PCM 구현을 사용하면 현재 샘플과 어큐뮬레이터 사이에 4 비트 서명 차이를 저장하고 해당 차이를 축합기에 추가하고 다음 샘플로 이동합니다. [-8,7] 이외의 차이가있는 경우 값을 클램핑해야하며 축적기가 따라 잡으려면 여러 샘플이 필요할 수 있습니다. 디코딩은 거의 메모리가 없으면 매우 빠릅니다. 각 값을 축합기에 추가하고 다음 샘플로 축합기를 출력합니다.

신호가 더 커지고 높은 피치가 발생할 때 어큐뮬레이터가 더 빨리 잡을 수 있도록 기본 DPCM보다 작은 개선은 조회 테이블을 사용하여 4 비트 값을 더 큰 비선형 범위로 해독하는 것입니다. 그러나 한계를 향해 큰 단위로 증가합니다. 및/또는 승수를 전환하기 위해 값 중 하나를 예약 할 수 있습니다. 인코더까지 언제 사용할시기를 결정합니다. 이러한 개선으로 인해 더 나은 품질을 달성하거나 4 대신 샘플 당 3 비트로 도망 갈 수 있습니다.

장치에 비선형 μ-l-l-l-law 또는 a-law ADC가있는 경우 8 비트 샘플로 11-12 비트에 비해 품질을 얻을 수 있습니다. 또는 아마도 디코더에서 직접 할 수 있습니다. http://en.wikipedia.org/wiki/m-law_algorithm

당신이 만들고있는 것에 따라 이미이 모든 일을하는 저렴한 칩이있을 수 있습니다. 나는 아무것도 보지 않았다.

Answer 5

명령 줄 스위치가있는 압축 소프트웨어 도구 또는 다른 알고리즘을 시험해 볼 수있는 압축 라이브러리를 사용하여 다른 압축 알고리즘을 시도해야합니다. 응용 프로그램에 일반적인 데이터를 사용하십시오. 그런 다음 어떤 알고리즘이 귀하의 요구에 가장 적합한 지 알고 있습니다.

Answer 6

나는 부트 로더를 위해 임베디드 시스템에서 Zlib를 사용하여 응용 프로그램 이미지를 시동시 RAM으로 압축 해제했습니다. 라이센스는 훌륭하게 허용되며 GPL 넌센스는 없습니다. 그것은 단일 malloc 호출을 만들지 만, 제 경우에는 이것을 스터브로 교체하여 정적 블록으로 포인터를 반환하고 해당 Free () 스터브를 대체했습니다. 크기를 올바르게 얻기 위해 메모리 할당 사용량을 모니터링 하여이 작업을 수행했습니다. 시스템이 동적 메모리 할당을 지원할 수 있다면 훨씬 간단합니다.

http://www.zlib.net/