Conceitos Basicos PPM RE-PAIR HUFFMAN ZIV

Prévia do material em texto

PESQUISA - ETAPA 3
Prof.ª: CRISTINA
SEGUNDO SEMESTRE – 2017
Prediction by Partial Matching (PPM)
Conceito básico: 
O PPM, ou Prediction by partial matching, é um método originalmente desenvolvido por J.Cleary e I.Witten. Este método baseia-se num codificador que mantém um modelo estatístico do texto. Nesse modelo é tido em consideração o contexto do símbolo para que se possa atribuir-lhe uma probabilidade e esta ser enviada para um codificador aritmético adaptativo. O contexto de um símbolo corresponde aos ‘N’ símbolos precedentes. Este método pode ser encarado como um método de pré-processamento, visto ser uma preparação dos dados de input que posteriormente serão utilizados pelo codificador aritmético adaptativo.
Como funciona:
O algoritmo PPM, na sua forma mais simplista, propõe para um dado símbolo ‘S’ de entrada lhe seja atribuída uma probabilidade ‘P’, para que ‘S’ seja enviado para um codificador aritmético adaptativo e codificado com probabilidade ‘P’. O modelo estatístico contará o número de vezes que o símbolo ocorreu anteriormente e em que contexto, atribuindo-lhe a respectiva probabilidade. Desta forma é possível atribuir uma probabilidade ao símbolo que não dependa apenas da frequência absoluta mas também no contexto em que ocorreu.
A ideia chave do PPM é utilizar o seu conhecimento, onde para isso inicia-se com um contexto de ordem - N. O codificador PPM troca para um contexto menor, ordem - N-1, quando a probabilidade é ‘0’, isto é, o símbolo nunca foi visto na estrutura de dados anteriormente, no contexto em que se encontra.
Exemplo prático:
- Sistema embarcado para um monitor Holter que utiliza o modelo PPM na compressão de sinais ECG
Através de um monitor Holter, cardiologistas podem obter sinais ECG, que servem de base para a percepção de sintomas e atividades em pacientes, captados e armazenados pelos monitores em períodos maiores ou iguais a 24 horas, requisitando grandes espaços de armazenamento, aumentando, assim, o custo deste monitor. Utilizando o PPM, o dispositivo desenvolvido poderá reduzir consideravelmente a quantidade de dados armazenados, reduzindo, portanto, o espaço de armazenamento e o custo do dispositivo, permitindo ainda a rápida transmissão dos dados. Integrando o simulador de sinais ECG ao dispositivo, possibilita-se a geração de amostras de sinais eletrocardiográficos através do sistema embarcado, economizando tempo e eliminando dificuldades na obtenção de sinais, em comparação com a captação real de sinais ECG através de métodos invasivos e não invasivos. O mesmo permite a análise e o estudo de sinais ECG normais e anormais.
Re-Pair
Conceito básico: 
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.
Como funciona:
O primeiro passo de Re-Pair é atribuir um inteiro para cada símbolo no alfabeto e reescrever o texto com a sequência de inteiros correspondentes. Então, iterativamente, o par mais frequente de inteiros consecutivos, 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 são trocadas por C. Esse processo é repetido até que nenhum par consecutivo se repita no texto. Note que uma frase como C pode por sua vez, participar de novas frases como E -> D.C., portanto, o dicionário pode ser visto como uma hierarquia binária de frase, onde as folhas são símbolos do alfabeto e os nodos internos constroem outras frases ou símbolos.
Exemplo prático:
- Uso do método de compreensão Re-Pair para reduzir o espaço requerido por índices utilizados em espaços métricos baseado em permutações.
No banco de dados de objetos a partir de um espaço métrico, consultas feitas através de elementos do método de busca por proximidade ou similaridade entre elementos. Isso requer indexação desses bancos de dados. O índice baseado na permutação (IBP) é muito eficaz, em relação a outros algoritmos de busca de proximidade para resolver essas consultas. Mas na prática, usar IBPs exige uma quantidade excessiva de espaço na memória principal. Portanto, o objetivo principal deste documento é compactar esses índices usando o método de compressão Re-Pair. A compressão com Re-Pair é substituir pares de símbolos que são repetidos em permutações com novos símbolos simples. Para realizar isso, um algoritmo recursivo é implementado usando estruturas de dados, como Hash Tables e Heaps Binary, para conseguir uma compactação eficiente, já que geralmente eles precisam revisar milhões de símbolos. O método proposto é comparado com a alternativa de IBP compactos. Isto é para salvar a representação binária de cada máquina variável IBP. Concatenar a cadeia de bits formada representa um número considerado índice compacto. Testes experimentais com bases de dados vetoriais de baixa e alta dimensionalidade. Onde é medido e comparado ao desempenho e ao grau de algoritmos de compressão. O Re-Pair é muito eficaz para baixa dimensionalidade (de fato comprimido para 92% na dimensão). O pior cenário avaliado, correspondente à dimensão 1024, o IBP é comprimido para 46% do espaço original, enquanto o algoritmo compacto reduz para 25%, mas tem a desvantagem de que a descongelação IBP é muito mais lenta sua descompressão. Finalmente, deve notar-se que a redução do espaço utilizado pelo próprio IBP é boa porque permite que você trabalhe com maiores volumes de dados sem usar espaço em disco como memória virtual. Lembre-se de que este último prejudica significativamente o desempenho das consultas pelo custo que usaria o sistema operacional para paginar a memória principal e a memória virtual. 
Códigos de Huffman com bytes
Conceito básico:
A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. A codificação de Huffman em bytes proposta por Moura é uma variação chamada Byte-Huffman (BH) que associa uma sequência de bytes ao invés de bits para cada palavra do texto. Moura propõe outra variação chamada de Byte-Huffman Sincronizado (BHS). O método BHS utiliza códigos de Huffman com dígitos de 7 bits e adiciona um bit extra de sincronização para cada dígito do código comprimido.
Como funciona:
Uma árvore binária completa, chamada de árvore de Huffman é construída recursivamente a partir da junção dos dois símbolos de menor probabilidade, que são então somados em símbolos auxiliares e estes símbolos auxiliares recolocados no conjunto de símbolos. O processo termina quando todos os símbolos forem unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, atribuindo-se valores binários de 1 ou 0 para cada aresta, e os códigos são gerados a partir desse percurso.
A codificação de Huffman tem desempenho ótimo quando as probabilidades dos símbolos são potências negativas de dois. A codificação gerada tem também a garantia de ser não ambígua, pois nenhum código pode ser o prefixo de outro código.
O resultado do algoritmo de Huffman pode ser visto como uma tabela de códigos de tamanho variável para codificar um símbolo da fonte. Assim como em outros métodos de codificação, os símbolos mais comuns são geralmente representados usando-se menos dígitos que os símbolos que aparecem com menos frequência.
Exemplo prático:
- Compactação sem perda pelo método de Huffman associado à transformada de wavelet
Consiste na criação de um compactador de dados sem perda, a partir da verificação da viabilidade do uso da Transformada Wavelet associadas a codificação de Huffman; possibilitando a compressão e descompressão do arquivo, mantendo a integridade dos dados sem prejudicar a sua utilização pelo usuário.
Métodos de Ziv-Lempel
Conceito básico:
LZW (Lempel-Ziv-Welch) é um algoritmo de compressão de dados, derivado do algoritmo LZ78, baseado na localização e no registro das padronagens de uma estrutura em dicionário que codificamstrings de símbolos, de comprimentos variáveis, como códigos individuais. Esse código formam um índice para um dicionário de frases.
Como funciona:
O algoritmo de Lempel-Ziv utiliza duas áreas de trabalho: 
Dicionário onde ficam armazenadas as informações codificadas.
Área de pesquisa onde fica a string a comprimir ou descomprimir.
O método consiste de:
Compressão: identificar, na área de pesquisa, a maior sequência de símbolos armazenada no dicionário e substituí-la por um código.
Descompressão: os códigos da área de pesquisa devem ser substituídos pelas sequências de símbolos do dicionário, correspondentes.
Exemplo prático:
No quadro abaixo mostramos os passes da compressão da cadeia A_ASA_DA_CASA usando o método de LZW. A coluna I representa a cadeia lida na entrada desde que a última saída foi emitida. A coluna no dic? Indica se a sequência em I está presente no dicionário. a coluna nova entrada mostra o que será inserido no dicionário (como o dicionário já contém os 256 símbolos do código ASCII é impraticável mostrar todo seu conteúdo, por isso listamos apenas as novas entradas). E por fim a coluna saída mostra o código que será emitido na saída do programa, junto com o que ele representa no dicionário (entre parênteses).