数多くのパターンから文字列を一致させよう

Question

URLマッチングのためのシステムを作りたい。このように動作します：

データベースには多くのパターンが含まれます。このようなパターンのメタデータは次のとおりです。

pattern1, keyword 
pattern2, keyword 
... 
... 

私は入力URLを持っています。 htttp：//example.com/blabla/111/2222/detail.htm

システムは、入力URLに最も一致するパターンのキーワードを入力して出力します。毎秒20,000件以上のリクエストがあります。

設計する必要があるのは、パターンとデータベースモデルです。私はこのシステムで2週間以上過ごしました。

私は、ツリー内のURLと一致すると考えています。

ツリー内のすべてのノードは、2種類の出力を実行できます。どのノードがURLとの一致を続けるか、またはノードはURLに適用するキーワードを知っています。

各ノードはコールバック（dbに格納されたスクリプト）で接続されます。したがって、異なるノードは異なる動作をします。

しかし、私たちが持っているものはたくさんのパターンです。パターンを「ノード」に変換する機能が必要だと思います。または少なくとも、dbのパターンを持つ既存のノードを持つツリーを構築できます。

私はまだ木の生成について考えています。しかし、もっと良い方法があるはずです。

非常に参考になります。ありがとうございました！！！

Answer 1

産業強度の文字列一致アルゴリズムの1つがhttp://en.wikipedia.org/wiki/String_searching_algorithmである必要があります。私はあなたがパターンと一致する正確なプレフィックスマッチングが必要なように思えるので、データベースバックアップのアプローチがうまくいくとは思わない。

ただし、プレフィックスマッチング（最初から最も長いマッチング）を使用している場合は、接頭辞トライ「trie」を使用できます。私の場合は、データベースを永続的なストアとして使用しますが、一致するようにしておきます。trie

Answer 2

まず、本論文読み：あなたが望む追加の制約で...

pattern1|pattern2|pattern3|... 

：正規表現の表記で

Regular Expression Matching Can Be Simple And Fast

を、何を持っていることは、単純な "交代" であります知っているどのパターンが一致した。私はこの詳細を提供するために "Thompson NFA"を増やすことは簡単だろうと思う。 （アイデア：パターンを一意に識別するために、各パターンの末尾にユニークなマジックトークンを入れます。マジックトークンは空の文字列と一致します...マッチングエンジンが1つに当たるとすぐに、どのパターンがマッチしたかをすぐに知ることができます）

これは、エンジンの正規表現を最大限に活用します。この論文からNFAの実装を変更したくない場合でも、正規表現には膨大な量の理論的かつ実用的な作業があります。ですから、私は間違いなく大きな交代正規表現から始まり、そこから作業するでしょう。

速度を上げるために、正規表現オプティマイザ（PerlのRegexp::Optimizerのようなもの）を使用して、大きな代替正規表現をNFAに変換することができます。

または、一般的なregexpエンジン（PCREなど）から始め、十分に速いかどうかを確認することができます。