หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

▒ μคลุมเครือ

การค้นหาแบบคลุมเครือเล็กๆ น้อยๆ ที่มีประสิทธิภาพที่ไม่น่าเบื่อ นี่คือความคลุมเครือของฉันเหรอ? มีหลายอย่างที่เหมือนกัน แต่อันนี้เป็นของฉัน¹

ภาพรวม

uFuzzy เป็นไลบรารีการค้นหาแบบคลุมเครือที่ออกแบบมาเพื่อจับคู่วลีค้นหาที่ค่อนข้างสั้น (เข็ม) กับรายการวลีสั้นถึงกลางจำนวนมาก (กองหญ้า) มันอาจจะอธิบายได้ดีที่สุดว่าเป็น String.includes() ที่ให้อภัยมากกว่า แอปพลิเคชันทั่วไป ได้แก่ การกรองรายการ การเติมข้อความอัตโนมัติ/คำแนะนำ และการค้นหาชื่อเรื่อง ชื่อ คำอธิบาย ชื่อไฟล์ และฟังก์ชัน

ในโหมด MultiInsert เริ่มต้นของ uFuzzy แต่ละการจับคู่จะต้องมีอักขระตัวอักษรและตัวเลขทั้งหมดจากเข็มในลำดับเดียวกัน ในโหมด SingleError ยอมรับการพิมพ์ผิดเพียงครั้งเดียวในแต่ละเทอม (ระยะทาง Damerau – Levenshtein = 1) .search() API ของมันสามารถจับคู่คำที่ไม่เรียงลำดับได้อย่างมีประสิทธิภาพ รองรับการยกเว้นสตริงย่อยหลายรายการ (เช่น fruit -green -melon ) และคำที่ตรงทั้งหมดด้วยตัวอักษรที่ไม่ใช่ตัวอักษรอัลฟ่า (เช่น "C++" , "$100" , "#hashtag" ) เมื่อถือ ให้ถูกต้อง ก็สามารถจับคู่กับคุณสมบัติของวัตถุหลาย ๆ อย่างได้อย่างมีประสิทธิภาพเช่นกัน

คุณสมบัติ

  • ผลลัพธ์คุณภาพสูงไร้ขยะ พร้อมชุดข้อมูลใดก็ได้ ไม่จำเป็นต้องปรับแต่งตัวเลือกการจัดทำดัชนีหรือเพิ่มพารามิเตอร์เพื่อให้ได้คะแนนความเกี่ยวข้องโดยพลการ
  • การควบคุมความคลุมเครือที่แม่นยำ ซึ่งเป็นไปตามกฎที่ตรงไปตรงมา โดยไม่ส่งคืนแมตช์ที่ไม่คาดคิด
  • การเรียงลำดับคุณสามารถให้เหตุผล และปรับแต่งได้โดยใช้ Array.sort() แบบง่ายๆ ซึ่งเข้าถึงสถิติ/ตัวนับของแต่ละแมตช์ ไม่มี "คะแนน" แบบกล่องดำประกอบให้เข้าใจ
  • ชุดตัวเลือกที่กระชับ ซึ่งไม่ได้โต้ตอบด้วยวิธีลึกลับในการเปลี่ยนแปลงพฤติกรรมที่รวมกันอย่างมาก
  • รวดเร็วโดยใช้ทรัพยากรต่ำ - ไม่มีดัชนีให้สร้าง ดังนั้นการเริ่มต้นระบบจึงต่ำกว่า 1 มิลลิวินาที โดยมีค่าใช้จ่ายหน่วยความจำเกือบเป็นศูนย์ การค้นหาวลีสามคำในชุดข้อมูลวลี 162,000 รายการใช้เวลา 5 มิลลิวินาที หากไม่มีคำที่ไม่เรียงลำดับ
  • ไมโครที่มีการพึ่งพาเป็นศูนย์ - ปัจจุบัน ~ 7.5KB ขั้นต่ำ

การสาธิต uFuzzy

ชุดอักขระ ตัวอักษร ตัวกำกับเสียง

uFuzzy ได้รับการปรับให้เหมาะสมสำหรับตัวอักษรละติน/โรมัน และอาศัยนิพจน์ทั่วไปที่ไม่ใช่ Unicode ภายใน

การรองรับภาษาต่างๆ เพิ่มมากขึ้นโดยเพิ่ม regexps ละตินในตัวด้วยตัวอักษรเพิ่มเติม หรือโดยใช้ตัวแปร {unicode: true} สากลที่ช้ากว่าและเป็นสากล ตัวเลือก {alpha: "..."} ที่เรียบง่ายกว่าแต่มีความยืดหยุ่นน้อยกว่าจะแทนที่ส่วน AZ และ az ของ regexps ละตินในตัวด้วยตัวอักษรที่คุณเลือก (ตัวพิมพ์จะถูกจับคู่โดยอัตโนมัติระหว่างการเปลี่ยน)

ฟังก์ชัน uFuzzy.latinize() util สามารถใช้เพื่อตัดสำเนียง/ตัวกำกับเสียงทั่วไปออกจากกองหญ้าและเข็มก่อนที่จะค้นหา 

 // Latin (default)
let opts = { alpha : "a-z" } ;
// OR
let opts = {
  // case-sensitive regexps
  interSplit : "[^A-Za-z\d']+" ,
  intraSplit : "[a-z][A-Z]" ,
  intraBound : "[A-Za-z]\d|\d[A-Za-z]|[a-z][A-Z]" ,
  // case-insensitive regexps
  intraChars : "[a-z\d']" ,
  intraContr : "'[a-z]{1,2}\b" ,
} ;

// Latin + Norwegian
let opts = { alpha : "a-zæøå" } ;
// OR
let opts = {
  interSplit : "[^A-Za-zæøåÆØÅ\d']+" ,
  intraSplit : "[a-zæøå][A-ZÆØÅ]" ,
  intraBound : "[A-Za-zæøåÆØÅ]\d|\d[A-Za-zæøåÆØÅ]|[a-zæøå][A-ZÆØÅ]" ,
  intraChars : "[a-zæøå\d']" ,
  intraContr : "'[a-zæøå]{1,2}\b" ,
} ;

// Latin + Russian
let opts = { alpha : "a-zа-яё" } ;
// OR
let opts = {
  interSplit : "[^A-Za-zА-ЯЁа-яё\d']+" ,
  intraSplit : "[a-z][A-Z]|[а-яё][А-ЯЁ]" ,
  intraBound : "[A-Za-zА-ЯЁа-яё]\d|\d[A-Za-zА-ЯЁа-яё]|[a-z][A-Z]|[а-яё][А-ЯЁ]" ,
  intraChars : "[a-zа-яё\d']" ,
  intraContr : "'[a-z]{1,2}\b" ,
} ;

// Unicode / universal (50%-75% slower)
let opts = {
  unicode : true ,
  interSplit : "[^\p{L}\d']+" ,
  intraSplit : "\p{Ll}\p{Lu}" ,
  intraBound : "\p{L}\d|\d\p{L}|\p{Ll}\p{Lu}" ,
  intraChars : "[\p{L}\d']" ,
  intraContr : "'\p{L}{1,2}\b" ,
} ;

การค้นหาทั้งหมดในปัจจุบันไม่คำนึงถึงตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ ไม่สามารถทำการค้นหาแบบคำนึงถึงตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ได้

การสาธิต

หมายเหตุ: ไฟล์ testdata.json เป็นชุดข้อมูลสตริง/วลีที่หลากหลาย 162,000 รายการ และมีขนาด 4MB ดังนั้นการโหลดครั้งแรกอาจช้าเนื่องจากการถ่ายโอนผ่านเครือข่าย ลองรีเฟรชเมื่อเบราว์เซอร์ของคุณแคชไว้

ขั้นแรก uFuzzy แยกออกเพื่อสาธิตประสิทธิภาพ

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma

ตอนนี้เป็นหน้าเปรียบเทียบเดียวกัน บูทด้วย fuzzysort, QuickScore และ Fuse.js:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma

นี่คือรายการไลบรารีทั้งหมดแต่ด้วยชุดข้อมูลที่ลดลง (เพียง hearthstone_750 , urls_and_titles_600 ) เพื่อหลีกเลี่ยงไม่ให้เบราว์เซอร์ของคุณขัดข้อง:

https://leeoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo

คำถาม?

คำตอบ:

  • https://news.ycombinator.com/item?id=33035580
  • https://old.reddit.com/r/javascript/comments/xtrszc/ufuzzyjs_a_tiny_efficient_fuzzy_search_that/

อื่น ๆ : https://github.com/leeoniya/uFuzzy/issues

การติดตั้ง

โหนด 

 npm i @leeoniya/ufuzzy

 const uFuzzy = require ( '@leeoniya/ufuzzy' ) ;

เบราว์เซอร์ 

 < script src = "./dist/uFuzzy.iife.min.js" > < / script >

ตัวอย่าง 

 let haystack = [
    'puzzle' ,
    'Super Awesome Thing (now with stuff!)' ,
    'FileName.js' ,
    '/feeding/the/catPic.jpg' ,
] ;

let needle = 'feed cat' ;

let opts = { } ;

let uf = new uFuzzy ( opts ) ;

// pre-filter
let idxs = uf . filter ( haystack , needle ) ;

// idxs can be null when the needle is non-searchable (has no alpha-numeric chars)
if ( idxs != null && idxs . length > 0 ) {
  // sort/rank only when <= 1,000 items
  let infoThresh = 1e3 ;

  if ( idxs . length <= infoThresh ) {
    let info = uf . info ( idxs , haystack , needle ) ;

    // order is a double-indirection array (a re-order of the passed-in idxs)
    // this allows corresponding info to be grabbed directly by idx, if needed
    let order = uf . sort ( info , haystack , needle ) ;

    // render post-filtered & ordered matches
    for ( let i = 0 ; i < order . length ; i ++ ) {
      // using info.idx here instead of idxs because uf.info() may have
      // further reduced the initial idxs based on prefix/suffix rules
      console . log ( haystack [ info . idx [ order [ i ] ] ] ) ;
    }
  }
  else {
    // render pre-filtered but unordered matches
    for ( let i = 0 ; i < idxs . length ; i ++ ) {
      console . log ( haystack [ idxs [ i ] ] ) ;
    }
  }
}

การค้นหาแบบรวม

uFuzzy ให้ uf.search(haystack, needle, outOfOrder = 0, infoThresh = 1e3) => [idxs, info, order] wrapper ซึ่งรวม filter , info , ขั้นตอน sort ลำดับด้านบน วิธีนี้ยังใช้ตรรกะที่มีประสิทธิภาพในการจับคู่คำค้นหาที่ไม่เรียงลำดับ และรองรับการยกเว้นสตริงย่อยหลายรายการ เช่น fruit -green -melon

ไฮไลท์การแข่งขัน

รับการแข่งขันที่สั่งซื้อของคุณก่อน: 

 let haystack = [
  'foo' ,
  'bar' ,
  'cowbaz' ,
] ;

let needle = 'ba' ;

let u = new uFuzzy ( ) ;

let idxs = u . filter ( haystack , needle ) ;
let info = u . info ( idxs , haystack , needle ) ;
let order = u . sort ( info , haystack , needle ) ;

ปากกาเน้นข้อความ innerHTML พื้นฐาน ( <mark> -ช่วงที่ห่อ): 

 let innerHTML = '' ;

for ( let i = 0 ; i < order . length ; i ++ ) {
  let infoIdx = order [ i ] ;

  innerHTML += uFuzzy . highlight (
    haystack [ info . idx [ infoIdx ] ] ,
    info . ranges [ infoIdx ] ,
  ) + '<br>' ;
}

console . log ( innerHTML ) ;

ปากกาเน้นข้อความ innerHTML พร้อมฟังก์ชันการทำเครื่องหมายแบบกำหนดเอง ( <b> -ช่วงที่ห่อหุ้ม): 

 let innerHTML = '' ;

const mark = ( part , matched ) => matched ? '<b>' + part + '</b>' : part ;

for ( let i = 0 ; i < order . length ; i ++ ) {
  let infoIdx = order [ i ] ;

  innerHTML += uFuzzy . highlight (
    haystack [ info . idx [ infoIdx ] ] ,
    info . ranges [ infoIdx ] ,

    mark ,
  ) + '<br>' ;
}

console . log ( innerHTML ) ;

ปากกาเน้นข้อความองค์ประกอบ DOM/JSX พร้อมการทำเครื่องหมายแบบกำหนดเองและฟังก์ชันต่อท้าย: 

 let domElems = [ ] ;

const mark = ( part , matched ) => {
  let el = matched ? document . createElement ( 'mark' ) : document . createElement ( 'span' ) ;
  el . textContent = part ;
  return el ;
} ;

const append = ( accum , part ) => { accum . push ( part ) ; } ;

for ( let i = 0 ; i < order . length ; i ++ ) {
  let infoIdx = order [ i ] ;

  let matchEl = document . createElement ( 'div' ) ;

  let parts = uFuzzy . highlight (
    haystack [ info . idx [ infoIdx ] ] ,
    info . ranges [ infoIdx ] ,

    mark ,
    [ ] ,
    append ,
  ) ;

  matchEl . append ( ... parts ) ;

  domElems . push ( matchEl ) ;
}

document . getElementById ( 'matches' ) . append ( ... domElems ) ;

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

uFuzzy มีโหมดการทำงานสองโหมดที่แตกต่างกันในกลยุทธ์การจับคู่:

  • intraMode: 0 (ค่าเริ่มต้น) กำหนดให้อักขระตัวอักษรและตัวเลขทั้งหมดในแต่ละคำค้นหาต้องอยู่ในลำดับเดียวกันในทุกรายการที่ตรงกัน ตัวอย่างเช่น เมื่อค้นหา " cat " โหมดนี้สามารถจับคู่สตริงด้านล่างได้ สิ่งที่ตรงกัน จริงๆ จะขึ้นอยู่กับการตั้งค่าความคลุมเครือเพิ่มเติม
    • แมว
    • เสื้อ โค้ ท
    • เกา​
    • ไม่ เป็นไร
    • tra c tors a re la t e
  • intraMode: 1 อนุญาตให้มีข้อผิดพลาดเดียวในแต่ละเงื่อนไขของวลีค้นหา โดยที่ข้อผิดพลาดเป็นหนึ่งใน: การทดแทน (การแทนที่) การขนย้าย (สลับ) การแทรก (การเพิ่มเติม) หรือการลบ (การละเว้น) สตริงการค้นหาที่มีข้อผิดพลาดด้านล่างสามารถส่งคืนรายการที่ตรงกันที่มี " example " สิ่งที่ตรงกัน จริงๆ จะขึ้นอยู่กับการตั้งค่าความคลุมเครือเพิ่มเติม ตรงกันข้ามกับโหมดก่อนหน้า การค้นหา " ตัวอย่าง " จะไม่ตรงกับ " ex tr a m a ple "
    • example - แน่นอน
    • examplle - การแทรกเดี่ยว (เพิ่มเติม)
    • exemple - การทดแทนเดี่ยว (การแทนที่)
    • exmaple - การขนย้ายเดี่ยว (สลับ)
    • exmple - การลบครั้งเดียว (ละเว้น)
    • xamp - บางส่วน
    • xmap - บางส่วนพร้อมการขนย้าย

การค้นหามี 3 ขั้นตอน:

  1. ตัวกรอง กรอง haystack ทั้งหมดด้วย RegExp ที่รวดเร็วที่รวบรวมจาก needle ของคุณโดยไม่ต้องดำเนินการใดๆ เพิ่มเติม โดยจะส่งคืนอาร์เรย์ของดัชนีที่ตรงกันตามลำดับเดิม
  2. ข้อมูล จะรวบรวมสถิติโดยละเอียดเพิ่มเติมเกี่ยวกับการจับคู่ที่กรอง เช่น ออฟเซ็ตเริ่มต้น ระดับฟัซ ตัวนับคำนำหน้า/ต่อท้าย ฯลฯ นอกจากนี้ยังรวบรวมตำแหน่งการจับคู่สตริงย่อยสำหรับการเน้นช่วงด้วย สุดท้ายจะกรองรายการที่ตรงกันที่ไม่สอดคล้องกับกฎคำนำหน้า/คำต่อท้ายที่ต้องการออก เมื่อต้องการทำทั้งหมดนี้ จะคอมไพล์ needle ใหม่เป็น RegExps ที่มีราคาแพงกว่าสองรายการ ซึ่งสามารถแบ่งพาร์ติชันการแข่งขันแต่ละรายการได้ ดังนั้นจึงควรรันบนชุดย่อยที่ลดลงของกองหญ้า ซึ่งโดยปกติจะส่งคืนโดยเฟสตัวกรอง การสาธิต uFuzzy มีรั้วกั้นอยู่ที่ <= 1,000 รายการที่กรอง ก่อนที่จะดำเนินการในระยะนี้
  3. Sort ใช้ Array.sort() เพื่อกำหนดลำดับผลลัพธ์สุดท้าย โดยใช้ออบเจ็กต์ info ที่ส่งคืนจากเฟสก่อนหน้า คุณสามารถจัดเตรียมฟังก์ชันการเรียงลำดับแบบกำหนดเองได้ผ่านตัวเลือก uFuzzy: {sort: (info, haystack, needle) => idxsOrder}

เอพีไอ

ไฟล์ uFuzzy.d.ts LoC จำนวน 200 รายการที่มีการแสดงความคิดเห็นอย่างเสรี

ตัวเลือก

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

ตัวเลือก คำอธิบาย ค่าเริ่มต้น ตัวอย่าง
intraMode การจับคู่คำควรทำอย่างไร 0 0 แทรกหลายอัน
1 ข้อผิดพลาดเดียว

ดูวิธีการทำงาน
intraIns อนุญาตให้ใช้อักขระพิเศษได้สูงสุดจำนวน
ระหว่างอักขระแต่ละตัวภายในเทอม		 จับคู่ค่าของ intraMode (อย่างใดอย่างหนึ่ง 0 หรือ 1 ) กำลังค้นหา "แมว"...
0 สามารถจับคู่ได้: cat , s cat , cat ch, va cat e
1 ตรงกับ: ca r t , c h a p t er, out ca s t
interIns จำนวนอักขระพิเศษสูงสุดที่อนุญาตระหว่างข้อกำหนด Infinity กำลังค้นหา "อยู่ที่ไหน"...
Infinity สามารถจับคู่ได้: ที่ไหน คือ ที่ไหน มี blah w คือ dom
5 เทียบไม่ได้: ที่ไหนมีปัญญาโง่เขลา
intraSub
intraTrn
intraDel
 สำหรับ intraMode: 1 เท่านั้น
ประเภทข้อผิดพลาดที่ต้องยอมรับภายในเงื่อนไข		 จับคู่ค่าของ intraMode (อย่างใดอย่างหนึ่ง 0 หรือ 1 ) 0 เลขที่
1 ใช่
intraChars regexp บางส่วนสำหรับการแทรกที่อนุญาต
ตัวอักษรระหว่างแต่ละตัวอักษรภายในเทอม		 [azd'] [azd] จับคู่เฉพาะตัวอักษรและตัวเลขเท่านั้น (ไม่คำนึงถึงตัวพิมพ์เล็กและใหญ่)
[w-] จะจับคู่ตัวอักษรและตัวเลข ขีดล่าง และยัติภังค์
intraFilt โทรกลับเพื่อไม่รวมผลลัพธ์ตามเงื่อนไขและการจับคู่ (term, match, index) => true ทำสิ่งที่คุณทำเอง บางที... - ขีดจำกัดความยาวต่างกัน
- ระยะทางเลเวนชไตน์
- ระยะชดเชยหรือเนื้อหา
interChars regexp บางส่วนสำหรับอักขระที่อนุญาตระหว่างคำ . . ตรงกับตัวอักษรทั้งหมด
[^azd] จะจับคู่เฉพาะช่องว่างและเครื่องหมายวรรคตอนเท่านั้น
interLft กำหนดขอบเขตด้านซ้ายของระยะเวลาที่อนุญาต 0 กำลังค้นหา "ความบ้าคลั่ง"...
0 ใดก็ได้ - ทุกที่: ro mania n
1 หลวม - ช่องว่าง, เครื่องหมายวรรคตอน, อัลฟ่า-ตัวเลข, การเปลี่ยนตัวพิมพ์: Track Mania , mania c
2 เข้มงวด - ช่องว่าง เครื่องหมายวรรคตอน: ความบ้าคลั่ง cally
interRgt กำหนดขอบเขตสิทธิของระยะเวลาที่อนุญาต 0 กำลังค้นหา "ความบ้าคลั่ง"...
0 ใดก็ได้ - ทุกที่: ro mania n
1 หลวม - ช่องว่าง, เครื่องหมายวรรคตอน, อัลฟ่า-ตัวเลข, การเปลี่ยนตัวพิมพ์: Mania Star
2 เข้มงวด - ช่องว่าง เครื่องหมายวรรคตอน: mania _foo
sort ฟังก์ชั่นการเรียงลำดับผลลัพธ์แบบกำหนดเอง (info, haystack, needle) => idxsOrder ค่าเริ่มต้น: การเรียงลำดับการค้นหา จัดลำดับความสำคัญของการจับคู่คำเต็มและความหนาแน่นของอักขระ
การสาธิต: การเรียงลำดับแบบพิมพ์ล่วงหน้า จัดลำดับความสำคัญของออฟเซ็ตเริ่มต้นและความยาวที่ตรงกัน

การประเมินงานที่คล้ายกันอย่างลำเอียง

การประเมินนี้แคบมากและแน่นอนว่ามีอคติต่อกรณีการใช้งานของฉัน คลังข้อความ และความเชี่ยวชาญทั้งหมดของฉันในการใช้งานห้องสมุดของตัวเอง มีความเป็นไปได้สูงที่ฉันจะไม่ได้รับประโยชน์อย่างเต็มที่จากคุณสมบัติบางอย่างในไลบรารีอื่น ๆ ที่อาจปรับปรุงผลลัพธ์ในบางแกนได้อย่างมีนัยสำคัญ ฉันยินดีรับการปรับปรุง PR จากใครก็ตามที่มีความรู้เชิงลึกเกี่ยวกับห้องสมุดมากกว่าการใช้เวลา 10 นาทีอย่างเร่งรีบของฉันในตัวอย่าง "การใช้งานพื้นฐาน" และเอกสาร README

คุณภาพการค้นหา

หนอนพยาธิ #1.

ก่อนที่เราจะพูดถึงประสิทธิภาพ มาพูดถึงคุณภาพการค้นหากันก่อน เพราะความเร็วนั้นไม่เกี่ยวข้องเมื่อผลลัพธ์ของคุณมีเสียงแปลกๆ อยู่ว่า "โอ้ ใช่แล้ว!" และ "WTF?"

คุณภาพการค้นหาเป็นเรื่องส่วนตัวมาก สิ่งที่ถือเป็นการจับคู่อันดับต้นๆ ที่ดีในกรณี "พิมพ์ข้างหน้า / แนะนำอัตโนมัติ" อาจเป็นการจับคู่ที่ไม่ดีในสถานการณ์ "ค้นหา / ค้นหาทั้งหมด" โซลูชันบางอย่างปรับให้เหมาะสมสำหรับอย่างหลัง บางอย่างสำหรับวิธีแรก เป็นเรื่องปกติที่จะพบปุ่มที่บิดเบือนผลลัพธ์ไปในทิศทางใดทิศทางหนึ่ง แต่สิ่งเหล่านี้มักจะเกิดขึ้นเองและไม่สมบูรณ์ เป็นอะไรที่มากกว่าแค่ตัวแทนในการสร้าง "คะแนน" การจับคู่แบบผสมเดี่ยว

อัปเดต (2024): คำวิจารณ์ด้านล่างเกี่ยวกับการจับคู่ bizzare เป็นจริงสำหรับการกำหนด ค่าเริ่มต้น ของ Fuse.js เท่านั้น ในทางตรงข้าม การตั้งค่า ignoreFieldNorm: true ทำให้ผลลัพธ์ดีขึ้นมาก แต่การเรียงลำดับการจับคู่คุณภาพสูงยังคงไม่ดีนัก

มาดูการจับคู่บางรายการที่ผลิตโดยไลบรารีการค้นหาแบบคลุมเครือที่ได้รับความนิยมสูงสุด Fuse.js และอื่นๆ บางส่วนที่มีการเน้นการจับคู่ที่ถูกนำมาใช้ในการสาธิต

เมื่อค้นหาคำว่า "twili" บางส่วน เราจะเห็นผลลัพธ์เหล่านี้ปรากฏเหนือผลลัพธ์ "twilight" ที่เห็นได้ชัดจำนวนมาก:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili

  • ทวิ อา ห ลิง
  • จำนวน การแจ้งเตือนทั้งหมดที่ได้รับ ว่า ยัง อยู่
  • Tom Clancy's Ghost Recon Wil dlands - การเปิดใช้งาน Uplay แบบมาตรฐานสำหรับ การ สั่งซื้อล่วงหน้า
  • heHunter ™: Call of the Wild - Bearclaw Li te CB-60

การแข่งขันที่ไม่ดีเหล่านี้ไม่เพียงแต่แยกออกจากกันเท่านั้น แต่จริงๆ แล้วยังมีอันดับสูงกว่าสตริงย่อยตามตัวอักษรอีกด้วย

จบคำค้นหาเป็น "ทไวไลท์" ยังคง ให้คะแนนผลลัพธ์ที่สูงกว่า:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight

  • เวทมนตร์: The Gathering - การดวลของ Planeswalkers พร้อม ปลดล็อค แสง
  • เขา วิลดี อี ใช่มั้ ย

เอ็นจิ้นบางตัวทำงานได้ดีกว่าด้วยการจับคู่คำนำหน้าบางส่วน โดยมีค่าใช้จ่ายในการเริ่มต้น/จัดทำดัชนีที่สูงขึ้น:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili

ที่นี่ match-sorter ส่งคืนผลลัพธ์ 1,384 รายการ แต่เฉพาะ 40 รายการแรกเท่านั้นที่เกี่ยวข้อง เราจะรู้ได้อย่างไรว่าจุดตัดอยู่ที่ไหน?

ผลงาน

หนอนพยาธิ #2.

มาตรฐานทั้งหมดห่วย แต่อันนี้อาจห่วยมากกว่าอันอื่น

  • ฉันได้พยายามทำตามคำแนะนำ "ประสิทธิภาพที่ดีที่สุด" เมื่อพบมันในเอกสารของแต่ละห้องสมุด แต่ก็แน่นอนว่ามีหินบางก้อนที่ไม่ถูกเปิดใช้งานเมื่อใช้เครื่องมือค้นหาที่แตกต่างกันประมาณ 20 รายการ
  • แม้ว่าฉันจะพยายามอย่างเต็มที่แล้ว แต่คุณภาพของผลลัพธ์ก็ยังคงแตกต่างกันอย่างมากระหว่างไลบรารีต่างๆ และแม้แต่ระหว่างคำค้นหาด้วย ในบางกรณี ผลลัพธ์ที่ได้แย่มากแต่ไลบรารีทำงานเร็วมาก ในกรณีอื่นๆ ผลลัพธ์จะดีกว่า แต่ห้องสมุดค่อนข้างช้า ความเร็วสูงสุดจะมีประโยชน์อะไรเมื่อคุณภาพการค้นหาต่ำกว่ามาตรฐาน นี่เป็นหัวข้อเชิงอัตวิสัยและเหมาะสมอย่างยิ่งที่จะส่งผลต่อการตีความตัวเลขเหล่านี้อย่างแน่นอน ฉันถือว่าคุณภาพการค้นหาของ uFuzzy ไม่เป็นสองรองใคร ดังนั้น มุมมองของฉันเกี่ยวกับไลบรารีที่เร็วกว่าส่วนใหญ่มักเป็นการแลกเปลี่ยนด้านคุณภาพที่ฉันดีใจที่ไม่ได้ทำ ฉันขอแนะนำให้คุณประเมินผลลัพธ์ของวลีค้นหาที่เปรียบเทียบทั้งหมดด้วยตนเองเพื่อตัดสินใจด้วยตนเอง
  • ไลบรารีข้อความและการค้นหาเอกสารจำนวนมากที่เปรียบเทียบที่นี่ได้รับการออกแบบมาให้ทำงานได้ดีที่สุดโดยใช้คำที่ตรงทั้งหมดมากกว่าการจับคู่บางส่วน (ซึ่งเกณฑ์มาตรฐานนี้เบี่ยงเบนไป)

ถึงกระนั้น มีบางสิ่งที่ดีกว่าการเลิกจ้าง YMMV/ทำด้วยตัวเองด้วยมือ และดีกว่าไม่มีอะไรเลยอย่างแน่นอน

เกณฑ์มาตรฐาน

สิ่งแวดล้อม

วันที่ 2023-10
ฮาร์ดแวร์ ซีพียู: Ryzen 7 PRO 5850U (1.9GHz, 7nm, 15W TDP)
แรม: 48GB
SSD: ซัมซุง SSD 980 PRO 1TB (NVMe)
ระบบปฏิบัติการ EndeavourOS (อาร์คลินุกซ์)
v6.5.4-arch2-1 x86_64
โครเมียม v117.0.5938.132
  • แต่ละการวัดประสิทธิภาพสามารถรันได้โดยการเปลี่ยนพารามิเตอร์ libs เป็นชื่อไลบรารีที่ต้องการ: https://leeoniya.github.io/uFuzzy/demos/compare.html?bench&libs=uFuzzy
  • เอาต์พุตผลลัพธ์จะถูกระงับในโหมด bench เพื่อหลีกเลี่ยงการเปรียบเทียบ DOM
  • การวัดจะดำเนินการในส่วนประสิทธิภาพของ DevTools ของ Chrome โดยการบันทึกการโหลดซ้ำหลายครั้งของหน้าเปรียบเทียบ โดยมีการบังคับเก็บขยะในระหว่างนั้น การวิ่งกลาง/ทั่วไปใช้เพื่อรวบรวมตัวเลข
  • คลังข้อมูลการค้นหาคือ 162,000 คำและวลี โหลดจาก testdata.json ขนาด 4MB
  • ประเภทการวัดประสิทธิภาพ จากนั้นจะลบคำค้นหาต่อไปนี้แบบอักขระต่ออักขระ (ทุกๆ 20 มิลลิวินาที) ซึ่งจะทำให้เกิดการค้นหาสำหรับการกดปุ่มแต่ละครั้ง: test , chest , super ma , mania , puzz , prom rem stor , twil

หากต้องการประเมินผลลัพธ์สำหรับแต่ละไลบรารี หรือเปรียบเทียบหลายไลบรารี เพียงไปที่หน้าเดียวกันซึ่งมี libs มากขึ้นและไม่มี bench : https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore ,ฟิวส์&ค้นหา=ซุปเปอร์%20ma.

ตัวอย่างโปรไฟล์

มีการประเมินเมตริกหลายรายการ:

  • เวลาเริ่มต้น - ระยะเวลาที่ใช้ในการโหลดไลบรารีและสร้างดัชนีที่จำเป็นเพื่อทำการค้นหา
  • รันไทม์แบบเปรียบเทียบ - ระยะเวลาที่ใช้ในการดำเนินการค้นหาทั้งหมด
  • หน่วยความจำที่ต้องการ - ขนาดฮีป JS สูงสุดที่ใช้ระหว่างการทำงาน รวมถึงจำนวนที่ยังคงเหลืออยู่หลังจากการบังคับรวบรวมขยะในตอนท้าย
  • ต้นทุน GC - ต้องใช้เวลาเท่าไรในการเก็บขยะในตอนท้าย (ปัญหาเธรดหลัก)
ลิบ ดาว ขนาด (นาที) เริ่มต้น ค้นหา
(x86)		 ฮีป (จุดสูงสุด) เก็บไว้ GC
uFuzzy (ลอง) ★ 2.3k 7.6KB 0.5ms 434ms 28.4MB 7.4MB 18ms
uFuzzy (ลอง)
(แคชคำนำหน้าภายนอก)		 210ms 27.8MB 7.4MB 18ms
uFuzzy (ลอง)
(ไม่อยู่ในลำดับ, คลุมเครือ)		 545ms 29.5MB 7.4MB 18ms
uFuzzy (ลอง)
(outOfOrder, fuzzier, SingleError)		 508ms 30.0MB 7.4MB 18ms
-
Fuse.js (ลอง) ★ 16.6k 24.2KB 31ms 33875มิลลิวินาที 245MB 13.9MB 25ms
FlexSearch (แสง) (ลอง) ★ 10.700 6.2KB 3210ms 83มิลลิวินาที 670MB 316MB 553มิลลิวินาที
Lunr.js (ลอง) ★ 8.7k 29.4KB 1704มิลลิวินาที 996ms 380MB 123MB 166ms
Orama (เดิมชื่อ Lyra) (ลอง) ★ 6.4k 41.5KB 2650ms 225ms 313MB 192MB 180ms
MiniSearch (ลอง) ★ 3.4k 29.1KB 504ms 1453ms 438MB 67MB 105ms
จับคู่ตัวเรียงลำดับ (ลอง) ★ 3.4k 7.3KB 0.1ms 6245มิลลิวินาที 71MB 7.3MB 12ms
fuzzysort (ลอง) ★ 3.4k 6.2KB 50ms 1321มิลลิวินาที 175MB 84MB 63มิลลิวินาที
เวด (ลอง) ★ 3000 4KB 781ms 194ms 438MB 42MB 130ms
fuzzysearch (ลอง) ★ 2.7000 0.2KB 0.1ms 529ms 26.2MB 7.3MB 18ms
ค้นหา js (ลอง) ★ 2.1000 17.1KB 5620มิลลิวินาที 1190ms 1740MB 734MB 2600ms
Elasticlunr.js (ลอง) ★ 2000 18.1KB 933ms 1330ms 196MB 70MB 135ms
Fuzzyset (ลอง) ★ 1.4k 2.8KB 2962มิลลิวินาที 606ms 654MB 238MB 239ms
ดัชนีการค้นหา (ลอง) ★ 1.4k 168KB RangeError: เกินขนาดสแต็กการโทรสูงสุดแล้ว
sifter.js (ลอง) ★ 1.1000 7.5KB 3ms 1,070ms 46.2MB 10.6MB 18ms
fzf-for-js (ลอง) ★ 831 15.4KB 50ms 6290ms 153MB 25MB 18ms
คลุมเครือ (ลอง) ★ 819 1.4KB 0.1ms 5427มิลลิวินาที 72MB 7.3MB 14ms
รวดเร็วคลุมเครือ (ลอง) ★ 346 18.2KB 790ms 19266มิลลิวินาที 550MB 165MB 140ms
ItemsJS (ลอง) ★ 305 109KB 2400ms 11304ms 320MB 88MB 163ms
LiquidMetal (ลอง) ★ 292 4.2KB (ชน)
FuzzySearch (ลอง) ★ 209 3.5KB 2ms 3948มิลลิวินาที 84MB 10.5MB 18ms
FuzzySearch2 (ลอง) ★ 186 19.4KB 93ms 4189ms 117MB 40.3MB 40ms
QuickScore (ลอง) ★ 153 9.5KB 10ms 6915มิลลิวินาที 133MB 12.1MB 18ms
ndx (ลอง) ★ 142 2.9KB 300ms 581มิลลิวินาที 308MB 137MB 262ms
fzy (ลอง) ★ 133 1.5KB 0.1ms 3932มิลลิวินาที 34MB 7.3MB 10ms
เครื่องมือคลุมเครือ (ลอง) ★ 13 3กิโลไบต์ 0.1ms 5138ms 164MB 7.5MB 18ms
fuzzyMatch (ลอง) ★ 0 1กิโลไบต์ 0.1ms 2415มิลลิวินาที 83.5MB 7.3MB 13ms
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด