libsearch

pencarian lib?

Pencarian teks JavaScript yang sederhana dan bebas indeks, digunakan di seluruh proyek pribadi saya seperti YC Vibe Check, linus.zone/entr, dan perangkat lunak produktivitas pribadi saya. Baca sumber beranotasi untuk memahami cara kerjanya.

APInya

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, fungsi search . 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. Biasanya 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 untuk mencari item tersebut. Misalnya, jika items adalah daftar objek seperti { name: 'Linus' } , by harus berupa fungsi x => x.name . Ini memiliki nilai x => String(x) secara default, yang berfungsi untuk items bertipe string[] .
• options ( opsional ) adalah kamus opsi:
  • caseSensitive membuat penelusuran peka huruf besar-kecil. Secara default, ini false .
  • mode mengontrol cara mencocokkan 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 "University of California " tetapi tidak " California n University".
    • mode: 'prefix' berarti bahwa setiap kata kueri mungkin merupakan "awalan" yang tidak lengkap dari kata yang cocok. "Uni Cali" akan cocok dengan " Uni versity of Cali fornia" dan " Cali fornian Uni versity" Bahkan dalam mode ini, setiap kata kueri harus cocok di suatu tempat — " Cali fornia" tidak cocok, karena tidak cocok dengan kueri kata "Uni".
    • mode: 'autocomplete' adalah gabungan dari dua mode lainnya yang berguna bila digunakan dalam penelusuran bergaya pelengkapan otomatis, yang mana pengguna terus-menerus mengetikkan kueri saat hasil penelusuran ditampilkan. Mode ini identik dengan mode: 'word' , hanya saja kata kueri terakhir mungkin tidak lengkap seperti di mode: 'prefix' . Artinya "University of Cali" akan cocok dengan " University of Cali fornia", 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.

Instalasi dan penggunaan

Di web, dengan <script>

Masukkan ini ke dalam HTML Anda:

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

Ini akan mengekspos fungsi search sebagai window.libsearch.search .

Melalui NPM

npm install libsearch
# or
yarn add libsearch

Dan gunakan dalam kode Anda:

 import { search } from 'libsearch' ;

// search(...);

Menggunakan tipe TypeScript

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

Bagaimana cara kerjanya

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 peringkat hasil TF-IDF yang cukup baik. Itu tidak memberikan beragam fitur yang datang dengan perpustakaan seperti FlexSearch dan lunr.js, tetapi merupakan langkah besar di atas text.indexOf(query) > -1 , dan cukup cepat untuk dapat digunakan untuk mencari ribuan dokumen di setiap penekanan tombol dalam pengalaman saya.

Ada dua ide kunci dalam cara libsearch menyampaikan hal ini:

1. Mengubah kueri menjadi ekspresi reguler

Mesin JavaScript modern dilengkapi dengan mesin ekspresi reguler yang sangat optimal, dan libsearch memanfaatkan ini untuk pencarian teks bebas indeks yang cepat 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 seperti 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 pertanyaan O(n) , karena setiap dokumen perlu dipindai untuk mencari kata kuncinya. Namun seringkali, 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 sehingga 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.

2. Peringkat TF-IDF "Cukup baik" berdasarkan kecocokan RegExp dan panjang dokumen

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.

Perkembangan

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

• Modul ES build , yang baru saja dicentang tipe search.ts dan tipenya dihapus. Ini adalah kode yang diimpor saat libsearch diimpor di Node.js
• Browser build , yang mengekspor fungsi search utama ke window.libsearch global

Pembuatan modul ES diproduksi dengan tsc , kompiler TypeScript, dan pembuatan browser yang diperkecil diproduksi lebih lanjut dengan Webpack.

Perintah NPM/Benang:

• lint dan fmt , yang lint dan secara otomatis memformat kode sumber di repositori
• test menjalankan pengujian unit pada versi terbaru perpustakaan; Anda harus menjalankan build:tsc sebelum menjalankan test
• Berbagai perintah build:* mengatur produksi berbagai jenis build perpustakaan:
  • build:tsc membangun build modul ES
  • build:w menjalankan build:tsc pada setiap penulisan file
  • build:cjs membangun build browser dari build modul ES
  • build:all membangun kedua build, secara berurutan
• clean menghapus semua file yang dihasilkan/membangun di dist/
• docs membuat dokumentasi berbasis Litterate, yang ada di Thesephist.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.