About the Algorithms: Chord Charts

This post assumes some familiarity with code and algorithms, but I do recognize this site is dedicated to music and not code. I've tried to keep things light on code, but did think it might be interesting to those with understanding of both music and code; if that's not you and/or you have questions about this, feel free to reach out!

Motivation and Design

My primary concerns for the chord chart algorithms are speed and flexibility. Flexibility, because I wanted to be able to find any chord, on any type of stringed instrument, in any tuning - all without needing a database of predetermined chord-charts to assemble.

Speed is a important because having this flexibility involves a lot of computation. If you disregard the practicality of a what might be considered a chart, a standard guitar has over 100 million different configurations of notes that you can think of as a chart that can be represented. Most of these aren't playable or even musical, but without being told, an algorithm won't know this. I want all of this searching to happen instantly - to find a good, playable option for any chord in any tuning.

To accomplish this, I need to teach the algorithm how to rule out the charts that will never make sense, before it even considers them. Before I get to that though, let's take a look at the overall inputs, outputs, and pieces involved in this process.

Function inputs

As with any challenging problem, the best path to success to limit the scope of the problem. In this case, the core algorithm focuses on a very limited inputs and outputs - other processes and tools use this core functionality to provide what you see on the site.

This core algorithm is a function with the following type:

findChordCharts
    :: NoteName             -- Root note of chord
    -> [NoteName]           -- All notes in chord
    -> StringedInstrument   -- Instrument strings and their tuning
    -> QueryOptions         -- Chart filtering configuration
    -> Set ChordChart       -- Result: a set of ChordChart values

We accept the notes we want a chart for, the tuning, and some filtering options. Everything else, like searching by a chord short or long-name, or by a chord chart signature, etc, is handled by something else that can ask this `findChordCharts` function for the charts we care about.

Function outputs

For output, we get a set of `ChordChart`s. This `ChordChart` type looks like this:

newtype ChordChart = ChordChart [Maybe (Fret, Note)]

This newtype is just a wrapper around a list of `Maybe` frets and notes. The list items represent a guitar string, an item will be `Nothing` if that string is to be muted, or `Just (fret number, note value)` if the string is played. Having the note value is a little redundant, though it makes computation a little easier and is nice to have later on, so it's a part of the algorithm.

Algorithm Flow

In order to break the problem down to something more managable, and also apply some filtering based on what's possible to play, the first step is to break the fretboard into a set of spans to check for charts in. As a player of the guitar, you won't be able to span more than 4 (or maybe 5, in extreme scenarios) frets while playing a chord.

This reduces our charts we need to consider down from to over 100 million to several hundred thousand. Though this is still a lot to compute, considering this is only one step in everything we compute to get a chord chart.

With each span (frets x to y), we run our `chartsAtSpan` function; this is the type for this function and the new `ChartSpan` type it uses:

chartsAtSpan
    :: NoteName         -- Root note of the chord
    -> Set NoteName     -- All notes in the chord
    -> QueryOptions     -- Chart filtering configuration
    -> ChartSpan        -- Span of frets on the instrument with notes in the chord
    -> [ChordChart]     -- Result: a list of ChordChart values

newtype ChartSpan = ChartSpan (NonEmpty [(Fret, Note)]) deriving Show

Note the similarities between this and our `ChartSpan` type that is used as an argument here, it's basically a little version of `findChordCharts`, except it operates on a `ChartSpan` rather than an entire instrument. This does several things for us, first, as mentioned before, it scopes us to only the frets that might be considered for an actually playable chord chord, say frets 2 through 6.

Beyond this, when we constructed each fret-span, we filtered out any frets that wouldn't be in the chord. This simplifies further processing, but it also further reduces the number of charts we need to consider. This time from several hundred thousand to hundreds, or potentially just over a thousand - depending on the number of notes in the chord.

As we dig into this chartsAtSpan, we find a few last optimizations. First, we ensure the chord starts with the root (or alternate-root, in the case of inversions) note. Also, as we build the chart, which we do one fret at a time, we we abandon any chart if it looks like it won't work for the options that are configured; here some of these checks that are run:

• Ensure we have enough strings left to meet the minimum required
• If we don't allow 'complex mutes', but we find a string-span doesn't have any of the notes we need in our chord, we'll stop processing.

It's difficult to compute how far this reduces the amount of charts we need to consider, but it brings the number down to a sufficiently small number for quick computation.

From here, we hand off our results to a number of other processes to compute various statistics about our chart, so we filter charts that are still unplayable and can sort by the most-likely desired chart. The main sorting criteria here are charts that are easy to play and on lower frets. I'll cover how we determine these other things - like ease of play - in another post.

Conclusion

Even if you aren't setting out to write this same sort of algorithm, I hope this was an interesting glimpse into everything that's happening inside the machine when you search for your next chord chart.

I've shown how to take a problem, whose naive implementation is slow, and make it around 100,000 times faster. Beyond some simple caching, most responses are computed at runtime, and most charts are computed in 10s of milliseconds or less, which is useful, especially when we are building our chord chart collections, which run this entire process for every chord in a scale, just to select the best chart for the collection.