Aula9-Processamento de Cadeias

Prévia do material em texto

Processamento de Cadeias 
Prof: Ekler Paulino de Mattos 
ekler.mattos@gmail.com 
CPCX/UFMS 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• Introdução 
• Cadeia: Entende-se uma sequência de elementos 
denominados caracteres. 
 
• Caracteres: são elementos escolhidos por um conjunto de 
elementos denominados alfabeto. 
 
• Ex: 011010101 é uma cadeia com alfabeto {0,1}. 
 
• Caracteres: 
• Não possuem relações estruturais entre si, a não ser a 
sua ordem sequêncial. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• Cadeias presentes na computação (Exemplos) 
 
• Processamento de textos, palavras, códigos, 
mensagens, 
 
 
• Aplicações: tratamento computacional de dicionários, 
mensagens de correio eletrônico, sequenciamento de 
DNA (biologia computacional), criptografia entre outros. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• Questões a serem tratadas: 
• Casamento de cadeias: Consiste verificar se a primeira 
delas contém a segunda, ou seja, se os caracteres que 
compõem a segunda cadeia aparecem sequencialmente 
também na primeira. 
• Ex: edição de textos. 
 
• Codificação de mensagens: Dada uma cadeia de 
caracteres, denominada mensagem, o problema consiste 
em codificá-la através da atribuição de códigos a seus 
caracteres, de modo a minimizar o comprimento total da 
mensagem codificada. 
• Ex: transmissão de mensagens em uma rede. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• O Problema do Casamento de Cadeias 
• Sequência de caracteres escolhidos de um conjunto 
chamado alfabeto. O número de caracteres da cadeia 
 é o seu comprimento. 
 
• Sejam X, Y, duas cadeias de caracteres com comprimentos n, 
m, respectivamente. n >=m. 
 
• Y é uma subcadeia da X quando Y for uma subsequencia 
consecutiva de X, isto é, quando existir algum inteiro l <= n-
m, Y é sufixo, tal que 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• O Problema do Casamento de Cadeias 
• Consiste em verificar se Y é subcadeia de X. Em caso 
positivo, localizar Y em X. Diz-se, então, que houve um 
casamento de Y com X na posição l + 1. 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• O Algoritmo da Força Bruta 
• Sejam X e Y cadeias com caracteres xi e yi, 1 <= I <= n e 1 
<= j <= m, m <= n. Deseja-se verificar se Y é subcadeia de X 
e, em caso positivo, localizar Y em X. Um método bastante 
simples consiste em examinar todas as possíveis situações. 
Se Y é subcadeia de X, então Y se encontra em X, deslocado 
de l posições à esquerda. 
 
• Idéia: Consiste em comparar Y com a subcadeia de tamanho 
m de X, que se inicia no caractere , para todos os 
possíveis de l. Ou seja, l = 0, 1, …, n-m. 1lx
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• O Algoritmo da Força Bruta 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
• O Algoritmo da Força Bruta 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
Lista de Exercícios 3 – L3 
Entrega: 18/11/2013 
• O Algoritmo da Força Bruta 
• Exercício 1: 
• Considerando duas cadeias de caracteres X e Y, de 
tamanhos m e n onde m>= n. Implemente o algoritmo de 
Força Bruta que: 
• A) Recupere a quantidade de ocorrências da cadeia 
 Y dentro na cadeia X. 
 
• B) Recupere as posições da cadeia Y em que foi 
encontrada a cadeia X. 
 
 
 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
• O Algoritmo de Knuth, Morris e Pratt. 
• Revisão do algoritmo de Força Bruta. 
http://www.youtube.com/watch?v=GVizb_fi
08E&feature=related 
http://www.youtube.com/watch?v=Zj_er99
KMb8&feature=related 
(c) Ekler Paulino de Mattos