我需要比较 2 组乐曲(即演奏 - 采用 MIDI 格式 - 提取并保存在数据库表中的音符细节，与乐谱 - 采用 XML 格式)。在根据乐谱(即音符细节——音高、持续时间、节奏)评估演奏时，需要进行音符对齐——以识别引用(乐谱)音符中遗漏/额外/不正确/交换的音符。
我在一件作品中大约有 1800-2500 个音符(甚至可以更多 - 使用复音，现在我正在做单音)。那么我是否必须将所有这些都放入一个数组中？会不会是内存过载或者栈溢出？
有KMP、Boyce-Moore等字符串匹配算法。但是音符对齐也可以通过动态规划来完成。我如何使用动态编程来解决这个问题？可用的算法有哪些？是关于近似字符串匹配吗？
哪种方法效率更高？像 Boyce-Moore 这样的字符串匹配算法，还是动态规划？我如何评估哪个更有效？
非常感谢任何见解或建议 提前致谢
最佳答案
有趣的问题 - 我认为这 paper涵盖了很多您感兴趣的内容。他们解决了错误和音乐对齐问题，并使用 DP 作为求解器讨论了他们的结果。他们引入了一种称为“快速近似匹配”的算法，他们声称该算法比 DP 方法更好。
看起来在搜索中使用的主要作者是 Mongeau & Sankoff。看来他们的原始论文在该领域引发了大量工作。
整洁的东西。希望这可以帮助。
关于algorithm - 使用字符串匹配算法或动态规划对齐音符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3005438/