フォーラムやチャットルームなどのシナリオでは、ユーザーエクスペリエンスを確保するために、多くの悪い言葉をブロックする必要があります。単一のキーワード検索の場合、それは自然に指標と通常の方法でより効率的です。ただし、多くのキーワードがある場合、フルテキストと一致するためにindexofまたは通常の単語を繰り返し呼び出す場合、パフォーマンスの消費は非常に高くなります。ターゲット文字列のサイズは通常大きいため、結果が1つのトラバーサルで得られるようにする必要があります。このようなニーズに基づいて、テキスト全体の各文字を順番に一致させる方法を簡単に考えることができます。たとえば、このテキストでは、「マイクジョーダンは「Just Do It」と言っていたので、マークはコーダーでした。」キーワードが「マイク」と「マーク」の場合、文全体を通過できます。 「M」が見つかったら、「I」または「A」に一致できるかどうかを確認します。最後まで一致させることができれば、キーワードを正常に見つけることができます。そうしないと、移動し続けます。次に、キーワードの構造は次のようにする必要があります。
var keywords = {m：{i：{k：{e：{end：true}}}}、a：{r：{k：{end：true}}}}}}}上記から、このデータはツリー構造であり、キーワードグループに基づいてツリー構造を作成することはまだ時間がかかりますが、キーワードはすでに与えられているため、一致する前にこのようなデータ構造を事前に作成できます。コードは次のとおりです。
function buildtree（keywords）{var tblcur = {}、key、str_key、length、j、i; var tblroot = tblcur; for（j = keywords.length -1; j> = 0; j- = 1）{str_key = keywords [j]; length = str_key.length; for（i = 0; i <length; i += 1）{key = str_key.charat（i）; if（tblcur.hasownproperty（key））{tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; //最後のキーワードtblcur = tblroot; } tblrootを返します;}このコードは、連続ステートメントを使用します：tblcur = tblcur [key] = {}。ここでの実行命令は、ステートメントの実行命令です。 []の動作レベルは=より高いため、最初のことはTBLCURオブジェクトに重要な属性を作成することです。 tblroot = tblcur = {}と組み合わせると、実行順序は次のとおりです。
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['key'] = undefined; // tblroot = {key：undefined} tblcur ['key'] = {}; tblcur = tblcur ['key'];上記のコードを介して、必要なクエリデータが構築されます。クエリインターフェイスのライティング方法を見てみましょう。
ターゲット文字列の各単語について、このキーワードの上から始めます。まず、キーワード[a]。ある場合は、キーワード[a] [b]をご覧ください。最後のキーワード[a] [b]…[x] = trueの場合、それは試合が成功したことを意味します。キーワード[a] [b]…[x] =定義されていない場合、マッチングは次の位置から再起動されます。
function search（content）{var tblcur、p_star = 0、n = content.length、p_end、match、// match_key、match_str、arrmatch = []、// sortains result arrlength = 0; // arrmatchの長さインデックスwhile（p_star <n）{tblcur = tblroot; //ルートに戻るp_end = p_star; match_str = ""; match = false; do {match_key = content.charat（p_end）; if（！（tblcur = tblcur [match_key]）））{//このマッチの終了p_star += 1;壊す; } else {match_str += match_key; } p_end += 1; if（tblcur.end）//テールに一致するかどうか{match = true; }} while（true）; if（match）{//最大一致arrmatch [arrlength] = {key：match_str、begin：p_star -1、end：p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}上記は、キーワードマッチングシステム全体の中核です。ここでは、JSの言語機能を非常によく使用していますが、効率は非常に高くなっています。 500,000ワードの「Soushen ji」を使用してテストし、与えられた300個のイディオムを見つけました。マッチング効果は約1秒です。重要なことに、ターゲットテキストは一度に通過するため、ターゲットテキストの長さはクエリ時間にほとんど影響しません。クエリ時間に大きな影響を与えるキーワードの数は、キーワードの数です。ターゲットテキストの各単語はキーワードを通過するため、クエリに特定の影響を与えます。
簡単な分析
上記の記事をいつ読んだのか疑問に思っていると思います。各単語のすべてのキーワードを通過できます。一部のキーワードが部分的に同じであっても、それらを完全に横断するのは非常に時間がかかります。ただし、JSのオブジェクトのプロパティは、ハッシュテーブルを使用して構築されます。この構造のデータは、単純なアレイトラバーサルとは大きく異なり、効率は順序ベースのアレイトラバーサルの効率よりもはるかに高くなっています。一部の学生はデータ構造に精通していない場合があるため、ハッシュテーブルの関連コンテンツについて簡単に説明します。
まず、データのストレージを見てみましょう。
メモリ内のデータのストレージは2つの部分で構成され、1つは値であり、もう1つはアドレスです。メモリをXinhua辞書と考えてください。単語の説明は値であり、ディレクトリはアドレスです。辞書はピニインによってソートされます。たとえば、同じ発音を持つ「Ni」は同じピースに配置されています。つまり、配列はメモリ領域にきちんと配置されています。この構造は配列であり、「Ni」番号1と10を指定してアクセスできます。構造図は次のとおりです。
アレイの利点は、それらが簡単にトラバースするのが簡単であり、サブスクリプトを介して対応するデータに直接アクセスできることです。しかし、特定のアイテムを追加または削除することは非常に困難です。たとえば、アイテム6を削除する場合は、アイテム5の後のデータを1つの位置で前進させる必要があります。最初のビットを削除する場合は、配列全体を移動する必要があります。
配列の追加と削除の問題を解決するために、リンクされたリストが表示されます。値を2つの部分に分割すると、部品は元の値を保存するために使用され、他の部分はアドレスを保存するために使用されます。これは別の同じ構造を指し、リンクリストを形成します。構造は次のとおりです。
上記の図から、リンクリストを追加および削除することが非常に簡単であることが明確に見ることができます。ターゲットアイテムと前のアイテムの次のアイテムを書き換えるだけで、完成します。ただし、アイテムの値を照会することは非常に困難です。ターゲットの場所にアクセスするには、順番にトラバースする必要があります。
これら2つの構造の利点を統合するには、次の構造を考えていなければなりません。
このデータ構造は、ハッシュテーブル構造です。リンクリストのヘッダーアドレスは配列に保存され、2次元データテーブルを形成できます。データの分布方法については、これはハッシュするアルゴリズムであり、通常の翻訳はハッシュアルゴリズムである必要があります。原則として、アルゴリズムには多くの種類がありますが、関数を介してキーを解決し、ソリューションから得られた結果に従ってデータを配置します。言い換えれば、キーと実際のアドレスの間にマッピングが形成されるため、この時点では、配列をサブスクリップしたり、単にトラバースしたりすることで配列にアクセスしなくなり、代わりにハッシュ関数の逆関数によってデータを見つけます。 JSのオブジェクトはハッシュ構造です。たとえば、OBJを定義します。 Hashingを介したOBJ.NAME、およびメモリ内の位置は上の図で90になる場合があります。 OBJ.NAMEを操作したい場合、基礎となるレイヤーは、ハッシュアルゴリズムを介して90の位置を自動的に見つけるのに役立ちます。つまり、メモリブロック全体を0から追跡するのではなく、アレイの12項目からリンクリストを直接検索し始めます。
JSでオブジェクトobj {key：value}を定義します。キーは文字列に変換され、ハッシュしてメモリアドレスを取得し、値を入力します。これにより、なぜ属性を自由に追加および削除できる理由、およびJSの配列に属性を割り当てることができる理由を理解することができます。
データボリュームが大きい状況では、ハッシュテーブルは、ハッシュアルゴリズムを介して多くの不必要な計算を減らすため、非常に明白な利点があります。いわゆるパフォーマンスの最適化は、実際にコンピューターを少なくすることです。最大の最適化は、計算しないことです！
アルゴリズムの最適化
アルゴリズムの基礎となる実装を理解したので、振り返ってみるとアルゴリズムの最適化を検討できます。ただし、最適化する前に、1つのことを強調する必要があります。盲目的にパフォーマンスを追求しないでください！たとえば、この場合、せいぜい最大5,000語を一致させることができるため、既存のアルゴリズムで十分であり、すべての最適化は不要です。私がまだ最適化について話している理由は、1MSの最適化を実際に行うのではなく、アルゴリズムとプログラムの理解を改善するためです。
キーワードには1つの単語がないことがわかりました。そのため、1つの単語の単位に応じてキーワードを通過することは無駄になります。ここでの最適化は、キーワードの最大長と最小長さを事前に統計し、毎回最小長の単位で検索することです。たとえば、私のテストケースのキーワードはイディオムであり、最短は4文字であるため、一致するたびに4文字を合わせます。ヒットした場合は、最大長を見つけるために深さで検索し続けます。言い換えれば、最初にツリーを構築するとき、それは最初に最小長で構築され、次に逐語的に追加されます。
簡単な計算が行われます。テストケースによると、300個のイディオムの場合、1つの単語を1つだけ比較する必要があり、単一ワードクエリの場合、4回を比較する必要があり、それぞれの比較は、回避可能なパフォーマンス消費であるツリー構造にアクセスする必要があります。さらに重要なことは、ここでの比較は文字列比較ではありません。ここのキーワードはすべてキーとして存在し、効果はOBJのキーと同じです。これはキーをハッシュして、対応するアドレスにアクセスします！したがって、1つの単語を比較することと4つの単語を比較することの違いを心配しないでください。文字列を比較しませんでした！
これは、複数のキーワードと一致することです。コードの最適化されたバージョンは、通常は利用できないため、投稿しません。