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一样，但它没有指定实现这一功能的算法。
我想知道这是怎么做的。显然，对于一个搜索引擎来说，每次搜索都要经历近百万个序列是不切实际的。仅仅保留第一个数字的索引(这是拉斯·考克斯做谷歌代码正则表达式搜索的相同方式)，然后蛮横地强迫剩下的数字也是行不通的，因为像0这样的数字几乎在所有序列中都存在。事实上，像0 1这样的一些查询匹配整个数据库的比例很高，因此算法需要对所需输出大小敏感的运行时间。
有人知道这个特性是如何实现的吗？
回答 2
Stack Overflow用户
发布于 2015-02-10 16:37:16
我的猜测是部分数据存储在倒排索引中。也就是说，每个数字都链接到一组序列，当输入多个序列时，将显示一组常见的序列。这是非常快的，几乎所有的搜索引擎都在使用。
存储为后缀树或任何链接的数据结构对此应用程序是无用的。
至少对于一些序列集(例如ax+b)，我认为以参数方式保存它们比存储实际序列更好。
Stack Overflow用户
发布于 2015-11-26 21:27:08
首先，在线搜索似乎只适用于1000以下的数字。它对更大的数字也有效吗？其次，出于好奇，对于您提供的示例，出于某种原因，OEIS没有列出A000027，这只是自然数字，但显然它应该匹配。
基于数据库的解决方案
如果这完全是在DB中实现的，那么对于4个项目的搜索，应该是这样的。
表格
序列{seqid、seqname等}
seqitem {value，seqid，location }
查询
选择si1.ds、si1.location、si2.location....来自seqitem si1、seqitem si2、seqitem si3、seqitem si4，其中si1.seqid = si2.seqid和si2.seqid = si3.seqid和si3.seqid = si4.seqid和si1.location < si2.location和si2.location < si3.location和si3.location < si4.location和si1.value =$v1和si2.value = $v2和si3.value = $v3和si4.value = $v4
https://stackoverflow.com/questions/25340798
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号