How to check if two Strings are approximately equal?

Question

I'm making a chat responder for a game and i want know if there is a way you can compare two strings and see if they are approximatley equal to each other for example:

if someone typed: "Strength level?" it would do a function.. then if someone else typed: "Str level?" it would do that same function, but i want it so that if someone made a typo or something like that it would automatically detect what they're trying to type for example: "Strength tlevel?" would also make the function get called.

is what I'm asking here something simple or will it require me to make a big giant irritating function to check the Strings?

if you've been baffled by my explanation (Not really one of my strong points) then this is basically what I'm asking.

How can I check if two strings are similar to each other?

Looks like you would need to translate the string to phonemes for this type of comparisons. — Olivier Refalo, Apr 09 '12 at 13:59
yep good idea, however "str" doesn't sound like "strength" - so you should really set the expectations. — Olivier Refalo, Apr 09 '12 at 14:06

score 18 · Accepted Answer · edited May 23 '17 at 12:09

18

See this question and answer: Getting the closest string match

Using some heuristics and the Levenshtein distance algorithm, you can compute the similarity of two strings and take a guess at whether they're equal.

enter image description here

Your only option other than that would be a dictionary of accepted words similar to the one you're looking for.

edited May 23 '17 at 12:09

Community

1
1

answered Apr 09 '12 at 14:02

Alain

26,663
20
114
184

score 6 · Answer 2 · edited Sep 25 '14 at 08:35

6

You can use Levenshtein distance.

edited Sep 25 '14 at 08:35

maxlath

1,804
15
24

answered Apr 09 '12 at 14:02

Sandro

1,266
2
13
25

i was looking for that precisely in my answer but couldn't remember the name, nice catch. – ericosg Apr 09 '12 at 14:03

score 2 · Answer 3 · answered Apr 09 '12 at 14:10

I believe you should use one of Edit distance algorithms to solve your problem. Here is for example Levenstein distance algorithm implementation in java. You may use it to compare words in the sentences and if sum of their edit distances would be less than for example 10% of sentence length consider them equals.

score 1 · Answer 4 · answered Apr 09 '12 at 14:02

Perhaps what you need is a large dictionary for similar words and common spelling mistakes, for which you would use for each word to "translate" to one single entry or key.

This would be useful for custom words, so you could add "str" in the same key as "strength".

However, you could also make a few automated methods, i.e. when your word isn't found in the dictionary, to loop recursively for 1 letter difference (either missing or replaced) and can recurse into deeper levels, i.e. 2 missing letters etc.

score 1 · Answer 5 · answered Apr 09 '12 at 14:03

1

I found a few projects that do text to phonemes translations, don't know which one is best

answered Apr 09 '12 at 14:03

Olivier Refalo

50,287
22
91
122

score 1 · Answer 6 · answered Apr 09 '12 at 14:14

If you want to find similar word beginnings, you can use a stemmer. Stemmers reduce words to a common beginning. The most known algorithm if the Port Stemmer (http://tartarus.org/~martin/PorterStemmer).

Levenshtein, as pointed above, is great, but computational heavy for distances greater than one or two.

How to check if two Strings are approximately equal?

6 Answers6

Linked