1
我正在處理一個巨大的時間序列數據庫。每n毫秒保存一次值。必須檢查數據庫中已有的舊時間序列的新時間序列。尋找（非常）快速近似匹配的（子）時間序列
在這一刻，我被困住了，因爲每個解決方案都像O（n2）一樣昂貴。
下面我有一些圖片，顯示一個匹配的短時間序列（灰色和橙色）。算法應該能夠識別這樣的匹配，而不需要精確，因爲我需要速度。近似就足夠了。
我在處理「最長的公共子序列問題」或「動態時間翹曲」的網絡中研究過一些論文。但要麼處理完美的測量或完美的尺寸，要麼處理O（n²）。
- 完美2個時間序列（灰色和橙色）
- 不精確新的測量（橙色），但仍匹配
- 短新的測量（橙色），但仍匹配
的匹配
- 一個巨大的新的測量（橙色），但仍然匹配
- 一個新的測量與故障（橙色），但仍匹配
的bitap算法似乎在文本搜索中實現了類似的事情，也許你可以適應它？ – biziclop
是的，我可以修改字母表。我查看了維基百科有關[bitap]（https://en.wikipedia.org/wiki/Bitap_algorithm）並發現了[Gene Meyer的論文]（http://www.win.tue.nl/~ jfg/educ/bit.mat.pdf），這非常有趣。但我找不到任何實現。網裏有沒有出來？ – user1587451
如果您真的閱讀過維基百科頁面，您會發現bitap已經在'agrep'中實現。 –