Thesephist/libsearch: Pencarian teks lengkap yang sederhana dan bebas indeks untuk JavaScript

Pencarian teks JavaScript yang sederhana dan bebas indeks, digunakan di seluruh proyek pribadi saya Pemeriksaan Getaran YC, linus.zone/entrdan perangkat lunak produktivitas pribadi saya. Baca sumber beranotasi untuk memahami cara kerjanya di balik terpal.

Mari kita mulai dengan beberapa contoh singkat:

import { search } from 'libsearch'; // on Node.js
const { search } = window.libsearch; // in the browser

const articles = (
    { title: 'Weather in Berkeley, California' },
    { title: 'University report: UC Berkeley' },
    { title: 'Berkeley students rise in solidarity...' },
    { title: 'Californian wildlife returning home' },
);

// basic usage
search(articles, 'berkeley cali', a => a.title);
// => ({ title: 'Weather in Berkeley, California' })
search(articles, 'california', a => a.title);
// => (
//   { title: 'Weather in Berkeley, California' },
//   { title: 'Californian wildlife returning home' },
// )

// mode: 'word' only returns whole-word matches
search(articles, 'california', a => a.title, { mode: 'word' });
// => ({ title: 'Weather in Berkeley, California' })

// case sensitivity
search(articles, 'W', a => a.title, { caseSensitive: true });
// => ({ title: 'Weather in Berkeley, California' })

// empty query returns the full list, unmodified
search(articles, '', a => a.title);
// => ({...}, {...}, {...}, {...})

Secara lebih formal, libsearch memperlihatkan satu API, yaitu search fungsi. Fungsi ini membutuhkan dua argumen wajib dan dua argumen opsional:

function search<T>(
    items: T(),
    query: string,
    by?: (it: T) => string,
    options?: {
        caseSensitive: boolean,
        mode: 'word' | 'prefix' | 'autocomplete',
    },
): T()

• items adalah daftar item yang akan dicari. Khas items akan berupa array string atau array objek dengan beberapa properti string.
• query adalah kueri string yang dapat digunakan untuk mencari daftar item.
• by (opsional) adalah fungsi predikat yang mengambil item dari items dan mengembalikan nilai string yang dapat digunakan untuk mencari item tersebut. Misalnya jika items adalah daftar objek seperti { name: 'Linus' }, by harus berupa fungsi x => x.name. Ini ada nilainya x => String(x) secara default, yang berfungsi untuk items tipe string().
• options (opsional) adalah kamus opsi:
  • caseSensitive membuat penelusuran peka huruf besar-kecil. Dia false secara default.
  • mode mengontrol cara mencocokkan kata-kata kueri yang tidak lengkap:
    • mode: 'word' mengharuskan setiap kata kueri untuk hanya mencocokkan kata yang lengkap dan tepat, bukan sebagian kata. Misalnya, kueri “California” akan cocok dengan “Universitas Kalifornia“tapi tidak”Kalifornian Universitas”.
    • mode: 'prefix' berarti bahwa setiap kata kueri mungkin merupakan “awalan” yang tidak lengkap dari kata yang cocok. “Uni Cali” akan cocok dengan keduanya “Universitasversi dari Kalifornia” dan “Kalifornian Universitasversity” Bahkan dalam mode ini, setiap kata kueri harus cocok di suatu tempat — “Kalifornia” tidak cocok, karena tidak cocok dengan kata query “Uni”.
    • mode: 'autocomplete' adalah gabungan dari dua mode lainnya yang berguna saat digunakan dalam penelusuran gaya pelengkapan otomatis, yang mana pengguna terus-menerus mengetikkan kueri saat hasil penelusuran ditampilkan. Mode ini identik dengan mode: 'word'kecuali bahwa kata kueri terakhir mungkin tidak lengkap seperti pada mode: 'prefix'. Artinya “Universitas Cali” akan cocok dengan “Universitas California”, yang berguna karena pengguna dapat menemukan kecocokannya sebelum mengetikkan kueri lengkapnya.

Anda dapat menemukan lebih banyak contoh bagaimana opsi-opsi ini digabungkan dalam pengujian unit.

Masukkan ini ke dalam HTML Anda:

<script src="https://unpkg.com/libsearch/dist/browser.js">script>

Ini akan mengungkap search berfungsi sebagai window.libsearch.search.

npm install libsearch
# or
yarn add libsearch

Dan gunakan dalam kode Anda:

import { search } from 'libsearch';

// search(...);

libsearch dikirimkan dengan definisi tipe TypeScript yang dihasilkan dari file sumber. Menggunakan libsearch dari NPM akan membuat mereka diambil oleh kompiler TypeScript.

libsearch memungkinkan Anda melakukan pencarian teks lengkap dasar di seluruh daftar objek JavaScript dengan cepat, tanpa memerlukan indeks pencarian yang sudah dibuat sebelumnya, sekaligus menawarkan penawaran yang cukup bagus TF-IDF peringkat hasil. Itu tidak memberikan beragam fitur yang disertakan dengan perpustakaan seperti FlexSearch dan lunr.jstetapi merupakan langkah besar di atas text.indexOf(query) > -1dan cukup cepat untuk dapat digunakan untuk mencari ribuan dokumen pada setiap penekanan tombol menurut pengalaman saya.

Ada dua ide kunci dalam cara libsearch menyampaikan hal ini:

Mesin JavaScript modern dikirimkan bersama mesin ekspresi reguler yang sangat optimaldan libsearch memanfaatkan ini untuk pencarian teks yang cepat dan bebas indeks dengan mengubah string kueri menjadi filter ekspresi reguler pada waktu pencarian.

Sebagian besar perpustakaan pencarian teks lengkap bekerja dengan terlebih dahulu mengharuskan pengembang untuk membuat struktur data “indeks” yang memetakan istilah pencarian ke dokumen di mana istilah tersebut muncul. Hal ini biasanya merupakan trade-off yang baik, karena ini memindahkan beberapa pekerjaan komputasi “pencarian” untuk dilakukan lebih awal, sehingga pencarian itu sendiri dapat tetap cepat dan akurat. Ini juga memungkinkan transformasi mewah dan pembersihan data lemmatisasi pada data yang diindeks tanpa merusak kecepatan pencarian. Namun saat membuat prototipe dan aplikasi web sederhana, saya sering kali tidak ingin mengalami kerumitan dalam melakukan langkah “pengindeksan” terpisah untuk mendapatkan solusi pencarian yang “cukup baik”. Indeks perlu disimpan di suatu tempat dan dipelihara secara konstan seiring perubahan dan pertumbuhan kumpulan data yang mendasarinya.

Tugas utama indeks pencarian adalah memetakan “token” atau kata kunci yang muncul dalam dataset ke dokumen yang memunculkannya, sehingga muncul pertanyaan “dokumen manakah yang mengandung kata X?” cepat (O(1)) untuk menjawab pada waktu pencarian. Tanpa indeks, ini berubah menjadi O(n) pertanyaan, karena setiap dokumen perlu dipindai untuk mencari kata kunci. Namun sering kali, pada perangkat keras modern, untuk kumpulan data yang cukup kecil (beberapa MB) yang biasa terdapat pada aplikasi web sisi klien, n cukup kecil, cukup kecil itu O(n) pada setiap penekanan tombol tidak terlihat.

libsearch mengubah kueri seperti “Uni of California” menjadi daftar filter ekspresi reguler, (^|W)Uni($|W), (^|W)of($|W), (^|W)California. Ia kemudian “mencari” tanpa memerlukan indeks dengan memfilter korpus melalui setiap ekspresi reguler tersebut.

Metrik TF-IDF konvensional dihitung untuk setiap kata sebagai:

(# matches) / (# words in the doc) * log(# total docs / # docs that matched)

Mendapatkan jumlah kata dalam dokumen memerlukan tokenisasi dokumen, atau setidaknya membagi dokumen dengan spasi, yang secara komputasi mahal. Jadi libsearch memperkirakannya dengan menggunakan panjang dokumen (jumlah karakter).

Menggunakan kueri ekspresi reguler yang dijelaskan di atas, rumus TF-IDF libsearch adalah:

(# RegExp matches) / (doc.length) * log(# docs / # docs that matched RegExp)

yang dihitung untuk setiap kata saat pencarian dilakukan, dan kemudian dikumpulkan di akhir untuk penyortiran.

Kode sumber libsearch ditulis dalam TypeScript. Untuk mengizinkan perpustakaan digunakan di TypeScript, vanilla Node.js, dan web, kami mengkompilasi dua build:

• Itu Pembuatan modul ESyang adil search.ts tipe dicentang dan tipe dihapus. Ini adalah kode yang diimpor kapan libsearch diimpor di Node.js
• Itu pembuatan perambanyang mengekspor utama search berfungsi ke window.libsearch global

Pembuatan modul ES diproduksi dengan tsckompiler TypeScript, dan versi browser yang diperkecil diproduksi lebih lanjut dengan Webpack.

Perintah NPM/Benang:

• lint Dan fmtyang lint dan secara otomatis memformat kode sumber di repositori
• test menjalankan pengujian unit pada perpustakaan versi terbaru; kamu harus lari build:tsc sebelum berlari test
• Bermacam-macam build:* perintah mengatur produksi berbagai jenis perpustakaan:
  • build:tsc membangun build modul ES
  • build:w berjalan build:tsc pada setiap file tulis
  • build:cjs membangun build browser dari pembuatan modul ES
  • build:all membangun kedua bangunan, secara berurutan
• clean menghapus semua file yang dihasilkan/dibangun dist/
• docs membangun dokumentasi berbasis Literate, yang ada di thisphist.github.io/libsearch.

Sebelum masuk ke main atau publishing, saya biasanya lari

yarn fmt && yarn build:all && yarn test && yarn docs

untuk memastikan aku tidak melupakan apa pun.