11

整数序列在线百科全书支持搜索包含您的查询作为子序列的序列，例如。搜索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 所做的 Google Code Regex Search 的方式）并强制其余的数字也行不通，因为0几乎所有序列中都有类似的数字。事实上，一些查询喜欢0 1匹配整个数据库的很大一部分，所以算法需要一个对所需输出大小敏感的运行时间。

有谁碰巧知道这个功能是如何实现的？

4

2 回答 2

3

我的猜测是部分数据存储在倒排索引中。也就是说，每个数字都链接到一组序列，当输入多个序列时，会显示一组公共序列。这是非常快的，几乎每个搜索引擎都在使用。

存储为后缀树或任何链接的数据结构对于此应用程序是无用的。

至少对于某些序列集（例如 ax+b），我认为最好以参数方式保存它们而不是存储实际序列。

于 2015-02-10T08:37:15.843 回答
0

首先，在线搜索似乎只适用于 1000 以内的数字。它也适用于更大的数字吗？其次，出于好奇，对于您提供的示例，出于某种原因，OEIS 没有列出 A000027，它只是自然数，但显然它应该匹配。

基于数据库的解决方案

如果这纯粹是在 DB 中实现的，对于 4 项搜索，它会是这样的。

表

序列 {seqid、seqname 等..}

seqitem {值，seqid，位置}

询问

从 seqitem si1、seqitem si2、seqitem si3、seqitem si4 中选择 si1.ds、si1.location、si2.location .... 其中 si1.seqid = si2.seqid 和 si2.seqid = si3.seqid 和 si3.seqid = si4 .seqid and si1.location < si2.location and si2.location < si3.location and si3.location < si4.location and si1.value =$v1 and si2.value = $v2 and si3.value = $v3 and si4.价值 = $v4

于 2015-11-26T13:27:08.483 回答