# Fuzzy Match / Implement Levenshtein distance to Construct 2

Get help using Construct 2

### » Thu Jul 28, 2016 12:48 pm

Message: Voytek can only post plain text URLS until they have 500 rep. 1 URLS modified. Why?
[SOLVED] Can someone demonstrate how Levenshtein distance can be translated into Construct 2?

What i want to achieve is the following:

1. I would like to have an array of sentences.
2. The user is supposed to enter one sentence, one at a time, and this sentence is meant to be compared with a correspoding model sentence stored in the array. No need to search through.
3. It is anticipated that the user will make some typos while entering the sentence. i want to allow such mistakes to happen like this:

Model sentence: "This text is awesome"
User input: "This next is awesome"
Result: comparison accepted.

It would be good if i could set the comparison threshold.

Taking all of the above into consideration, i have stumpled upon multiple times on this code below. I believe it could do what i want. Sadly i am not smart enough to translate it into construct 2. Can someone do it and help me achieve the goal described above?

// Compute the edit distance between the two given strings
exports.getEditDistance = function(a, b){
if(a.length == 0) return b.length;
if(b.length == 0) return a.length;

var matrix = [];

// increment along the first column of each row
var i;
for(i = 0; i <= b.length; i++){
matrix[i] = [i];
}

// increment each column in the first row
var j;
for(j = 0; j <= a.length; j++){
matrix[0][j] = j;
}

// Fill in the rest of the matrix
for(i = 1; i <= b.length; i++){
for(j = 1; j <= a.length; j++){
if(b.charAt(i-1) == a.charAt(j-1)){
matrix[i][j] = matrix[i-1][j-1];
} else {
matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
Math.min(matrix[i][j-1] + 1, // insertion
matrix[i-1][j] + 1)); // deletion
}
}
}

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

source page of the code: https://gist.github.com/andrei-m/982927
Last edited by Voytek on Thu Jul 28, 2016 4:53 pm, edited 1 time in total.
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 1:53 pm

This should do the trick.
You can set the text to anything on the RestartText function
Edit: Re-read, Idk what you mean by error threshold
B
43
S
18
G
17
Posts: 2,247
Reputation: 17,556

### » Thu Jul 28, 2016 2:25 pm

Thanks for the caps and your kind contribution, i will view it shortly.

What i mean by "the comparison threshold" is this:

Model:"This text is awesome"
User Input:"This next is awesome"
Threshold: only one typo thus the comparison passes the threshold

Model:"This text is awesome"
User Input:"Thisnext is awesome"
Threshold: only one typo + lack of a "space", thus the comparison passes the threshold

Basically i would like to be able to accept lack of spacing and perhaps "natural misspellings" like cat vs xat, hero vs gero, dark vs sark if that is possible.

Examples of something that would not pass the threshold:

This ext iawesome"
Threshold: missing "t", missing "s", missing "space", thus too many mistakes, comparison does not pass the threshold.

In a sense, the threshold is a measure of comparison acceptability despite some mistakes but not too many. Party metaphor: i do accept some gatecrushers. However too many gatecrushers spoil the party.
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 2:32 pm

Rhis texy ia aqesome, definitely does not pass the threshold
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 2:35 pm

I also do not send everyone, who has come to the party, home only because some invited people did not show up.
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 2:37 pm

Mmmmmm... I'll see if i can implement the algorithm
B
43
S
18
G
17
Posts: 2,247
Reputation: 17,556

### » Thu Jul 28, 2016 2:51 pm

i will keep my fingers crossed, i hope you will fill it with your intellectual benevolence so that construct 2 becomes impregnated with a glorious result!
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 3:12 pm

A glorious result it is!

I implemented the levenshtein distance algorithm, it works as intended, I added a threshold, and a basic trim (removing all spaces), but you should customize how you accept mistakes yourself.

Here ya go!
B
43
S
18
G
17
Posts: 2,247
Reputation: 17,556

### » Thu Jul 28, 2016 4:51 pm

You nailed it! What a blast! I hope I will level up to match you someday as what you have done is so cool! I am so thankful that a higher intelligence of yours wandered into my initial post : ) Now I will do my best to get my head around your glorious creation, which should be so much easier. Just to let you know that I attempt to recreate some duolingo.com functionality. I believe the algorithm sets me on the right way to do it with Construct 2. If you don’t know duolingo, check it out if you like learning “spoken” languages. Feel free to follow me there: “wpwojtek” if you wish. There will be a party tonight. Look up the sky, there will be a shooting star for you : )
B
14
S
3
G
1
Posts: 57
Reputation: 1,422

### » Thu Jul 28, 2016 10:16 pm

Happy to help
B
43
S
18
G
17
Posts: 2,247
Reputation: 17,556