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

注: この機能は、Spanner の Enterprise エディションと Enterprise Plus エディションで利用できます。詳細については、Spanner エディションの概要をご覧ください。

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

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

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

• n-gram ベースの近似検索
• Soundex を使用した音声検索

n-gram ベースの近似検索を使用する

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

スキーマ

GoogleSQL

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);

PostgreSQL

この例では spanner.tokenize_substring を使用しています。

CREATE TABLE albums (
  albumid character varying NOT NULL,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (
    spanner.tokenize_substring(albumtitle, ngram_size_min=>2, ngram_size_max=>3,
                      relative_search_types=>'{word_prefix, word_suffix}'::text[])) VIRTUAL HIDDEN,
PRIMARY KEY(albumid));

CREATE SEARCH INDEX albumsindex
ON albums(albumtitle_tokens)
INCLUDE (albumtitle);

クエリ

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

GoogleSQL

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

PostgreSQL

この例では、spanner.score_ngrams と spanner.search_ngrams を使用しています。

SELECT albumid
FROM albums
WHERE spanner.search_ngrams(albumtitle_tokens, 'Hatel Kaliphorn')
ORDER BY spanner.score_ngrams(albumtitle_tokens, 'Hatel Kaliphorn') DESC
LIMIT 10

n-gram ベースの近似検索のパフォーマンスと再現率を最適化する

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

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

$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

通常、検索クエリは SEARCH_NGRAMS 関数と SCORE_NGRAMS 関数の両方で同じです。このため、文字列リテラルではなくクエリ パラメータを指定した引数を使用し、SEARCH_NGRAMS 関数と SCORE_NGRAMS 関数で同じクエリ パラメータを指定することをおすすめします。

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

• n-gram の最小サイズと最大サイズは、TOKENIZE_SUBSTRING（/spanner/docs/reference/standard-sql/search_functions#tokenize_substring）関数または TOKENIZE_NGRAMS 関数で指定します。1 文字の n-gram は非常に多くのドキュメントに一致する可能性があるため、おすすめしません。一方、長い n-gram の場合、SEARCH_NGRAMS はスペルミスのある短い単語と一致しない可能性があります。
• 通常、SEARCH_NGRAMS が照合する必要がある n-gram の最小数（SEARCH_NGRAMS の min_ngrams 引数と min_ngrams_percent 引数で設定）の値を大きくすると、クエリの速度が向上しますが、再現率は低下します。

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

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

GoogleSQL

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

PostgreSQL

この例では、$1 クエリ パラメータを使用しています。このパラメータは「Hatel Kaliphorn」にバインドされています。

SELECT albumid
FROM
  (
    SELECT albumid, spanner.score_ngrams(albumtitle_tokens, $1) AS score
    FROM albums
    WHERE spanner.search_ngrams(albumtitle_tokens, $1)
    LIMIT 10000
  ) AS inner_query
ORDER BY inner_query.score DESC
LIMIT 10

n-gram ベースのファジー検索と拡張クエリモード

拡張クエリモードでは、n-gram ベースのファジー検索に加えて、スペルミスのある単語も処理されます。したがって、2 つの特徴の間には重複があります。次の表に違いを示します。

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

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

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

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

GoogleSQL

CREATE TABLE Singers (
  SingerId INT64,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN,
  Name STRING(MAX),
  NameSoundex STRING(MAX) AS (LOWER(SOUNDEX(Name))),
  NameSoundex_Tokens TOKENLIST AS (TOKEN(NameSoundex)) HIDDEN
) PRIMARY KEY(SingerId);

CREATE SEARCH INDEX SingersPhoneticIndex ON Singers(AlbumTitle_Tokens, NameSoundex_Tokens);

PostgreSQL

この例では spanner.soundex を使用しています。

CREATE TABLE singers (
  singerid bigint,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.tokenize_fulltext(albumtitle)) VIRTUAL HIDDEN,
  name character varying,
  namesoundex character varying GENERATED ALWAYS AS (lower(spanner.soundex(name))) VIRTUAL,
  namesoundex_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.token(lower(spanner.soundex(name))) VIRTUAL HIDDEN,
PRIMARY KEY(singerid));

CREATE SEARCH INDEX singersphoneticindex ON singers(albumtitle_tokens, namesoundex_tokens);

次のクエリは、AlbumTitle に「cat」が含まれるものを対象として、「stefan」を SOUNDEX の「Steven」と照合します。

GoogleSQL

SELECT SingerId
FROM Singers
WHERE NameSoundex = LOWER(SOUNDEX("stefan")) AND SEARCH(AlbumTitle_Tokens, "cat")

PostgreSQL

SELECT singerid
FROM singers
WHERE namesoundex = lower(spanner.soundex('stefan')) AND spanner.search(albumtitle_tokens, 'cat')

次のステップ

• トークン化と Spanner のトークン化ツールについて確認する。
• 検索インデックスについて確認する。
• 全文検索クエリについて確認する。