내 압축기를 더 빠르게 만드는 방법에 대한 제안

Question

사용자 지정 압축기로 압축하는 일부 데이터가 있는데 압축 된 데이터는 괜찮지 만 압축기에 오래 걸리는데 어떻게하면 더 빠르게 만들 수 있는지에 대한 조언을 구하고 있습니다. 내가 당신에게 모든 세부 사항을 알려주지.

입력 데이터는 최대 2^16 바이트의 배열입니다. 배열의 해당 바이트는 0x08과 0x37 사이의 값을 갖지 않으므로 (이미 포함 된) 길이가 4 ~ 51 바이트 인 임의의 발견 된 시퀀스를 대체하여 작동하는 간단한 LZ와 유사한 압축 스키마를 위해이를 사용할 수 있다고 결정했습니다. 시퀀스의 시작 부분의 인덱스의 하위 및 상위 바이트를 주소 지정하는 2 바이트가 뒤에 오는 0x08에서 0x37 범위의 단일 바이트로 "하위 주소"(배열의 시작에 더 가깝다)에서 발견됩니다. 따라서 압축 해제기에 원본 데이터의 길이 (단일 바이트 내에서)와 원래 데이터의 주소를 부여하여 원래의 어레이를 재구성합니다.

압축기는 모든 색인 (왼쪽에서 오른쪽으로)에서 시작하여 51에서 4 바이트까지의 길이 (길이가 긴 순서를 먼저 테스트 함)의 임의의 순서에 대해 해당 문자가 '왼쪽'인지 확인합니다. 어떤 의미인지는 보다 낮은 시작 지점보다 내가 확인하고 있습니다. 일치하는 항목이 두 개 이상인 경우 '저장하는 항목'을 더 많이 선택합니다. 이는 가장 왼쪽에있는 더 긴 일치를 의미합니다.

결과는 완벽한 있습니다 ...하지만 물론이 과도하게 살해한다 - 그것은 4 그 내부 memcmp는()와 사이클 '에 대한'중첩 그리고 그것은 현대적인 워크 스테이션에서 분에게 소요 약 20KB 상당의 데이터를 압축하기 때문에 도움이 필요합니다.

코드를 액세스 할 수있는 경우 here에 액세스 할 수 있습니다. 'job'은 44 행에서 시작됩니다.

물론 내가 필요한 세부 사항을 줄 수 있습니다. 여기에는 비밀이 없습니다. (BTW, 경우에 따라 ... 나는 이러한 이유로 압축 스키마를 변경하지 않을 것입니다. 이 제품은 내가 필요한만큼 정확하게 작동합니다.)

감사합니다.

Answer 1

정말 명백한 사실은 길이를 반복하지 않아도되고, 그 위치에서 가장 길게 일치하는 것이 무엇인지 알아내는 것입니다. 그것은 "검색"이 아니며 일치하는 모든 문자 쌍에 대해 일치를 1만큼 계속 확장하십시오. 그것이 멈 추면 그 위치에서 가장 길게 매치됩니다 (당연히 51에서 멈추도록 강요 할 수 있으므로 오버런하지 않습니다).

다른 일반적인 트릭은 3 또는 4 문자의 키를 찾을 수있는 오프셋 목록에 매핑하는 해시 맵을 유지하는 것입니다. 그렇게하면 성냥을 맺을 희망이있는 직위 만 시도하면됩니다. 이는 하단의 DEFLATE RFC에도 설명되어 있습니다.