Menemukan kecocokan perkiraan dengan penelusuran fuzzy

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

Selain melakukan penelusuran token yang sama persis menggunakan fungsi SEARCH dan SEARCH_SUBSTRING, Spanner juga mendukung penelusuran perkiraan (atau fuzzy). Penelusuran kabur menemukan dokumen yang cocok meskipun ada perbedaan kecil 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 oleh penelusuran substring. Konfigurasi tokenizer penting karena memengaruhi kualitas dan performa penelusuran. Contoh berikut menunjukkan cara membuat kueri dengan kata yang salah eja atau dieja secara berbeda untuk menemukan perkiraan pencocokan 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 recall untuk penelusuran perkiraan berbasis n-gram

Contoh kueri di bagian sebelumnya melakukan penelusuran 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 bersama dalam set data ini adalah [ali, orn]. Secara default, SEARCH_NGRAMS mencocokkan semua dokumen dengan minimal dua n-gram bersama, sehingga "Kaliphorn" cocok dengan "California".
  2. SCORE_NGRAMS mengurutkan kecocokan berdasarkan kemiripan. Kemiripan dua string ditentukan sebagai rasio n-gram bersama yang berbeda dengan n-gram yang tidak sama:
$$ \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 fungsi TOKENIZE_SUBSTRING(/spanner/docs/reference/standard-sql/search_functions#tokenize_substring) atau TOKENIZE_NGRAMS. Sebaiknya jangan gunakan n-gram satu karakter karena dapat cocok dengan sejumlah besar dokumen. Di sisi lain, n-gram yang panjang menyebabkan SEARCH_NGRAMS melewatkan kata singkat yang salah eja.
  • 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 recall.

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

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

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 parameter kueri $1 yang terikat dengan '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 eja. Dengan demikian, 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 singkat yang berisi 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 parsial Melakukan penelusuran substring yang memungkinkan kesalahan ejaan Hanya mendukung penelusuran untuk seluruh kata (SEARCH_SUBSTRING tidak mendukung argumen enhance_query)
Kata yang salah eja Mendukung kata yang salah eja dalam indeks atau kueri Hanya mendukung kata yang salah eja dalam kueri
Koreksi Menemukan kecocokan yang salah eja, meskipun kecocokan tersebut bukan kata yang sebenarnya Memperbaiki kesalahan ejaan untuk kata umum yang terkenal

Melakukan penelusuran fonetik dengan Soundex

Spanner menyediakan fungsi SOUNDEX untuk menemukan kata yang dieja secara 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 diterapkan 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 mencocokkan "stefan" dengan "Steven" di SOUNDEX, beserta 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