例えば、あなたが毎日約400万のRedditコメントを摂取しているとすれば、ほぼリアルタイムで1万の特定のキーワードの存在を検出する必要があります。 The naive answer is obvious - loop through each comment and keyword. すべてのコメントとキーワードをスループします。 for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 しかも、見た目もゆっくり。 あなたが数学を無視しても、それは(簡単に)数十億の文字列比較を行っている。複雑さは四角形であり、あなたが小さなVPSでそれを実行する方法はありません。 ルイス・ヴァン・ウィンクルがF5Bot(無料のRedditスクラップサービス)を構築する際に直面した問題です)そして、彼は貧血のCPUを持つ小さなVPSでそれを実行しました。 1975年のアルゴリズムで、 それはあなたが単一のパスでパターンを検索することができます。 コレクション 「600ドルの図書館問題」 この問題は、マーガレット・コラシックが政府が提供するテープでキーワードを検索するツールを開発していた1975年のベル・ラボで発生しました. 図書学者は、一度に数百のキーワードを検索しながら600ドルの使用制限を打ちました (そしてプログラムは終わらなかった)。 CorasickはAlfred Ahoのアルゴリズム設計セミナーに参加し、 Aho-Corasickアルゴリズムとして知られているものを発明しました。 彼女はそれを実装しました。 ライブラリグラファーの検索は今、25ドルで行われました。 なぜケア Aho-corasickは実は非常に人気のあるアルゴリズムです。   Aho-Corasick. ウイルススキャナは、数千のマルウェア署名をスキャンするためにそれを使用します。 F5Bot は、Reddit と Hacker News のコメントを監視するためにそれを使用します。 fgrep ワイ F5Botのベンチマークをご覧ください。 Loaded 3000 keywords to search on a text of 19377 chars

searching with strpos (naive):  0.384 seconds
searching with aho-corasick:    0.055 seconds (7x faster)
 それは僕がどんな日でも喜ぶようなフレックスだ。 どのように機能する 基本的なアイデアは - あなたが複数のキーワードを検索している場合、あなたは余計な仕事をしています。 あなたが検索しているとしましょう: で、 で、 天才的なアプローチを使用して、あなたはあなたのテキストを3回スキャンします - 各キーワードのための1回。 "art" "cart" "ted" あなたがすでに探している場合 あなたはそれがそこにあることを知っています、あなたはそこから始めることができます。 終わりの状態のマシンを構築し、共有サフィックスを活用するだけです。 基本的に、各ノードがあなたのキーワードの一つのプレフィックスを表す木です。 文字ごとにテキスト文字をスキャンすると、あなたはこのグラフを通って移動します。 トリエに恐ろしく似ていますか? それはトリエだからです! "art" スマートなのは、アルゴリズムがノード間で「失敗リンク」を構築するということです。英語では、「次の文字が一致しない場合は、ルートから始めてはいけません。 シンプルな例を挙げてみると、探していると、 , アルゴリズムは trie (プレフィックスツリー) を構築し、ブルー/グリーンで表示される追加リンクを追加します。 {a, ab, b, bc, bca, c, ca, caa} もしあなたがAのことを知っているなら 単にAを追加するだけです。 このようにして、あなたはすぐに最も長い一致するサフィックスにジャンプする代わりに、再びルートから単語をスキャンすることができます。 , you walk through this trie (automaton) once, character by character. The text is only scanned once - so you end up with a time complexity of O(n); where n is the length of the text. テキストは一度だけスキャンされます。 trie 失敗リンク "abccab" ナイフなアプローチは、あなたが単語を繰り返しスキャンすることになります; O(n * m * k)は、mはキーワードの数であり、kはその平均的な長さです Aho-CorasickはO(n+m+z)、zは合計数です。 実施 あなたは見つけることができます A 最近のプロジェクトで、ゲノムファイル(基本的に4M文字)の9つの変異(パターン)を検索するために調整し、0.75sで全体を検索しました。 単純な実施 シンプルな例を挙げて、それがどのように機能するかを説明します。  
# naive approach
for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 
# with aho-corasick
step 1: build an automaton (trie) using patterns
step 2: add failure links (with bfs)
step 3: search automaton by following failure links, and return patterns that matched
 実用化は、実際のコードの約60行だと思います。 最近の図書館もありますが、 使えるのは超簡単です。 pyahocorasick これを使うときは、 スパムする必要はありません。 段落に3つのキーワードを検索する際には、以下のように使用します。 ahocorasick 
 
 
 頻繁に変更しない数千のキーワードを探しています(F5Bot usecase) しばしば走る必要がある(思考ストリーム) 閉鎖思考 Aho-Corasickは、50年前にペンと紙でマーガレットによって発明されたが、AIはなかった。 今日のコンピュータは数百万倍速く、今日の600ドルの検索問題は微妙だが、あなたが小さなVPSで毎日数百万のRedditコメントを処理しているなら、ハードウェアを問題に投げ込むことはできない。 考えるための食べ物、おそらくあなたが実装する予定の何よりもあなたの問題を解決する50歳のアルゴリズムがあります。 Footnotes: 
 
 
 
 
 
 The original 1975 paper Efficient string matching: An aid to bibliographic search is surprisingly readable. オリジナル1975年の論文Efficient string matching: An aid to bibliographic searchは驚くほど読みやすい。 マーガレット・J・コラシック博士論文(1974年)は「オープン・システム内で独占データを確保する」という論文で、自身のウィキペディアページを持っていないのが残念で、アルゴリズムとアルフレッド・アホ(彼はAWKの「A」である- Aho、Weinberger、Kernighan)はそれぞれ独自のウィキペディアページを持っている。 Python ライブラリは pyahocorasick と呼ばれ、C で生産用に実装されています. 私は私のバージョンよりもかなり速いと確信していますが、原則は同じです. 私はすぐにベンチマークを実行します. KMP (Knuth-Morris-Pratt) は、パターンを最終的な自動にコンパイルするための類似のアプローチを使用します. Basically ahocorasick for a single pattern. Both precalculate a structure and exploit the prefixes that appear. Aho-Corasick オートマトンは巨大になる - O(すべてのキーワードの文字合計) あなたが何百万のパターンを持っている場合、それは重要なメモリが必要かもしれません。

This story contains new, firsthand information uncovered by the writer.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

このオーディオは、ストーリーの元の言語で制作されています。

1975年のアルゴリズムは、現代のキーワード検索のブルートフォースを打ち負かす

About Author

コメント

ラベル

この記事は

Related Stories

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

暗号通貨の成長: 効果的なユーザーペルソナの作成

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

暗号通貨の成長: 効果的なユーザーペルソナの作成

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps