Menemukan kecocokan perkiraan dengan penelusuran fuzzy

Halaman ini menjelaskan cara menggunakan penelusuran fuzzy sebagai bagian dari penelusuran teks lengkap.

Selain melakukan penelusuran token yang tepat menggunakan fungsi SEARCH dan SEARCH_SUBSTRING, Spanner juga mendukung penelusuran perkiraan (atau fuzzy). Penelusuran fuzzy menemukan dokumen yang cocok meskipun ada sedikit perbedaan antara kueri dan dokumen.

Spanner mendukung jenis penelusuran fuzzy berikut:

  • Penelusuran perkiraan berbasis n-gram
  • Penelusuran fonetik menggunakan Soundex

Penelusuran fuzzy berbasis n-gram mengandalkan tokenisasi substring yang sama dengan yang diperlukan penelusuran substring. Konfigurasi tokenizer penting karena memengaruhi kualitas dan performa penelusuran. Contoh berikut menunjukkan cara membuat kueri dengan kata-kata yang salah dieja atau dieja berbeda untuk menemukan kecocokan perkiraan dalam indeks penelusuran.

Skema

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

Contoh ini menggunakan 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);

Kueri

Kueri berikut menemukan album dengan judul yang paling mirip dengan "Hatel Kaliphorn", seperti "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

Contoh ini menggunakan spanner.score_ngrams dan 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

Mengoptimalkan performa dan perolehan untuk penelusuran perkiraan berbasis n-gram

Kueri contoh di bagian sebelumnya menelusuri dalam dua fase, menggunakan dua fungsi yang berbeda:

  1. SEARCH_NGRAMS menemukan semua album kandidat yang memiliki n-gram yang sama dengan kueri penelusuran. Misalnya, n-gram tiga karakter untuk "California" mencakup [cal, ali, lif, ifo, for, orn, rni, nia] dan untuk "Kaliphorn" mencakup [kal, ali, lip, iph, pho, hor, orn]. N-gram yang sama dalam set data ini adalah [ali, orn]. Secara default, SEARCH_NGRAMS cocok dengan semua dokumen yang memiliki setidaknya dua n-gram yang sama, sehingga "Kaliphorn" cocok dengan "California".
  2. SCORE_NGRAMS memberi peringkat kecocokan berdasarkan kemiripan. Kemiripan dua string didefinisikan sebagai rasio n-gram bersama yang berbeda dengan n-gram non-bersama yang berbeda:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Biasanya, kueri penelusuran sama di seluruh fungsi SEARCH_NGRAMS dan SCORE_NGRAMS. Cara yang direkomendasikan untuk melakukannya adalah menggunakan argumen dengan parameter kueri bukan dengan literal string, dan menentukan parameter kueri yang sama dalam fungsi SEARCH_NGRAMS dan SCORE_NGRAMS.

Spanner memiliki tiga argumen konfigurasi yang dapat digunakan dengan SEARCH_NGRAMS:

  • Ukuran minimum dan maksimum untuk n-gram ditentukan dengan TOKENIZE_SUBSTRING atau TOKENIZE_NGRAMS fungsi. Sebaiknya jangan gunakan n-gram satu karakter karena dapat cocok dengan dokumen dalam jumlah yang sangat besar. Di sisi lain, n-gram yang panjang menyebabkan SEARCH_NGRAMS tidak menemukan kata-kata pendek yang salah dieja.
  • Jumlah minimum n-gram yang harus cocok dengan SEARCH_NGRAMS (ditetapkan dengan argumen min_ngrams dan min_ngrams_percent di SEARCH_NGRAMS). Angka yang lebih tinggi biasanya membuat kueri lebih cepat, tetapi mengurangi perolehan.

Untuk mencapai keseimbangan yang baik antara performa dan perolehan, Anda dapat mengonfigurasi argumen ini agar sesuai dengan kueri dan workload tertentu.

Sebaiknya sertakan LIMIT dalam untuk menghindari pembuatan kueri yang sangat mahal saat menemukan kombinasi n-gram populer.

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

Contoh ini menggunakan spanner.score_ngrams dan spanner.search_ngrams. Parameter kueri $1 terikat ke '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

Penelusuran fuzzy berbasis n-gram versus mode kueri yang ditingkatkan

Selain penelusuran fuzzy berbasis n-gram, mode kueri yang ditingkatkan juga menangani beberapa kata yang salah dieja. Oleh karena itu, ada beberapa tumpang tindih antara kedua fitur tersebut. Tabel berikut merangkum perbedaannya:

Penelusuran fuzzy berbasis n-gram Mode kueri yang ditingkatkan
Biaya Memerlukan tokenisasi substring yang lebih mahal berdasarkan n-gram Memerlukan tokenisasi teks lengkap yang lebih murah
Jenis kueri penelusuran Berfungsi baik dengan dokumen pendek yang memiliki beberapa kata, seperti nama orang, nama kota, atau nama produk Berfungsi sama baiknya dengan dokumen berukuran apa pun dan kueri penelusuran berukuran apa pun
Penelusuran kata sebagian Melakukan penelusuran substring yang memungkinkan kesalahan ejaan Hanya mendukung penelusuran seluruh kata (SEARCH_SUBSTRING tidak mendukung argumen enhance_query)
Kata yang salah dieja Mendukung kata yang salah dieja dalam indeks atau kueri Hanya mendukung kata yang salah dieja dalam kueri
Koreksi Menemukan kecocokan yang salah dieja, meskipun kecocokan tersebut bukan kata yang sebenarnya Mengoreksi kesalahan ejaan untuk kata-kata umum yang terkenal

Melakukan penelusuran fonetik dengan Soundex

Spanner menyediakan SOUNDEX fungsi untuk menemukan kata-kata yang dieja berbeda, tetapi terdengar sama. Misalnya, SOUNDEX("steven"), SOUNDEX("stephen") danSOUNDEX("stefan") semuanya adalah "s315", sedangkan SOUNDEX("stella") adalah "s340". SOUNDEX peka huruf besar/kecil dan hanya berfungsi untuk alfabet berbasis Latin.

Penelusuran fonetik dengan SOUNDEX dapat diimplementasikan dengan kolom yang dihasilkan dan indeks penelusuran seperti yang ditunjukkan dalam contoh berikut:

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

Contoh ini menggunakan 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);

Kueri berikut cocok dengan "stefan" ke "Steven" di SOUNDEX, bersama dengan AlbumTitle yang berisi "cat":

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

Langkah berikutnya