11

Online Encyclopedia of Integer Sequences は、クエリをサブシーケンスとして含むシーケンスの検索をサポートしています。を検索する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として実装されたようですが、これがどのアルゴリズムで実装されているかは指定されていません。

どうやって作っているのか気になります。1 回の検索で 100 万近くのシーケンスを処理することは、検索エンジンにとって明らかに非現実的です。最初の数字のインデックス (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、場所}

クエリ

si1.ds、si1.location、si2.location .... を選択します。 .seqid および si1.location < si2.location および si2.location < si3.location および si3.location < si4.location および si1.value =$v1 および si2.value = $v2 および si3.value = $v3 および si4。値 = $v4

于 2015-11-26T13:27:08.483 に答える