Casamento de caracteres

Trabalho Prático 1 de AEDs III
Thamara Karen Cunha Andrade
Departamento de Ciências da Computação - Universidade Federal de Minas Gerais
(UFMG)
[e-mail]

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 de elementos 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 da mú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 as notas 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, os vetores 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 obtida