Proposal Audio Diff
What Diff Does
- If you can compare short moments of sound, say 100ms fragments, then you can extend it to a method for comparing and aligning audio of any length, allowing for changes in the length. That's comparison of sequences allowing for insertions or deletions (indels).
- Diff extends a method for comparing small fixed size elements to become a method for aligning sequences of those fixed size elements.
Is Diff Difficult?
The difficulty in 'diff' is not in the essence of it, which is a simple but powerful idea. As the Wikipedia article shows, diff can be presented in 20 lines or so of code. The difficulties are in specialising it to particular applications. It's an O(mn) algorithm, so speed matters. It invites numerous variations, many of which are ideal for certain uses. The parameters in its tables can be tweaked in innumerable ways. If there are variations possible in the underlying fragment comparison algorithm, it's 10 times more so with the algorithm extended to sequences. Interface design for diff is challenging too.
On the plus side, diff is very powerful. Comparison underlies so much of understanding of data of all kinds. It's possible to be selective about what areas to explore. You don't have to go into all the variations, or just work on one variant that is good enough. One can work on two paths, one with a simple to write but flexible version of diff, where experimentation on variations is easy, another with an extreme optimised but very specialised variant for an application like database data mining where the optimisation is central - and the main research is on how to use those results. One can also work just on the interface, with a minimal basic diff (fast, simple, basic) to drive it.
- The commercial program araxis merge has a good interface for working with textual differences between two files. I particularly like the way that once aligned you can replace a block in one file with the corresponding block from the other with a single click. You can shuttle blocks around easily.
- If we were to line up two audio tracks in this way, we could mix-and-match between the two tracks. This would be extraordinarily cool. I don't know of any commercial audio software that can do this - perhaps someone else can look.
- In developing a diff algorithm it can be helpful to present the match-matrix graphically. In molecular biology the 'dotplot' is used to do this, (though it's not usually recognised how closely related to alignment this is!). There is no reason not to do something similar for sound. It is useful for the bench scientist, and in sound it will probably be useful to the end user too.
Longest Common Subsequence Algorithm
It's explained well on Wikipedia. For the moment we're only interested in comparing two sequences, so the preamble about NP hardness of aligning more than two sequences is of no relevance to us. For comparing two sequences the algorithm has complexity O(nm) where n and m are the sizes of the two sequences.
The vital insight is that there is a correspondence between an 'alignment' of two text sequences and a path through the grid shown in the example. The path goes from the top left corner to the bottom right hand corner.
There's more information here. This brings in the idea that there is a 'cost' for an indel (= insertion or deletion), i.e. a penalty whenever a letter is aligned against a space.
The section of this page on sequence alignment covers related material. At the time it was written there was a bit more mystique around 'dynamic programming' and I wanted to dispel that. Nowadays the idea that dynamic programming is just recursion with memoisation (in my terms recursion with a cache) is much more mainstream. Although we don't yet have tools that can automatically convert a recursive formulation of an algorithm to an efficient memoised/dynamic-programming equivalent, it's clear that the change is not hugely challenging in itself. FFT can in fact be formulated as a recursive algorithm with memoisation - it's just that it's better to memoise it by hand.
- The LCS algorithm is scoring '1' for a match, and '0' for a mismatch. An obvious and very useful extension is to score an alignment/path-through-the-matrix where the component scores depend on the 'letters' matched - for example S and T might be considered similar, near to 1 in score, whilst A and W might be near to 0 in score. We can plug in any function we like for pairwise similarity for short segments.
- Instead of a fixed penalty for an indel, we can make it a function of the length so that once a 'gap' is above a certain length increasing it further does not cost us much.
- A modified algorithm need not align the entirety of either sequence. Perhaps surprisingly it does not cost us any more in algorithm complexity to find the best scoring local subsequence. This variant is valuable for database searching, for finding whether part of one sequence is present in part of some other sequence in a database.
- Multiple sequences, not just two. It's NP hard, if you read the literature, but you don't have to do it that way. In practice a perfectly workable way of aligning real world multiple sequences builds them up from 'best-pairwise alignments', and only does k(k-1)/2 of these for k sequences. You might want to leave your workstation running overnight all the same.
- For DNA database searching a lot of attention to detail in the implementation can boost the performance significantly. It doesn't change the O(mn)ness of the algorithm, but for my use it did make the algorithm 50 times faster. See this page for details.
- (The big one) - Multiple takes of the same 'session'. Allow the user to mix and match.
- Spot every cough from the audience in a recording (irregular spacing)
- Graph the speed of an engine from its sound (regular, but unknown, spacing)
- Gather evidence of the noise pollution (pneumatic drill, heavy lorries) from building works nearby over a 10 day long recording.... He's planning to take them to court.