#482

pending completion

Build # #482

Build Type

push

GitHub Actions

Committed by

web-flow

Commit Message

Pass stored fields to boostDocument callback (#213)

This makes it more convenient to perform dynamic boosting.

Run Details

211 of 216 branches covered (97.69%)

Branch coverage included in aggregate %.

1 of 1 new or added line in 1 file covered. (100.0%)

664 of 664 relevant lines covered (100.0%)

763.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/src/SearchableMap/fuzzySearch.ts

/* eslint-disable no-labels */
import { LEAF } from './TreeIterator'
import { RadixTree } from './types'

export type FuzzyResult<T> = [T, number]

export type FuzzyResults<T> = Map<string, FuzzyResult<T>>

/**
 * @ignore
 */
export const fuzzySearch = <T = any>(node: RadixTree<T>, query: string, maxDistance: number): FuzzyResults<T> => {
  const results: FuzzyResults<T> = new Map()
  if (query === undefined) return results

  // Number of columns in the Levenshtein matrix.
  const n = query.length + 1

  // Matching terms can never be longer than N + maxDistance.
  const m = n + maxDistance

  // Fill first matrix row and column with numbers: 0 1 2 3 ...
  const matrix = new Uint8Array(m * n).fill(maxDistance + 1)
  for (let j = 0; j < n; ++j) matrix[j] = j
  for (let i = 1; i < m; ++i) matrix[i * n] = i

  recurse(
    node,
    query,
    maxDistance,
    results,
    matrix,
    1,
    n,
    ''
  )

  return results
}

// Modified version of http://stevehanov.ca/blog/?id=114

// This builds a Levenshtein matrix for a given query and continuously updates
// it for nodes in the radix tree that fall within the given maximum edit
// distance. Keeping the same matrix around is beneficial especially for larger
// edit distances.
//
//           k   a   t   e   <-- query
//       0   1   2   3   4
//   c   1   1   2   3   4
//   a   2   2   1   2   3
//   t   3   3   2   1  [2]  <-- edit distance
//   ^
//   ^ term in radix tree, rows are added and removed as needed

const recurse = <T = any>(
  node: RadixTree<T>,
  query: string,
  maxDistance: number,
  results: FuzzyResults<T>,
  matrix: Uint8Array,
  m: number,
  n: number,
  prefix: string
): void => {
  const offset = m * n

  key: for (const key of node.keys()) {
    if (key === LEAF) {
      // We've reached a leaf node. Check if the edit distance acceptable and
      // store the result if it is.
      const distance = matrix[offset - 1]
      if (distance <= maxDistance) {
        results.set(prefix, [node.get(key)!, distance])
      }
    } else {
      // Iterate over all characters in the key. Update the Levenshtein matrix
      // and check if the minimum distance in the last row is still within the
      // maximum edit distance. If it is, we can recurse over all child nodes.
      let i = m
      for (let pos = 0; pos < key.length; ++pos, ++i) {
        const char = key[pos]
        const thisRowOffset = n * i
        const prevRowOffset = thisRowOffset - n

        // Set the first column based on the previous row, and initialize the
        // minimum distance in the current row.
        let minDistance = matrix[thisRowOffset]

        const jmin = Math.max(0, i - maxDistance - 1)
        const jmax = Math.min(n - 1, i + maxDistance)

        // Iterate over remaining columns (characters in the query).
        for (let j = jmin; j < jmax; ++j) {
          const different = char !== query[j]

          // It might make sense to only read the matrix positions used for
          // deletion/insertion if the characters are different. But we want to
          // avoid conditional reads for performance reasons.
          const rpl = matrix[prevRowOffset + j] + +different
          const del = matrix[prevRowOffset + j + 1] + 1
          const ins = matrix[thisRowOffset + j] + 1

          const dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins)

          if (dist < minDistance) minDistance = dist
        }

        // Because distance will never decrease, we can stop. There will be no
        // matching child nodes.
        if (minDistance > maxDistance) {
          continue key
        }
      }

      recurse(
        node.get(key)!,
        query,
        maxDistance,
        results,
        matrix,
        i,
        n,
        prefix + key
      )
    }
  }
}

export default fuzzySearch

1	/* eslint-disable no-labels */
2	import { LEAF } from './TreeIterator'	2✔
3	import { RadixTree } from './types'
4
5	export type FuzzyResult<T> = [T, number]
6
7	export type FuzzyResults<T> = Map<string, FuzzyResult<T>>
8
9	/**
10	* @ignore
11	*/
12	export const fuzzySearch = <T = any>(node: RadixTree<T>, query: string, maxDistance: number): FuzzyResults<T> => {	2✔
13	const results: FuzzyResults<T> = new Map()	141✔
14	if (query === undefined) return results	141✔
15
16	// Number of columns in the Levenshtein matrix.
17	const n = query.length + 1	133✔
18
19	// Matching terms can never be longer than N + maxDistance.
20	const m = n + maxDistance	133✔
21
22	// Fill first matrix row and column with numbers: 0 1 2 3 ...
23	const matrix = new Uint8Array(m * n).fill(maxDistance + 1)	133✔
24	for (let j = 0; j < n; ++j) matrix[j] = j	741✔
25	for (let i = 1; i < m; ++i) matrix[i * n] = i	884✔
26
27	recurse(	133✔
28	node,
29	query,
30	maxDistance,
31	results,
32	matrix,
33	1,
34	n,
35	''
36	)
37
38	return results	133✔
39	}
40
41	// Modified version of http://stevehanov.ca/blog/?id=114
42
43	// This builds a Levenshtein matrix for a given query and continuously updates
44	// it for nodes in the radix tree that fall within the given maximum edit
45	// distance. Keeping the same matrix around is beneficial especially for larger
46	// edit distances.
47	//
48	// k a t e <-- query
49	// 0 1 2 3 4
50	// c 1 1 2 3 4
51	// a 2 2 1 2 3
52	// t 3 3 2 1 [2] <-- edit distance
53	// ^
54	// ^ term in radix tree, rows are added and removed as needed
55
56	const recurse = <T = any>(	2✔
57	node: RadixTree<T>,
58	query: string,
59	maxDistance: number,
60	results: FuzzyResults<T>,
61	matrix: Uint8Array,
62	m: number,
63	n: number,
64	prefix: string
65	): void => {
66	const offset = m * n	1,196✔
67
68	key: for (const key of node.keys()) {	4,781✔
69	if (key === LEAF) {	4,781✔
70	// We've reached a leaf node. Check if the edit distance acceptable and
71	// store the result if it is.
72	const distance = matrix[offset - 1]	531✔
73	if (distance <= maxDistance) {	531✔
74	results.set(prefix, [node.get(key)!, distance])	203✔
75	}
76	} else {
77	// Iterate over all characters in the key. Update the Levenshtein matrix
78	// and check if the minimum distance in the last row is still within the
79	// maximum edit distance. If it is, we can recurse over all child nodes.
80	let i = m	4,250✔
81	for (let pos = 0; pos < key.length; ++pos, ++i) {	4,250✔
82	const char = key[pos]	6,020✔
83	const thisRowOffset = n * i	6,020✔
84	const prevRowOffset = thisRowOffset - n	6,020✔
85
86	// Set the first column based on the previous row, and initialize the
87	// minimum distance in the current row.
88	let minDistance = matrix[thisRowOffset]	6,020✔
89
90	const jmin = Math.max(0, i - maxDistance - 1)	6,020✔
91	const jmax = Math.min(n - 1, i + maxDistance)	6,020✔
92
93	// Iterate over remaining columns (characters in the query).
94	for (let j = jmin; j < jmax; ++j) {	6,020✔
95	const different = char !== query[j]	17,919✔
96
97	// It might make sense to only read the matrix positions used for
98	// deletion/insertion if the characters are different. But we want to
99	// avoid conditional reads for performance reasons.
100	const rpl = matrix[prevRowOffset + j] + +different	17,919✔
101	const del = matrix[prevRowOffset + j + 1] + 1	17,919✔
102	const ins = matrix[thisRowOffset + j] + 1	17,919✔
103
104	const dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins)	17,919✔
105
106	if (dist < minDistance) minDistance = dist	17,919✔
107	}
108
109	// Because distance will never decrease, we can stop. There will be no
110	// matching child nodes.
111	if (minDistance > maxDistance) {	6,020✔
112	continue key	3,187✔
113	}
114	}
115
116	recurse(	1,063✔
117	node.get(key)!,
118	query,
119	maxDistance,
120	results,
121	matrix,
122	i,
123	n,
124	prefix + key
125	)
126	}
127	}
128	}
129
130	export default fuzzySearch	2✔

lucaong / minisearch / #482

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous