Diffusion Open Access Compliance Check Tool (OACCT) (paginated-inlines) Browse

rOACCT/node_modules/commander/lib/suggestSimilar.js
f646e1f695a7paginated-inlines

suggestSimilar.js
View Options

			const maxDistance = 3;

			function editDistance(a, b) {
			// https://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
			// Calculating optimal string alignment distance, no substring is edited more than once.
			// (Simple implementation.)

			// Quick early exit, return worst case.
			if (Math.abs(a.length - b.length) > maxDistance) return Math.max(a.length, b.length);

			// distance between prefix substrings of a and b
			const d = [];

			// pure deletions turn a into empty string
			for (let i = 0; i <= a.length; i++) {
			d[i] = [i];
			}
			// pure insertions turn empty string into b
			for (let j = 0; j <= b.length; j++) {
			d[0][j] = j;
			}

			// fill matrix
			for (let j = 1; j <= b.length; j++) {
			for (let i = 1; i <= a.length; i++) {
			let cost = 1;
			if (a[i - 1] === b[j - 1]) {
			cost = 0;
			} else {
			cost = 1;
			}
			d[i][j] = Math.min(
			d[i - 1][j] + 1, // deletion
			d[i][j - 1] + 1, // insertion
			d[i - 1][j - 1] + cost // substitution
			);
			// transposition
			if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
			d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + 1);
			}
			}
			}

			return d[a.length][b.length];
			}

			/**
			* Find close matches, restricted to same number of edits.
			*
			* @param {string} word
			* @param {string[]} candidates
			* @returns {string}
			*/

			function suggestSimilar(word, candidates) {
			if (!candidates \|\| candidates.length === 0) return '';
			// remove possible duplicates
			candidates = Array.from(new Set(candidates));

			const searchingOptions = word.startsWith('--');
			if (searchingOptions) {
			word = word.slice(2);
			candidates = candidates.map(candidate => candidate.slice(2));
			}

			let similar = [];
			let bestDistance = maxDistance;
			const minSimilarity = 0.4;
			candidates.forEach((candidate) => {
			if (candidate.length <= 1) return; // no one character guesses

			const distance = editDistance(word, candidate);
			const length = Math.max(word.length, candidate.length);
			const similarity = (length - distance) / length;
			if (similarity > minSimilarity) {
			if (distance < bestDistance) {
			// better edit distance, throw away previous worse matches
			bestDistance = distance;
			similar = [candidate];
			} else if (distance === bestDistance) {
			similar.push(candidate);
			}
			}
			});

			similar.sort((a, b) => a.localeCompare(b));
			if (searchingOptions) {
			similar = similar.map(candidate => `--${candidate}`);
			}

			if (similar.length > 1) {
			return `\n(Did you mean one of ${similar.join(', ')}?)`;
			}
			if (similar.length === 1) {
			return `\n(Did you mean ${similar[0]}?)`;
			}
			return '';
			}

			exports.suggestSimilar = suggestSimilar;