libsearch

ลิบเสิร์ช ?

ค้นหาข้อความ JavaScript ที่เรียบง่ายและไม่ต้องใช้ดัชนี ซึ่งใช้กับโปรเจ็กต์ส่วนตัวของฉัน เช่น YC Vibe Check, linus.zone/entr และซอฟต์แวร์เพิ่มประสิทธิภาพการทำงานส่วนบุคคลของฉัน อ่านแหล่งที่มาที่มีคำอธิบายประกอบเพื่อทำความเข้าใจวิธีการทำงานภายใต้ประทุน

เอพีไอ

เริ่มต้นด้วยตัวอย่างสั้นๆ:

 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 ) ;
// => [{...}, {...}, {...}, {...}]

อย่างเป็นทางการมากขึ้น libsearch เปิดเผย API เดียวซึ่งเป็นฟังก์ชัน search ฟังก์ชันนี้รับอาร์กิวเมนต์ที่จำเป็นสองอาร์กิวเมนต์และอาร์กิวเมนต์ทางเลือกสองอาร์กิวเมนต์:

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

• items คือรายการสิ่งของที่จะค้นหา โดยทั่วไป items จะเป็นอาร์เรย์ของสตริงหรืออาร์เรย์ของอ็อบเจ็กต์ที่มีคุณสมบัติสตริงบางอย่าง
• query คือคิวรีสตริงที่ใช้ค้นหารายการต่างๆ
• by ( ทางเลือก ) เป็นฟังก์ชันเพรดิเคตที่รับไอเท็มจาก items และส่งกลับค่าสตริงที่ใช้ค้นหาไอเท็มนั้น ตัวอย่างเช่น หาก items เป็นรายการของวัตถุเช่น { name: 'Linus' } by จะต้องเป็นฟังก์ชัน x => x.name สิ่งนี้มีค่า x => String(x) เป็นค่าเริ่มต้น ซึ่งใช้ได้กับ items ประเภท string[]
• options ( ทางเลือก ) เป็นพจนานุกรมของตัวเลือก:
  • caseSensitive ทำให้การค้นหาคำนึงถึงตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ มันเป็น false โดยค่าเริ่มต้น
  • mode ควบคุมวิธีการจับคู่คำค้นหาที่ไม่สมบูรณ์:
    • mode: 'word' กำหนดให้ทุกคำค้นหาต้องจับคู่เฉพาะคำที่ตรงทั้งหมด แทนที่จะจับคู่ส่วนของคำ ตัวอย่างเช่น ข้อความค้นหา "California" จะตรงกับ "University of California " แต่ไม่ตรงกับ " California n University"
    • mode: 'prefix' หมายความว่าคำค้นหาทุกคำอาจเป็น "คำนำหน้า" ที่ไม่สมบูรณ์ของคำที่ตรงกัน "Uni Cali" จะจับคู่ทั้ง " Uni versity of Cali fornia" และ " Cali fornian Uni versity" แม้ในโหมดนี้ คำค้นหาทุกคำจะต้องตรงกันที่ไหนสักแห่ง — " Cali fornia" ไม่ตรงกัน เนื่องจากไม่ตรงกับข้อความค้นหา คำว่า "ยูนิ"
    • mode: 'autocomplete' เป็นลูกผสมของอีกสองโหมดที่มีประโยชน์เมื่อใช้ในการค้นหาแบบเติมข้อความอัตโนมัติ โดยที่ผู้ใช้พิมพ์ข้อความค้นหาอย่างต่อเนื่องในขณะที่ผลการค้นหาถูกส่งกลับ โหมดนี้จะเหมือนกับ mode: 'word' ยกเว้นว่าคำค้นหาสุดท้ายอาจไม่สมบูรณ์เหมือนใน mode: 'prefix' หมายความว่า "University of Cali" จะตรงกับ " University of Cali fornia" ซึ่งมีประโยชน์เนื่องจากผู้ใช้อาจพบรายการที่ตรงกันก่อนที่จะพิมพ์ข้อความค้นหาทั้งหมด

คุณสามารถดูตัวอย่างเพิ่มเติมว่าตัวเลือกเหล่านี้รวมกันได้อย่างไรในการทดสอบหน่วย

การติดตั้งและการใช้งาน

บนเว็บด้วย <script>

วางสิ่งนี้ลงใน HTML ของคุณ:

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

สิ่งนี้จะแสดงฟังก์ชัน search เป็น window.libsearch.search

ผ่านทาง NPM

npm install libsearch
# or
yarn add libsearch

และใช้ในรหัสของคุณ:

 import { search } from 'libsearch' ;

// search(...);

การใช้ประเภท TypeScript

libsearch มาพร้อมกับคำจำกัดความประเภท TypeScript ที่สร้างจากไฟล์ต้นฉบับ การใช้ libsearch จาก NPM ควรให้คอมไพเลอร์ TypeScript เลือกพวกมัน

มันทำงานอย่างไร

libsearch ช่วยให้คุณดำเนินการค้นหาข้อความแบบเต็มขั้นพื้นฐานในรายการอ็อบเจ็กต์ JavaScript ได้อย่างรวดเร็ว โดยไม่ต้องใช้ดัชนีการค้นหาที่สร้างไว้ล่วงหน้า ขณะเดียวกันก็เสนอการจัดอันดับผลลัพธ์ TF-IDF ที่ดีพอสมควร มันไม่ได้นำเสนอคุณสมบัติที่หลากหลายที่มาพร้อมกับไลบรารีเช่น FlexSearch และ lunr.js แต่เป็นขั้นตอนสำคัญเหนือ text.indexOf(query) > -1 และเร็วพอที่จะใช้สำหรับการค้นหาเอกสารหลายพันรายการใน ทุกการกดแป้นพิมพ์จากประสบการณ์ของฉัน

มีแนวคิดสำคัญสองประการในการที่ libsearch นำเสนอสิ่งนี้:

1. การแปลงข้อความค้นหาให้เป็นนิพจน์ทั่วไป

เอ็นจิ้น JavaScript สมัยใหม่มาพร้อมกับเอ็นจิ้นนิพจน์ทั่วไปที่ได้รับการปรับปรุงให้เหมาะสมที่สุด และ libsearch ใช้ประโยชน์จากสิ่งนี้เพื่อค้นหาข้อความที่รวดเร็วและไม่มีดัชนีโดยการแปลงสตริงการสืบค้นเป็นตัวกรองนิพจน์ทั่วไปในเวลาค้นหา

ไลบรารีการค้นหาข้อความแบบเต็มส่วนใหญ่ทำงานโดยกำหนดให้นักพัฒนาสร้างโครงสร้างข้อมูล "ดัชนี" เป็นครั้งแรกโดยจับคู่คำค้นหากับเอกสารที่ปรากฏ โดยปกติแล้วนี่เป็นการแลกเปลี่ยนที่ดี เพราะมันจะทำให้งานคำนวณบางอย่างของการ "ค้นหา" ต้องดำเนินการล่วงหน้า ดังนั้นการค้นหาจึงสามารถคงความรวดเร็วและแม่นยำได้ นอกจากนี้ยังช่วยให้สามารถแปลงรูปแบบแฟนซีและการล้างข้อมูลเช่นการย่อข้อมูลในข้อมูลที่จัดทำดัชนีโดยไม่ทำลายความเร็วในการค้นหา แต่เมื่อสร้างต้นแบบและเว็บแอปแบบธรรมดา ฉันมักไม่ต้องการให้เกิดความซับซ้อนในการมีขั้นตอน "การจัดทำดัชนี" แยกต่างหากเพื่อให้ได้โซลูชันการค้นหาที่ "ดีเพียงพอ" ดัชนีจะต้องถูกจัดเก็บไว้ที่ใดที่หนึ่งและบำรุงรักษาอย่างต่อเนื่องเมื่อชุดข้อมูลพื้นฐานเปลี่ยนแปลงและเติบโต

งานหลักของดัชนีการค้นหาคือการแมป "โทเค็น" หรือคำหลักที่ปรากฏในชุดข้อมูลกับเอกสารที่ปรากฏ ดังนั้นคำถาม "เอกสารใดมีคำว่า X" รวดเร็ว ( O(1) ) เพื่อตอบในเวลาค้นหา หากไม่มีดัชนี คำถามนี้จะกลายเป็นคำถาม O(n) เนื่องจากเอกสารทุกฉบับจำเป็นต้องได้รับการสแกนเพื่อหาคำหลักนั้น แต่บ่อยครั้งสำหรับฮาร์ดแวร์สมัยใหม่ สำหรับชุดข้อมูลที่มีขนาดเล็กเพียงพอ (ไม่กี่ MB) โดยทั่วไปในเว็บแอปฝั่งไคลเอ็นต์ n ค่อนข้างเล็ก เล็กพอที่จะทำให้ O(n) ในทุกการกดแป้นพิมพ์ไม่สามารถมองเห็นได้ชัดเจน

libsearch แปลงข้อความค้นหาเช่น "Uni of California" เป็นรายการตัวกรองนิพจน์ทั่วไป (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California จากนั้นจะ "ค้นหา" โดยไม่ต้องใช้ดัชนีโดยการกรองคลังข้อมูลผ่านนิพจน์ทั่วไปแต่ละรายการ

2. การจัดอันดับ TF-IDF "ดีพอ" โดยพิจารณาจากการจับคู่ RegExp และความยาวของเอกสาร

เมตริก TF-IDF ทั่วไปได้รับการคำนวณสำหรับแต่ละคำดังนี้:

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

การได้รับจำนวนคำในเอกสารต้องใช้โทเค็นในเอกสาร หรืออย่างน้อยก็แยกเอกสารด้วยช่องว่าง ซึ่งมีราคาแพงในการคำนวณ ดังนั้น libsearch จึงประมาณค่านี้โดยใช้ความยาวของเอกสาร (จำนวนอักขระ) แทน

การใช้แบบสอบถามนิพจน์ทั่วไปที่อธิบายไว้ข้างต้น สูตร TF-IDF ของ libsearch คือ:

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

ซึ่งคำนวณสำหรับแต่ละคำในขณะที่ทำการค้นหา จากนั้นจึงนำมารวมกันในตอนท้ายเพื่อการเรียงลำดับ

การพัฒนา

ซอร์สโค้ดของ libsearch เขียนด้วย TypeScript เพื่อให้สามารถใช้ไลบรารี่กับ TypeScript, vanilla Node.js และเว็บได้ เราได้รวบรวมสองบิลด์:

• การสร้างโมดูล ES ซึ่งเป็นเพียงการตรวจสอบประเภท search.ts และลบประเภทออก นี่คือโค้ดที่นำเข้าเมื่อนำเข้า libsearch ใน Node.js
• เบราว์เซอร์บิลด์ ซึ่งส่งออกฟังก์ชัน search หลักไปยัง window.libsearch global

การสร้างโมดูล ES นั้นถูกสร้างขึ้นด้วย tsc คอมไพเลอร์ TypeScript และการสร้างเบราว์เซอร์แบบย่อส่วนนั้นถูกสร้างขึ้นเพิ่มเติมด้วย Webpack

คำสั่ง NPM/เส้นด้าย:

• lint และ fmt ซึ่ง lint และจัดรูปแบบซอร์สโค้ดในที่เก็บโดยอัตโนมัติ
• test รันการทดสอบหน่วยในไลบรารีรุ่นล่าสุด คุณควรรัน build:tsc ก่อนที่จะรัน test
• คำสั่ง build:* ต่างๆ ประสานการสร้างไลบรารีประเภทต่างๆ:
  • build:tsc สร้างบิลด์โมดูล ES
  • build:w รัน build:tsc ในทุกไฟล์ที่เขียน
  • build:cjs สร้างเบราว์เซอร์บิลด์ จากโมดูล ES
  • build:all สร้างทั้งสอง build ตามลำดับ
• clean จะลบไฟล์ที่สร้าง/สร้างทั้งหมดใน dist/
• docs สร้างเอกสารที่ใช้ Litterate ซึ่งอยู่ที่ thesephist.github.io/libsearch

ก่อนที่จะดันไปที่หลักหรือเผยแพร่ผมมักจะวิ่ง

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

เพื่อให้แน่ใจว่าฉันจะไม่ลืมสิ่งใดเลย