Skip to content

Commit 00ad01c

Browse files
bennadelbennadel
committed
Add fuzzy-matcher poc for Angular 7.2.15.
1 parent b1b30b0 commit 00ad01c

25 files changed

Lines changed: 8221 additions & 0 deletions

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ with.
1010

1111
## My JavaScript Demos - I Love JavaScript!
1212

13+
* [Performing A SublimeText-Inspired Fuzzy Search For String Matching In Angular 7.2.15](https://bennadel.github.io/JavaScript-Demos/demos/fuzzy-match-angular7/)
1314
* [Using replaceUrl To Persist Search Filters In The URL Without Messing Up The Browser History In Angular 7.2.14](https://bennadel.github.io/JavaScript-Demos/demos/router-filter-replace-state-angular7/)
1415
* [Creating A Proxy For Analytics Libraries In Order To Defer Loading And Parsing Overhead In Angular 7.2.13](https://bennadel.github.io/JavaScript-Demos/demos/delayed-script-load-proxy-service-angular7/)
1516
* [Thought Experiment: Partially-Applying Ng-Template References In Angular 7.2.13](https://bennadel.github.io/JavaScript-Demos/demos/partially-applied-templates-angular7/)

‎demos/fuzzy-match-angular7/.gitignore‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
2+
# Now that we're using Webpack, we can install modules locally and just ignore
3+
# them since the assets are baked into the compiled modules.
4+
node_modules/

‎demos/fuzzy-match-angular7/app/app.component.less‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
2+
:host {
3+
display: block ;
4+
font-size: 18px ;
5+
}
6+
7+
.filter {
8+
font-size: 22px ;
9+
}
10+
11+
.match {
12+
font-size: 18px ;
13+
14+
&__segment {
15+
color: #454545 ;
16+
display: inline-block ;
17+
white-space: pre ;
18+
19+
&--on {
20+
color: #000000 ;
21+
font-weight: 800 ;
22+
}
23+
}
24+
}

‎demos/fuzzy-match-angular7/app/app.component.ts‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
2+
// Import the core angular services.
3+
import { Component } from "@angular/core";
4+
5+
// Import the application components and services.
6+
import { FuzzyMatcher } from "./fuzzy-matcher";
7+
import { FuzzySegment } from "./fuzzy-matcher";
8+
import { primates } from "./primates";
9+
import { Species } from "./primates";
10+
11+
// ----------------------------------------------------------------------------------- //
12+
// ----------------------------------------------------------------------------------- //
13+
14+
interface FilterMatch {
15+
score: number;
16+
value: Species;
17+
segments: FuzzySegment[];
18+
}
19+
20+
@Component({
21+
selector: "my-app",
22+
styleUrls: [ "./app.component.less" ],
23+
template:
24+
`
25+
<input
26+
type="text"
27+
name="filter"
28+
[(ngModel)]="form.filter"
29+
(ngModelChange)="applyFilter()"
30+
placeholder="Search primates...."
31+
autofocus
32+
class="filter"
33+
/>
34+
35+
<ul *ngIf="matches.length">
36+
<li *ngFor="let match of matches" class="match">
37+
38+
<span
39+
*ngFor="let segment of match.segments"
40+
class="match__segment"
41+
[class.match__segment--on]="segment.isMatch"
42+
>{{ segment.value }}</span>
43+
44+
</li>
45+
</ul>
46+
`
47+
})
48+
export class AppComponent {
49+
50+
public form: {
51+
filter: string;
52+
};
53+
public matches: FilterMatch[];
54+
55+
private fuzzyMatcher: FuzzyMatcher;
56+
57+
// I initialize the app component.
58+
constructor( fuzzyMatcher: FuzzyMatcher ) {
59+
60+
this.fuzzyMatcher = fuzzyMatcher;
61+
62+
this.form = {
63+
filter: ""
64+
};
65+
this.matches = [];
66+
67+
}
68+
69+
// ---
70+
// PUBLIC METHODS.
71+
// ---
72+
73+
// I apply the current filter to the collection of primates, generate a set of fuzzy
74+
// matches.
75+
public applyFilter() : void {
76+
77+
// If there is no filter, then hide the list entirely. We only want to show
78+
// matches when we have something to match on.
79+
if ( ! this.form.filter ) {
80+
81+
this.matches = [];
82+
return;
83+
84+
}
85+
86+
this.matches = primates
87+
// First, we want to take the updated form input and use it to SCORE the
88+
// collection of values. This phase will have to evaluate the entire set of
89+
// values; but, will only do the minimal amount of work needed to calculate a
90+
// scope. Then, we'll be able to use that score to narrow down and format the
91+
// set of values that we end-up showing to the user.
92+
.map(
93+
( primate ) => {
94+
95+
return({
96+
value: primate,
97+
score: this.fuzzyMatcher.scoreValue( primate.name, this.form.filter )
98+
});
99+
100+
}
101+
)
102+
// Now that the entire set of values has been scored, let's sort them from
103+
// highest to lowest.
104+
.sort(
105+
( a, b ) => {
106+
107+
return(
108+
( ( a.score > b.score ) && -1 ) || // Move item up.
109+
( ( a.score < b.score ) && 1 ) || // Move item down.
110+
0
111+
);
112+
113+
}
114+
)
115+
// For the sake of the demo, we only want to show the top-scoring matches.
116+
// Slice off the top of the scored values.
117+
.slice( 0, 20 )
118+
// At this point, we've narrowed down the set of values to the ones we want
119+
// to show to the user. Now, we can go back and create a data-structure that
120+
// can be more easily rendered (but takes more processing).
121+
.map(
122+
( scoredValue ) => {
123+
124+
return({
125+
score: scoredValue.score,
126+
value: scoredValue.value,
127+
segments: this.fuzzyMatcher.parseValue( scoredValue.value.name, this.form.filter )
128+
});
129+
130+
}
131+
)
132+
;
133+
134+
}
135+
136+
}

‎demos/fuzzy-match-angular7/app/app.module.ts‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
2+
// Import the core angular services.
3+
import { BrowserModule } from "@angular/platform-browser";
4+
import { FormsModule } from "@angular/forms";
5+
import { NgModule } from "@angular/core";
6+
7+
// Import the application components and services.
8+
import { AppComponent } from "./app.component";
9+
10+
// ----------------------------------------------------------------------------------- //
11+
// ----------------------------------------------------------------------------------- //
12+
13+
@NgModule({
14+
imports: [
15+
BrowserModule,
16+
FormsModule
17+
],
18+
declarations: [
19+
AppComponent
20+
],
21+
bootstrap: [
22+
AppComponent
23+
]
24+
})
25+
export class AppModule {
26+
// ...
27+
}

‎demos/fuzzy-match-angular7/app/fuzzy-matcher.ts‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
2+
// Import the core angular services.
3+
import { Injectable } from "@angular/core";
4+
5+
// ----------------------------------------------------------------------------------- //
6+
// ----------------------------------------------------------------------------------- //
7+
8+
export type FuzzyScore = number;
9+
10+
export interface FuzzySegment {
11+
value: string;
12+
isMatch: boolean;
13+
}
14+
15+
@Injectable({
16+
providedIn: "root"
17+
})
18+
export class FuzzyMatcher {
19+
20+
// I parse the value against the given input, dividing it up into a collection of
21+
// segments that either match or do not match sequences within the input.
22+
public parseValue( value: string, input: string ) : FuzzySegment[] {
23+
24+
var valueLength = value.length;
25+
var inputLength = input.length;
26+
var valueIndex = 0;
27+
var inputIndex = 0;
28+
29+
var segments: FuzzySegment[] = [];
30+
var segment: FuzzySegment;
31+
32+
while ( valueIndex < valueLength ) {
33+
34+
var valueChar = value.charAt( valueIndex++ ).toLowerCase();
35+
var inputChar = input.charAt( inputIndex ).toLowerCase();
36+
37+
// If this character matches the input, add to a matching segment.
38+
if ( valueChar === inputChar ) {
39+
40+
inputIndex++;
41+
42+
if ( segment && segment.isMatch ) {
43+
44+
segment.value += valueChar;
45+
46+
} else {
47+
48+
segment = {
49+
value: valueChar,
50+
isMatch: true
51+
};
52+
segments.push( segment );
53+
54+
}
55+
56+
// If we've run out of input characters to match, we can short-circuit
57+
// the segmentation - we know that the rest of the value will contain
58+
// non-matching characters - we can add them to a final segment.
59+
if ( ( inputIndex === inputLength ) && ( valueIndex < valueLength ) ) {
60+
61+
segments.push({
62+
value: value.slice( valueIndex ),
63+
isMatch: false
64+
});
65+
66+
// Force the while-loop to end.
67+
break;
68+
69+
}
70+
71+
// If this character does NOT match the input, add to a non-matching segment.
72+
} else {
73+
74+
if ( segment && ! segment.isMatch ) {
75+
76+
segment.value += valueChar;
77+
78+
} else {
79+
80+
segment = {
81+
value: valueChar,
82+
isMatch: false
83+
};
84+
segments.push( segment );
85+
86+
}
87+
88+
}
89+
90+
}
91+
92+
return( segments );
93+
94+
}
95+
96+
97+
// I compare the input to the given value and return a score for the fuzzy match.
98+
public scoreValue( value: string, input: string ) : FuzzyScore {
99+
100+
// For the scoring process, we don't need to maintain the case of the arguments.
101+
// As such, we can normalize them now so that we don't have to do it inside of
102+
// each loop iteration.
103+
var normalizedValue = value.toLowerCase();
104+
var normalizedInput = input.toLowerCase();
105+
106+
var valueLength = normalizedValue.length;
107+
var inputLength = normalizedInput.length;
108+
var valueIndex = 0;
109+
var inputIndex = 0;
110+
111+
// When several letters are matched in a row, we're going to give them extra
112+
// weight in the scoring since this more likely to provide a meaningful match.
113+
var previousIndexMatched = false;
114+
var score = 0;
115+
116+
while ( valueIndex < valueLength ) {
117+
118+
var valueChar = normalizedValue.charAt( valueIndex++ ); // Get and increment.
119+
var inputChar = normalizedInput.charAt( inputIndex );
120+
121+
// If the current character matches the next part of the sequential input,
122+
// we are going to increase the score of the match.
123+
if ( valueChar === inputChar ) {
124+
125+
inputIndex++;
126+
127+
// If the previous character was also a match, let's bump the score by
128+
// slightly more.
129+
score += ( previousIndexMatched )
130+
? 3
131+
: 2
132+
;
133+
134+
previousIndexMatched = true;
135+
136+
// If we've run out of input characters to match, then we can short-
137+
// circuit the scoring based on the number of remaining characters in the
138+
// value (each remaining character will be detracted from the score).
139+
if ( inputIndex === inputLength ) {
140+
141+
return( score -= ( valueLength - valueIndex ) );
142+
143+
}
144+
145+
// If the current character does NOT Match the next part of the sequential
146+
// input, we are going to decrease the score of the match.
147+
} else {
148+
149+
score -= 1;
150+
previousIndexMatched = false;
151+
152+
}
153+
154+
}
155+
156+
return( score );
157+
158+
}
159+
160+
}

0 commit comments

Comments
 (0)