Fuse.js中的Bitap算法源码分析 - 开源项目

前几天分享了开源的Fuse.js开源模糊搜索工具，其中介绍到了其主要的算法是对Bitap算法的修改实现，那今天就来分析下其源码中的实现。

温馨提示文章有点长。

Bitap算法

简介

bitap算法（也称为shift-or、shift-and或Baeza-Yates-Gonnet算法）是一种近似字符串匹配算法。该算法判断给定文本是否包含与给定模式“近似相等”的子字符串，其中近似相等是根据Levenshtein距离定义的 - 如果子字符串和模式彼此之间的距离在给定的k以内，则算法认为它们相等。该算法首先预先计算一组位掩码，其中包含模式的每个元素的一个位。然后它能够使用速度极快的 按位运算完成大部分工作。

简易注释：
近似字符串匹配算法： 在计算机科学中，近似字符串匹配（通常俗称模糊字符串搜索）是 一种查找与模式近似匹配（而非精确匹配）的字符串的技术。近似字符串匹配问题通常分为两个子问题：在给定字符串中查找近似子字符串匹配和查找与模式近似匹配的字典字符串。

Levenshtein距离： 两个字符串之间的Levenshtein距离，是度量它们之间差异的一种字符串度量，也被称为编辑距离。

位掩码： 是”位（Bit）“和”掩码（Mask）“的组合词。”位“指代着二进制数据当中的二进制位，而”掩码“指的是一串用于与目标数据进行按位操作的二进制数字。组合起来，就是”用一串二进制数字（掩码）去操作另一串二进制数字“的意思。

其中关于位掩码如果不太了解的同学，强烈建议阅读这篇文章。奇怪的知识——位掩码。

基本思想

Bitap 算法通过使用位操作来进行模式匹配，核心思想是将模式转换为一系列的位掩码，然后在文本中滑动这些掩码以查找匹配的位置。该算法的时间复杂度是 O(mn)，其中 m 是模式的长度，n 是文本的长度。

算法步骤

Bitap 算法的主要步骤

  • 初始化位掩码：为每个字符生成一个位掩码，表示该字符在模式中出现的位置。
  • 处理文本：逐个字符地处理文本，更新位掩码并检查匹配位置。
  • 允许错误：在处理时考虑一定数量的错误，并根据错误类型（插入、删除、替换）更新位掩码。
  • 返回结果：返回匹配的位置。

Fuse.js中的Bitap算法实现

BitapSearch类中包含两部分，分别为构造器和searchIn函数。

BitapSearch构造器函数

在Fuse.js对此算法的实现主要在src/search/bitap/index.js这个目录的入口文件下，构造并暴露了BitapSearch类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import search from './search'
import createPatternAlphabet from './createPatternAlphabet'
import { MAX_BITS } from './constants'
import Config from '../../core/config'

export default class BitapSearch {
  constructor(
    pattern,
    {
      location = Config.location,
      threshold = Config.threshold,
      distance = Config.distance,
      includeMatches = Config.includeMatches,
      findAllMatches = Config.findAllMatches,
      minMatchCharLength = Config.minMatchCharLength,
      isCaseSensitive = Config.isCaseSensitive,
      ignoreLocation = Config.ignoreLocation
    } = {}
  ) {
    this.options = {
      location,
      threshold,
      distance,
      includeMatches,
      findAllMatches,
      minMatchCharLength,
      isCaseSensitive,
      ignoreLocation
    }

    this.pattern = isCaseSensitive ? pattern : pattern.toLowerCase()

    this.chunks = []

    if (!this.pattern.length) {
      return
    }

    const addChunk = (pattern, startIndex) => {
      this.chunks.push({
        pattern,
        alphabet: createPatternAlphabet(pattern),
        startIndex
      })
    }

    const len = this.pattern.length

    if (len > MAX_BITS) {
      let i = 0
      const remainder = len % MAX_BITS
      const end = len - remainder

      while (i < end) {
        addChunk(this.pattern.substr(i, MAX_BITS), i)
        i += MAX_BITS
      }

      if (remainder) {
        const startIndex = len - MAX_BITS
        addChunk(this.pattern.substr(startIndex), startIndex)
      }
    } else {
      addChunk(this.pattern, 0)
    }
  }

  searchIn(text) {
    const { isCaseSensitive, includeMatches } = this.options

    if (!isCaseSensitive) {
      text = text.toLowerCase()
    }

    // Exact match
    if (this.pattern === text) {
      let result = {
        isMatch: true,
        score: 0
      }

      if (includeMatches) {
        result.indices = [[0, text.length - 1]]
      }

      return result
    }

    // Otherwise, use Bitap algorithm
    const {
      location,
      distance,
      threshold,
      findAllMatches,
      minMatchCharLength,
      ignoreLocation
    } = this.options

    let allIndices = []
    let totalScore = 0
    let hasMatches = false

    this.chunks.forEach(({ pattern, alphabet, startIndex }) => {
      const { isMatch, score, indices } = search(text, pattern, alphabet, {
        location: location + startIndex,
        distance,
        threshold,
        findAllMatches,
        minMatchCharLength,
        includeMatches,
        ignoreLocation
      })

      if (isMatch) {
        hasMatches = true
      }

      totalScore += score

      if (isMatch && indices) {
        allIndices = [...allIndices, ...indices]
      }
    })

    let result = {
      isMatch: hasMatches,
      score: hasMatches ? totalScore / this.chunks.length : 1
    }

    if (hasMatches && includeMatches) {
      result.indices = allIndices
    }

    return result
  }
}

以上是完整代码，接下来我们逐块分析，首先看BitapSearch类的构造器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
export default class BitapSearch {
    //构造器的参数主要是读取对应的配置信息，如果未传入则使用Config定义好的默认值
    constructor(
        pattern, //要匹配的字符信息
        {
            location = Config.location, //配置项 确定文本中预期找到模式的大致位置。
            threshold = Config.threshold, //配置项 匹配算法在什么时候放弃。阈值为0.0需要完全匹配（字母和位置都匹配），阈值为1.0可以匹配任何内容。
            distance = Config.distance, //配置项 确定匹配必须与模糊位置(由位置指定)的接近程度。精确的字母匹配，即距离模糊位置的字符将被视为完全不匹配。距离为0要求匹配在指定的确切位置。如果距离为1000，则需要使用0.8的阈值在要找到的位置的800个字符内找到完美匹配
            includeMatches = Config.includeMatches, //配置项 是否应该将匹配项包含在结果集中。当为true时，结果集中的每个记录将包含匹配字符的索引。因此，它们可以用于突出显示目的。
            findAllMatches = Config.findAllMatches, //配置项 当为true时，匹配函数将继续到搜索模式的末尾，即使已经在字符串中找到了完全匹配。
            minMatchCharLength = Config.minMatchCharLength, //配置项 只返回长度超过此值的匹配项。(例如，如果您想忽略结果中的单个字符匹配，请将其设置为2)。
            isCaseSensitive = Config.isCaseSensitive, //配置项 是否区分搜索内容的大小写
            ignoreLocation = Config.ignoreLocation //配置项 当为true时，搜索将忽略位置和距离，因此模式出现在字符串的哪个位置并不重要
        } = {}
    ) {
        this.options = {
            location,
            threshold,
            distance,
            includeMatches,
            findAllMatches,
            minMatchCharLength,
            isCaseSensitive,
            ignoreLocation
        }

        this.pattern = isCaseSensitive ? pattern : pattern.toLowerCase()

        this.chunks = []

        if (!this.pattern.length) {
            return
        }

        const addChunk = (pattern, startIndex) => {
            this.chunks.push({
                pattern,
                alphabet: createPatternAlphabet(pattern),
                startIndex
            })
        }

        const len = this.pattern.length

        if (len > MAX_BITS) {
            let i = 0
            const remainder = len % MAX_BITS
            const end = len - remainder

            while (i < end) {
                addChunk(this.pattern.substr(i, MAX_BITS), i)
                i += MAX_BITS
            }

            if (remainder) {
                const startIndex = len - MAX_BITS
                addChunk(this.pattern.substr(startIndex), startIndex)
            }
        } else {
            addChunk(this.pattern, 0)
        }
    }
}

在addChunk函数中调用了createPatternAlphabet函数如下：

1
2
3
4
5
6
7
8
9
10
11
export default function createPatternAlphabet(pattern) {
  let mask = {}

  for (let i = 0, len = pattern.length; i < len; i += 1) {
    const char = pattern.charAt(i)
    mask[char] = (mask[char] || 0) | (1 << (len - i - 1))
  }

  return mask
}

此函数的作用是会返回一个个对象 mask，对象的key是需要匹配字符串中的字符，value是一个二进制数，表示该字符在模式字符串中的位置。生成一个类似字典的对象，用于计算某个字符在目标字符串中出现的位置。

我们来验证一下此函数,当我们参数输入vapausQiBlog时，返回的对象结果时这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    v: 2048,
    a: 1280,
    p: 512,
    u: 128,
    s: 64,
    Q: 32,
    i: 16,
    B: 8,
    l: 4,
    o: 2,
    g: 1
}

这样看起来可能不是很直观，接下来我们将其转换成同长度的二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    v: "100000000000",  // 2048
    a: "010100000000",  // 1280
    p: "001000000000",  // 512
    u: "000001000000",  // 128
    s: "000000100000",  // 64
    Q: "000000010000",  // 32
    i: "000000001000",  // 16
    B: "000000000100",  // 8
    l: "000000000010",  // 4
    o: "000000000001",  // 2
    g: "0000000000001"  // 1
}

其中数值为1的位置，对应的就是输入参数字符的所在位置。

实际调用及代码释义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//首先，初始化一个空数组 this.chunks，用于存储分割后的模式块。如果模式字符串为空，则直接返回。
this.chunks = []

if (!this.pattern.length) {
    return
}
//定义一个内部函数 addChunk，它接收一个模式块 pattern 和它在原始模式字符串中的起始索引 startIndex。这个函数会将模式块、其对应的字符掩码表（由 createPatternAlphabet 生成）以及起始索引添加到 this.chunks 数组中。
const addChunk = (pattern, startIndex) => {
    this.chunks.push({
        pattern,
        alphabet: createPatternAlphabet(pattern),
        startIndex
    })
}
//获取模式字符串的长度
const len = this.pattern.length

//如果模式字符串的长度 len 大于 MAX_BITS，则进行以下操作1、初始化变量 2、分割模式字符串
if (len > MAX_BITS) {
    let i = 0
    const remainder = len % MAX_BITS
    const end = len - remainder

    while (i < end) {
        addChunk(this.pattern.substr(i, MAX_BITS), i)
        i += MAX_BITS
    }

    if (remainder) {
        const startIndex = len - MAX_BITS
        addChunk(this.pattern.substr(startIndex), startIndex)
    }
} 
//如果模式字符串的长度小于或等于 MAX_BITS，则直接调用 addChunk 函数，将整个模式字符串作为一个块添加到 this.chunks 中。
else {
    addChunk(this.pattern, 0)
}

这段代码主要是将一个较长的模式字符串 this.pattern 分割成多个较小的块，并为每个块生成一个字符掩码表。这是为了在Bitap算法中处理较长模式字符串时，避免超出处理位数的限制（MAX_BITS源码里面设置为 32）。

searchIn函数

searchIn方法中，调用了search函数。search函数接收的参数为text目标字符串，以及pattern模式串和opions参数配置项。

在search函数中又回调用computeScore函数来获取评分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
export default function computeScore(
    pattern,
    {
        errors = 0,
        currentLocation = 0,
        expectedLocation = 0,
        distance = Config.distance,
        ignoreLocation = Config.ignoreLocation
    } = {}
) {
    //错误数量与模式长度的比率。错误越多，精度越低
    const accuracy = errors / pattern.length
    //如果 ignoreLocation 为 true，只返回 accuracy，不考虑位置。
    if (ignoreLocation) {
        return accuracy
    }
    //当前匹配位置与预期匹配位置之间的绝对距离。
    const proximity = Math.abs(expectedLocation - currentLocation)

    if (!distance) {
        // Dodge divide by zero error.
        return proximity ? 1.0 : accuracy
    }
    //如果不忽略位置，返回 accuracy 加上 proximity 除以 distance 的结果。这个结果综合考虑了匹配的精度和位置的接近度。
    return accuracy + proximity / distance
}

这个函数的主要作用是根据模式匹配的精度和位置接近度计算一个得分，用于评估模式在文本中的匹配质量。分数越低，代表越匹配。

回到search方法中第一次调用此函数的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  let index

// Get all exact matches, here for speed up
while ((index = text.indexOf(pattern, bestLocation)) > -1) {
    let score = computeScore(pattern, {
        currentLocation: index,
        expectedLocation,
        distance,
        ignoreLocation
    })

    currentThreshold = Math.min(score, currentThreshold)
    bestLocation = index + patternLen

    if (computeMatches) {
        let i = 0
        while (i < patternLen) {
            matchMask[index + i] = 1
            i += 1
        }
    }
}

// Reset the best location
bestLocation = -1

这段代码主要是在文本 text 中查找模式 pattern 的所有精确匹配位置。 对每个匹配位置，计算匹配得分，并更新当前最小匹配阈值 currentThreshold 和最佳匹配位置bestLocation。 如果启用了匹配掩码 computeMatches，更新匹配掩码matchMask ，记录匹配位置。

在此之后，初始化几个变量的值，并计算出mask掩码的值。

  • bestLocation：初始化为 -1，表示尚未找到最佳匹配位置。
  • lastBitArr：用于保存上一轮的位数组。
  • finalScore：初始化为 1，表示最终的匹配得分（越低越好，初始化为1代表不匹配）。
  • binMax：初始化为模式长度和文本长度之和，用于二分搜索的最大边界。
  • mask：创建一个掩码，用于检查匹配。
1
2
3
4
5
6
7
bestLocation = -1

let lastBitArr = []
let finalScore = 1
let binMax = patternLen + textLen

const mask = 1 << (patternLen - 1)

接下来对模式的字符串做循环处理，并且每循环一次增加一次误差处理（computeScore计算得分的方法中的errors匹配这里面的i）

1
for (let i = 0; i < patternLen; i += 1) {}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let binMin = 0
let binMid = binMax  
while (binMin < binMid) {
  const score = computeScore(pattern, {
    errors: i,
    currentLocation: expectedLocation + binMid,
    expectedLocation,
    distance,
    ignoreLocation
  })

  if (score <= currentThreshold) {
    binMin = binMid
  } else {
    binMax = binMid
  }

  binMid = Math.floor((binMax - binMin) / 2 + binMin)
}

使用二分搜索确定当前误差级别下可以偏移的最大距离。
computeScore 方法计算当前偏移位置的匹配得分，并根据得分调整 binMin 和 binMax，最终确定 binMid。
一直循环搜索，直到找到最佳匹配或者搜索范围缩小到为空为止（score <= currentThreshold）。

1
2
3
4
let start = Math.max(1, expectedLocation - binMid + 1)
let finish = findAllMatches
  ? textLen
  : Math.min(expectedLocation + binMid, textLen) + patternLen

计算起始位置：
start：计算当前误差级别下的起始位置。
finish：计算结束位置。如果 findAllMatches 为 true，则设置为文本长度；否则，设置为当前误差级别允许的最大位置。

1
2
let bitArr = Array(finish + 2)
bitArr[finish + 1] = (1 << i) - 1

初始化位数组 bitArr，用于保存当前轮匹配结果。
bitArr[finish + 1] 设置为 (1 << i) - 1，用于辅助匹配计算

说明：
1 << i： 将数字1向左移动i位，1 << i将产生一个具有i个零尾随的二进制数。

  • i = 0，则 1 << 0 结果是 1 (二进制: 0001)
  • i = 1，则 1 << 1 结果是 2 (二进制: 0010）

(1 << i) - 1： 将所有位都设置为 1，直到左移位数。

  • i = 0，则 (1 << 0) - 1 结果是 0 (二进制: 0000)
  • i = 1，则 (1 << 1) - 1 结果是 1 (二进制: 0001)
1
2
let currentLocation = j - 1
let charMatch = patternAlphabet[text.charAt(currentLocation)]

let currentLocation = j - 1: 将j减去1 得到当前字符在文本中的位置

let charMatch = patternAlphabet[text.charAt(currentLocation)]: 从 patternAlphabet 中获取 text 中 currentLocation 位置的字符的匹配掩码。patternAlphabet 是一个映射对象，将字符映射到对应的掩码值。

1
2
3
4
5
if (computeMatches) {
  matchMask[currentLocation] = +!!charMatch
}

bitArr[j] = ((bitArr[j + 1] << 1) | 1) & charMatch

用computeMatches: 检查是否需要计算匹配，computeMatches是基于 minMatchCharLength 或 includeMatches 的配置（const computeMatches = minMatchCharLength > 1 || includeMatches）。

bitArr[j] = ((bitArr[j + 1] << 1) | 1) & charMatch:

  • bitArr[j + 1] << 1: 将 bitArr[j + 1] 左移一位，这在位运算中相当于将所有位向左移动一位，末尾补 0。
  • | 1: 将结果的最低位设置为 1，这是为了标记当前位置的匹配。
  • & charMatch: 将上面得到的值与 charMatch 进行按位与运算，确保只有在字符匹配的位上才会保持 1。

在每次循环中：

第一次循环（i = 0）：处理精确匹配，不允许任何错误。

后续循环（i > 0）：允许 i 次错误，使用位运算合并错误匹配状态。

通过这种方式，能够在文本和模式中允许一定数量的错误，进行模糊匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (bitArr[j] & mask) {
  finalScore = computeScore(pattern, { //...一些参数，这里省略  })

  // This match will almost certainly be better than any existing match.
  // But check anyway.
  if (finalScore <= currentThreshold) {
    // Indeed it is
    currentThreshold = finalScore
    bestLocation = currentLocation

    // Already passed `loc`, downhill from here on in.
    if (bestLocation <= expectedLocation) {
      break
    }

    // When passing `bestLocation`, don't exceed our current distance from `expectedLocation`.
    start = Math.max(1, 2 * expectedLocation - bestLocation)
  }
}

如果位置匹配成功，接下来计算当前位置的得分 finalScore。

如果得分小或等于当前阈值 ，说明目前已经获取了最优的结果匹配，更新阈值和最优匹配位置。

如果最优匹配位置 bestLocation 小于等于期望位置 expectedLocation，说明已经找到了期望位置的最优匹配，跳出循环；

否则更新搜索起点 start的位置保证在向左搜索时不超过当前距离期望位置的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// No hope for a (better) match at greater error levels.
const score = computeScore(pattern, {
  errors: i + 1,
  currentLocation: expectedLocation,
  expectedLocation,
  distance,
  ignoreLocation
})

if (score > currentThreshold) {
  break
}

lastBitArr = bitArr

  • 这里计算下一个错误级别（errors: i + 1）的匹配得分。
  • 调用 computeScore 函数，传递模式、当前位置和预期位置、允许的最大距离以及是否忽略位置的标志。
  • computeScore 函数会根据当前的误差数量和其他参数来计算得分，得分越低越好。

理解：

计算下一个错误级别的得分是为了提前判断在当前错误级别的基础上增加一个错误是否还有希望找到更好的匹配。如果在增加一个错误后得分已经超过了当前阈值 currentThreshold，就可以提前终止搜索，避免无谓的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const result = {
  isMatch: bestLocation >= 0,
  // Count exact matches (those with a score of 0) to be "almost" exact
  score: Math.max(0.001, finalScore)
}

if (computeMatches) {
  const indices = convertMaskToIndices(matchMask, minMatchCharLength)
  if (!indices.length) {
    result.isMatch = false
  } else if (includeMatches) {
    result.indices = indices
  }
}

然后就是构建需要返回结果的result对象。

  • isMatch： 是否找到匹配位置
  • score： 设置匹配的得分 score，表示匹配的好坏程度
  • indices： 匹配的索引数组 通过convertMaskToIndices函数匹配掩码进行转换

最后在BitapSearch类中的searchIn方法解构 search返回的result数据，并通过配置项计算处理返回最终数据。

总结

简单将Fuse的内部搜索实现的代码做了一次粗略的阅读分析，文章较长，可能存在部分小错误在编写的时候没有发现，如有发现请指正，万分感谢。