Menemukan kecocokan perkiraan dengan penelusuran fuzzy

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

Selain melakukan penelusuran token persis 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 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 berbeda untuk menemukan kecocokan yang mendekati 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

Contoh kueri di bagian sebelumnya menelusuri dalam dua fase, menggunakan dua fungsi yang berbeda:

  1. SEARCH_NGRAMS menemukan semua album kandidat yang memiliki n-gram bersama 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 cocok dengan semua dokumen dengan minimal dua n-gram bersama, sehingga "Kaliphorn" cocok dengan "California".
  2. SCORE_NGRAMS mengurutkan kecocokan berdasarkan kemiripan. Kesamaan dua string ditentukan sebagai rasio n-gram bersama yang berbeda dengan n-gram tidak 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 dengan menggunakan argumen dengan parameter kueri daripada 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 atau TOKENIZE_NGRAMS. Kami tidak merekomendasikan n-gram satu karakter karena dapat mencocokkan sejumlah besar dokumen. Di sisi lain, n-gram panjang menyebabkan SEARCH_NGRAMS melewatkan kata-kata pendek 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). Jumlah 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 juga LIMIT 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 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 eja. 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 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 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 salah eja untuk kata-kata umum yang sudah dikenal

Melakukan penelusuran fonetik dengan Soundex

Spanner menyediakan fungsi SOUNDEX untuk menemukan kata-kata yang dieja berbeda, tetapi terdengar sama. Misalnya, SOUNDEX("steven"), SOUNDEX("stephen"), dan SOUNDEX("stefan") semuanya "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 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