단어 목록 인코딩을 위한 압축 알고리즘
https://stackoverflow.com/questions/405433
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 단어 목록을 효과적으로 철자 검사 사전으로 변환하기 위한 알고리즘 및/또는 데이터 구조에 대한 구체적인 제안이나 참조를 찾고 있습니다.이 체계의 목적은 원시 단어 목록을 인코딩된 형식으로 매우 높은 압축 비율로 만드는 것입니다.인코딩된 사전에 대한 유일한 출력 요구 사항은 제안된 대상 단어가 상대적으로 효율적인 방식으로 원본 단어 목록에 대해 존재하는지 테스트할 수 있다는 것입니다.예를 들어, 애플리케이션은 100,000 단어 사전과 비교하여 10,000 단어를 확인하려고 할 수 있습니다.그것은 ~ 아니다 인코딩된 사전 형식이 원래 단어 목록 형식으로 [쉽게] 다시 변환될 수 있어야 한다는 요구 사항 - 결과 사전에 대해 테스트된 각 단어에 대해 바이너리 예/아니요 결과가 필요한 전부입니다.
나는 압축 비율을 향상시키기 위해 인코딩 체계가 단수형 및 복수형, 소유형, 축약형 등과 같은 특정 언어의 알려진 구조를 활용할 것이라고 가정합니다.나는 주로 영어 단어를 인코딩하는 데 특히 관심이 있지만 명확하게 하기 위해 이 체계는 모든 ASCII 텍스트 "단어"를 인코딩할 수 있어야 합니다.
제가 염두에 두고 있는 특정 애플리케이션은 비휘발성 저장 공간이 매우 중요하고 사전이 무작위로 액세스 가능한 읽기 전용 메모리 영역인 임베디드 장치용이라고 가정할 수 있습니다.
편집하다:사전의 요구 사항을 요약하면 다음과 같습니다.
- 거짓 긍정 제로
- 거짓 부정 제로
- 매우 높은 압축률
- 감압 필요 없음
해결책
McIlroy 's를 참조하십시오 "철자 목록 개발" ~에 그의 술집 페이지. 미니 컴퓨터의 맞춤법 검사에 관한 고전적인 오래된 종이는 나열된 것들에 놀랍게 잘 맵핑됩니다. 접미사 스트리핑 및 두 가지 다른 압축 방법의 상세한 분석 : 블룸 필터 및 관련 체계 Huffman-Coding Sparse Bitset; 나는 그가 선택한 방법보다 우선적으로 블룸 필터와 함께 갈 것입니다. (진주 프로그래밍 이 논문에 대한 짧은 장이 있습니다.)
전체 텍스트 검색 시스템에 Lexicon을 저장하는 데 사용되는 방법 (예 : 정보 검색 소개. 위의 방법과 달리 이것은 잘못된 긍정이 없습니다.
다른 팁
블룸 필터 (http://en.wikipedia.org/wiki/bloom_filter 그리고 http://www.coolsnap.net/kevin/?p=13)는 일부 맞춤법 검사기에서 사전 단어를 매우 작게 저장하는 데 사용되는 데이터 구조입니다. 그러나 잘못된 긍정의 위험이 있습니다.
패딩 된 접미사 트리를 제안합니다. Wordlist의 우수한 압축 및 우수한 조회 시간.
요약 :
- 제로 오 탐지
- 제로 오 탐지 부정
- 높은 압축 비율
- 반대로 필요하지 않습니다 (즉, 무수압이 필요하지 않음)
나는 블룸 필터를 제안하려고했지만, 이것들은 0이 아닌 오 탐지가 있습니다.
대신 진주를 프로그래밍하는 유사한 요구 사항에 대해 이야기합니다 (/usr/share/dict/words 41k).
이것은 줄기의 수축 접근법을 취했습니다.
- 현재
- 대표하다
- 대표
- 와전
7비트 형식의 연속 접미사로 단어를 저장하면 30% 이상의 압축률을 얻을 수 있습니다.이것이 무엇인지는 잘 모르겠지만 트리 구조로 매우 효과적으로 변환됩니다.
전.:a+n+d+s|an+d+y|및+es+roid
다음과 비교하면 26자입니다.
A와 Andes Android로 광고
33입니다.
7비트 콘텐츠로 저장하기 위한 압축률 12.5%를 고려하면 총 압축률은 약 31%입니다.물론 압축 비율은 단어 목록의 크기와 내용에 따라 달라집니다.
이를 26-루트 트리 구조로 바꾸면 플랫 파일에 대한 일반 텍스트 하위 문자열 비교보다 검색 속도가 더 빨라질 수 있습니다.
생각해 보면 26개의 문자와 구분 기호 2개만 사용하는 경우 모든 작업을 5비트로 수행할 수 있습니다. 이는 그 자체로 37.5% 압축이며 위의 예에서는 50% 이상의 압축률을 가져옵니다.
나는 당신의 최선의 방법이라고 생각합니다 압축 된 접미사 트리 / 압축 된 접미사 어레이. 위의 링크에서 풍부한 정보를 찾을 수 있습니다. 이것은 진행중인 연구 분야이며 실제로 매우 흥미 롭습니다.
나는 이것에 대한 전문가는 아니지만 그렇지 않습니다 접두사 트리 이것에 대한 거의 표준 솔루션? 그것은 단어의 일반적인 접두사를 한 번만 저장합니다.
순수한 압축의 경우 최대 압축 사이트는 4MB 영어 단어 목록에 대한 몇 가지 결과를 제공하며, 최고의 프로그램은 이것을 약 400KB로 압축합니다. 텍스트/워드 압축을위한 다른 압축 리소스는 다음과 같습니다. 허터 상 페이지 그리고 큰 텍스트 압축 벤치 마크.
Knuth는 a "패트리샤 트리" 안에 컴퓨터 프로그래밍의 기술 vol. 삼. 나는 실제 작업에 그것을 사용한 적이 없지만 아마도 도움이 될 것입니다.
편집 : RAM 제약 조건은 무엇입니까? RAM보다 RAM이 더 많으면 ROM의 데이터 압축 (RAM으로 감압이 필요한)이 올바른 방법 일 것입니다. 나는 당신이 중간 정도이지만 많은 양의 RAM을 가지고 있다면, 기술적으로는 데이터 구조의 일부를 메모리의 압축 블로브로 저장하고, 몇 가지 주위를 유지하고 적절한 것을 동적으로 압축시킬 수있는 최소한의 캐시를 저장할 수 있다고 생각합니다. 캐시에 없을 때 블로브.
