ファジー検索で近似一致を検索する

このページでは、全文検索の一部としてファジー検索を使用する方法について説明します。

Spanner は、SEARCH 関数と SEARCH_SUBSTRING 関数を使用してトークンの完全一致検索を行うだけでなく、近似検索（またはファジー検索）もサポートしています。ファジー検索では、クエリとドキュメントの差がわずかであっても、一致するドキュメントを見つけます。

Spanner は、次のタイプのファジー検索をサポートしています。

  • N グラムベースの近似検索
  • Soundex を使用した発音検索

N グラムベースのファジー検索は、部分文字列検索が必要とするものと同じ部分文字列トークン化に依存します。検索の品質とパフォーマンスに影響するため、トークナイザの構成は重要です。次の例は、スペルミスや異なるスペルの単語を含むクエリを作成し、検索インデックスで近似一致を見つける方法を示しています。

スキーマ

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (
    TOKENIZE_SUBSTRING(AlbumTitle, ngram_size_min=>2, ngram_size_max=>3,
                       relative_search_types=>["word_prefix", "word_suffix"])) HIDDEN,
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsIndex
ON Albums(AlbumTitle_Tokens)
STORING (AlbumTitle);

クエリ

次のクエリは、「Hatel Kaliphorn」に最も近いタイトルのアルバム（「Hotel California」など）を検索します。

SELECT AlbumId
FROM Albums
WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn")
ORDER BY SCORE_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn") DESC
LIMIT 10

N グラムベースの近似検索のパフォーマンスと再現率を最適化する

前のセクションのサンプルクエリは、次の 2 つの異なる関数を使用して、2 つのフェーズで検索します。

  1. SEARCH_NGRAMS: 検索クエリと N グラムを共有するすべての候補アルバムを検索します。たとえば、「California」の 3 文字の N グラムには [cal, ali, lif, ifo, for, orn, rni, nia] が含まれ、「Kaliphorn」では [kal, ali, lip, iph, pho, hor, orn] が含まれます。これらのデータセットが共有する N グラムは [ali, orn] です。デフォルトでは、SEARCH_NGRAMS は 2 つ以上の共有 N グラムを持つすべてのドキュメントを照合します。したがって、「Kaliphorn」は「California」と一致します。
  2. SCORE_NGRAMS は、類似度によって一致をランク付けします。2 つの文字列の類似性は、共通する個別の N グラムと共通しない個別の N グラムの比率として定義されます。
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Spanner には、SEARCH_NGRAMS で使用できる 3 つの構成引数があります。

  1. TOKENIZE_SUBSTRING または TOKENIZE_NGRAMS で指定された N グラムの最小サイズと最大サイズ。1 文字の N グラムは非常に多くのドキュメントに一致するため、使用はおすすめしません。一方、長い N グラムでは、SEARCH_NGRAMS は短い単語のスペルミスを引き起こす可能性があります。
  2. SEARCH_NGRAMS が照合する必要がある N グラムの最小数（SEARCH_NGRAMS の min_ngrams 引数と min_ngrams_percent 引数で設定）。値を大きくすると通常はクエリの速度が向上しますが、再現率は低下します。

パフォーマンスと再現率のバランスをとるために、これらの引数は特定のクエリとワークロードに合わせて構成できます。

また、一般的な N グラムの組み合わせが検出されたときに、非常にコストの高いクエリが作成されないように、内部 LIMIT を含めることもおすすめします。

SELECT AlbumId
FROM (
  SELECT AlbumId,
         SCORE_NGRAMS(AlbumTitle_Tokens, @p) AS score
  FROM Albums
  WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, @p)
  LIMIT 10000  # inner limit
)
ORDER BY score DESC
LIMIT 10  # outer limit

N グラムベースのファジー検索と拡張クエリモード

拡張クエリモードでは、N グラムベースの曖昧検索に加えて、スペルミスのある単語も処理されます。したがって、2 つの特徴の間には重複があります。次の表に違いをまとめます。

N グラムベースのファジー検索 拡張クエリモード
費用 N グラムに基づくより高コストな部分文字列トークン化が必要 費用の安い全文トークン化が必要
検索クエリの種類 人名、都市名、商品名など、数語の短いドキュメントに適している あらゆるサイズのドキュメントとあらゆるサイズの検索クエリでも同様に機能
単語の一部分検索 スペルミスを可能にする部分文字列検索を実行する 単語全体の検索のみをサポートします（SEARCH_SUBSTRING は enhance_query 引数をサポートしていません）
スペルミスのある単語 インデックスまたはクエリでスペルミスのある単語をサポートする クエリ内のスペルミスのある単語のみをサポートする
修正 一致が実際の単語でない場合でも、スペルミスのある一致を検索する 一般的なよく知られた単語のスペルミスを修正する

Soundex を使用して音声検索を行う

Spanner には、つづりは異なるが発音が同じ単語を見つけるための SOUNDEX 関数があります。たとえば、SOUNDEX("steven")、SOUNDEX("stephen")、SOUNDEX("stefan") はすべて「s315」で、SOUNDEX("stella") は「s340」です。SOUNDEX では大文字と小文字が区別され、ラテンベースのアルファベットでのみ機能します。

SOUNDEX を使用した音声検索は、次の例に示すように、生成された列とセカンダリ インデックスを使用して実装できます。

CREATE TABLE Singers (
  SingerId INT64,
  Name STRING(MAX),
  Name_Soundex STRING(MAX) AS (LOWER(SOUNDEX(name)))
) PRIMARY KEY(SingerId);

CREATE INDEX SingersPhoneticIndex ON Singers(Name_Soundex);

次のクエリは、「stefan」と「Steven」を照合します。

SELECT SingerId
FROM Singers
WHERE Name_Soundex = LOWER(SOUNDEX("stefan"))

次のステップ