7

次の形式の文字列を表すための適切なデータ構造を探しています。

Domain:Key1=Value1,Key2=Value2...

  • 各「ドメイン」には、次のパターン文字を含めることができます - *, ?( *- 0 文字以上、?- 0 または 1 文字)

  • 各「キー」には、次のパターン文字を含めることができます - *, ?( *- 0 文字以上、?- 0 または 1 文字)

  • 各「値」には、次のパターン文字を含めることができます - *, ?( *- 0 以上の文字、?- 0 または 1 文字)

例:

JBoss:*
*:*
JBoss:type=ThreadPool,*
JBoss:type=Thread*,*
JB*:name=http1,type=ConnectionPool

JMX ObjectName に精通している場合、基本的にこれは ObjectName パターンです。

各パターンに対応するルールを簡単に保存し、新しいルールをすばやく削除、更新、および追加できる方法を探しています。

私は Prefix Trie を使用することから始めましたが、パターン文字*, ?.

4

3 に答える 3

1

それを行う最も簡単な方法は、複数の状態への遷移を可能にするトライのようなNFAを構築することだと思います。もちろん、これにより、一致する一連の文字が与えられた複数の状態にマップされる別のデータ構造を持つという複雑さが追加されます。たとえば、あなたの例では：

JBoss:*
*:*
JBoss:type=ThreadPool,*
JBoss:type=Thread*,*
JB*:name=http1,type=ConnectionPool

あなたが一致しようとしているとしましょうJBoxx:name=*

substring に一致する場合、この時点で 3 つのブランチがあるため、状態とおよびJBoを保持するデータ構造が必要になります。が入ってきたら行き止まりなのでルートを捨ててとを使う。簡単な実装は、任意の時点で可能な一致状態のセットを用意し、それらのそれぞれで次の文字を試すことです。また、(この場合のように) 複数の一致を解決する方法も必要になります。おそらく、最長一致と同じくらい単純なものでしょうか?JBoJB**xJBoJB**

トライを、広く受け入れられている DFA フォーマットではなく、NFA と考えると、すべてが理にかなっているように思えます。それが役立つことを願っています。

于 2011-06-17T01:10:04.350 に答える
0

この他のスレッドを見ることができます：ワイルドカードを使用した単語検索のための効率的なデータ構造

またはこのサイト：ワイルドカードクエリ

2番目のサイトは、「通常のBツリーと逆のBツリーの2つのBツリーを使用して、単一の*シンボルを含むワイルドカードクエリを処理できます」で終わります。

これはあなたにとってはやり過ぎかもしれませんが、読む価値があるかもしれません。

幸運を

于 2011-06-17T12:16:50.423 に答える
0

私はあなたがロープを使いたいと信じています

于 2011-06-17T01:23:36.840 に答える