プログラムでは、次の形式のクエリに効率的に答える必要があります。
文字列のセットと
Aクエリ文字列を指定すると、q が次のサブシーケンスであるようなqすべてが返されます。s ∈ As
たとえば、givenA = {"abcdef", "aaaaaa", "ddca"}とexactが返されq = "acd"ます。"abcdef"
これまでに検討した内容は以下のとおりです。
可能な文字ごとに、それが表示されるすべての文字列/場所のソート済みリストを作成します。クエリを実行するには、関連する文字のリストをインターリーブし、それをスキャンして、文字列境界内で一致するものを探します。
限られた数の異なる文字によって返されるリストが非常に密になるため、これはおそらく文字ではなく単語の場合により効率的です。
n 接頭辞
qが持つ可能性のあるそれぞれについて、一致するすべての文字列のリストを保存します。n現実的には 3 に近いかもしれません。それよりも長いクエリ文字列の場合、最初のリストをブルート フォースします。これは少しスピードアップするかもしれませんが、いくつかの n サブシーケンスが のすべての文字列の近くに存在することは容易に想像できます
A。つまり、最悪の場合は、セット全体を総当たり攻撃するのと同じです。
上記のタスクを大規模な s に対して効率的に実行するのに役立つ可能性のあるデータ構造、アルゴリズム、または前処理のトリックを知っていますAか? (私sの場合は100文字前後になります)
更新:一部の人々は、LCS を使用してqが のサブシーケンスであるかどうかを確認することを提案していsます。これは、次のような単純な関数を使用して実行できることを思い出してください。
def isSub(q,s):
i, j = 0, 0
while i != len(q) and j != len(s):
if q[i] == s[j]:
i += 1
j += 1
else:
j += 1
return i == len(q)
更新 2:qの性質とAその要素について詳しく説明するよう求められました。できるだけ一般的に機能するものを好みますが、A長さは約 10^6 で、挿入をサポートする必要があると思います。要素sは短くなり、平均の長さは 64 になります。クエリqは 1 ～ 20 文字のみで、ライブ検索に使用されるため、クエリ「ab」はクエリ「abc」の直前に送信されます。繰り返しますが、上記のソリューションをできるだけ使用しないことをお勧めします。
更新 3:ルックアップを使用したデータ構造をO(n^{1-epsilon})使用すると、OVP を解決したり、SETH の推測を反証したりすることができるようになると思いました。それがおそらく私たちの苦しみの理由です。唯一のオプションは、推測を反証するか、近似を使用するか、データセットを利用することです。クワドレットと試行は、さまざまな設定で最後に実行されると思います。
