検索アルゴリズム——JSアルゴリズムの実装

検索テーブルsearchテーブル
テーブル関連の概念を検索
ルックアップテーブルは、同じタイプのデータ要素(またはレコード)からなるセットです.「集合」の中のデータ要素の間には完全に緩い関係があるので、ルックアップテーブルは非常に便利なデータ構造である.
スタティックルックアップテーブルstatic searchテーブル
動的検索テーブルdynamic searchテーブル
キーワードkeyキーワードはデータ要素の中のデータ項目の値で、データ要素を識別することができます.
静的な検索テーブル
順序表の検索
順序検索のプロセス:テーブルの最後のレコードから開始し、記録されたキーワードを所与の値と比較します.記録されたキーワードと所与の値が等しい場合、検索に成功します.
小技:見張りはルックアップテーブルの最初の記録に検索対象の値を格納すると、検索中の各ステップはすべてテーブル全体の検索が完了したかどうかを検出することを避けることができます.利点アルゴリズムは簡単で面広に適応し,表の構造にはいかなる要求もない.欠点の平均検索長は大きいです.特に、nが大きい場合、検索効率は低い(1＋n)／2である.
順序表の検索

半値検索は、まず検索対象の記録の範囲を決定し、その後、その記録が見つかるか見つからないまで範囲を徐々に縮小する.

半変換ルックアップの効率は、順序検索よりも高いが、半分割ルックアップは、順序格納構造にのみ適用され、(線形チェーンテーブルは有効に半分割ルックアップできない)

フィボナッチ検索

F0 =0，
F1=1;
Fi=F(i-1)+F(i-2);

フィボナッチの検索の平均性能は半値検索よりも優れていますが、最悪の場合は半値検索よりも性能が悪いです.O(logn)は、分割時に加算、減算だけを行うという利点があります.

補間ルックアップは、与えられた値keyに基づいて比較するキーワードを決定するルックアップ方法である.

令i=(key-ST[l].key)(h-l+1)/(ST[h].key-ST[l].key)ここで、ST[l].keyとST[h].keyは、それぞれ、規則表の中で最小のキーワードと最大のキーワードを記録している.明らかにこの補間ルックアップはキーワード分布が均一なテーブルにしか適合していないが、この場合、表長の大きなシーケンステーブルは、その平均性能が半値ルックアップよりも良い.
スタティックツリーの検索
秩序テーブルのルックアップ性能についての前述の議論は「等確率」を前提として行われた.ただし、順序テーブル内の各記録のルックアップ確率が不等式である場合は、静的ツリーテーブルのルックアップを採用することができる.
検索が成功した場合のみを考慮すると、検索性能を最適にする判定ツリーは、その帯域内経路長とPH値を最小にする二叉樹である(静的最適検索ツリーstatic optimal search table).静的最適なツリーを構築するのにかかる時間的なコストが高いので、近似的に最適なルックアップツリーを構築するための効率的なアルゴリズムを紹介します.
インデックス順テーブルの検索
静的なルックアップテーブルをインデックス順テーブルで表すと、ルックアップはブロック単位で検索することができます.ブロックに分けて検索することは、索引順序検索とも呼ばれる.これは順序検索の改善方法である.このような検索方法では、表本体以外に「インデックステーブル」を作成する必要があります.すべてのレコードを複数のサブテーブルに分割して、各サブテーブルにインデックス項目を作成します.キーワード項目(サブテーブル内の最大のキーワードを保存する)とポインタ項目(サブテーブルの最初のレコードが表に記録されている位置を示す)があります.
動的検索テーブル
動的ルックアップテーブルの特徴は、テーブル構造自体がルックアッププロセスにおいて動的に生成されたものであり、すなわち、与えられた値keyに対して、テーブルにキーワードがkeyに等しいレコードがある場合、検索に成功して戻ります.そうでなければ、挿入キーワードはkeyの記録に等しいです.
二叉並び木binary sort tree
定義

左の子樹が空でない場合、左の子樹のすべての結点の値(キーワード)はルートの結点の値より小さい.

右のサブツリーが空でない場合、右のサブツリーのすべての結点の値(キーワード)はルートの結点の値よりも大きい.

左、右の木はそれぞれ二叉の並び木です.

結論:中の順序で、一本の二叉の並べ替えツリーを遍歴すると、得られた結点シーケンスは一つの増分シーケンスである.
バランス二叉樹AVL balancd binary tree
1本の空き木か、左右の2つのサブツリーの高さ差の絶対値は1を超えず、左右の2つのサブツリーは1本の平均二叉木であると定義されています.

赤黒い木

AVL

B-とB+ツリー
留学する
キーツリー(数字検索ツリー)
留学する
ハッシュ・テーブル
ハッシュ表の構成方法

直接アドレス指定法:キーワードまたはキーワードを取るある線形関数値はハッシュアドレスです.すなわち、H(key)＝keyまたはH(key)＝a・key＋bであり、aおよびbは定数(このハッシュ関数を自身関数と呼ぶ)である.中にH(key)の中に値があれば、H(key)の中に値がなくなるまで探してください.

デジタル分析法:一組の社員の生年月日などのデータを分析してみると、生年月日の上位の数字は大体同じであることが分かりました.このようにすれば、衝突の確率はとても大きいです.しかし、年月日の後の数人は月と具体的な日付の数字の違いが大きいと気づきました.衝突の確率は著しく低下します.したがって、数字分析法は数字の法則を探し出し、できるだけこれらのデータを利用して衝突確率の低いハッシュアドレスを構築します.

二乗取中法:キーワードの中でどれが分布しているかが確認できない場合、まずキーワードの二乗値を求め、必要に応じて二乗値の中間何位をハッシュアドレスとしてとることができます.二乗後の数桁とキーワードのそれぞれが関連しているため、キーワードによっては高い確率で異なるハッシュアドレスが発生します.

折りたたみ方法:キーワードを桁数の同じ部分に分割し、最後の部分の桁数を変えて、これらの部分の重ね合わせと(進数を除く)を取ることができます.ハッシュアドレスとして、デジタルビットの重畳には、シフト重畳とインター境界重畳の2つの方法があります.シフト重畳は、分割された各部分の最下位の位置を揃えることで加算されます.インター境界重畳は、端から端に向かって分割境界に沿って折り返して折りたたみ、その後、整列加算されます.

乱数法:ランダム関数を選択し、キーワードの乱数値をハッシュアドレスとして取り、キーワードの長さが異なる場合に用いられることが多い.

除算剰余法:キーワードを取るのは、ハッシュテーブルより長いmの数pで除かれた後に得られた残りの数がハッシュアドレスである.すなわちH(key)=key MOD p,p<=m.キーワードを直接型に取るだけでなく、折りたたみ、平方取中に型をとることもできます.pの選択は重要です.一般的に素数やmを取って、pの選択が悪いと、同義語が生まれやすいです.

衝突の処理方法

オープン・アドレス法:H i=(H(key)+di)MOD m,i=1,2,...,k(k==m-1)のうち、H(key)はハッシュ関数、mはハッシュテーブル長、diは増分シーケンスであり、下記の3つの取り方があります.1.1.di=1,2,3,…、m-1,探知、線形再678と呼ばれます.
1.2.di=1^2、-1^2,2^2、-2^2、③^2、±(k)^2、((*=m/2)は二次探知と称して再ハッシュします.1.3.di=疑似乱数シーケンスは、疑似乱数探査再ハッシュといいます.

再ハッシュ法:Hi=RHi(key)、i=1,2、…、k RHiはそれぞれ異なるハッシュ関数であり、つまり、同義語がアドレス競合を発生する時に別のハッシュ関数アドレスを計算し、衝突がなくなるまでは「集合」は生じにくいが、計算時間が増えた.

・

チェーンアドレス法(ファスナー法)すべてのキーワードを同義語として記録した記録を同じラインチェーンに保存

公共オーバーフローエリアを構築し、衝突したらすべてオーバーフロー表に記入

参考資料

動的検索--ジグザグ