🦌鹿心雨的小窝🦌
🦌鹿心雨的小窝
coverPiccoverPic

源码解析：Fuse.js 是如何实现模糊搜索的？

模糊搜索BitapFuse字符串匹配算法与数据结构JavaScript

🎈前言

最近一直都在用 Fuse.js 来进行表格搜索，有点好奇是怎么实现的，于是就翻了一下源码。

Fuse.js 是一个功能强大、轻量级、零依赖关系的 JS 模糊搜索库，适用于前后端各种 JS 项目。Fuse.js 根据匹配度、匹配位置、句子长度的因素，给每个搜索项评分并排序，得到模糊搜索的结果。举个利兹🕊：

ts
  1. const list = ['apple', 'orange', 'banana']
  2. const fuse = new Fuse(list)
  3. console.log(fuse.search('appnana'));
  4. // [ { item: 'banana', refIndex: 2 }, { item: 'apple', refIndex: 0 } ]

也可以用于复杂对象的搜索：

ts
  1. const list = [
  2.   { item: 'vue', tag: [ 'front end', 'browser' ] },
  3.   { item: 'axios', tag: [ 'request lib' ] },
  4.   { item: 'echart', tag: [ 'graph lib' ] },
  5.   { item: 'naive ui', tag: [ 'UI lib' ] },
  6.   { item: 'next', tag: [ 'full stack', 'server side render' ] }
  7. ]
  8. const fuse = new Fuse(list, {
  9.   keys: ['item', 'tag']
  10. })
  11. console.log(fuse.search('livue'));
  12. // [
  13. //   { item: { item: 'vue', tag: [Array] }, refIndex: 0 },
  14. //   { item: { item: 'naive ui', tag: [Array] }, refIndex: 3 },
  15. //   { item: { item: 'axios', tag: [Array] }, refIndex: 1 }
  16. // ]

它的核心模糊匹配算法是源自 Bitap 算法。Bitap算法（也被称为 shift-or、shift-and 或 Baeza-Yates-Gonnet 算法）是一种模糊字符串搜索算法。该算法可以判断给定文本是否包含与给定模式“大致相等”的子字符串，这里的“大致相等”是根据子串和模式之间的 Levenshtein 编辑距离是否在给定的距离以内来判断的。Bitap 算法预先计算模式串字符位置，使用二进制运算来进行，速度非常的快，时间复杂度是 O(mn)O(mn)，mm、nn 分别是目标串和模式串长度。

Levenshtein 编辑距离，就是两个字符串之间，通过增加、减少、替换字符，由一个转换成另一个所需的最少编辑操作次数。

下面以字符串数组为例，分析 Fuse.js 的算法。

✨初始化

我们一般先会创建Fuse的实例：

ts
  1. const list = [/*...*/]
  2. const fuse = new Fuse(list, {/*...*/})

创建实例时，内部会根据传入的数据创建索引FuseIndex，它的数据结构大概长这样子：

ts
  1. {
  2.   v: string // 待匹配的目标串
  3.   i: number // 目标串在原数据的位置
  4.   n: number // 范数（？），随目标串单词个数上升，影响搜索结果的排序
  5. }[]

📑创建索引

函数入口在 src/core/index.js。创建Fuse实例后，根据传入的docs构建索引。

ts
  1. export default class Fuse {
  2.   constructor(docs, options = {}, index) {
  3.     this.options = { ...Config, ...options }
  4.     if (
  5.       this.options.useExtendedSearch &&
  6.       !process.env.EXTENDED_SEARCH_ENABLED
  7.     ) {
  8.       throw new Error(ErrorMsg.EXTENDED_SEARCH_UNAVAILABLE)
  9.     }
  10.     this._keyStore = new KeyStore(this.options.keys)
  11.     this.setCollection(docs, index)
  12.   }
  14.   setCollection(docs, index) {
  15.     this._docs = docs
  17.     if (index && !(index instanceof FuseIndex)) {
  18.       throw new Error(ErrorMsg.INCORRECT_INDEX_TYPE)
  19.     }
  21.     this._myIndex =
  22.       index ||
  23.       createIndex(this.options.keys, this._docs, {
  24.         getFn: this.options.getFn,
  25.         fieldNormWeight: this.options.fieldNormWeight
  26.       })
  27.   }
  28. }

这里由于我们以字符串数组为例，这里就没有this.options.keys了，KeyStore先不看了，来看createIndex：

ts
  1. export function createIndex(
  2.   keys,
  3.   docs,
  4.   { getFn = Config.getFn, fieldNormWeight = Config.fieldNormWeight } = {}
  5. ) {
  6.   const myIndex = new FuseIndex({ getFn, fieldNormWeight })
  7.   myIndex.setKeys(keys.map(createKey))
  8.   myIndex.setSources(docs)
  9.   myIndex.create()
  10.   return myIndex
  11. }
  13. export default class FuseIndex {
  14.   constructor({
  15.     getFn = Config.getFn,
  16.     fieldNormWeight = Config.fieldNormWeight
  17.   } = {}) {
  18.     this.norm = normGenerator(fieldNormWeight, 3)
  19.     this.getFn = getFn
  20.     this.isCreated = false
  22.     this.setIndexRecords()
  23.   }
  24.   setIndexRecords(records = []) {
  25.     this.records = records
  26.   }
  27.   setSources(docs = []) {
  28.     this.docs = docs
  29.   }
  30. }

FuseIndex创建后，加入keys和docs，然后调用create创建索引：

ts
  1. create() {
  2.   if (this.isCreated || !this.docs.length) {
  3.     return
  4.   }
  5.   this.isCreated = true
  6.   // List is Array<String>
  7.   if (isString(this.docs[0])) {
  8.     this.docs.forEach((doc, docIndex) => {
  9.       this._addString(doc, docIndex)
  10.     })
  11.   } else {
  12.     // List is Array<Object>
  13.     this.docs.forEach((doc, docIndex) => {
  14.       this._addObject(doc, docIndex)
  15.     })
  16.   }
  17.   this.norm.clear()
  18. }
  19. _addString(doc, docIndex) {
  20.   if (!isDefined(doc) || isBlank(doc)) {
  21.     return
  22.   }
  23.   let record = {
  24.     v: doc,
  25.     i: docIndex,
  26.     n: this.norm.get(doc)
  27.   }
  28.   this.records.push(record)
  29. }

对于字符串的数据源来说，每一条索引是由v文本（也就是匹配时的目标串）、i在原数据数组中的下标、nnorm（大概叫…范数吧，和长度有关的一个值）。this.norm.get是一个随文本长度下降的权重，计算方法如下：

ts
  1. const SPACE = /[^ ]+/g
  2. // Field-length norm: the shorter the field, the higher the weight.
  3. // Set to 3 decimals to reduce index size.
  4. export default function norm(weight = 1, mantissa = 3) {
  5.   const cache = new Map()
  6.   const m = Math.pow(10, mantissa)
  7.   return {
  8.     get(value) {
  9.       // 这里 Token 是按空格分割算的，那中文就只有一个 Token，感觉像 bug
  10.       const numTokens = value.match(SPACE).length
  11.       if (cache.has(numTokens)) {
  12.         return cache.get(numTokens)
  13.       }
  14.       // Default function is 1/sqrt(x), weight makes that variable
  15.       const norm = 1 / Math.pow(numTokens, 0.5 * weight)
  16.       // In place of `toFixed(mantissa)`, for faster computation
  17.       const n = parseFloat(Math.round(norm * m) / m)
  18.       cache.set(numTokens, n)
  19.       return n
  20.     },
  21.     clear() {
  22.       cache.clear()
  23.     }
  24.   }
  25. }

简单来说，也就是

numTokens−0.5∗weightnumTokens^{-0.5*weight}

可见，numTokens越小，norm就大，后续可以看到分数随norm增加而下降，数据项根据分数从小到大排序，这样子比较短的数据项的排名就靠前。

这里的weight，可以在创建时从options.fieldNormWeight传入，默认为 1，norm随weight减小而增加。

到这里，索引就创建完了，如果传入['apple', 'orange', 'banana']，就有索引

json
  1. [
  2.   { v: 'apple', i: 0, n: 1 },
  3.   { v: 'orange', i: 1, n: 1 },
  4.   { v: 'banana', i: 2, n: 1 }
  5. ]

📙小结

简单总结一下大致流程：

graph LR
    A("new Fuse()")-->B("createIndex")-->C("myIndex = new FuseIndex()")-->D("myIndex.create()")

🗄搜索

创建完索引后，使用search函数进行模糊搜索，就像这样子

ts
  1. const fuse = new Fuse(/*...*/)
  2. const ans = fuse.search('appnana')

🚪搜索入口

搜索的流程从search方法开始：

ts
  1. search(query, { limit = -1 } = {}) {
  2.   // ...
  3.   let results = isString(query)
  4.     ? isString(this._docs[0])
  5.       ? this._searchStringList(query)
  6.       : this._searchObjectList(query)
  7.     : this._searchLogical(query)
  9.   computeScore(results, { ignoreFieldNorm })
  11.   if (shouldSort) {
  12.     results.sort(sortFn)
  13.   }
  15.   // ...
  16. }

字符串的数据调用_searchStringList方法，得出符合要求的每一项及其得分。

ts
  1. _searchStringList(query) {
  2.   const searcher = createSearcher(query, this.options)
  3.   const { records } = this._myIndex
  4.   const results = []
  5.   // Iterate over every string in the index
  6.   records.forEach(({ v: text, i: idx, n: norm }) => {
  7.     if (!isDefined(text)) {
  8.       return
  9.     }
  10.     const { isMatch, score, indices } = searcher.searchIn(text)
  11.     if (isMatch) {
  12.       results.push({
  13.         item: text,
  14.         idx,
  15.         matches: [{ score, value: text, norm, indices }]
  16.       })
  17.     }
  18.   })
  19.   return results
  20. }

结果中，results的每一项对于每一个源数据项的结果，matches对于字符串的数据来说只有一项，在搜索对象时，是每一个key对应的结果。computeScore计算其总分。

可以看到，结果是matches各个元素分数乘方之积。分数的取值范围是[0,1][0, 1]，后面的results.sort(sortFn)默认从小到大排序，key的weight越大，norm越大，分数越小，排名也越靠前。

ts
  1. import Config from './config'
  3. // Practical scoring function
  4. export default function computeScore(
  5.   results,
  6.   { ignoreFieldNorm = Config.ignoreFieldNorm }
  7. ) {
  8.   results.forEach((result) => {
  9.     let totalScore = 1
  11.     result.matches.forEach(({ key, norm, score }) => {
  12.       const weight = key ? key.weight : null
  14.       totalScore *= Math.pow(
  15.         score === 0 && weight ? Number.EPSILON : score,
  16.         (weight || 1) * (ignoreFieldNorm ? 1 : norm)
  17.       )
  18.     })
  20.     result.score = totalScore
  21.   })
  22. }

下面进入 Fuse.js 的核心部分，就是它的模糊匹配。

🗜创建搜索器

回到_searchStringList方法，可以看到创建了一个搜索器createSearcher，然后把每项索引扔进去计算分值：

ts
  1. _searchStringList(query) {
  2.   const searcher = createSearcher(query, this.options)
  3.   const { records } = this._myIndex
  4.   const results = []
  5.   // Iterate over every string in the index
  6.   records.forEach(({ v: text, i: idx, n: norm }) => {
  7.     if (!isDefined(text)) {
  8.       return
  9.     }
  10.     const { isMatch, score, indices } = searcher.searchIn(text)
  11.     if (isMatch) {
  12.       results.push({
  13.         item: text,
  14.         idx,
  15.         matches: [{ score, value: text, norm, indices }]
  16.       })
  17.     }
  18.   })
  19.   return results
  20. }

在createSearcher，它会根据搜索的模式串创建一个BitapSearch并缓存起来：

ts
  1. import { BitapSearch } from '../search'
  3. const registeredSearchers = []
  5. export default function register(...args) {
  6.   registeredSearchers.push(...args)
  7. }
  9. export function createSearcher(pattern, options) {
  10.   for (let i = 0, len = registeredSearchers.length; i < len; i += 1) {
  11.     let searcherClass = registeredSearchers[i]
  12.     if (searcherClass.condition(pattern, options)) {
  13.       return new searcherClass(pattern, options)
  14.     }
  15.   }
  16.   return new BitapSearch(pattern, options)
  17. }

✒用二进制掩码记录目标串字符

Bitap 算法会把模式串转化为二进制掩码，利用位运算来快速计算模式串和目标串之间的相似度。来看BitapSearch的构造函数：

ts
  1. export default class BitapSearch {
  2.   constructor(/* ... */) {
  3.     // ...
  4.     this.chunks = []
  5.     if (!this.pattern.length) {
  6.       return
  7.     }
  8.     const addChunk = (pattern, startIndex) => {
  9.       this.chunks.push({
  10.         pattern,
  11.         alphabet: createPatternAlphabet(pattern),
  12.         startIndex
  13.       })
  14.     }
  15.     const len = this.pattern.length
  16.     // const MAX_BITS = 32
  17.     if (len > MAX_BITS) {
  18.       let i = 0
  19.       const remainder = len % MAX_BITS
  20.       const end = len - remainder
  21.       while (i < end) {
  22.         addChunk(this.pattern.substr(i, MAX_BITS), i)
  23.         i += MAX_BITS
  24.       }
  25.       if (remainder) {
  26.         const startIndex = len - MAX_BITS
  27.         addChunk(this.pattern.substr(startIndex), startIndex)
  28.       }
  29.     } else {
  30.       addChunk(this.pattern, 0)
  31.     }
  32.   }
  33. }

在构造函数中，BitapSearch按照 31 的长度为一节对模式串进行切分，用二进制掩码每一个字符的位置。

ts
  1. function createPatternAlphabet(pattern) {
  2.   var mask = {};
  3.   for (var i = 0, len = pattern.length; i < len; i += 1) {
  4.     var _char = pattern.charAt(i);
  5.     mask[_char] = (mask[_char] || 0) | 1 << len - i - 1;
  6.   }
  7.   return mask;
  8. }

例如：abc，a 记录为 100，b 就是 010， c 就是 001。

至于为什么是 31 的长度，大概是因为 JS 二进制运算使用 32 位的二进制整数吧。另外，Bitap 算法中也是使用 31 位的二进制记录字符位置的。

🔍匹配入口

回到_searchStringList，serachIn方法用来进行字符串匹配。

ts
  1. _searchStringList(query) {
  2.   const searcher = createSearcher(query, this.options)
  3.   const { records } = this._myIndex
  4.   const results = []
  5.   records.forEach(({ v: text, i: idx, n: norm }) => {
  6.     // ...
  7.     const { isMatch, score, indices } = searcher.searchIn(text)
  8.     // ...
  9.   })
  10.   return results
  11. }

searchIn遇到完全匹配直接返回：

ts
  1. searchIn(text) {
  2.   const { isCaseSensitive, includeMatches } = this.options
  3.   if (!isCaseSensitive) {
  4.     text = text.toLowerCase()
  5.   }
  6.   // Exact match
  7.   if (this.pattern === text) {
  8.     let result = {
  9.       isMatch: true,
  10.       score: 0
  11.     }
  12.     if (includeMatches) {
  13.       result.indices = [[0, text.length - 1]]
  14.     }
  15.     return result
  16.   }
  17.   // ... Bitap
  18. }

如果模式串this.pattern和目标串text相等，则记分值为 0，也就是完全匹配，结束逻辑。否则进入 Bitap 模糊匹配的逻辑。

后面是 Bitap 的逻辑，这里用this.chunks中每一个模式串分块的掩码和目标串进行匹配，最后分数取每一分块分数的平均值。这里有几个值得注意的变量，后面会用到。

  • location：预期匹配子串出现的位置；
  • distance：影响匹配的子串与期望位置偏离对分数的影响，越大，偏离对分数影响越小；ignoreLocation可以使得分数计算忽略距离因素，如果你想搜索超长的文本，这大概会有用吧。
  • threshold：分数阈值，分数大于此值会被视为不匹配。

这些变量的值都是可以在new Fuse()的时候配置的，具体看Fuse.js 的文档。

ts
  1. searchIn(text) {
  2.   // ...
  3.   
  4.   let totalScore = 0
  5.   let hasMatches = false
  6.   this.chunks.forEach(({ pattern, alphabet, startIndex }) => {
  7.     const { isMatch, score, indices } = search(text, pattern, alphabet, {
  8.       location: location + startIndex,
  9.       distance,
  10.       threshold,
  11.       findAllMatches,
  12.       minMatchCharLength,
  13.       includeMatches,
  14.       ignoreLocation
  15.     })
  16.     if (isMatch) {
  17.       hasMatches = true
  18.     }
  19.     totalScore += score
  20.     // ...
  21.   })
  22.   let result = {
  23.     isMatch: hasMatches,
  24.     score: hasMatches ? totalScore / this.chunks.length : 1
  25.   }
  26.   if (hasMatches && includeMatches) {
  27.     result.indices = allIndices
  28.   }
  29.   return result
  30. }

📘小结

下面进一步介绍算法，这里先小结一下。Fuse 进行模糊匹配的总体流程是，先根据传入的数据源对每一项数据进行索引创建，搜索的时候，输入模式串，根据索引使用 Bitap 算法计算出每一项数据的得分，经过处理后返回允许的匹配度下符合匹配的数据。

graph LR
    D("search")-->E("searcher = new BitapSearch")-->|用二进制掩码记录目标串|H(addChunk)
    D-->F("searcher.searchIn")-->|完全匹配|I("return { isMatch: true, score: 0 }")
    F-->|Bitap 算法|G(search)

💻基于 Bitap 的模糊匹配

下面来看模糊匹配算法的实现，也是 Fuse.js 的核心。文件位置在 src/search/bitap/search.js，这里进行分段地解析。下面定义了一些变量，用到的时候下面再说，先可以不用关注它们：

ts
  1. export default function search(
  2.   text,
  3.   pattern,
  4.   patternAlphabet,
  5.   {
  6.     location = Config.location,
  7.     distance = Config.distance,
  8.     threshold = Config.threshold,
  9.     findAllMatches = Config.findAllMatches,
  10.     minMatchCharLength = Config.minMatchCharLength,
  11.     includeMatches = Config.includeMatches,
  12.     ignoreLocation = Config.ignoreLocation
  13.   } = {}
  14. ) {
  15.   if (pattern.length > MAX_BITS) {
  16.     throw new Error(ErrorMsg.PATTERN_LENGTH_TOO_LARGE(MAX_BITS))
  17.   }
  19.   const patternLen = pattern.length
  20.   // Set starting location at beginning text and initialize the alphabet.
  21.   const textLen = text.length
  22.   // Handle the case when location > text.length
  23.   const expectedLocation = Math.max(0, Math.min(location, textLen))
  24.   // Highest score beyond which we give up.
  25.   let currentThreshold = threshold
  26.   // Is there a nearby exact match? (speedup)
  27.   let bestLocation = expectedLocation
  29.   // Performance: only computer matches when the minMatchCharLength > 1
  30.   // OR if `includeMatches` is true.
  31.   const computeMatches = minMatchCharLength > 1 || includeMatches
  32.   // A mask of the matches, used for building the indices
  33.   const matchMask = computeMatches ? Array(textLen) : []
  34.   // ...
  35. }

🧮计算分数

先来看看每个目标串和模式串匹配得分是怎么计算的。得分主要受 Bitap 算法中的错误（匹配子串和模式串的编辑距离）和与预期位置的偏离影响。简单的来说，也就是：

errorspattern.length+abs(expectedLocation−currentLocation)distance\frac{errors}{pattern.length} + \frac{\text{abs}(expectedLocation - currentLocation)}{distance}

错误越多、离预期位置越远分数越高，搜索结果排名越靠后，或者被排除出搜索结果。

ts
  1. export default function computeScore(
  2.   pattern,
  3.   {
  4.     errors = 0,
  5.     currentLocation = 0,
  6.     expectedLocation = 0,
  7.     distance = Config.distance,
  8.     ignoreLocation = Config.ignoreLocation
  9.   } = {}
  10. ) {
  11.   const accuracy = errors / pattern.length
  12.   if (ignoreLocation) {
  13.     return accuracy
  14.   }
  15.   const proximity = Math.abs(expectedLocation - currentLocation)
  17.   if (!distance) {
  18.     // Dodge divide by zero error.
  19.     return proximity ? 1.0 : accuracy
  20.   }
  21.   return accuracy + proximity / distance
  22. }

🔦记录匹配分数下限

注意到currentThreshold的初始值是Config.threshold，在这里的作用是记录当前最小得分，如果说后面不可能比这个分数更小了，就退出。

类似地，expectedLocation也会根据当前最佳的匹配，更新位置。

先检测目标串text中是否包含模式串pattern，用于更新currentThreshold，后续减少运算。

ts
  1. // ...
  2. let index
  3. // Get all exact matches, here for speed up
  4. while ((index = text.indexOf(pattern, bestLocation)) > -1) {
  5.   let score = computeScore(pattern, {
  6.     currentLocation: index,
  7.     expectedLocation,
  8.     distance,
  9.     ignoreLocation
  10.   })
  11.   currentThreshold = Math.min(score, currentThreshold)
  12.   bestLocation = index + patternLen
  13.   // ...
  14. }
  15. // ...

📚模糊匹配

下面进入模糊匹配环节，它有两个循环，外层是允许的错误数，内层遍历目标串text。这里使用动态规划算法，状态记录在bitArr和lastBitArr中，分别表示当前和上次允许错误数的结果，finalScore记录最优的分数。在bitArr每一项都是二进制，每一位j表示在当前允许错误数下text.slice(j, j + patternLen)和pattern是否已成功匹配。

ts
  1. // Reset the best location
  2. bestLocation = -1
  4. let lastBitArr = []
  5. let finalScore = 1
  6. let binMax = patternLen + textLen
  8. const mask = 1 << (patternLen - 1)
  10. for (let i = 0; i < patternLen; i += 1) {
  11.   // ...
  12. }

🔎搜索匹配范围

下面进入外层循环，先根据bestLocation和currentThreshold计算出需要检索目标串的范围，也就是离bestLocation多远的地方分数不会大于currentThreshold。很明显这就是二分搜索。

ts
  1. for (let i = 0; i < patternLen; i += 1) {
  2.   // Scan for the best match; each iteration allows for one more error.
  3.   // Run a binary search to determine how far from the match location we can stray
  4.   // at this error level.
  5.   let binMin = 0
  6.   let binMid = binMax
  8.   while (binMin < binMid) {
  9.     const score = computeScore(pattern, {
  10.       errors: i,
  11.       currentLocation: expectedLocation + binMid,
  12.       expectedLocation,
  13.       distance,
  14.       ignoreLocation
  15.     })
  16.     if (score <= currentThreshold) {
  17.       binMin = binMid
  18.     } else {
  19.       binMax = binMid
  20.     }
  21.     binMid = Math.floor((binMax - binMin) / 2 + binMin)
  22.   }
  24.   // Use the result from this iteration as the maximum for the next.
  25.   binMax = binMid
  27.   let start = Math.max(1, expectedLocation - binMid + 1)
  28.   let finish = findAllMatches
  29.     ? textLen
  30.     : Math.min(expectedLocation + binMid, textLen) + patternLen
  31.   
  32.   // ...
  33. }

搜索的左端点自然是expectedLocation - binMid + 1，右端点一般情况下是expectedLocation + binMid加上模式串长度patternLen，其实这里考虑的是在text末尾，在允许的错误下匹配了模式串pattern的情况。

这里有点没看懂：findAllMatches可以在创建Fuse时配置，为true表示：即使已经在字符串中找到了一个完全匹配，匹配函数会在字符串中继续执行，直到搜索模式的末尾。看起来像是考虑匹配text全文，但是这里没太看懂，有几个疑问，textLen为什么看起来是可能小于Math.min(expectedLocation + binMid, textLen) + patternLen，而且为什么它对start为什么没有影响。

⭕进行匹配

初始化状态后，从后往前开始匹配：

ts
  1. for (let i = 0; i < patternLen; i += 1) {
  2.   // ...
  3.   let bitArr = Array(finish + 2)
  4.   bitArr[finish + 1] = (1 << i) - 1
  5.   for (let j = finish; j >= start; j -= 1) {
  6.     let currentLocation = j - 1
  7.     let charMatch = patternAlphabet[text.charAt(currentLocation)]
  8.     // ...
  9.     
  10.     // First pass: exact match
  11.     bitArr[j] = ((bitArr[j + 1] << 1) | 1) & charMatch
  12.     // Subsequent passes: fuzzy match
  13.     if (i) {
  14.       bitArr[j] |=
  15.         ((lastBitArr[j + 1] | lastBitArr[j]) << 1) | 1 | lastBitArr[j + 1]
  16.     }
  17.     if (bitArr[j] & mask) {
  18.       // 匹配完成...
  19.     }
  20.     // ...
  21.   }
  22. }

遍历匹配串时，每一步倒序加入目标串一个字符，这里用j记录循环变量，从finish递减到 1。

通过charMatch = patternAlphabet[text.charAt(j - 1)]获取当前目标串text的字符在模式串中的位置，通过((bitArr[j + 1] << 1) | 1) & charMatch记录当前位置是否与模式串匹配。举个栗子🌰：

如果目标串是'test'，模式串是tEst，patternAlphabet大概长这个样子：{ t: 1001, s: 10, E: 100 }。假设finish是 8，允许错误数i为 0，匹配情况如下所示：

j text.charAt(j - 1) charMatch bitArr[j + 1] bitArr[j]
8 undefined undefined 0 0
7 undefined undefined 0 0
6 undefined undefined 0 0
5 undefined undefined 0 0
4 ‘t’ 1001 0 1
3 ‘s’ 10 1 10
2 ‘e’ undefined 10 0
1 ‘t’ 1001 0 1

可以发现，如果上面匹配成功，最终bitArr[1]就是1000，也就是说bitArr[j] & (1 << (patternLen - 1))为真时，匹配成功。

我们看i > 1的情况，如果上次匹配当前位置离完全匹配就差 1 个编辑距离，那自然是匹配成功的。

Fuse.js 用lastBitArr[j] << 1 | 1、lastBitArr[j + 1] | 1、lastBitArr[j + 1]分别表示上次匹配的子串增加、替换、删除 1 个末尾的字符后，匹配的情况，总之合起来就是((lastBitArr[j + 1] | lastBitArr[j]) << 1) | 1 | lastBitArr[j + 1]。

到这里状态转移的过程大致描述清楚了，具体代码如下所示：

ts
  1. for (let i = 0; i < patternLen; i += 1) {
  2.   // ...
  3.   
  4.   // Initialize the bit array
  5.   let bitArr = Array(finish + 2)
  6.   bitArr[finish + 1] = (1 << i) - 1
  8.   for (let j = finish; j >= start; j -= 1) {
  9.     let currentLocation = j - 1
  10.     let charMatch = patternAlphabet[text.charAt(currentLocation)]
  11.     // ...
  13.     // First pass: exact match
  14.     bitArr[j] = ((bitArr[j + 1] << 1) | 1) & charMatch
  16.     // Subsequent passes: fuzzy match
  17.     if (i) {
  18.       bitArr[j] |=
  19.         ((lastBitArr[j + 1] | lastBitArr[j]) << 1) | 1 | lastBitArr[j + 1]
  20.     }
  21.     if (bitArr[j] & mask) {
  22.       finalScore = computeScore(pattern, {
  23.         errors: i,
  24.         currentLocation,
  25.         expectedLocation,
  26.         distance,
  27.         ignoreLocation
  28.       })
  30.       // This match will almost certainly be better than any existing match.
  31.       // But check anyway.
  32.       if (finalScore <= currentThreshold) {
  33.         // Indeed it is
  34.         currentThreshold = finalScore
  35.       
  36.         bestLocation = currentLocation
  38.         // Already passed `loc`, downhill from here on in.
  39.         if (bestLocation <= expectedLocation) {
  40.           break
  41.         }
  43.         // When passing `bestLocation`, don't exceed our current distance from `expectedLocation`.
  44.         start = Math.max(1, 2 * expectedLocation - bestLocation)
  45.       }
  46.     }
  47.   }
  49.   // ...
  50.   lastBitArr = bitArr
  51. }

🆗后续处理

然后计算下次循环分数的最小值，如果高于阈值则退出

ts
  1. for (let i = 0; i < patternLen; i += 1) {
  2.   // ...
  3.   // No hope for a (better) match at greater error levels.
  4.   const score = computeScore(pattern, {
  5.     errors: i + 1,
  6.     currentLocation: expectedLocation,
  7.     expectedLocation,
  8.     distance,
  9.     ignoreLocation
  10.   })
  12.   if (score > currentThreshold) {
  13.     break
  14.   }
  15.   // ...
  16. }

返回匹配结果

ts
  1. export default function search(/* ... */) {
  2.   // ...
  3.   const result = {
  4.     isMatch: bestLocation >= 0,
  5.     // Count exact matches (those with a score of 0) to be "almost" exact
  6.     score: Math.max(0.001, finalScore)
  7.   }
  8.   // ...
  9.   return result
  10. }

✔结语

到这里，Fuse.js 的源码大致解读完了。当然例如key分值的计算，对复杂数据项的处理还没有涉及到，可能后续更新一下，欢迎催更。总之我们对 Fuse.js 的工作原理和实现细节有了大致的理解。Fuse.js 通过其高效的索引机制和 Bitap 算法，提供了一种既快速又准确的模糊搜索解决方案。在前端长列表搜索等场景非常有用，作为一个轻量级无依赖的第三方库，在服务端小型项目也有用武之地。

上一篇：Nest 源码解析：依赖注入是怎么实现的？
下一篇：npm link 配合 Vite 插件监听 node_modules，丝滑调试 JS 库
0 条评论未登录用户
Ctrl or + Enter 评论
粤ICP备2023133136号
🌸 Run