トライグラム検索

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

トライグラム検索は、ターゲット オブジェクトの正確な構文またはスペルが正確にわかっていない場合[1]、またはクエリが正規表現である可能性がある場合に、テキストを検索する方法です[2]入力された検索語に最大 3 つの連続した文字(つまりtrigram ) に一致するオブジェクトを検索します。これらは一般的に近似一致です。[3]多くの共有トライグラムを持つ 2 つの文字列は、非常に似ていると予想できます。[4] Trigram を使用すると、インデックスを効率的に作成することもできます正規表現であるか、テキストと不正確に一致する検索の場合。インデックスを使用すると、検索を大幅に高速化できます。[5] [6]トリグラム一致数のしきい値をカットオフ ポイントとして指定できます。その後、結果は一致と見なされなくなります。[4]

検索を高速化するためにトリグラムを使用することは、正規表現であるクエリが役立つ場合があるコード検索の一部のシステムで使用される手法です[5] [2] [7] Elasticsearchなどの検索エンジン[8]およびデータベースなどPostgreSQLとして[4]

文字列「アリス」を考えてみましょう。文字列のトリグラムは、「ali」、「lic」、および「ice」で、スペースは含まれません。[5]トリグラムベースのインデックスを持つデータベースでこの文字列を検索するには、3 つのトリグラムをできるだけ多く含むオブジェクトを見つける必要があります。

トリグラム検索を使用して正規表現クエリを検索する具体的な例として、文字列 を検索することを検討してくださいab[cd]e。角かっこは、検索対象の文字列の 3 番目の文字がcまたはである可能性があることを示しますdこの状況では、2 つのトライグラムabcbceまたは 2 つのトライグラムabdとを持つオブジェクトのインデックスを照会できますbdeしたがって、このクエリを見つけるには、文字列の一致は必要なく、インデックスを直接クエリするだけで済みます。これは、実際には高速になる可能性があります。[2]

も参照

参考文献

  1. ^ ハーダーソン、オマール (1997). 「BLAISE III のトライグラム検索を使用した経済活動の対話型コーディング」 (PDF) . 国際ブレーズ ユーザー グループ注: この記事では、特定の種類の経済データを効率的にエンコードする方法としてトライグラム検索について説明し、システムのユーザーがデータの構造について多くのコンテキストを持っていない場合に、この手法が特に役立つことを発見しました。
  2. ^ a b c Cox、Russ (2012 年 1 月)。「トライグラム インデックスを使用した正規表現マッチングまたは Google コード検索の仕組み」 .
  3. ^ アダムズ、エリザベス。メルツァー、アーノルド (1993 年 3 月 1 日)。「全文検索におけるインデックス要素としてのトリグラム: 観察と実験結果」 . CSC '93: 1993 年のコンピュータ サイエンスに関する ACM 会議の議事録
  4. ^ a b c "F.33. pg_trgm" . PostgreSQL ドキュメント2022-05-12 . 2022 年5 月 28 日閲覧
  5. ^ a b c 「PostgreSQL トライグラム テキスト インデックスを使用した高速検索」 . ギットラボ2016-03-18 . 2022 年5 月 28 日閲覧
  6. ^ ゾーベル、ジャスティン。モファット、アリステア。サックス・デイビス、ロン(1993)。「圧縮された反転ファイルを使用して、部分的に指定された用語の大きなレキシコンを検索する」(PDF) . 非常に大規模なデータベース (VLDB) に関する会議 注: この研究論文は「トライグラム検索」という用語を使用していませんが、n グラムをインデックスとして使用した文献の最初の例であると思われ、Russ Cox の記事で a の構造の最初の例として引用されています。トライグラムに基づく逆インデックス。また、この論文では、このスタイルの検索を使用することで得られたパフォーマンスの成功例についても言及しています。
  7. ^ "ビッググレップ" . resources.sei.cmu.edu . 2022 年6 月 12 日閲覧BigGrep とも呼ばれます。n-gram を使用します (常に 3 であるとは限りません)。
  8. ^ "N-gram トークナイザー | Elasticsearch ガイド [8.2] | Elastic" . www.elastic.co . 2022 年5 月 28 日閲覧