subsequence, Seitenzahl 1

___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ tag123search ___ Fragen zur Suchalgorithmusmechanik und Implementierung. * NOT * für Fragen zur Verwendung von Suchtools innerhalb einer API (z. B. Google, Bing, Facebook). ___ tag123datastrukturen ___ Eine Datenstruktur ist eine Möglichkeit, Daten so zu organisieren, dass bestimmte Eigenschaften dieser Daten effizient abgefragt und / oder aktualisiert werden können. ___ answer28427233 ___

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.

___ tag123subsequenz ___ Eine Untersequenz ist eine Sequenz, die durch Löschen einiger Elemente und Beibehalten der relativen Reihenfolge der verbleibenden Elemente erhalten wird. Es ist eine Verallgemeinerung der Teilzeichenkette, die nur aufeinanderfolgende Elemente der ursprünglichen Folge enthält. ___ qstnhdr ___ Wie sucht OEIS nach der Suche? ___ answer33939926 ___

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

___ qstntxt ___

Die Online Encyclopedia of Integer Sequences unterstützt die Suche nach Sequenzen, die Ihre Abfrage als Untersequenz enthalten, z. Suche nach %code% gibt die %code% 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 %code% in fast allen Sequenzen vorkommen. Tatsächlich stimmen einige Abfragen wie %code% 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?

___ tag123oeis ___ Die Online-Enzyklopädie der Integer-Sequenzen (OEIS) ist eine Online-Datenbank für Integer-Sequenzen. ___