approx-string-match

A library for approximate string matching.

This can be used to find occurrences of a pattern P (of length m) in a text T (of length n) allowing for up to a given number of errors (k), where errors may include insertions, substitutions or deletions of characters from the pattern.

For example the pattern "annd" occurs in the string "four score and seven" with one error.

The implementation uses a bit-parallel algorithm by G. Myers [1] which, to the best of my knowledge, is the state of the art algorithm for the online version of the problem (where the text and pattern cannot be preprocessed in advance). It runs in O((k/w) * n) expected-time where k <= m and w is the word size (32 in JavaScript). It also includes some additional optimizations suggested in [3]. See comments in the code for more details.

Usage

npm install --save approx-string-match

1import search from "approx-string-match";
2
3const text = "Four score and seven";
4const pattern = "annd";
5const matches = search(text, pattern, 2 /* max errors */);
6console.log(matches);
7
8// Outputs `[{ start: 11, end: 14, errors: 1 }]`

API

The library exports a single function search(text, pattern, maxErrors) which returns an array of the closest matches for pattern in text allowing up to maxErrors errors.

1interface Match {
2  start: number;
3  end: number;
4  errors: number;
5}
6
7search(text: string, pattern: string, maxErrors: number): Match[]

Implementation notes

Word size

The algorithm uses bitwise operations on integers. Since JavaScript only supports bitwise operations on 32-bit integers, that is the word size, regardless of the platform.

If JS gains support for bitwise operations on larger integers in future, that support could be used to speed up this library.

Unicode

The library currently works on code units rather than code points, where the code unit is a UTF-16 value. What this means is that a change to a unicode character which requires multiple characters to represent in a JavaScript string, such as emoji, would actually count as two changes rather than one. This is because such chars require two elements to represent in a string (eg. "😊".length is 2).

Related reading

For an overview of the different approaches to approximate string matching and the history of the development of solutions, there is a good survey paper [2].

References

[1] G. Myers, “A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming,” vol. 46, no. 3, pp. 395–415, 1999.

[2] G. Navarro, “A guided tour to approximate string matching,” ACM Comput. Surv., vol. 33, no. 1, pp. 31–88, 2001.

[3] Šošić, M. (2014). "An SIMD dynamic programming c/c++ library" (Doctoral dissertation, Fakultet Elektrotehnike i računarstva, Sveučilište u Zagrebu).