algoritmo de embalagem texto

Question

Aposto que alguém tenha resolvido isso antes, mas minhas pesquisas vêm-se vazia.

Eu quero pegar uma lista de palavras em um buffer, mantendo o controle da posição inicial e comprimento de cada palavra. O truque é que eu gostaria de embalar o buffer de forma eficiente, eliminando a redundância.

Exemplo: boneca casa de bonecas

Estes podem ser embalados para o buffer é simplesmente como dollhouse, lembrando-se que é doll quatro letras começam na posição 0, dollhouse é nove letras a 0, e é house cinco letras em 3.

O que eu vim acima com até agora é:

1. Classificar as palavras mais longo para o mais curto: (casa de bonecas, casa, boneca)
2. Digitalizar o tampão para ver se a string já existe como um substring, em caso afirmativo observe o local.
3. Se ele não existir, adicioná-lo ao final do buffer.

Desde palavras longas, muitas vezes contêm palavras mais curtas, isso funciona muito bem, mas deve ser possível fazer significativamente melhor. Por exemplo, se eu estender a lista de palavras para incluir ragdoll, em seguida, meu algoritmo vem com dollhouseragdoll que é menos eficiente do que ragdollhouse.

Este é um passo de pré-processamento, então eu não estou terrivelmente preocupado com velocidade. O (n ^ 2) é muito bem. Por outro lado, minha lista real tem dezenas de milhares de palavras, então O (n!) É provavelmente fora de questão.

Como uma nota lateral, este regime de armazenagem é utilizado para os dados na tabela `nome de uma fonte TrueType, cf. http://www.microsoft.com/typography/otspec/name.htm

Answer 1

Este é o menor problema supercordas : encontrar a cadeia mais curta que contém um conjunto de cordas dadas como substrings. De acordo com a este papel IEEE (que você não pode ter acesso a, infelizmente, ), a solução deste problema é exatamente NP-completos . No entanto, as soluções heurísticas estão disponíveis.

Como primeiro passo, você deve encontrar todas as cadeias que são substrings de outras cordas e excluí-los (é claro que você ainda precisa gravar as suas posições em relação às cordas que contêm alguma forma). Essas seqüências totalmente contidos podem ser encontrados de forma eficiente usando um generalizada sufixo árvore .

Em seguida, fundindo repetidamente as duas cordas ter maior sobreposição, você está garantido para produzir uma solução cujo comprimento não é pior do que 4 vezes o comprimento mínimo possível. Deve ser possível encontrar sobreposição tamanhos rapidamente usando dois árvore patricia como sugerido por um comentário por Zifre em resposta de Konrad Rudolph. Ou, você pode ser capaz de usar a árvore de sufixo generalizados de alguma forma.

Me desculpe, eu não posso desenterrar um link decente para você - não parece ser uma página da Wikipedia, ou informações acessíveis publicamente sobre este problema particular. Ele é mencionado brevemente aqui , embora nenhuma sugeriu As soluções são fornecidas.

Answer 2

Eu acho que você pode usar um Radix Árvore . Não custa alguma memória por causa de ponteiros para as folhas e os pais, mas é fácil de combinar-se cordas (O (k) (onde k é o tamanho maior string).

Answer 3

Meu primeiro pensamento aqui é: usar uma estrutura de dados para determinar prefixos e sufixos de suas cordas comuns. Em seguida, classificar as palavras em consideração desses prefixos e sufixos. Isso resultaria em sua ragdollhouse desejado.

Answer 4

é semelhante à Knapsack problema, que é NP-completo, então não há um algoritmo "definitiva".

Answer 5

Eu fiz uma volta laboratório na faculdade em que a tarefa de implementar um programa de compressão simples.

O que fizemos sequencialmente foi aplicar essas técnicas para texto:

• BWT ( Burrows-Wheeler transformar ): ajuda letras de reordenamento em seqüências de idêntico letras (dica * existem substituições matemáticos para obter as letras em vez de realmente fazer as rotações)
• MTF ( Mover para frente transformar ): reescreve a sequência de letras como uma seqüência de índices de uma lista dinâmica.
• Huffman codificação : Uma forma de codificação de entropia que constrói um código de comprimento variável tabela em que os códigos curtos são dadas aos símbolos freqüentemente encontrados e códigos mais longos são dadas aos símbolos raramente encontradas

Aqui, eu encontrei o página atribuição .

Para receber de volta seu texto original, você fazer (1) Huffman decodificação, (2) inversa MTF, e depois (3) inversa BWT. Há vários bons recursos sobre tudo isso na Interwebs.

Answer 6

Refine etapa 3.

• Procure lista atual e ver se qualquer palavra na lista começa com um sufixo da palavra atual. (Você pode querer manter o sufixo mais tempo do que algum tempo - mais de 1, por exemplo).
• Se sim, em seguida, adicione o prefixo distinto esta palavra como um prefixo para a palavra existentes, e ajustar todas as referências existentes de forma adequada (lento!)
• Se não, adicione palavra para o fim da lista como no passo atual 3.

Isto lhe daria 'ragdollhouse', como os dados armazenados no seu exemplo. Não está claro se seria sempre trabalhar de forma otimizada (se você também tinha 'barbiedoll' e 'dólar' na lista de palavras, por exemplo).

Answer 7

Eu não reinventar esta roda mais uma vez. Há já passou uma enorme quantidade de mão de obra em algoritmos de compressão, porque não tomar uma das que já estão disponíveis?

Aqui estão algumas boas escolhas:

• gzip para compressão rápido / velocidade de descompressão
• bzip2 para uma compressão amargo pouco, mas muito mais lento descompressão
• LZMA para taxa de compressão muito elevada e descompressão rápida (mais rápido do que bzip2 mas mais lento que o gzip)
• lzop para muito rápido compressão / descompressão

Se você usar Java, gzip já está integrado .

Answer 8

Não está claro o que você quer fazer.

Você quer uma estrutura de dados que permite a você armazenar de forma a memória consciente as cordas enquanto as operações de locação como procurar possível em uma quantidade razoável de tempo?

Você só quer uma variedade de palavras, comprimido?

No primeiro caso, você pode ir para um trie patricia ou uma String B-Tree.

Para o segundo caso, você pode simplesmente adotar algumas techinique compactação do índice, assim:

Se você tem algo como:

aaa 
aaab
aasd
abaco
abad

Você pode comprimir assim:

0aaa
3b
2sd
1baco
2ad

O número é o comprimento da maior prefixo comum com a sequência anterior. Você pode ajustar esse esquema, por ex. planejamento de um "restart" do prefixo comum depois de apenas K palavras, para uma reconstrução rápida