Как OEIS выполняет поиск подпоследовательности?

Question

Онлайн-энциклопедия целочисленных последовательностей поддерживает поиск последовательностей, содержащих ваш запрос в качестве подпоследовательности, например. в поисках subseq:212,364,420,428 вернет 8*n+4 последовательность. ( http://oeis.org/search?q=subseq:212,364,420,428)

Эта удивительная функция, по-видимому, была реализована Расс Коксом как http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features, но не указано, с каким алгоритмом это реализовано.

Мне интересно, как это делается. Ясно, что прохождение почти миллиона последовательностей для каждого поиска нецелесообразно для поисковой системы. Простое сохранение индекса (то же самое, что и у Расса Кокса в Google Code Regex Search) для первого числа и грубое форсирование остальных также не работает, так как числа 0 есть почти во всех последовательностях. На самом деле некоторые запросы, такие как 0 1 соответствует высокому проценту от всей базы данных, поэтому алгоритму требуется время выполнения, чувствительное к требуемому размеру вывода.

Кто-нибудь знает, как реализована эта функция?

Answer 1

Я предполагаю, что часть данных хранится в инвертированном индексе. То есть каждое число связано с набором последовательностей, и при вводе нескольких последовательностей отображается набор общих последовательностей. Это очень быстро и используется почти каждой поисковой системой.

Хранение в виде суффиксов деревьев или любой связанной структуры данных для этого приложения бесполезно.

По крайней мере для некоторого набора последовательностей (например, ax+b), я думаю, что лучше сохранять их параметрически, чем сохранять фактическую последовательность.

Answer 2

Прежде всего, этот онлайн-поиск работает только с числами до 1000. Работает ли он и для больших чисел? Во-вторых, просто из любопытства, например, для примера, который вы предоставили, OEIS не перечисляет A000027, который является просто натуральными числами, но, очевидно, он должен совпадать.

База данных Решение

Если бы это было реализовано исключительно в БД, для поиска по 4 элементам это было бы примерно так.

таблицы

sequence {seqid, seqname и т.д..}

seqitem {значение, seqid, местоположение}

запрос

выберите 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