Tho*_*hle 9 algorithm search data-structures subsequence oeis
在线整数序列百科全书支持搜索包含您的查询作为子序列的序列,例如.搜索subseq:212,364,420,428将返回8*n+4序列.(http://oeis.org/search?q=subseq:212,364,420,428)
这个惊人的功能显然是由Russ Cox实现的http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的,但是没有用它实现的算法来指定.
我想知道它是如何完成的.对于搜索引擎来说,每次搜索显然要经过近一百万个序列是不切实际的.只保留一个索引(这是同一个Russ Cox对谷歌代码正则表达式搜索的方式)的第一个数字和暴力强迫其余的也不起作用,因为数字0几乎在所有序列中.实际上,一些查询0 1匹配总数据库的高百分比,因此算法需要对所需输出大小敏感的运行时间.
有谁碰巧知道这个功能是如何实现的？
我的猜测是部分数据存储在倒排索引中。即每个数字都链接到一组序列，当输入多个序列时，将显示公共序列集。这是非常快的，几乎每个搜索引擎都使用它。
存储为后缀树或任何链接的数据结构对于此应用程序来说是无用的。
至少对于某些序列集（例如 ax+b），我认为最好以参数方式保存它们而不是存储实际序列。