levenshtein-string-matcher.ts — astro Source File

Source Code

import type { StringMatcher } from '../definitions.js';

// Source: https://github.com/ka-weihe/fastest-levenshtein/blob/master/mod.ts
// License: https://github.com/ka-weihe/fastest-levenshtein/blob/master/LICENSE.md
export class LevenshteinStringMatcher implements StringMatcher {
	readonly #peq = new Uint32Array(0x10000);

	#myers_32(a: string, b: string): number {
		const n = a.length;
		const m = b.length;
		const lst = 1 << (n - 1);
		let pv = -1;
		let mv = 0;
		let sc = n;
		let i = n;
		while (i--) {
			this.#peq[a.charCodeAt(i)] |= 1 << i;
		}
		for (i = 0; i < m; i++) {
			let eq = this.#peq[b.charCodeAt(i)];
			const xv = eq | mv;
			eq |= ((eq & pv) + pv) ^ pv;
			mv |= ~(eq | pv);
			pv &= eq;
			if (mv & lst) {
				sc++;
			}
			if (pv & lst) {
				sc--;
			}
			mv = (mv << 1) | 1;
			pv = (pv << 1) | ~(xv | mv);
			mv &= xv;
		}
		i = n;
		while (i--) {
			this.#peq[a.charCodeAt(i)] = 0;
		}
		return sc;
	}

	#myers_x(b: string, a: string): number {
		const n = a.length;
		const m = b.length;
		const mhc = [];
		const phc = [];
		const hsize = Math.ceil(n / 32);
		const vsize = Math.ceil(m / 32);
		for (let i = 0; i < hsize; i++) {
			phc[i] = -1;
			mhc[i] = 0;
		}
		let j = 0;
		for (; j < vsize - 1; j++) {
			let mv = 0;
			let pv = -1;
			const start = j * 32;
			const vlen = Math.min(32, m) + start;
			for (let k = start; k < vlen; k++) {
				this.#peq[b.charCodeAt(k)] |= 1 << k;
// ... (92 more lines)