I've city names, like Newyork. Somebody may misspell it and write it as Newyoork. I want an algorithm or library which can match such patterns with some confidence level.
Any idea how to do it or if any pattern recognition library is present?
It is same as when we type something in Google with spelling mistake in it but instead it automatically corrects the mistake.
Comparing two strings A and B :-
Levenshtein comparison counts the number of steps (adding, replacing or removing a single character at a time) to change A into B.
Ratcliff comparison gives a match score (100 for two equal strings) based on the longest common sequence between A and B, with recurrence to compare the remaining sub-strings after each iteration.
Here are my C# implementations as string extender functions
public static class StringExtender
{
public static int CompareLevenshtein(this string A, string B)
{ return A.CompareLevenshtein(B, false); }
public static int CompareLevenshtein(this string A, string B, bool CaseSensitive)
{
int LA = A.Length;
int LB = B.Length;
if (LA == 0)
return LB;
else if (LB == 0)
return LA;
else
{
string A1 = CaseSensitive ? A : A.ToUpperInvariant();
string B1 = CaseSensitive ? B : B.ToUpperInvariant();
int[,] D = new int[LA + 1, LB + 1];
for (int i = 0; i <= LA; i++)
D[i, 0] = i;
for (int i = 0; i <= LB; i++)
D[0, i] = i;
for (int i = 1; i <= LA; i++)
{
char AI = A1[i - 1];
for (int j = 1; j <= LB; j++)
{
char BJ = B1[j - 1];
int cost = (AI == BJ ? 0 : 1);
D[i, j] = MimumumOf3(D[i - 1, j] + 1,
D[i, j - 1] + 1,
D[i - 1, j - 1] + cost);
}
}
return D[LA, LB];
}
}
private static int MimumumOf3(int i, int j, int k)
{ return Math.Min(Math.Min(i, j), k); }
public static float CompareStringsRatcliff(this string A, string B)
{ return CompareStringsRatcliff(A, B, false); }
public static float CompareStringsRatcliff(this string A, string B, bool CaseSensitive)
{
int LA = A.Length;
int LB = B.Length;
if ((LA == 0) || (LB == 0))
return 0.0f;
else
{
string A1 = (CaseSensitive ? A : A.ToUpperInvariant());
string B1 = (CaseSensitive ? B : B.ToUpperInvariant());
if (A1.Equals(B1))
return 100.0f;
else
return CompareStringsRatcliffInternal(A1, 0, LA - 1, B1, 0, LB - 1) * 200.0f / (LA + LB);
}
}
private static int CompareStringsRatcliffInternal(string A, int StartIndexA, int EndIndexA, string B, int StartIndexB, int EndIndexB)
{
if ((StartIndexA > EndIndexA) || (StartIndexB > EndIndexB))
return 0;
else
{
int NewStartIndexA = 0;
int NewStartIndexB = 0;
int BestMatches = 0;
for (int Ai = StartIndexA; Ai <= EndIndexA; Ai++)
for (int Bi = StartIndexB; Bi <= EndIndexB; Bi++)
{
int i = 0;
int Matches = 0;
while ((Ai + i <= EndIndexA) && (Bi + i <= EndIndexB) && (A[Ai + i] == B[Bi + i]))
{
Matches++;
if (Matches > BestMatches)
{
NewStartIndexA = Ai;
NewStartIndexB = Bi;
BestMatches = Matches;
}
i++;
}
}
if (BestMatches > 0)
{
BestMatches += CompareStringsRatcliffInternal(A, NewStartIndexA + BestMatches, EndIndexA, B, NewStartIndexB + BestMatches, EndIndexB);
BestMatches += CompareStringsRatcliffInternal(A, StartIndexA, NewStartIndexA - 1, B, StartIndexB, NewStartIndexB - 1);
}
return BestMatches;
}
}
}
You already quoted in your own question one service to use: Google itself. Looking at Google Maps API may be helpful too, I believe, but I don't remember if there was an auto-correction feature in their geolocation API.
Another possibility is to use a spell checker (on Windows where you have Microsoft Office, you can use the API provided by Microsoft Office; on other platforms, analog products are available). Get all the suggestions for a word from a spell checker, and compare them to the list of cities, to be sure that the suggestion is a geographic location, not a word from a dictionary.
spell checker won't be much help as they usually don't contain many city names. A list of known cities is needed instead.
You want Soundex, which is intended to do exactly this: recognize proper names that people have misspelt in various ways.
a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. The algorithm mainly encodes consonants; a vowel will not be encoded unless it is the first letter. Soundex is the most widely known of all phonetic algorithms (in part because it is a standard feature of popular database software such as PostgreSQL, MySQL, MS SQL Server and Oracle)...
