Predição por correspondência parcial - Prediction by partial matching

Predição por correspondência parcial ( PPM ) é uma técnica de compressão de dados estatísticos adaptativos com base na modelagem e previsão de contexto . Os modelos PPM usam um conjunto de símbolos anteriores no fluxo de símbolos não compactados para prever o próximo símbolo no fluxo. Os algoritmos PPM também podem ser usados ​​para agrupar dados em agrupamentos previstos na análise de agrupamento .

Teoria

As previsões geralmente são reduzidas a classificações de símbolos. Cada símbolo (uma letra, bit ou qualquer outra quantidade de dados) é classificado antes de ser compactado e o sistema de classificação determina a palavra-código correspondente (e, portanto, a taxa de compactação). Em muitos algoritmos de compressão, a classificação é equivalente à estimativa da função de massa de probabilidade. Dadas as letras anteriores (ou dado um contexto), cada símbolo é atribuído com uma probabilidade. Por exemplo, na codificação aritmética, os símbolos são classificados por suas probabilidades de aparecerem após os símbolos anteriores e a sequência inteira é compactada em uma única fração que é calculada de acordo com essas probabilidades.

O número de símbolos anteriores, n , determina a ordem do modelo PPM, que é denotado como PPM ( n ). Variantes ilimitadas em que o contexto não tem limitações de comprimento também existem e são indicadas como PPM * . Se nenhuma previsão pode ser feita com base em todos os n símbolos de contexto, uma previsão é tentada com n  - 1 símbolos. Este processo é repetido até que uma correspondência seja encontrada ou nenhum outro símbolo permaneça no contexto. Nesse ponto, uma previsão fixa é feita.

Grande parte do trabalho de otimização de um modelo PPM é lidar com entradas que ainda não ocorreram no fluxo de entrada. A maneira óbvia de lidar com eles é criar um símbolo "nunca visto" que aciona a sequência de escape . Mas que probabilidade deve ser atribuída a um símbolo que nunca foi visto? Isso é chamado de problema de frequência zero . Uma variante usa o estimador de Laplace, que atribui ao símbolo "nunca visto" uma pseudo-contagem fixa de um. Uma variante chamada PPMd incrementa o pseudo-contagem do símbolo "nunca visto" toda vez que o símbolo "nunca visto" é usado. (Em outras palavras, o PPMd estima a probabilidade de um novo símbolo como a razão entre o número de símbolos únicos e o número total de símbolos observados).

Implementação

As implementações de compactação PPM variam muito em outros detalhes. A seleção real do símbolo é geralmente registrada usando codificação aritmética , embora também seja possível usar a codificação Huffman ou mesmo algum tipo de técnica de codificação de dicionário . O modelo subjacente usado na maioria dos algoritmos PPM também pode ser estendido para prever vários símbolos. Também é possível usar modelagem não Markov para substituir ou complementar a modelagem Markov. O tamanho do símbolo é geralmente estático, normalmente um único byte, o que torna fácil o manuseio genérico de qualquer formato de arquivo.

Pesquisas publicadas sobre essa família de algoritmos podem ser encontradas em meados da década de 1980. As implementações de software não eram populares até o início dos anos 1990 porque os algoritmos PPM requerem uma quantidade significativa de RAM . Implementações recentes de PPM estão entre os programas de compactação sem perdas de melhor desempenho para texto em linguagem natural .

PPMd é uma implementação do PPMII de Dmitry Shkarin. Ele é usado no RAR por padrão. Ele também é usado pelo 7-Zip como um dos vários métodos de compactação possíveis no formato de arquivo 7z .

As tentativas de melhorar os algoritmos PPM levaram à série PAQ de algoritmos de compressão de dados.

Um algoritmo PPM, em vez de ser usado para compactação, é usado para aumentar a eficiência da entrada do usuário no programa de método de entrada alternativo Dasher .

Veja também

Origens

  • Cleary, J .; Witten, I. (abril de 1984). "Compressão de dados usando codificação adaptativa e correspondência parcial de strings". IEEE Trans. Comum. 32 (4): 396–402. CiteSeerX  10.1.1.14.4305 . doi : 10.1109 / TCOM.1984.1096090 .
  • Moffat, A. (novembro de 1990). "Implementando o esquema de compressão de dados PPM". IEEE Trans. Comum. 38 (11): 1917–1921. CiteSeerX  10.1.1.120.8728 . doi : 10.1109 / 26.61469 .
  • Cleary, JG; Teahan, WJ; Witten, IH "Contextos de comprimento ilimitado para PPM" . The Computer Journal . Oxford, Inglaterra: Oxford University Press. 40 (2_e_3): Páginas 67–75. doi : 10.1093 / comjnl / 40.2_and_3.67 . ISSN  0010-4620 .
  • C. Bloom, Resolvendo os problemas de modelagem de contexto .
  • WJ Teahan, estimativa de probabilidade para PPM .
  • SchüRmann, T .; Grassberger, P. (setembro de 1996). "Estimativa de entropia de sequências de símbolos". Caos . 6 (3): 414–427. arXiv : cond-mat / 0203436 . Bibcode : 1996Chaos ... 6..414S . doi : 10.1063 / 1.166191 . PMID  12780271 .

Referências

links externos