Algorithm to search and assign the BEST string for each element of a string array (from another string array)

This is for automating a testing process. I have two string arrays (extracted from two different sources for testing). Each string in one of the arrays has to be assigned to a string in the other array. The strings may not always match exactly, but there may be a similar string (best match) that can be used. If the degree of variance (based on percentage???) is too much, then the item can be appropriately marked.

What I need is an algorithm for searching the BEST string and reject 开发者_StackOverflowthe same if there isn't any.

The is no gold standard ("BEST") string comparision algorithm. There are rather a number of string similarity algorithms based on various assumptions. The similarity measure takes two strings and returns a number indicating how similar the strings are.

Using a similarity measure you can compare how equal the given strings with all the strings in your array. The similarity is a number and you can easily select the string with the best match, even when the given string and the one in the array are not identical.

It's also possible to introduce a cut-off threshold such as if no string is similar enough to the given string your algorithm can detect this.

A popular similarity measure is the Levenshtein distance where the number of character changes, additions, and removals in order to go from one string to the other is counted.

The levenshtein distance can easily be computed in c#, see for example this link for code sample.

http://php.net/manual/en/function.levenshtein.php

The first example there should put you right on track I think. It's for PHP, but the algorithm should be the one you're looking for.

You could split the strings into character bigrams, generating a vector of bigram counts for each string. The vectors can then be compared with, e.g., cosine similarity or a similar measure. Closely related is to use just the set of bigrams present, comparing the sets with the Jaccard index.

This approach is based on the statistics of the bigrams present, ignoring the ordering of the bigrams. Depending on the nature of your strings, this may be an advantage or a disadvantage.