2

電子メール フィルタを作成していますが、1 つの電子メールを多数のフィルタ/ルールに効率的に一致させる方法が必要です。電子メールは、次のフィールドのいずれかで照合できます。

  • 名前から
  • 差出人アドレス
  • 送信者名
  • 差出人住所
  • 主題
  • メッセージ本文

現在、5000 を超えるフィルターがあり (さらに増え続けています)、これらはすべて PostgreSQL (9.1) データベースの単一のテーブルで定義されています。各フィルターには、Python 正規表現が入力された上記のフィールドが 1 つ以上含まれている場合があります。

フィルタリングが現在行われている方法は、すべてのフィルターを選択してメモリにロードすることです。次に、空白以外のすべてのフィールドで正の一致が見つかるまで、電子メールごとにそれらを繰り返します。残念ながら、これは、1 つの電子メールに対して 30,000 (5000 x 6) もの再照合操作が行われる可能性があることを意味します。明らかに、これはフィルターが追加されるにつれてスケーリングされません (実際には既にスケーリングされていません)。

これを行うより良い方法はありますか？

これまでに検討したオプション：

  1. 保存された Python 正規表現を POSIX スタイルのものに変換して、PostgreSQL の SIMILAR TO 式を利用します。これで本当に速くなるのだろうか？単に負荷を別の場所に移動しているように思えます。

  2. ユーザーごとにフィルターを定義します。これは実際には実用的ではありませんが、私たちのシステムではユーザーが事前定義された豊富なフィルターから実際に利益を得ているからです。

  3. フィルタリングする最初の電子メールが正規表現として保存されるエラスティック検索のようなドキュメントベースの検索エンジンに切り替えます。同様のメールを見つけることで、特定の機能セットに絞り込んでテストし、肯定的な一致を得ることができます.

  4. ベイズ フィルターに切り替えると、同様のメールや既存のメールへの変更を検出する機械学習機能も得られますが、それらは同じものであると推測するのに十分な確率で一致します。これはクールに聞こえますが、特にうまくスケーリングできるかどうかもわかりません。

他に考慮すべきオプションやアプローチはありますか?

4

2 に答える 2

3

PostgreSQL バージョン 9.1 でのトライグラムのサポートにより、必要なものが得られる場合があります。

http://www.postgresql.org/docs/9.1/interactive/pgtrgm.html

9.2 (2012 年の夏にリリース予定) では、ほぼ確実に実行可能なソリューションになるでしょう。新しいバージョンは、正規表現との高速マッチングにトライグラム インデックスを使用する方法を知っているからです。当店では、トライグラム インデックスの速度が非常に優れていることがわかりました。

また、検索引数との類似性に基づいて K 個のベスト マッチを見つける「最近傍」検索を実行したい場合は、トライグラム インデックスが最適です。実際には、インデックス スキャンから「距離」の順に行が返されます。 "。記事については、KNN-GiST を検索してください。

于 2012-04-18T17:42:06.600 に答える
0

これらの正規表現はどれほど複雑ですか? それらが本当に正規表現である場合 (すべてのクレイジーな python 拡張機能なし)、それらすべてを (代替として) 単一の正規表現に結合してから、単純な (つまりメモリ内の) 正規表現マッチャーを使用できます。

これが機能するかどうかはわかりませんが、一般的な状態をマージするため、regexp が非常に小さな状態マシンにコンパイルされることに驚くと思います。

また、高速な正規表現エンジンについては、高速スキャンを行うnrgrepの使用を検討してください。これにより、あるヘッダーから次のヘッダーにジャンプするときにスピードアップが得られるはずです（私自身は使用していませんが、彼らは友人の友人であり、私が読んだときの論文はかなりきれいに見えました）.

于 2012-04-18T19:19:10.453 に答える