Casamento de caracteres

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1617 palavras )
  • Download(s) : 0
  • Publicado : 10 de dezembro de 2012
Ler documento completo
Amostra do texto
Trabalho Prático 1 de AEDs III
Thamara Karen Cunha Andrade
Departamento de Ciências da Computação - Universidade Federal de Minas Gerais
(UFMG)
thamara@dcc.ufmg.br

1. INTRODUÇÃO
Para o processamento de de textos em linguagem natural, códigos, dicionários,
sequenciamento de DNA em biologia computacional, entre outros, usamos cadeias de
caracteres que consistem em uma sequencia deelementos de um conjunto, denominado
alfabeto. Para procurar padrões em textos utilizamos algoritmos de emparelhamento de
cadeias que podem nos retornar o casamento exato do padrão ou aproximado, este
ultimo sendo usado em corretores ortográficos, filtros de spam e revisão de arquivos.
O problema dado consiste em verificar se houve ou não plágio musical em certa
música considerando os arcodes damúsica como texto, e a sequencia de acordes do
trecho suspeito como padrão. Uma atenção especial foi dada ao fato de que é
considerado plágio caso o trecho da música esteja em outro tom, ou seja, o programa
avalia a distância entre as notas musicais para definir se houve ou não o plágio.

2. SOLUÇÃO PROPOSTA
Para a solução do problema, foram utilizados dois vetores contendo inicialmente
asnotas musicais da música T[1...n] e do trecho suspeito P[1...m] (convertidas para
inteiros). Podemos ver na tabela 1 as notas e os valores definidos para cada nota:
Tabela 1: Notas musicais e suas representações
A

B

C

Db

Bb
1

A#

Cb

B#

C#

2

3

4

5

D

E

F

Gb

D#
6

Eb

Fb

E#

F#

7

8

9

10

G

Ab
G#

11

12

A seguir, osvetores iniciais são atualizados para conterem não o valor da nota
musical, mas sim a diferença entre as notas da música, seguindo a tabela acima, fazendo
com que os vetores T e P tenham tamanhos n-1 e m-1 respectivamente. Note que, apesar
de estarem representadas em uma tabela, as notas musicais são uma sequencia circular,
fazendo com que a distância de A a Ab seja 1(podendo ser obtidasubtraindo Ab de A,
ou A de Ab, sendo que quando a distância é um número negativo soma-se 12 para obter
o valor correto. Ex.: Ab-A=12-1=1, A-Ab=1-12=-11+12=1.).
Com os vetores preparados, o processo de encontrar tal padrão P no texto T é
inicializaado. Para isso foram utilizados quatro metodos de casamento exato de
caracteres, sendo o metodo força bruta o único que não pré-processa o padrão outexto
antes do inicio do processo de casamento. Os demais algoritmos(KMP, BMH e Shift-

And) pré-processam o padrão gerando complecidade de tempo menor que o de força
bruta, porém com complexidade de espaço maior.
De modo geral e superficial temos que o programa tem o seguinte algoritmo:
Algoritmo do programa:
Lê a entrada;
Dado o metodo escolhido, processa a cadeia de caracteres;
Imprime asaida.
Fim do programa.
Os algoritmos Shift-And, e BHM foram retirados do livro Projeto de algoritmos
de Ziviani[1], já algoritmo KMP é apresentado no livro de Cormem[2] e de Sedgewick[3].
Todos os algoritmos descritos utilizam a seguinte representação:
T

vetor texto

n

tamanho do vetor texto

P

vetor padrão

m

tamanho do vetor padrão

2.1. Algoritmo de Força bruta
Oalgoritmo tenta casar qualquer subcadeia no texto de comprimento m com o
padrão.
ForçaBruta(T, n, P, m)
para s

0 até n – m faça
faça se P[i ... m] = T [s + 1 ... s + m]
então retorna s

fim do algoritmo
Complexidade: O processamento de caracteres via ForçaBruta demora tempo
O((n-m+1)m), ou seja, O(n2) e esse caso é restrito ao pior caso, onde o padrão não
encontra-se no texto. Como oalgoritmo não pré-processa nenhum vetor, a
complexidade de espaço é dada por O(1) para todos os casos.

2.2. Algoritmo de Knuth-Morris-Pratt
O algoritmo de Knuth-Morris-Pratt utiliza da ideia de autômato finito para
melhorar a eficiência do algoritmo de casamento de caracteres. A ideia consiste tem
depois de casado alguns caracteres do padrão P no texto T, ao encontrar um caractere
que não...
tracking img