¿Algoritmo para optimizar la identificación de progresiones de acordes en una canción?
Desarrollo una aplicación de música y necesito encontrar una combinación “óptima” de progresiones de acordes/harmónicos estándar utilizados en una canción. Las progresiones estándar en mi base de datos son de 2 o 4 acordes, y no son “exclusivas”.
Por ejemplo, si una parte de una canción utiliza la secuencia de acordes Fm7-Bb7-Eb7M-Ab7M, coincidirá con las progresiones estándar Fm7-Bb7 (II-V) y Bb7-Eb7M (V-I), pero también con Fm7-Bb7-Eb7M-Ab7M (II-V-I-IV). Por supuesto, una canción puede tener cualquier número de acordes, y muy a menudo hay secuencias de acordes que no corresponden a ninguna progresión de acordes estándar.
La combinación óptima de progresiones estándar que estoy buscando es aquella que minimiza el número de compases de la canción que no están cubiertos por ninguna progresión estándar.
Me es difícil encontrar la manera correcta de abordar esto, cualquier ayuda es bienvenida.
EDITAR:
De hecho @user58697, es mucho más fácil de explicar con una secuencia de letras y un vocabulario de palabras de 2 o 4 letras, por ejemplo:
- texto = ABCDDCEFGHX
- vocabulario = ABCD, CDDC, EFGH, AB
Quiero seleccionar las palabras de manera que minimice el número de letras que no formen parte de una palabra:
- texto = {ABCD}DC{EFGH}X: 3 letras que no forman parte de una palabra.
- texto = {AB}{CDDC}{EFGH}X: mejor solución.
Con un texto largo, generalmente hay varias soluciones óptimas.
davy.ai
Una posible aproximación para resolver este problema es utilizar un algoritmo de programación dinámica.
En primer lugar, podemos representar cada secuencia de acordes como un grafo donde cada nodo corresponde a un acorde y cada arista corresponde a una transición de un acorde a otro. También podemos etiquetar cada arista con el intervalo (por ejemplo, II, V, IV) que corresponde a la progresión de acordes.
Luego, podemos utilizar programación dinámica para calcular la solución óptima para subcadenas de la canción. Específicamente, podemos definir un arreglo
dp[i]que representa el número mínimo de medidas no cubiertas para la subcadena que comienza en la posicióni. Podemos calculardp[i]de la siguiente manera:icorresponde a una progresión estándar, entoncesdp[i] = 0.dp[i + longitud de la arista]. Elegimos el acorde que minimice el costo.Finalmente, la solución óptima para toda la canción se encuentra en
dp[0].Nota que este algoritmo tiene una complejidad temporal de O(N^2), donde N es la longitud de la canción. Sin embargo, se puede optimizar aún más utilizando memorización para evitar recalcular los mismos subproblemas. Además, la elección de progresiones estándar y sus grafos correspondientes puede tener un impacto significativo en la calidad de la solución.