Data structure for storing chord warming rules?

Question

What would be the most appropriate (naturally appropriate) way to represent different sequences of chord (musical) rules in the data structure so that each chord has a weighted set of options that it could advance to?

This data structure will be implemented in the procedural program for generating music in such a way that you could encode: (language-agnostic pseudocode)

Chord[7] songArray; Chord first = new Chord(I); //set the first chord value songArray[0] = first; for (i=0; i<7; i++){ Chord temp = songArray[i].next(); //select the following chord songArray[i+1] = temp; } 

Note. In classical type music, each chord in a given key can naturally move to another chord, following these rules:

  ---------------------- | Chord | Leads to | |======================= | I | any | | ii | V, vii | | iii | IV, vi | | IV | ii, V, vii | | V | vi | | vi | ii, ii, IV, V| | vii | I | ---------------------- 

The data structure will store various progressions as weighted parameters. As an example, consider the IV chord in any key way: IV can naturally go to ii, V or vii, but it can also violate the rules that apply to any other chord. Violation of the rules will occur infrequently.

I looked at some structure of linked lists / tree data, but it is unlikely to be like any type of tree or list I have ever used - in addition, I cannot figure out how to implement weighting:

Another thought was to use JSON or something similar, but it seems to reboot too quickly:

 { "I":{ "100%":{ "I", "ii", "iii", "IV", "V", "vi", "vii" } }, "ii":{ "80%":{ "V", "vii" }, "20%":{ "i", "ii", "iii", "IV", "vi" } }, // ... } 

Note. I am sure that this is implemented in several languages, and at the moment I am not interested in a specific language implementation, but in the language-agnostic architecture of the data structure.

Answer 1

A Markov chain can be a good help for this problem.

The Markov chain is a stochastic process where the transition to the next state is determined by the current state. Thus, for a given interval from the table, you apply weights to the "Leads to" values, and then arbitrarily determine what state will develop.

Answer 2

I expect you to have less than 100 chords, so if you use 32 bits to represent the likelihood of a series (probably excessive overflow), you will get an array of 100x100x4 (40,000) in size for a flat Markov representation. Depending on the sparseness of the matrix (for example, if you have 50 chords, but each usually displays up to 2 or 3 chords) for speed and less important spatial reasons, you may need an array of arrays, where each element of the final array (chord identifier , probability).

In any case, one of the key points here is that you should use a probability series rather than a sequence of probabilities. That is, instead of saying: "This chord has a 10% chance, and it has a 10% chance, and it has a 80% chance), they say:" the first chord has a 10% chance, the first two chords have a 20% chance, and the first three chords have a 100% chance. "

Here's why: When you select a random but weighted value, you can generate a number in a fixed range (for unsigned integers, from 0 to 0xFFFFFFFF), and then perform a binary search through chords rather than a linear search. (Find the element with the least number of probabilities that is still greater than or equal to the number you created.)

On the other hand, if you have only a few of the following chords for each chord, a linear search is more likely to be faster than a binary search due to a tougher cycle, and then the entire series of probabilities saves calculating a simple current sum of probability values.

If you don’t need the most amazing performance (and I suspect you don’t - for the computer there simply aren’t many chords in the music) for this part of your code, I honestly just stick to the flat representation of the Markov matrix - it’s easy to understand, easy to implement, reasonable execution speed.

Just as it is distracting, these kinds of things lend themselves well to thinking about prognostic coding - a general data compression methodology. You can consider an n-gram based algorithm (like PPM) to achieve a higher order of structure in your generation of music without requiring too much material. He worked in data compression for many years.

Answer 3

It seems that you need some kind of directional, weighted graph , where the nodes are chords, and the ribs are the progression parameters with the weights of the ribs being the probability of progression.