나는 압축하려는 짧은 문자열 목록을 가지고 있지만 전체 목록의 압축을 풀지 않고도 언제든지 목록의 임의 문자열을 압축 해제 할 수 있기를 원합니다.짧은 문자열의 긴 목록을 압축하십시오.
나는 사전 목록을 알고 있으며 사전 처리의 양은 중요하지 않습니다. 또한 상당한 O (1) 메모리 오버 헤드가있는 경우에도 문제가 없습니다.
저는 무손실 압축 알고리즘을 사용하여 각 문자열을 독립적으로 압축 할 수 있다는 것을 알고 있습니다. 그러나 문자열이 매우 짧고 각각 중복성이 많지 않으므로 제대로 작동하지 않습니다. 그러나 전체적으로 중복성이 많습니다.
한 번에 약 64K 개의 문자열 (약 32 개의 문자열)을 압축하는 것이 좋습니다. 원하는 문자열을 얻으려면 평균 16 개의 문자열 만 압축해야합니다. 마찬가지로 1,000,000. deflate (gzip이 사용하는 압축 방법)를 사용하면 거의 동일한 압축률을 얻을 수 있습니다.
또 다른 방법으로는 deflate를 사용하여 2,000,000 개의 문자열에서 가장 일반적으로 보이는 하위 문자열로 구성된 32K "사전"을 작성하는 것입니다. 그런 다음 각 문자열은 32K를 사용하여 개별적으로 압축하여 일치 항목을 그릴 수 있습니다. 문자열에 그런 종류의 공통점이있는 경우 동일한 압축에 가까워 질 수 있습니다. (zlib'sdeflateSetDictionary() 및 inflateSetDictionary() 기능을 참조하십시오.
목록은 얼마 동안입니까? 문자열은 얼마나 짧습니까? 그들은 보통 컴프레서로 얼마나 압축합니까? –
@MarkAdler 2 백만 개의 문자열, 평균 크기 2k, gzip으로 ~ 35 % 압축률 –