Data structure for storing chord progression rules? [closed]

Question

What would be the most appropriate (naturally suited) way to represent the various chord progression (musical) rules in a data-structure such that each chord had a weighted set of options that it could progress to?

This data structure would be implemented in a procedural music generation program in a way that you could code: (language-agnostic pseudo-code)

Chord[7] songArray;

Chord first = new Chord(I); //set the first chord's 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 progress 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 would store the various progressions as weighted options. As an example, consider the IV chord in any given major key: IV can naturally progress to ii, V, or vii, but could also break the rules in progressing to any other chord. Breaking the rules would happen infrequently.

I have considered some sort of linked list/tree data structure, but it would hardly resemble any type of tree or list I've ever used -- additionally, I can't work out how to implement the weighting:

Another thought was to use JSON or something similar, but it seems to get redundant very quickly:

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

Note: I am comfortable implementing this in a handful of languages, and at this point am NOT concerned with a specific language implementation, but a language-agnostic data-structure architecture.

Answer 1

A Markov Chain might be a good fit for this problem.

A Markov chain is a stochastic process where the progression to the next state is determined by the current state. So for a given interval from your table you would apply weights to the "Leads to" values and then determine randomly to which state to progress.

Answer 2

I'd expect you to have less than 100 chords, therefore if you use 32 bits to represent probability series (likely extreme overkill) you'd end up with a 100x100x4 (40000) byte array for a flat Markov matrix representation. Depending on the sparsity of the matrix (e.g. if you have 50 chords, but each one typically maps to 2 or 3 chords) for speed and less importantly space reasons you may want an array of arrays where each final array element is (chord ID, probability).

In either case, one of the key points here is that you should use a probability series, not a probability sequence. That is, instead of saying "this chord has a 10% chance, and this one has a 10% chance, and this one has a 80% chance) 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 go to select a random but weighted value, you can generate a number in a fixed range (for unsigned integers, 0 to 0xFFFFFFFF) and then perform a binary search through the chords rather than linear search. (Search for the element with least probability series value that is still greater than or equal to the number you generated.)

On the other hand, if you've only got a few following chords for each chord, a linear search would likely be faster than a binary search due to a tighter loop, and then all the probability series saves you calculating a simple running sum of the probability values.

If you don't require the most staggeringly amazing performance (and I suspect you don't -- for a computer there's just not that many chords in a piece of music) for this portion of your code, I'd honestly just stick to a flat representation of a Markov matrix -- easy to understand, easy to implement, reasonable execution speed.

Just as a fun aside, this sort of thing lends itself well to thinking about predictive coding -- a common methodology in data compression. You might consider an n-gram based algorithm (e.g. PPM) to achieve higher-order structure in your music generation without too much example material required. It's been working in data compression for years.

Answer 3

It sounds like you want some form of directed, weighted graph where the nodes are the chords and the edges are the progression options with edge weights being the progression's likelihood.