퍼지 검색을 사용해 근사치 일치 찾기

이 페이지에서는 전체 텍스트 검색의 일부로 퍼지 검색을 사용하는 방법을 설명합니다.

SEARCH 및 SEARCH_SUBSTRING 함수를 사용하여 정확한 토큰 검색을 실행하는 것 외에도 Spanner는 근사(또는 퍼지) 검색을 지원합니다. 퍼지 검색은 쿼리와 문서 간에 작은 차이가 있어도 일치하는 문서를 찾습니다.

Spanner는 다음 유형의 퍼지 검색을 지원합니다.

  • N-그램 기반 근사 검색
  • Soundex를 사용한 음성 검색

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-그램 기반 근사 검색의 성능 및 재현율 최적화

이전 섹션의 샘플 쿼리는 두 가지 함수를 사용하여 두 단계로 검색합니다.

  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는 공유 N-그램이 2개 이상 있는 모든 문서와 일치시키므로 'Kaliphorn'은 'California'와 일치합니다.
  2. SCORE_NGRAMS는 유사성을 기준으로 일치 항목의 순위를 매깁니다. 두 문자열의 유사성은 고유한 공유 N-그램과 고유한 비공유 N-그램의 비율로 정의됩니다.
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

일반적으로 검색어는 SEARCH_NGRAMS 함수와 SCORE_NGRAMS 함수에서 동일합니다. 이를 실행하는 권장 방법은 문자열 리터럴 대신 쿼리 파라미터와 함께 인수를 사용하고 SEARCH_NGRAMS 및 SCORE_NGRAMS 함수에 동일한 쿼리 파라미터를 지정하는 것입니다.

Spanner에는 SEARCH_NGRAMS와 함께 사용할 수 있는 세 가지 구성 인수가 있습니다.

  • N-그램의 최소 및 최대 크기는 TOKENIZE_SUBSTRING(/spanner/docs/reference/standard-sql/search_functions#tokenize_substring) 또는 TOKENIZE_NGRAMS 함수로 지정됩니다. 한 글자 N-gram은 매우 많은 문서와 일치할 수 있어 권장하지 않습니다. 반면에 긴 N-그램을 사용하면 SEARCH_NGRAMS가 철자가 틀린 짧은 단어를 놓칠 수 있습니다.
  • SEARCH_NGRAMS가 일치해야 하는 최소 N-그램 개수(SEARCH_NGRAMS의 min_ngrams 및 min_ngrams_percent 인수로 설정). 숫자가 클수록 일반적으로 쿼리 속도가 빨라지지만 재현율이 감소합니다.

성능과 재현율 간의 균형을 유지하기 위해 이러한 인수를 특정 쿼리 및 워크로드에 맞게 구성할 수 있습니다.

또한 인기 있는 N-그램 조합이 발생할 때 쿼리 비용이 크게 높지 않도록 내부 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

이 예시에서는 'Hatel Kaliphorn'에 바인딩된 쿼리 파라미터 $1를 사용합니다.

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-그램 기반 퍼지 검색과 향상된 쿼리 모드 비교

N-그램 기반 퍼지 검색 외에 향상된 쿼리 모드도 맞춤법이 틀린 단어를 처리합니다. 따라서 두 기능 사이에는 약간의 중복이 있습니다. 다음 표에는 차이점이 요약되어 있습니다.

N-그램 기반 퍼지 검색 향상된 쿼리 모드
비용 N-그램을 기반으로 더 비싼 하위 문자열 토큰화가 필요합니다. 비용이 더 저렴한 전체 텍스트 토큰화가 필요합니다.
검색어 유형 사람 이름, 도시 이름, 제품 이름과 같이 단어가 몇 개 밖에 없는 짧은 문서에 적합합니다. 모든 크기의 문서와 모든 크기의 검색어에 동일하게 작동합니다.
부분 단어 검색 맞춤법이 틀려도 검색할 수 있는 하위 문자열 검색을 실행합니다. 전체 단어 검색만 지원합니다(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);

다음 쿼리는 SOUNDEX의 'stefan'과 'Steven'을 일치시키고 'cat'이 포함된 AlbumTitle도 일치시킵니다.

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

다음 단계