トライグラム検索

トリグラム検索は、対象オブジェクトの正確な構文やスペルが正確にわからない場合^[¹^] 、またはクエリが正規表現である場合^[²^]にテキストを検索する方法です。これは、検索語の3文字のサブストリング（つまりトリグラム）に対して最も多く一致するオブジェクトを見つけます。これらは一般的にほぼ一致しています^[³^] 。多くの共通のトリグラムを持つ2つの文字列は、非常に似ていると予想されます^[⁴^] 。トリグラムを使用すると、正規表現またはテキストに不完全に一致する検索に対して検索エンジンのインデックスを効率的に作成することもできます。インデックスは検索を大幅に高速化できます^[⁵^]^[⁶^]。結果が一致しなかった後に、トリグラムの一致数のしきい値をカットオフポイントとして指定できます^[⁴^{] 。}

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

例

文字列「alice」を考えてみましょう。この文字列の3文字の英字は、スペースを除いて「ali」、「lic」、「ice」になります。^{[ 5 ]} 3文字の英字に基づくインデックスを持つデータベースでこの文字列を検索するには、3つの英字をできるだけ多く含むオブジェクトを見つける必要があります。

正規表現クエリの検索にトリグラム検索を使用する具体的な例として、文字列を検索することを考えてみましょう。ab[cd]eここで、括弧は、検索対象の文字列の 3 番目の文字がcまたはである可能性があることを示しています。この場合、2 つのトリグラムと、または 2 つのトリグラムとdを持つオブジェクトをインデックスにクエリすることができます。したがって、このクエリを見つけるにはの文字列マッチングは必要なく、インデックスを直接クエリするだけで済み、実際にはより高速になる可能性があります。^[²^]abcbceabdbde

参考文献

↑ Hardarson, Omar (1997). "BLAISE III でのトライグラム検索を使用した経済活動の対話型コーディング" (PDF) . International Blaise User Group .注：この記事では、特定の種類の経済データを効率的にエンコードする方法としてトリグラム検索について論じており、この手法は、システムの利用者がデータの構造に関するコンテキストをほとんど持っていない場合に特に有用であることがわかります。
1 2 3 Cox, Russ (2012 年 1 月). 「トリグラムインデックスを使用した正規表現マッチング、または Google コード検索の仕組み」。
↑ Adams, Elizabeth; Meltzer, Arnold (1993年3月1日). 「全文検索におけるインデックス要素としてのトリグラム：観察と実験結果」 . 1993年ACMコンピュータサイエンス会議（CSC '93）議事録. pp. 433–439 . doi : 10.1145/170791.170891 . ISBN 0897915585. S2CID 16701550 .
1 2 3 "F.33. pg_trgm" . PostgreSQL ドキュメント. 2022-05-12 . 2022-05-28に取得.
1 2 3 「PostgreSQL トリグラムテキストインデックスを使用した高速検索」 . GitLab . 2016-03-18 . 2022-05-28に取得.
↑ Zobel, Justin; Moffat, Alistair; Sacks-Davis, Ron (1993). "圧縮された転置ファイルを使用して部分的に指定された用語を大規模辞書から検索する" (PDF) .超大規模データベースに関する会議 (VLDB) .注：この研究論文では「トリグラム検索」という用語は使用されていませんが、文献においてnグラムをインデックスとして使用した最初の例であると思われます。また、Russ Cox氏の論文では、トリグラムに基づく逆インデックスの構造を初めて示した例として引用されています。さらに、この論文では、この検索方式を用いた際の良好なパフォーマンス結果も報告されています。
↑ 「Big Grep」 . resources.sei.cmu.edu . 2017年8月11日. 2022年6月12日取得.BigGrepとも呼ばれる。nグラム（必ずしも3つとは限らない）を使用する。
↑ "Nグラムトークナイザー | Elasticsearchガイド[ 8.2 ] | Elastic" . www.elastic.co . 2022年5月28日取得.

[1] Hardarson, Omar (1997). "BLAISE III でのトライグラム検索を使用した経済活動の対話型コーディング" (PDF) . International Blaise User Group .注：この記事では、特定の種類の経済データを効率的にエンコードする方法としてトリグラム検索について論じており、この手法は、システムの利用者がデータの構造に関するコンテキストをほとんど持っていない場合に特に有用であることがわかります。

[:2-2] 1 2 3 Cox, Russ (2012 年 1 月). 「トリグラムインデックスを使用した正規表現マッチング、または Google コード検索の仕組み」。

[3] Adams, Elizabeth; Meltzer, Arnold (1993年3月1日). 「全文検索におけるインデックス要素としてのトリグラム：観察と実験結果」 . 1993年ACMコンピュータサイエンス会議（CSC '93）議事録. pp. 433–439 . doi : 10.1145/170791.170891 . ISBN 0897915585. S2CID 16701550 .

[:0-4] 1 2 3 "F.33. pg_trgm" . PostgreSQL ドキュメント. 2022-05-12 . 2022-05-28に取得.

[:1-5] 1 2 3 「PostgreSQL トリグラムテキストインデックスを使用した高速検索」 . GitLab . 2016-03-18 . 2022-05-28に取得.

[6] Zobel, Justin; Moffat, Alistair; Sacks-Davis, Ron (1993). "圧縮された転置ファイルを使用して部分的に指定された用語を大規模辞書から検索する" (PDF) .超大規模データベースに関する会議 (VLDB) .注：この研究論文では「トリグラム検索」という用語は使用されていませんが、文献においてnグラムをインデックスとして使用した最初の例であると思われます。また、Russ Cox氏の論文では、トリグラムに基づく逆インデックスの構造を初めて示した例として引用されています。さらに、この論文では、この検索方式を用いた際の良好なパフォーマンス結果も報告されています。

[7] 「Big Grep」 . resources.sei.cmu.edu . 2017年8月11日. 2022年6月12日取得.BigGrepとも呼ばれる。nグラム（必ずしも3つとは限らない）を使用する。

[8] "Nグラムトークナイザー | Elasticsearchガイド[ 8.2 ] | Elastic" . www.elastic.co . 2022年5月28日取得.

[

[

[

[ 7 ]

[ 8 ]

トライグラム検索

例

関連項目

参考文献

関連するトピック

構文やスペルが正確にわからない場合

、またはクエリが正規表現

にテキストを検索する

サブストリング