1

データベースに次のURLのセットがあるとします

url                     data
^(.*)google.com/search   foobar
^(.*)google.com/alerts   barfoo
^(.*)blah.com/foo/(.*)   foofoo
... 100's more

野生のURLがあれば、そのURLが既存のURLセットに属しているかどうかを確認し、対応するデータフィールドを取得したいと思います。

私の質問は次のとおりです。

  1. それを行うためにデータベースをどのように設計しますか
  2. djangoは、各正規表現をループして一致するものをチェックすることでurlresolutionを実行します。これは、おそらく1000のURLがある場合、これがこれにアプローチするための最良の方法ですか？
  3. 私が見ることができる既存の実装はありますか？
4

5 に答える 5

1

「2.djangoは、各正規表現をループして一致するものをチェックすることでurlresolutionを実行します。これは、おそらく1000のURLがある場合、これがこれにアプローチするための最良の方法ですか？」

「3.私が見ることができる既存の実装はありますか？」

多数の正規表現を実行することが問題になる場合は、正規表現の大規模なコレクションを高速化するためのPython拡張モジュールであるesmreを確認する必要があります。これは、各正規表現の固定文字列を抽出し、それらをAho-Corasickに着想を得たパターンマッチャーに配置することで機能し、ほとんどすべての作業をすばやく排除します。

于 2009-07-19T04:01:23.207 に答える
0

Djangoには、URLが一般的に階層的であるという利点があります。Djangoプロジェクト全体には数百以上のURLが含まれている可能性がありますが、おそらく一度に処理できるのは1ダース以下のパターンのみです。この方法で悪用できる構造がURLにありますか？

それ以外に、ある種のヒューリスティックを作成してみることができます。たとえば、パターンの「修正された」部分を見つけて、それらの一部を削除してから（単純な部分文字列検索によって）、正規表現の一致に切り替えます。

スペクトルの極限では、製品オートマトンを作成できます。これは非常に高速ですが、メモリ要件はおそらく実用的ではありません（そして、今後数世紀の間、その状態が続く可能性があります）。

于 2009-07-17T22:40:58.340 に答える
0

djangoアプローチが機能しない可能性があると判断する前に、それを実装して、一般的なワークロードを適用してみてください。非常に厳しいアプローチの場合、実際に各正規表現のコストを計ることができ、それは最もコストがかかり、最も頻繁に使用される正規表現を改善するためのガイドになります。特に、最も頻繁に使用される安価な正規表現をリストの先頭に配置することができます。これは、まだ知らない問題を修正するための新しいテクノロジーを発明するよりも、おそらく良い選択です。

于 2009-07-17T22:59:39.550 に答える
0

正規表現の設計には、確かにもっと注意が必要です。たとえば、プレフィックス^(.*)は任意の入力と一致します。さまざまな理由でグループをキャプチャするためにプレフィックスが必要になる場合がありますが、プレフィックスがあると、データベース内のURLを簡単に削除できないことを意味します。

正規表現の難しさについてのTokenMacGuyのコメントにはある程度同意しますが、問題の実際の規模によっては、状況が完全に絶望的ではない場合があります。たとえば、URLが一致する場合、その最初の文字が一致する必要があります。たとえば、入力の最初の文字がそのURLと一致することを指定して、URLを事前にフィルタリングできます。つまり、セカンダリテーブルがありますMatchingFirstCharactersこれは、最初の文字と、その最初の文字に一致するURLの間のルックアップです。（これは、私の答えの最初の段落で述べたように、あいまいなプレフィックスがたくさんない場合にのみ機能します。）このアプローチを使用すると、完全に一致するために必ずしもすべての正規表現をロードする必要はありません。少なくとも最初の文字が一致するもの。アイデアをさらに一般化できると思いますが、それは読者の練習です;-)

于 2009-07-18T12:04:34.267 に答える
0

私が傾倒している計画は、URLからドメイン名+ tldを選択し、それをキーとして使用してすべての正規表現を見つけ、この正規表現サブセットのそれぞれをループして一致するものを見つける計画です。

これには2つのテーブルを使用します

class Urlregex(db.Model):
    """
    the data field is structured as a newline separated record list
    and each record is a space separated list of regex's and 
    dispatch key. Example of one such record

    domain_tld: google.com
    data:
        ^(.*)google.com/search(.*) google-search

    """
    domain_tld = db.StringProperty()
    data = db.TextProperty()

class Urldispatch(db.Model):
    urlkey = db.StringProperty()
    data = db.TextProperty()

したがって、2 dbの読み取りとドメイン固有のURLサブセットのループのコストのために、すべての着信URLを大きなdbのURLと照合できる必要があります。

于 2009-07-18T15:02:42.473 に答える