Pesquisa etapa 3

Prévia do material em texto

PESQUISA - ETAPA 3 
 
 
 
 
 
BRUNO REZENDE PEREIRA 16-33251 
 
 
 
 
 
Prof.ª: CRISTINA 
 
 
DIVINÓPOLIS-MG 
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 codificam strings 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).