Die Online Encyclopedia of Integer Sequences unterstützt die Suche nach Sequenzen, die Ihre Abfrage als Untersequenz enthalten, z. Suche nach subseq:212,364,420,428 gibt die 8*n+4 Sequenz zurück. ( Ссылка )
Diese erstaunliche Funktion wurde anscheinend von Russ Cox wie von Ссылка implementiert, aber es wird nicht mit welchem Algorithmus angegeben Dies ist implementiert.
Ich frage mich, wie es gemacht wird. Es ist für eine Suchmaschine unpraktisch, fast eine Million Sequenzen für jede Suche durchzugehen. Einen Index zu halten (wie Russ Cox die Google Code Regex-Suche gemacht hat) der ersten Nummer und der Brute den Rest, funktioniert auch nicht, da Zahlen wie 0 in fast allen Sequenzen vorkommen. Tatsächlich stimmen einige Abfragen wie 0 1 mit einem hohen Prozentsatz der gesamten Datenbank überein, sodass der Algorithmus eine Laufzeit benötigt, die für die gewünschte Ausgabegröße empfindlich ist.
Weiß jemand zufällig, wie diese Funktion implementiert ist?
Meine Vermutung ist Teil der Daten ist in einem invertierten Index gespeichert. Das heißt, jede Zahl ist mit einer Reihe von Reihen verknüpft, und wenn mehrere Folgen eingegeben werden, wird die Menge der gemeinsamen Folgen angezeigt. Dies ist extrem schnell und wird von fast jeder Suchmaschine verwendet.
Das Speichern als Suffix-Struktur oder eine verknüpfte Datenstruktur ist für diese Anwendung nutzlos.
Zumindest für einige Sequenzen (zB ax + b) halte ich es für besser, sie parametrisch zu speichern, anstatt die eigentliche Sequenz zu speichern.
Zunächst scheint die Online-Suche nur mit Zahlen bis zu 1000 zu funktionieren. Funktioniert sie auch für größere Zahlen? Zweitens, nur aus Neugier, für das von Ihnen bereitgestellte Beispiel, gibt OEIS aus irgendeinem Grund keine A000027 auf, die nur natürliche Zahlen sind, aber offensichtlich sollte es übereinstimmen.
Datenbankbasierte Lösung
Wenn dies rein in der Datenbank implementiert wurde, würde es für eine 4-Punkte-Suche in etwa so aussehen.
Tabellen
Sequenz {seqid, seqname, etc ..}
seqitem {Wert, Seqid, Ort}
Abfrage
Wählen Sie si1.ds, si1.location, si2.location .... von Seqitem Si1, Seqitem Si2, Seqitem Si3, Seqitem Si4 where si1.seqid = si2.seqid und si2.seqid = si3.seqid und si3.seqid = si4.seqid und si1.Ort & lt; si2.location und si2.location & lt; si3.location und si3.location & lt; si4.location und si1.value = $ v1 und si2.value = $ v2 und si3.value = $ v3 und si4.value = $ v4
Tags und Links algorithm search data-structures subsequence oeis