2

入力文字列 (URL) を、単純なワイルドカードをサポートする文字列ルールの大規模なセット (1k から 250k の範囲) と照合する必要があります。

ワイルドカード サポートの要件は次のとおりです。

ワイルドカード (*) は、URL の「一部」のみを置き換えることができます。これは、ドメイン、パス、およびパラメーターのフラグメントです。たとえば、「*.part.part/*/part?part=part&part=*」のようになります。この規則の唯一の例外は、「/*」がスラッシュの後の任意のものと一致する必要があるパス領域です。

例:

  • *.site.com/* -- sub.site.com/home.html、sub2.site.com/path/home.html と一致する必要があります
  • sub.site.*/path/* -- sub.site.com/path/home.html、sub.site.net/path/home.html と一致する必要がありますが、sub.site.com/home.html とは一致しません。

追加要件:

  • 高速ルックアップ (「高速」は相対的な用語であることは理解しています。最大 250k のルールを考えると、可能であれば 1.5 秒以内に収まります。 )
  • 最新のデスクトップの範囲内で動作します (例: サーバーの実装ではありません)。
  • 入力文字列を指定して 0:n の一致を返す機能
  • マッチにはルールデータが添付されます

そのようなタスクに最適なシステム/アルゴリズムは何ですか? ルール自体を SQLite データベースに格納して、C++ でソリューションを開発します。

4

2 に答える 2

2

まず第一に、最もパフォーマンスの悪い検索の 1 つは、文字列 " .domain.com/path " の両端にワイルドカードを使用することです。したがって、私の最初の推奨事項は、ドメインが DB に格納されているので、ドメインの順序を逆にすることです: com.domain.example/path1/path2/page.html。これにより、物事をより整頓し、文字列で「一方向」にのみワイルドカードを使用できるようになり、ルックアップがはるかに高速になります。

ジョンは、DB 内でこれをすべて行う方法についていくつかの良い点を述べていると思います。それがうまくいかない場合は、リストに対して C++ の正規表現ライブラリを使用します。そうすれば、最高のパフォーマンスと最も一般的な正規表現構文が得られるに違いありません。

于 2009-07-02T05:52:18.280 に答える
1

私が間違っていなければ、URL と同じように、文字列規則をドメイン、パス、およびクエリの断片に分割できます。次に、テスト対象の URL の対応する部分に対して、それらの各部分に標準のワイルドカード マッチング アルゴリズムを適用できます。すべてのピースが一致した場合、ルールは一致です。

例

ルール: *.site.com/*
    ドメイン => *.site.com
    パス => /*
    クエリ => [空]

URL: sub.site.com/path/home.html
    ドメイン => sub.site.com
    パス => /path/home.html
    クエリ => [空]

マッチングプロセス:
    ドメイン => *.site.com は sub.site.com と一致しますか? はい
    path => /* /path/home.html と一致しますか? はい
    クエリ => [空] 一致 [空] YES

結果：一致

ルールをデータベースに保存しているので、これらの 3 つの部分に分割して保存します。超高速が必要な場合は、 を に変換し*、%データベースのネイティブLIKE操作を使用してマッチングを行うことができます。次に、次のようなクエリがあります

SELECT *
FROM   ruleTable
WHERE  @urlDomain LIKE ruleDomain
   AND @urlPath   LIKE rulePath
   AND @urlQuery  LIKE ruleQuery

ここで@urlDomain、 、@urlPath、および@urlQueryは、準備済みステートメント内の変数です。クエリは、URL に一致するルールを返すか、一致するものがない場合は空の結果セットを返します。

于 2009-07-02T04:39:25.487 に答える