数万のキーワードに対応する JavaScript 即時一致コード_JavaScript スキル

キーワード検索に関して最初に思い浮かぶのは、indexOf や replace などの文字関数を使用するか、せいぜい正規表現を追加することくらいです。実装は非常に簡単ですが、よく考えたことがありますか。その背景には効率の問題があるのでしょうか？たとえば、フォーラムでのキーワード フィルタリングでは、通常、フィルタリングされるキーワードの数や検出されるテキストの長さは多くないため、この瞬間のプロセスではあまり注目する価値はありません。しかし、キーワードの数が数個ではなく数千個になり、検出されるテキストも長い場合、結果はそれほど楽観的ではなくなります。キーワードを追加するたびに全文検索が追加され、最終的にかかる時間が許容範囲をはるかに超えることは誰もが知っています。

そのような極端なキーワード検索を考慮しているため、通常の 1 つずつの横断検索は明らかに実行不可能です。現在では JavaScript が使用されていますが、この言語でハッシュ テーブルを使用しないのはもったいないことです。時計の独自のサポートにより、大きな時間を得る代わりに、小さなスペースを取り出すこともできます。

まず例を見てみましょう。たとえば、foo1、foo2、bar1、bar2 というキーワードがあります。スペースは時間と交換されるため、検索する前に前処理する必要があります。前述したように、JS の柔軟で効率的なテーブルは、明らかにツリー構造を使用するのに最も有利です。たとえ理解できなくても、最終的な実装構造は次のコードのようになります。これも JSON に慣れていると非常に馴染みます:

コードをコピーします コードは次のとおりです:

var Root =
{
f:
{
o:
o:
: true ,
: true
}
}
},
b:
{
a:
r :
{
: true,
: true
}
}
}
};



このレイヤーごとの構造は、木のように、各文字は木の枝であり、最後の文字は葉であり、新しいノードはありません。
この時点で、必要なのは記事の各単語をツリーの下に検索するだけであることを理解してください。葉に到達できれば、現在のキャラクターがキーワードの 1 つであることを意味しますが、途中で対応する枝が見つからない場合は、もちろんキーワードではありません。

たとえば、foo1 は Root 構造に沿って下方向にアクセスされ、最終的に Root['f']['o']['o']['1'] に到達します。つまり、一致が完了します。 。次に、foo1 の長さをスキップして、後で検索を続けます。

したがって、記事全体で各キーワードの位置を確認するには 1 回の検索のみが必要です。
JSのハッシュテーブルの性能は非常に高いので、いわゆるブランチの検索が非常に高速です。 JS の柔軟性により、この効果を実現するコードも非常に短くなります。

実際、キーワードの数は検索時間とほとんど関係がなく、記事の長さだけが検索時間に影響を与えることがわかります。

限界テストをしてみましょう:
キーワード: イディオム全集 (19830 項目)
内容: Zhuxian.txt 全集 (1659219 ワード)
時間: 935ms
( Chrome26 / i3- 2312 CPU)
20,000 個のキーワードと一致する 160 万語の記事は 1 秒もかかりません。 JavaScript の柔軟性を最大限に活用することで、まだまだ大きな可能性があることがわかります。