A Recuperação de Dados

Exercício – Etapa 3 Luiz Henrique Alves Gondim PPM

PPM(Prediction by Partial Matching) é um método para prever o próximo símbolo dependendo n anterior.Este método é chamado previsão de Markov modelo de ordem n. Em caso de texto em linguagem natural como o Inglês é claro intuitivamente e provado por alguns pesquisadores que a probabilidade de cada símbolo próximo é altamente dependente de símbolos anteriores. O método mais óbvio para usar este recurso é para incorporá-lo com uma das compressões entropia conhecidos que têm para reunir estatísticas . Os candidatos naturais são Huffman e Arithmetic compressões . Pode ser variantes adaptativa ou estática desta algoritmos.

A questão-chave é mudar alfabeto para ser alfabeto de sequências e não alfabeto de símbolos individuais :

- Suponha modelo de Markov de ordem n .

- Deixe o fluxo de entrada para ser sequência X .

- Para cada Xi símbolo que está na sequência X em lugar i:

Atualizar probabilidade da sequência Y , y = [ XI - XI N ... ] . Seja y a ser um símbolo do alfabeto alvo.

Atualize todas as estruturas relevantes no algoritmo de base.

Execute o restante das etapas necessárias exigidas no algoritmo de base . Observe definição da sequência y:

y = [ Xi-n ... Xi ] .

If X i -n ou outras partículas da sequência não estão disponíveis , há algumas opções para lidar com esta situação:

- Xi saída não codificada e pular para o próximo símbolo

- Adicionar símbolo abreviado para o alfabeto .

RE-Pair

É uma técnica de dicionário semiestática baseada na localização dos pares frequentes de símbolos e sua substituição por um novo símbolo. O primeiro passo da Re-Pair é atribuir um inteiro para cada símbolo no alfabeto e reescrever o texto com a sequencia de inteiros correspondente. Entao, iterativamente, o par mais frequente de inteiros consecutivo, A . B, é identificado. Uma regra C -> A . B, para um novo inteiro C, é inserida no dicionário e todas as ocorrências de A x B sao trocados por C( C é chamado de frase). Esse processo ;e repetido ate que

nenhum par consecutivo reputa-se no texto. E assim por sua vez C pode, por sua vez, participar em novas frases com E -> D.C. Portanto, o dicionário pode ser visto como uma hierarquia binaria de frases, onde as folhas sao símbolos do alfabeto e os nodos internos constroem outras frases ou símbolos. Sendo que a sequencia final tenha sido obtida, ela pode ser deixada da maneira que esta ou pode ser sujeita a mais uma processo de compressão de ordem zero.

Codigo Huffman com bytes

O método original proposto por Huffman leva naturalmente a árvores de codificação binárias, como elas produzem a melhor compressão em comparação com árvores de codificação de maior paridade. Ë possível, entretanto, fazer o código atribuir uma sequência de bytes inteiros para cada símbolo. Como resultado, a árvore de Huffman possui grau 256 no lugar de 2.

Usando-se bytes em vez de bits para codificar, o que considera uma modelo baseado em palavras, degrada as taxas de compressão para cerca de 30%, mas elas ainda são competitivas. A descompressão de códigos de Huffman com bytes é muito mais rápida do que a do código binário, já que operações de deslocamento de bits e mas caramento não são necessárias.

Outra vantagem da codificação de huffman com bytes é que a busca direta no texto comprimido é mais simples , já que podemos realizar comparação do tipo byte a byte, como é feita na comparação de strings tradicional. O processo é simples, varre todos os bytes do texto comprimido uma vez e realiza muito pouco trabalho por byte examinado. Consequentemente, ele é muito rápido. Em particular, o processo é muito melhor de que uma varredura sequencial sobre o texto original, visto que somente 30% de E/S é necessária.

Códigos Densos

É uma alternativa de codificação que é mais simples do que a codificação de Huffman por bytes, e que pode render quase o mesmo desempenho de compressão quando combinada com modelagem baseada em palavras, é a codificação densa. A ideia ainda consistem em atribuir codewords menores para símbolos mais frequentes, mas a codificação depende somente do hanking do símbolo( isto é, a posição dele quando ordenado por frequência decrescente)