5

問題:文字列の大きな静的リストが提供されます。データとワイルドカード要素 (* と ?) で構成されるパターン文字列。アイデアは、パターンに一致するすべての文字列を返すことです - とても簡単です。

現在の解決策:私は現在、大きなリストをスキャンし、各エントリをパターンに対してグロビングする線形アプローチを使用しています。

私の質問:検索の複雑さが O(n) 未満になるように、大きなリストを格納できる適切なデータ構造はありますか?

おそらく接尾辞-trie に似たものですか？ハッシュテーブルでバイグラムとトリグラムを使用することも検討しましたが、返された単語のリストとパターンのマージに基づいて一致を評価するために必要なロジックは悪夢であり、さらにそれが正しいとは確信していませんアプローチ。

4

6 に答える 6

1

通常のトライを作成して、ワイルドカード エッジを追加できます。その場合、複雑さは O(n) になります。ここで、n はパターンの長さです。**最初にパターン内の実行を置き換える必要があります*(これも O(n) 操作です)。

単語のリストがI am a oxの場合、トライは次のようになります。

  (私 ($ [私])
   a (m ($ [午前])
      n ($ [an])
      ? ($ [am an])
      * ($ [am an]))
   o (x ($ [ox])
      ? ($ [牛])
      * ($ [ox]))
   ? ($ [私]
      m ($ [am])
      n ($ [an])
      x ($ [オックス])
      ? ($ [牛です])
      * ($ [私は牛です]
         m ($ [am]) ...)
   * ($ [私は牛です]
      私 ...
    ...

そして、ここにサンプルの python プログラムがあります:

システムのインポート

def addWord(ルート、ワード):
    add(ルート、単語、単語、'')

def add(ルート、ワード、テール、前):
    テール == '' の場合:
        addLeaf(ルート、ワード)
    そうしないと：
        頭=尾[0]
        tail2 = テール[1:]
        add(addEdge(root, head), word, tail2, head)
        add(addEdge(root, '?'), word, tail2, head)
    前の場合 != '*':
        範囲内の l の場合 (len(tail)+1):
           add(addEdge(ルート, '*'), ワード, テール[l:], '*')

def addEdge (ルート、文字):
    root.has_key(char) でない場合:
        ルート[文字] = {}
    ルートを返す[文字]

def addLeaf(ルート、単語):
    root.has_key('$') でない場合:
        root['$'] = []
    葉=根['$']
    単語がリーフにない場合:
        leaf.append(単語)

def findWord(ルート、パターン):
    前 = ''
    パターン内の p の場合:
        p == '*' および prev == '*' の場合:
            継続する
        前 = p
        root.has_key(p) でない場合:
            戻る []
        ルート = ルート[p]
    root.has_key('$') でない場合:
        戻る []
    ルートを返す['$']

デフラン（）：
    print("単語を入力してください。1 行に 1 つずつ、1 行の . で終了します")
    ルート = {}
    一方 1:
        行 = sys.stdin.readline()[:-1]
        if line == '.': 改行
        addWord(ルート、行)
    print(repr(ルート))
    print("ここで検索パターンを入力します。複数の連続した '*' を使用しないでください")
    一方 1:
        行 = sys.stdin.readline()[:-1]
        if line == '.': 改行
        print(findWord(ルート、行))

走る（）
于 2010-03-28T08:20:15.797 に答える
1

データセットのサイズが非常に大きいため、その使用によって節約されるのと同じくらい多くの時間を構築に費やす可能性があることを除いて、接尾辞 trie を試すことをお勧めします。建設コストを償却するために複数回クエリを実行する必要がある場合に最適です。おそらく数百のクエリ。

また、これは並列処理の良い言い訳になることに注意してください。リストを 2 つに分割して 2 つの異なるプロセッサに渡し、ジョブを 2 倍の速さで完了させます。

于 2010-03-28T08:20:44.370 に答える
0

文字列の文字数を数えることで、単純なスピードアップを実現できます。s のない文字列bや単一の文字列bは queryabba*と一致しないため、テストしても意味がありません。文字よりも単語の方がはるかに多いため、文字列がそれらで構成されている場合、これは単語全体ではるかにうまく機能します。さらに、インデックスを作成できるライブラリがたくさんあります。一方、あなたが言及したn-gramアプローチと非常によく似ています。

それを行うライブラリを使用しない場合は、インデックスで最初に最もグローバルに使用頻度の低い文字 (または単語、または n-gram) を検索することにより、クエリを最適化できます。これにより、より多くの一致しない文字列を前もって破棄できます。

一般に、すべての高速化は、おそらく一致しないものを破棄するという考えに基づいています。何をどれだけ索引付けするかは、データによって異なります。たとえば、典型的なパターンの長さが文字列の長さに近い場合、文字列がパターンを保持するのに十分な長さであるかどうかを簡単に確認できます。

于 2010-03-30T00:09:15.620 に答える
0

メモリを気にせず、リストを前処理する余裕がある場合は、すべてのサフィックスの並べ替えられた配列を作成し、元の単語を指すようにします。たとえば、['hello', 'world'] の場合は、次のように保存します。

[('d'    , 'world'),
 ('ello' , 'hello'),
 ('hello', 'hello'),
 ('ld'   , 'world'),
 ('llo'  , 'hello'),
 ('lo'   , 'hello'),
 ('o'    , 'hello'),
 ('orld' , 'world'),
 ('rld'  , 'world'),
 ('world', 'world')]

この配列を使用して、パターンの一部を使用して候補一致のセットを構築します。

たとえば、パターンが の場合、部分文字列 のバイナリ チョップを使用して*or*一致候補を見つけ、通常のグロビング アプローチを使用して一致を確認します。('orld' , 'world')or

ワイルドカードがより複雑な場合、たとえば、とh*oの候補セットを構築し、最終的な線形グロブの前にそれらの交点を見つけます。ho

于 2010-03-28T08:19:11.070 に答える
0

複数文字列検索用の優れたアルゴリズムはたくさんあります。Google の「Navarro 文字列検索」を実行すると、複数文字列オプションの優れた分析が表示されます。多くのアルゴリズムは、「通常の」場合に非常に優れています (かなり長い検索文字列: Wu-Manber、検索対象のテキストではあまり見られない文字を含む検索文字列: 並列 Horspool)。Aho-Corasick は、検索で最悪の動作を引き起こすように入力テキストがどのように調整されていても、入力文字ごとの (ごくわずかな) 限られた量の作業を保証するアルゴリズムです。Snort のようなプログラムにとって、サービス拒否攻撃に直面した場合、これは非常に重要です。本当に効率的な Aho-Corasick 検索を実装する方法に興味がある場合は、ACISM - an Aho-Corasick Interleaved State Matrixをご覧ください。

于 2014-01-25T04:33:51.047 に答える
0

あなたは現在線形検索を行っていると言います。これにより、最も頻繁に実行されるクエリ パターンに関するデータが得られますか? 例えば、あなたの現在のユーザーの間で（私はそれがあったと思います）blah*よりもはるかに一般的ですか？bl?h

この種の事前知識があれば、可能性のあるすべてのクエリを均等に作成するという、はるかに困難でありながら価値の低い問題を解決しようとするのではなく、一般的に使用されるケースにインデックス作成の取り組みを集中させ、それらを O(1) にまで下げることができます。速い。

于 2010-03-28T08:42:58.783 に答える