Compare Strings AND Allow Typos

Discussion and feedback on Construct 2

Post » Sun Jul 24, 2016 3:32 pm

Is there a way to compare two String values in the form of sentences so that the end result of comparison would accept "natural" typos or some typos within some measure like this?

Model string stored in the game code: "I like cats"

User input: "I like vats"

End result: comparison accepts user's typo. Eventually there is a match.

I would like to make a game with a lot of sentences like this. I hope there is a way to achieve this as easily as possible. Please help, i think this is a tricky one :/
B
11
S
1
Posts: 42
Reputation: 565

Post » Sun Jul 24, 2016 3:40 pm

Use System > Compare Variable to compare the strings.
Image
B
75
S
23
G
3
Posts: 673
Reputation: 9,273

Post » Sun Jul 24, 2016 4:17 pm

Well, I think what you are trying to achieve here is a game that analyzes the user inputs if they have a typo and the input is close to the required text then it will accept it.

I admit this will be tricky but very achievable.

But there will be limitations though, a typo of letters will be accepted by typo like forgetting to put "space" between texts will not work, and it is kind of impossible for me to find a workaround for that mistake since we can only analyze a typo, word for word by measuring the percentage of typo. And we will use the expressions tokennat & tokencount for this.

So, is this what you mean? If you are asking for a .capx file, I'll be glad to make it for you, just say the word. But I think you can do it by yourself using the tokennat and tokencount expressions.
Image



The Things you can create is only limited by your imagination. If you don't have the skills then use your motivation as a natural force to exceed all expectations. Chadori RebornXD
B
55
S
17
G
90
Posts: 1,112
Reputation: 59,147

Post » Sun Jul 24, 2016 11:53 pm

Thanks Chad for your reply, i really appreciate it!

With reference to: "Well, I think what you are trying to achieve here is a game that analyzes the user inputs if they have a typo and the input is close to the required text then it will accept it." Yes! this is exactly what i am aiming at. You are on the same wavelength with me on this.

With reference to: "If you are asking for a .capx file, I'll be glad to make it for you, just say the word." Yes, I am humbly asking for the .capx file. I will do my research on the methods suggested by you but having a solution handed would make me sleep better :) Therefore, I will greately appreciate your .capx contribution. I am only a strong beginner in javascript programming and in construct 2 programming as well. It will be something new to learn for me. Thank you in advance.

By the way, i have anticipated someone suggesting using so called "regular expressions" and i am moderately happy there is something neater than getting my head around the "elusive" regex.

I am looking forward to your next relpy!
B
11
S
1
Posts: 42
Reputation: 565

Post » Mon Jul 25, 2016 2:39 am

There's an efficient and easy to implement fuzzy match algorithm that I used in my proposal for typing events that could probably fit your needs (there's a working example in the previous link). Here's a website that describes the algorithm in detail: http://www.catalysoft.com/articles/StrikeAMatch.html

Basically you pre-process the strings you would like to compare by splitting it's letter pairs ("TEXT" => "TE,EX,XT"). You can store each pair as an entry in a 1D array or use a comma separated string. Then you iterate through each pair of the first string and find if there's a match in the second one (you can use the Find expression). If there's a match you increment a variable Intersection an remove the pair from the second list. After processing every pair you calculate the similarity of the two strings by dividing the number of matching pairs by the total number of pairs (sum from the two strings):

Similarity = 2 * Intersection / TotalNumberOfPairs

Having the similarity, you just need to set a threshold of how much the strings need to match an use a compare:

Similarity > 0.9 => do stuff
Scirra Employee
B
148
S
53
G
17
Posts: 711
Reputation: 17,700

Post » Tue Jul 26, 2016 2:19 pm

@Voytek - Sorry for the delay, I didn't expect this to be very complicated especially because of all the loops I used .But fortunately I have completed the sample .capx file of your requested Typo Corrector w/ Analyzer. I used here the Dictionary plugin instead of the Array plugin since it is far complicated in the Array Plugin. So about the comments, I am sorry but I don't have any time left to fill those up since I will be having my exams tomorrow, but I believe you can understand it. But if I have time then maybe I can make it tomorrow.

Btw, the accuracy is not very great but for games, especially considering performance then I think that will be enough.
And the tolerance rate is 75%, if the pre-made sentence is 75% similar to the typed one then it will auto-correct.

@Animmaniac - Your algorithm is very good but sadly I didn't find a way to implement that in C2. I think a plugin using your algorithm is better than using C2 events. You made it accurate by pairing 2 chars alternately while mine was by comparing each char index with it's neighboring chars. I think your's makes more sense though since the formula was thought out.

.Capx Link:
https://1drv.ms/u/s!AjcW2ueud6qpwlt_a_Ew0XXRm0tR
Image



The Things you can create is only limited by your imagination. If you don't have the skills then use your motivation as a natural force to exceed all expectations. Chadori RebornXD
B
55
S
17
G
90
Posts: 1,112
Reputation: 59,147

Post » Tue Jul 26, 2016 6:15 pm

Thanks Chad for all your effort and the caps. At the moment of writing this reply i have not viewed them yet but i definitely will. Good luck on your exams! Up unti now, I have been trying to implement Animmaniac's suggestion. Unfortunately what i managed to come up with is pretty miserable. I could not turn the code into "neat loops" and i cannot imagine how i could possibly come up with all the possibilities of user typos in the "pre-processing" procedure.

Here is my "production":
Image

Could anyone improve the code, help me learn as well as get this thing done while following Animmaniac's suggestion?

One question is bugging me a lot, namely: how to divide the user input into the pairs to compare? I assume that user input is stored in the Array2. I hope i did not get what Animmaniac suggested at the wrong end. Anyway I am sorry if anything i have done/written is retarded. I am just an aspiring programmer.
B
11
S
1
Posts: 42
Reputation: 565

Post » Tue Jul 26, 2016 6:16 pm

Message: Voytek can only post plain text URLS until they have 500 rep. 1 URLS modified. Why?
https://postimg.org/image/iwuyi9oo7/
B
11
S
1
Posts: 42
Reputation: 565

Post » Mon Aug 01, 2016 2:37 am

Here's a demo of the algorithm I suggested: Fuzzy Match Demo
And here's the capx: Fuzzy Match capx

*To test it just type in the editboxes and it will calculate the similarity between the two strings, giving a match if it's over 80%.

I included some other heuristics that you can test to see what fits better your use case. To combine them I just used a simple average and got very decent results.

In my auto-complete demo I have also used the number of matched characters, but in this demo I only included the strings' length similarity. However if you also want to implement it you only need to do the same it's done in the pairs comparison, just feed individual letters to the arrays instead of pairs.
Last edited by Animmaniac on Wed Aug 10, 2016 11:04 pm, edited 1 time in total.
Scirra Employee
B
148
S
53
G
17
Posts: 711
Reputation: 17,700

Post » Mon Aug 01, 2016 3:06 pm

This is truly grandiose! Animmaniac, thanks so much for your superb contribution. I would never come up with anything close at this stage of my programming development. My skills are a “baby tiger level”, therefore thanks for being such a benevolent beast! This will allow me to learn and grow. Hopefully i will match you someday!
B
11
S
1
Posts: 42
Reputation: 565


Return to Construct 2 General

Who is online

Users browsing this forum: Cliffu, justifun and 11 guests