Hist´orico
Um dos principais problemas durante a implementa¸c˜ao dos algoritmos utilizados para a detec¸c˜ao de padr˜oes em Carvalho (2001) foi a tendˆencia a sobrevalorizar pequenos intervalos durante a procura por padr˜oes. Isto era causado pela pr´opria metodologia empregada, a qual considerava como mais relevantes os padr˜oes que estivessem mais pr´oximos, em distˆancia euclidiana, dos centros de clusters calculados por meio de um SOM (Self-Organising Map), tal como proposto por Kohonen et al. (1996). Na medida em que a detec¸c˜ao de padr˜oes ´e um importante passo na implementa¸c˜ao das regras de Lerdahl & Jackendoff (1996), este problema demanda por uma solu¸c˜ao que leve a uma melhor precis˜ao dos resultados.
Com este objetivo em mente, imaginou-se uma solu¸c˜ao de car´ater h´ıbrido que pudesse caracterizar-se tanto pela precis˜ao na descoberta de padr˜oes quanto por uma flexibilidade que, atrav´es de generaliza¸c˜ao, permitisse a detec¸c˜ao de varia¸c˜oes dos mesmos. Assim, mostrou-se como promissor um algoritmo que ´e constitu´ıdo pelos passos seguintes:
1. Inicialmente, com a ajuda de uma heur´ıstica faz-se a varredura do trecho a ser analisado `a procura de padr˜oes repetitivos n˜ao-triviais (ver defini¸c˜oes adiante). 2. A partir dos padr˜oes encontrados cria-se um ou mais conjuntos de treinamento
(dependendo da dimens˜ao dos padr˜oes) constitu´ıdos dos padr˜oes originais acrescidos de varia¸c˜oes dos mesmos obtidas atrav´es da introdu¸c˜ao de ru´ıdo.
3. Com os conjuntos de treinamento obtidos no item anterior treina-se uma rede neural ou sistema nebuloso.
4. A partir dos resultados dos treinamentos varre-se novamente o trecho a ser analisado `a procura de variantes dos padr˜oes principais.
Neste trabalho ´e descrita primeira parte do algoritmo acima e ´e apresentada uma imple- menta¸c˜ao da mesma. Uma descri¸c˜ao detalhada dos procedimentos pode ser encontrada em Hsu et al. (2001).
Padr˜oes Repetitivos N˜ao-triviais – Defini¸c˜oes
Antes que seja descrita a heur´ıstica empregada faz-se necess´aria a exposi¸c˜ao das defini¸c˜oes de padr˜oes repetitivos e da n˜ao-trivialidade dos mesmos (Hsu et al., 2001).
Defini¸c˜ao 1
Para um subconjunto X de uma seq¨uˆencia de notas S, se X aparece mais do que uma vez em S n´os denominamos X um padr˜ao repetitivo em S. A freq¨uˆencia de repeti¸c˜ao do padr˜ao repetitivo X ´e o n´umero de apari¸c˜oes de X em S. O comprimento do padr˜ao repetitivo X, representado como kXk ´e o n´umero de notas em X.
Defini¸c˜ao 2
Um padr˜ao repetitivo X ´e n˜ao-trivial se e somente se n˜ao existe outro padr˜ao repetitivo Y tal que f req(X) = f req(Y ) e X ´e uma substring de Y .
Descri¸c˜ao da Heur´ıstica
Nesta subse¸c˜ao ser´a descrita a seq¨uˆencia de passos na qual opera o identificador de padr˜oes n˜ao-triviais. A entrada do algoritmo ´e uma lista de notas (das quais, neste primeiro est´agio, s˜ao desconsideradas as dura¸c˜oes) e a sa´ıda ´e uma lista de duplas cujo primeiro elemento ´e o padr˜ao e o segundo sua freq¨uˆencia de repeti¸c˜ao:
{(p1, f1), (p2, f2), . . . , (pi, fi)}
O algoritmo em quest˜ao constitui-se de duas se¸c˜oes fundamentais, as quais s˜ao expostas a seguir:
1. Constru¸c˜ao da Matriz Correlativa
(a) Considere uma lista de notas S, de comprimento n e cuja i-´esima nota ´e Si. (b) Considere uma matriz T (a matriz correlativa), de tamanho n×n e inicializada
com zeros.
(c) Para a primeira linha de T, considerando 2 ≤ j ≤ n, se S1 = Sj, ent˜ao, T1,j = 1.
(d) Para o restante da parte triangular superior de T:
Ti,j = Ti−1,j−1+ 1 se Si = Sj. considerando 2 ≤ i ≤ (n − 1), 3 ≤ j ≤ n, e i < j. 0 em outro caso.
2. Detec¸c˜ao dos Padr˜oes a partir da Matriz
(a) Considere S[a : b] um subconjunto de S indo da a-´esima at´e a b-´esima nota. (b) Considere um conjunto de padr˜oes candidatos CS inicializado como vazio.
(c) ∀ Ti,j > 0 ∃ P = S[j − Ti,j : j], sendo que P e todas as suas substrings s˜ao padr˜oes repetitivos.
(d) Na medida em que todas as substrings que n˜ao s˜ao sufixos2 de P s˜ao calculados durante o processamento de outras c´elulas, somente ´e necess´ario o processa- mento do pr´oprio P e de suas substrings sufixos. Sendo assim, para cada padr˜ao pat, subconjunto sufixo de P, acumula-se o n´umero de repeti¸c˜oes (rep_count), verifica-se se ´e subconjunto de outro padr˜ao (sub_count) e armazena-se o re- sultado no conjunto CS, o que pode ocorrer atrav´es de um dos quatro casos:
2
S˜ao chamados aqui aqui de sufixos as substrings cujo ´ultimo elemento ´e tamb´em o ´ultimo elemento de P.
Caso 1
Se Ti+1,j+1 = 0 ∧ pat /∈ CS, insere(pat, 1, 0) em CS. Caso 2
Se Ti+1,j+1 = 0 ∧ pat ∈ CS, atualiza (pat, rep count, sub count) para (pat, rep count + 1, sub count).
Caso 3
Se Ti+1,j+1 6= 0 ∧ pat /∈ CS, insere(pat, 1, 1) em CS. Caso 4
Se Ti+1,j+1 6= 0 ∧ pat ∈ CS, atualiza (pat, rep count, sub count) para (pat, rep count + 1, sub count + 1).
(e) Ap´os a inser¸c˜ao de todos os padr˜oes repetitivos no conjunto candidato CS ´e necess´ario remover os padr˜oes triviais. Isto ´e feito simplesmente eliminando os padr˜oes que possuem os mesmos ´ındices rep_count e sub_count.
(f) Finalmente, ´e necess´ario calcular a freq¨uˆencia dos padr˜oes restantes e n˜ao- triviais, atrav´es da equa¸c˜ao (Hsu et al., 2001):
fp =
(1 +p1 + 8 × rep countp) 2
Implementa¸c˜ao
Apesar de sua eficiˆencia, m´etodo apresentado originalmente possui uma limita¸c˜ao digna de nota. Esta prov´em do modo como m´usica ´e normalmente estruturada. De acordo com a praxis tradicional, um determinado padr˜ao pode (e normalmente o faz) aparecer, durante o transcurso de uma obra, com pequenas varia¸c˜oes em sua forma original. Sendo assim, um sistema visando a detec¸c˜ao de padr˜oes deve ser capaz de lidar com estas pequenas varia¸c˜oes nas diversas apari¸c˜oes de um determinado padr˜ao. Este n˜ao ´e o caso, entretanto, da presente heur´ıstica em sua forma original, a qual somente percebe repeti¸c˜oes literais de um padr˜ao. No sentido de superar este problema trˆes melhorias foram implementadas. O trabalho original, tratando exclusivamente da detec¸c˜ao de padr˜oes de alturas, elimi- na a possibilidade do reconhecimento do padr˜ao transposto (musicalmente falando) como sendo apenas uma variante do mesmo. Com o objetivo de incrementar a capacidade do algoritmo implementou-se, al´em da detec¸c˜ao de alturas somente, tamb´em a detec¸c˜ao de padr˜oes intervalares, o que elimina a falha de reconhecimento em padr˜oes transpostos3.
Na mesma linha de pensamento, considerou-se interessante e enriquecedor a inclus˜ao
3´
E importante ressaltar aqui que o termo transposi¸c˜ao, em M´usica, significa o deslocamento de um dado conjunto de alturas a um dado intervalo. Assim, ao utilizar-se uma representa¸c˜ao num´erica para as alturas (em inteiros), transpor um trecho significa simplesmente realizar a soma alg´ebrica de uma constante (representando o intervalo ao qual se deseja transpor o trecho) aos valores representantes das alturas do trecho. Por exemplo, se o padr˜ao [72–67–78] for transposto ascendentemente de um intervalo de 3 (ter¸ca-maior ), tornar-se-´a [75–70–81], enquanto se for transposto descendentemente por um intervalo de -2 (segunda-maior ), tornar-se-´a [70–65–76].
das varia¸c˜oes tem´aticas retrograda¸c˜ao, invers˜ao e retrograda¸c˜ao da invers˜ao4, todas tanto do ponto de vista de alturas quanto do ponto de vista intervalar. Desta forma, o identifi- cador torna-se mais adequado no tratamento anal´ıtico de obras polifˆonicas, nas quais s˜ao comuns tais tipos de varia¸c˜ao e tratamento.
Finalmente, foi considerado durante o c´alculo uma banda de passagem ao inv´es de uma ´unica altura. Este m´etodo torna poss´ıvel detectar pequenas varia¸c˜oes intervalares no interior de padr˜oes perceptivamente idˆenticos. Visando seguir a pr´atica musical real, a largura de banda aplicada a uma altura ´e proporcional `a dimens˜ao do intervalo entre ela e a pr´oxima altura.