유사하지만 동일한 문자열 목록을 압축하는 가장 좋은 방법은 무엇입니까?

Question

나는 아주 유사하지만 절대적으로 동일하지는 숫자가 많이 있습니다.

그들은 다소 다소 다를 수 있지만, 육안으로 유사성을 볼 수 있습니다.

모든 길이는 동일합니다. 각각 256 바이트입니다. 총 문자열 수는 2 ^ 16 미만입니다.

그러한 경우에 가장 좋은 압축 방법은 무엇입니까?

업데이트 ( 데이터 형식 ) :

데이터를 공유 할 수는 없지만 현실에 꽤 가까이 묘사 할 수 있습니다.

비행기에서 이동 및 도면을위한 일부 장치의 명령 순서 인 표기법 (예 : 로고 언어)을 상상해보십시오. 다음과 같은 :

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

.

등등.

이 언어의 전체 어휘는 영어 알파벳의 크기를 초과하지 않습니다.

문자열은 "U12C6P1L74D74R74U74P0 ...."전체 그림을 설명합니다.

이제는이 언어의 도움으로 매우 구체적인 이미지를 그릴 수있는 1 만 명의 수업을 상상해보십시오. 해당 국가의 국기처럼. 우리는 10K의 문자열을 모두 서로 다르며 동시에 모두 똑같습니다.

우리의 작업은 가능한 한 잘 끈 전체 무리를 압축합니다.

내 의심은 여기 에이 유사성과 흔한 길이를 착취하는 방법이 있으며, 허프만 (Huffman)의 흔한 길이가 있습니다. 명시 적으로 사용하지 않을 것입니다.

Answer 1

데이터가 무엇인지 알려주시겠습니까?어쩌면 DNA 서열처럼?처럼

agctgtgcgagagagagggtggg ...

ggctgtgcgagcgagagcggtggg ...

cgctgtgagagngagagggtgggg ...

ngctgtgcgagagagaggggtggg ...

ggctgtgcgagtgaggggtggg ...

... ...

? 어쩌면 아닐 수도 있습니다.어쨌든 여기에 두 가지 수준 또는 두 가지 방법이 있습니다 :

1. 허프만 코딩 : Ref.너 자신에 의한 위키 백과

2. stringology : ref. http://books.google.com.hk/books/abore./jewels_of_stringology.html?id=9ndohjxtiyyc

   문제를 해결하기 쉽지만 가장 좋은 방법을 선택하기가 어렵습니다. http:///en/en.wikipedia.org/wiki/data_compression http:///ko> 더 많은 도구.

Answer 2

256 바이트의 픽스 폭이 있고 2의 힘이 있기 때문에 Burrow-Wheeler 변환이나 그 크기의 전면 알고리즘이나 그 크기의 두 배로 옮길 것입니다.그런 다음 허프만 코드를 사용해 볼 수 있습니다.어쩌면 256 바이트와 BWT 및 MFT에서 Hilbert 곡선을 시도 할 수 있습니까?

Answer 3

"총 문자열의 총 수는 2 ^ 16 미만입니다."이것은 작고 경계 된 숫자입니다. 이는 직업을 매우 쉽게 만듭니다. 이전에 본 모든 문자열의 조회 테이블 (해시 테이블)을 유지하지 않는 이유는 무엇입니까?그런 다음 256 바이트의 모든 행을이 조회 테이블에 2 바이트 인덱스로 변환 할 수 있습니다.

다음과 같은 16 비트 정수가 있습니다.이러한 정수에는 "펜이 내려 가면 다음 명령이 그리기 시작할 가능성이 90 %가 있습니다."라는 패턴이 포함됩니다.이와 같은 패턴에 데이터가 포함되어 있으면 PPM이 원하는 것입니다.7-Zip은 고품질 PPM 구현을 가지고 있습니다.GUI 또는 CMD 라인을 사용하여 선택할 수 있습니다.