string comparison with the most similar string

does an开发者_高级运维yone know if exist an algorithm that given one string A and an array of strings B, compares the A string with all the strings in B giving in output the most similar one.

For "the most similar one" I mean that for example,

if the A string is: "hello world how are you"

then

"asdf asdewr hello world how asfrqr you"

is more similar than:

"h2ll4 w1111 h11 111 111"

The usual measurement for this is the Levenshtein distance. Compute the Levenshtein distance from the original to each candidate, and take the smallest distance as the most likely candidate.

Define similarity. Algorithms that can do this include:

1. Levenshtein/LCS/n-gram distance (compare the string with each of the strings in your set, take the one with lowest distance)
2. tf-idf indexing
3. Levenshtein automata
4. Hopfield networks
5. BK-trees

All of which can feasibly by implemented in C or C++. Google "string similarity", "duplicate finding" or "record linkage" for the available metrics and algorithms.

This is usually done with checking a bunch of variations of the string that you have ... take a look at spelling correction algorithms - e.g. here