subproblems-algorithm · dannenberg1984-online-accompaniment

Real-time accompaniment solves most of the synchronization problems inherent in taped accompaniment; however, this new approach requires the computer to have the ability to follow the soloist. Three subproblems arise: detecting and processing input from the live performer, matching this input against a score of expected input, and generating the timing information necessary to control the generation of the accompaniment. It is expected that the live solo performance will contain mistakes or be imperfectly detected by the computer [...]. An efficient dynamic programming algorithm for finding the best match between solo performance and the score is presented. [...] The dynamic programming technique [10, 11] used for "time-warping" in speech research motivated the algorithm described in this paper. [...] The best match is the longest common subsequence of the two streams.