Performing A SublimeText-Inspired Fuzzy Search For String Matching In Angular 7.2.15

// Import the core angular services.
import { Component } from "@angular/core";

// Import the application components and services.
import { FuzzyMatcher } from "./fuzzy-matcher";
import { FuzzySegment } from "./fuzzy-matcher";
import { primates } from "./primates";
import { Species } from "./primates";

// ----------------------------------------------------------------------------------- //
// ----------------------------------------------------------------------------------- //

interface FilterMatch {
	score: number;
	value: Species;
	segments: FuzzySegment[];
}

@Component({
	selector: "my-app",
	styleUrls: [ "./app.component.less" ],
	template:
	`
		<input
			type="text"
			name="filter"
			[(ngModel)]="form.filter"
			(ngModelChange)="applyFilter()"
			placeholder="Search primates...."
			autofocus
			class="filter"
		/>

		<ul *ngIf="matches.length">
			<li *ngFor="let match of matches" class="match">

				<span
					*ngFor="let segment of match.segments"
					class="match__segment"
					[class.match__segment--on]="segment.isMatch"
					>{{ segment.value }}</span>

			</li>
		</ul>
	`
})
export class AppComponent {

	public form: {
		filter: string;
	};
	public matches: FilterMatch[];

	private fuzzyMatcher: FuzzyMatcher;

	// I initialize the app component.
	constructor( fuzzyMatcher: FuzzyMatcher ) {

		this.fuzzyMatcher = fuzzyMatcher;

		this.form = {
			filter: ""
		};
		this.matches = [];

	}

	// ---
	// PUBLIC METHODS.
	// ---

	// I apply the current filter to the collection of primates, generate a set of fuzzy
	// matches.
	public applyFilter() : void {

		// If there is no filter, then hide the list entirely. We only want to show
		// matches when we have something to match on.
		if ( ! this.form.filter ) {

			this.matches = [];
			return;

		}

		this.matches = primates
			// First, we want to take the updated form input and use it to SCORE the
			// collection of values. This phase will have to evaluate the entire set of
			// values; but, will only do the minimal amount of work needed to calculate a
			// scope. Then, we'll be able to use that score to narrow down and format the
			// set of values that we end-up showing to the user.
			.map(
				( primate ) => {

					return({
						value: primate,
						score: this.fuzzyMatcher.scoreValue( primate.name, this.form.filter )
					});

				}
			)
			// Now that the entire set of values has been scored, let's sort them from
			// highest to lowest.
			.sort(
				( a, b ) => {

					return(
						( ( a.score > b.score ) && -1 ) || // Move item up.
						( ( a.score < b.score ) && 1 ) || // Move item down.
						0
					);

				}
			)
			// For the sake of the demo, we only want to show the top-scoring matches.
			// Slice off the top of the scored values.
			.slice( 0, 20 )
			// At this point, we've narrowed down the set of values to the ones we want
			// to show to the user. Now, we can go back and create a data-structure that
			// can be more easily rendered (but takes more processing).
			.map(
				( scoredValue ) => {

					return({
						score: scoredValue.score,
						value: scoredValue.value,
						segments: this.fuzzyMatcher.parseValue( scoredValue.value.name, this.form.filter )
					});

				}
			)
		;

	}

}

export interface FuzzySegment {
	value: string;
	isMatch: boolean;
}

<li *ngFor="let match of matches" class="match">

	<span
		*ngFor="let segment of match.segments"
		class="match__segment"
		[class.match__segment--on]="segment.isMatch"
		>{{ segment.value }}</span>

</li>

// Import the core angular services.
import { Injectable } from "@angular/core";

// ----------------------------------------------------------------------------------- //
// ----------------------------------------------------------------------------------- //

export type FuzzyScore = number;

export interface FuzzySegment {
	value: string;
	isMatch: boolean;
}

@Injectable({
	providedIn: "root"
})
export class FuzzyMatcher {

	// I parse the value against the given input, dividing it up into a collection of
	// segments that either match or do not match sequences within the input.
	public parseValue( value: string, input: string ) : FuzzySegment[] {

		var valueLength = value.length;
		var inputLength = input.length;
		var valueIndex = 0;
		var inputIndex = 0;

		var segments: FuzzySegment[] = [];
		var segment: FuzzySegment;

		while ( valueIndex < valueLength ) {

			var valueChar = value.charAt( valueIndex++ ).toLowerCase();
			var inputChar = input.charAt( inputIndex ).toLowerCase();

			// If this character matches the input, add to a matching segment.
			if ( valueChar === inputChar ) {

				inputIndex++;

				if ( segment && segment.isMatch ) {

					segment.value += valueChar;

				} else {

					segment = {
						value: valueChar,
						isMatch: true
					};
					segments.push( segment );

				}

				// If we've run out of input characters to match, we can short-circuit
				// the segmentation - we know that the rest of the value will contain
				// non-matching characters - we can add them to a final segment.
				if ( ( inputIndex === inputLength ) && ( valueIndex < valueLength ) ) {

					segments.push({
						value: value.slice( valueIndex ),
						isMatch: false
					});

					// Force the while-loop to end.
					break;

				}

			// If this character does NOT match the input, add to a non-matching segment.
			} else {

				if ( segment && ! segment.isMatch ) {

					segment.value += valueChar;

				} else {

					segment = {
						value: valueChar,
						isMatch: false
					};
					segments.push( segment );

				}

			}

		}

		return( segments );

	}


	// I compare the input to the given value and return a score for the fuzzy match.
	public scoreValue( value: string, input: string ) : FuzzyScore {

		// For the scoring process, we don't need to maintain the case of the arguments.
		// As such, we can normalize them now so that we don't have to do it inside of
		// each loop iteration.
		var normalizedValue = value.toLowerCase();
		var normalizedInput = input.toLowerCase();

		var valueLength = normalizedValue.length;
		var inputLength = normalizedInput.length;
		var valueIndex = 0;
		var inputIndex = 0;

		// When several letters are matched in a row, we're going to give them extra
		// weight in the scoring since this more likely to provide a meaningful match.
		var previousIndexMatched = false;
		var score = 0;

		while ( valueIndex < valueLength ) {

			var valueChar = normalizedValue.charAt( valueIndex++ ); // Get and increment.
			var inputChar = normalizedInput.charAt( inputIndex );

			// If the current character matches the next part of the sequential input,
			// we are going to increase the score of the match.
			if ( valueChar === inputChar ) {

				inputIndex++;

				// If the previous character was also a match, let's bump the score by
				// slightly more.
				score += ( previousIndexMatched )
					? 3
					: 2
				;

				previousIndexMatched = true;

				// If we've run out of input characters to match, then we can short-
				// circuit the scoring based on the number of remaining characters in the
				// value (each remaining character will be detracted from the score).
				if ( inputIndex === inputLength ) {

					return( score -= ( valueLength - valueIndex ) );

				}

			// If the current character does NOT Match the next part of the sequential
			// input, we are going to decrease the score of the match.
			} else {

				score -= 1;
				previousIndexMatched = false;

			}

		}

		return( score );

	}

}