Algoritmo de compressão para listas de Codificação do Word

Question

Eu estou estou procurando sugestões ou referências específicas a um algoritmo e / ou estruturas de dados para a codificação de uma lista de palavras para o que seria efetivamente viria a ser um dicionário de verificação ortográfica. Os objetivos deste esquema resultaria em uma proporção muito alta compressão da lista de palavras-prima na forma codificada. A única exigência de saída que eu tenho no dicionário codificado é que qualquer palavra meta proposta pode ser testado para a existência contra a lista palavra original de uma maneira relativamente eficiente. Por exemplo, a aplicação pode querer verificar 10.000 palavras contra um dicionário de 100.000 palavras. É não um requisito para a forma de dicionário codificado para ser capaz de ser [facilmente] convertidos de volta para a forma de lista palavra original - um sim binárias / não resultado é tudo o que é necessário para cada palavra testado contra o dicionário resultante.

Estou assumindo o esquema de codificação, para melhorar a taxa de compressão, iria tirar proveito de estruturas conhecidas em um determinado idioma, tais como formas singular e plural, formas possessivas, contrações, etc. Eu estou interessado especificamente na codificação principalmente palavras em inglês, mas para ser claro, o esquema deve ser capaz de codificar "palavras" texto todo e qualquer ASCII.

A aplicação particular que tenho em mente você pode supor é para dispositivos embarcados onde o espaço de armazenamento não volátil é um prêmio eo dicionário seria uma área de memória só de leitura aleatória acessível.

Editar : Para resumir os requisitos do dicionário:

• zero falsos positivos
• zero falsos negativos
• taxa de compressão muito alto
• Não há necessidade de descompressão

Answer 1

Veja de McIlroy "Desenvolvimento de uma lista de ortografia" em < a href = "http://www.cs.dartmouth.edu/~doug/pubs.html" rel = "noreferrer"> sua página bares . papel velho clássico sobre a verificação ortográfica em um minicomputador, que restrições mapear surpreendentemente bem para aqueles que você listou. A análise detalhada de Affix decapagem e dois métodos diferentes de compressão: filtros Bloom e um esquema de codificação relacionado Huffman-bitset um escasso; Eu iria com Filtros Bloom provavelmente em preferência ao método que ele escolheu, que aperta mais alguns kB fora a um custo significativo na velocidade. ( Programação Pérolas tem um capítulo curto sobre este papel.)

Veja também os métodos utilizados para armazenar o léxico nos sistemas de busca de texto completo, por exemplo, Introduction to Information Retrieval . Ao contrário dos métodos acima esta não tem falsos positivos.

Answer 2

A Bloom Filter ( http://en.wikipedia.org/wiki/Bloom_filter http://www.coolsnap.net/kevin/?p=13 ) é uma estrutura de dados usada para armazenar as palavras do dicionário de uma forma muito compacta em alguns corretores ortográficos. Há, no entanto, um risco para a falsos positivos.

Answer 3

Eu sugiro uma árvore sufixo acolchoada. Boa compressão em listas de palavras, e excelente pesquisa vezes.

http://en.wikipedia.org/wiki/Suffix_tree

Answer 4

Para resumir:

• zero falsos positivos
• zero falsos negativos
• alta taxa de compressão
• sem necessidade de inverso (isto é, sem descompressão necessário)

Eu ia sugerir filtros Bloom, mas estes têm diferentes de zero falsos positivos.

Em vez disso, Programação Pérolas fala de um conjunto semelhante de requisitos (/usr/share/dict/words em 41K).

Isso levou a abordagem de contração de hastes: Por exemplo: Enviado era a raiz, por isso poderia ter pré e pós-fixes acrescentou:

• presente
• representa
• representação
• deturpação

Answer 5

Você pode obter uma taxa de 30% + compressão fora de armazenar palavras como sufixos sucessivas em formato de 7 bits. Eu não tenho certeza do que isso é chamado, mas se traduz bastante eficaz em uma estrutura de árvore.

ex .: a + n + d + s | an + d + y | e + ES + roid

é 26 caracteres, em comparação com:

a a de Anúncios Como e qualquer andes android

que é 33.

Fatorando taxa de compressão de 12,5% para o armazenamento como o conteúdo de 7 bits, que é cerca de compressão total de 31%. Taxa de compressão depende, é claro, do tamanho e do conteúdo de sua lista de palavras.

transformar isso em uma estrutura de árvore de 26 raiz provavelmente resultar em pesquisas que são mais rápidos do que um texto simples substring comparação contra um arquivo simples.

Agora que penso nisso, se você estiver usando apenas 26 caracteres mais dois para delimitadores, você pode fazer tudo em 5 bits, que é compressão de 37,5%, em si e por si, trazendo o exemplo acima para mais de uma compressão de 50% taxa.

Answer 6

Eu acho que sua melhor aposta é um Compressed Sufixo Árvore / Compressed Sufixo matriz . Você pode encontrar uma grande variedade de informações nos links acima. Esta é uma área de investigação em curso, muito interessante.

Answer 7

Eu não sou um especialista sobre isso, mas não é prefixo árvore praticamente solução padrão para isso? Que armazena prefixos comuns de palavras apenas uma vez.

Answer 8

Para compressão pura, o compressão máxima ofertas do site alguns resultados para um 4 MB wordlist Inglês, melhor programa comprime este para cerca de 400 KB. Alguns outros recursos de compressão para texto / compressão palavra são a Prêmio Hutter página e Texto Grande compressão de Referência .

Answer 9

Knuth menciona um "Patricia trie" em The Art of Computer Programming vol. 3 . Eu nunca usei-o para qualquer trabalho real, mas talvez isso seria útil.

edit: qual é a sua restrição RAM? Se você tem muito mais memória RAM do que ROM disponível, talvez a compressão de dados na ROM (requerendo descompressão na RAM) é o caminho certo a seguir. Suponho que se você tem um meio, mas não grande quantidade de RAM, tecnicamente você também pode armazenar porções da estrutura de dados como blobs compactados na memória, e um cache menos recentemente utilizado para manter várias delas ao redor, então descomprimir dinamicamente o apropriado blob quando não está no cache.