Here are some sample CBMR/MIR algorithm implementations I was working on in 2002-2003 as a part of a musical information retrieval project C-BRAHMS. For more information, refer to a poster (large file), a short general introduction, a longer introduction to geometric algorithms with performance test results (these have been published at ISMIR 2003). More articles are available here. There is also an introduction in Finnish (ps). These are the only existing implementations of some of the algorithms.
This is the best starting point for understanding the system and the bit-parallel algorithms. It is an early prototype implemented in plain Ruby. It contains easy-to-read implementations of some bit-parallel string-matching algorithms, including MonoPoly algorithm. Tested with Ruby 1.8.5 and SMF 0.15.6 (available at www.ruby-lang.org or locally here).
MidiSearch 0.1
(Requires SMF)
The above prototype does not contain geometric algorithms. The scripts below give an example of how to implement them. The last one also fixes a bug in the published algorithm.
Bit-parallel string matching algorithm ShiftOrAnd
Geometric algorithm P1
Geometric algorithm P2
Geometric algorithm P3
Geometric algorithm P3 with a fix for overlapping note segments problem
The last prototype doesn't work with Ruby 1.8. Use Ruby 1.6.8 and SMF 0.12 (available here). Algorithms are implemented in C, which makes the system very efficient (details here). Implemented algorithms include e.g. P1, P2, P3, and LCTS. They use advanced approaches like bit-parallelism, sparse dynamic programming, and geometric approach. They support e.g. transposition invariance and partial matches. The software has been in production use as a demo server since 2003. It's possible to set up your own web-based MIDI file search engine, but you need to update urls in some files manually (use e.g. grep to find them).
MelodySearch 0.2.7
(Requires
Ruby 1.6.8,
SMF 0.12,
DRb and
zlib)
Use the test files included in the package, your own MIDI files or Mutopia collection (see Mutopia project homepage).
The SIA(M)E algorithms mentioned in the articles cannot be distributed because they have been patented. However, the newer non-patented geometric algorithm P2 is superior to SIA(M)E algorithms in performance and memory consumption.