여기 내 문제가 있습니다 - 일부 출력을 작성해야하는 프로그램이 있으며 압축 후 출력은 가능한 작아야합니다.사전 압축의 과학이 있습니까?
이 상황에서 묻는 첫 번째 질문은 "내 데이터에 사용해야하는 데이터는 무엇입니까?"입니다. XML? JSON? SQLite? TXT? 구조?
나는 "규칙"는 C와 같은 구조체 그러나 내가 알아 내기 위해 고군분투하고있어, 다른 형식들보다 압축하기 전에 당신에게 가능한 가장 작은 파일 을 줄 것입니다되는 말을 상당히 논쟁의 여지가없는 것 같아요 압축 후 해당 구조체를 가능한 한 작게 설계 할 경우 입니다. 소위 '사전 압축'작업.
예를 들어 최근에 나는 가능한 한 콤팩트 한 DNA를 보관해야했습니다. DNA에는 'A', 'C', 'G', 'T', 'N'의 5 글자가 있습니다. N은 '알지 못합니다.' 즉, 문자 당 최소 이진수는 3 비트입니다.
000 = A
001 = C
010 = G
011 = T
100 = N
그래서 나는 내가 생각 권리, 그리고, 네 글자 'AACA'처럼 말하는 DNA의 일정한 길이의 문자열을 사용하는 코드를 작성하고, '000 000 001 000'처럼 바이너리로 변환 한 후 반환 무엇을했다 2 바이트 'xxxx0000', '00001000'여기서 x는 패딩 (또한 0)입니다.
실제 프로그램은 76 자의 DNA를 가져와 29 바이트를 반환하지만 같은 생각입니다. 그런 다음이 29 바이트를 구조체 (29 uint8 바이트)에 썼습니다. 7211405 개의 DNA 조각으로 209130745 바이트 또는 209MB의 파일이 생성되었습니다. LZMA 압축 후이 파일은 74.3Mb로 줄어 들었습니다.
그런 다음 동일한 인코딩/압축을 다시 실행하기로 결정했지만 이번에는 각 문자를 4 비트로 인코딩합니다. 기본적으로 이전 파일의 4 번째 비트는 모두 0.001이됩니다. 001은 0001 등이됩니다. 결과 파일의 크기는 274Mb이므로 65Mb 더 커지지 만 70.2Mb 또는 4.1Mb로 압축됩니다. 최종 파일의 상당 부분 파일 크기.
그리고 gzip, bzip2 등에서 같은 것을 볼 수 있습니다. 바이트 당 2 개의 DNA 문자를 얻기 위해 제로를 추가하면 압축기가 도움이됩니다. 그래서 지금 뭐야? 압축기를 돕기 위해 내가 뭘 할 수 있을까요? 더 작은 파일 크기 (무손실)를 얻으려면 어떻게해야합니까?
내가 생각한 트릭 중 하나는 DNA 서열을 저장하여 정렬하고 순서를 재현하는 데 사용할 수있는 별도의 키가 있다는 것입니다. NumPy와이는 original_array을 다시 사용할 수 있습니다 my_array 배열의 인덱스의 목록입니다
my_array,key = numpy.unique(original_array, return_inverse=True)
my_arrayoriginal_array의 고유 항목의 정렬 된 목록하게 및 key 이루어집니다. 이상적으로, my_array는 키처럼 잘 압축 될 것입니다. 그러나 두 파일의 합은 대략 정렬되지 않은 구조체의 합계입니다. 어떤 경우에는 조금 작고 다른 곳에서는 조금 크지 만 집에 쓰지는 않습니다.
또 다른 아이디어는 그래프/trei (여전히 구조체로 인코딩되지만 각 행은 항목이 아닌 노드 임)와 같이 완전히 다른 데이터 구조를 사용하는 것이지만, 나는 생각하고있다. 잘못된 방법으로 압축합니다. 엔트로피의 한계를 넘어 파일 크기를 줄일 수는 없지만 작은 압축되지 않은 파일을 만드는 것보다 더 나은 경로 인 바이트에 데이터를 정렬하는 것과 같은 사전 압축에 대한 비밀이있을 수 있습니다. 그러나 더 큰 압축 파일.내가 을 요구하고 있지 않다
이 '어떻게 예압을해야합니까'나는 '부탁 해요 내가에 대한 자세한 내용을 배울 수있는 것은 예압, 그리고 그렇다면, 난 화두/검색어 무엇인가 ''을 찾고 있습니다.
불명확하거나 너무 광범위하게 폐쇄 된 것은 부끄러운 일입니다. Google의 '사전 압축'이 끝나면 여기에서 찾을 수있는 훌륭한 자료가 있습니다. http://mattmahoney.net/dc/dce.html –