Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

closed as off-topic by gnat, GlenH7, Dan Pichelman, Doc Brown, MichaelT Sep 5 '13 at 15:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – gnat, GlenH7, Dan Pichelman, Doc Brown, MichaelT
If this question can be reworded to fit the rules in the help center, please edit the question.

4  
"Newyork" is also misspelled. The correct spelling is "New York City". Just sayin'. –  tdammers Feb 17 '12 at 11:04

3 Answers 3

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)...

share|improve this answer
1  
Depends on what kind of misspelling they are. If they are keyed by people who don't know how those names should be spelled, than Soundex is appropriate. But if they were just keyed in by sloppy typists, Levenshtein distance is more appropriate. I suspect Google uses the later. –  Jan Hudec Feb 17 '12 at 10:35
    
I suspect Google uses something more sophisticated than either - after all, they have quite some natural-language know-how (see also Google Translate). They're probably using some sort of adaptive Bayesian algorithm (with feedback from search result usage), with lots of manual tweaks and exceptions, that is, statistics with some hard knowledge sprinkled on top. –  tdammers Feb 17 '12 at 11:06

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;
        }
    }
}
share|improve this answer
    
Is it is the code of generic algorithm in C#? How about php.net/manual/en/function.similar-text.php or php.net/manual/en/function.levenshtein.php? –  AgA Feb 17 '12 at 10:50

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.

share|improve this answer
    
+1, but obviously a spell checker won't be much help as they usually don't contain many city names. A list of known cities is needed instead. –  Jan Hudec Feb 17 '12 at 10:33
    
Depending on some licensed api may be something I'd like to avoid. –  AgA Feb 17 '12 at 10:52
    
+1 for the suggestion to use an existing spell checker. Something like aspell is easy to incorporate into software and you could use custom dictionaries with just city names. –  Karl Bielefeldt Feb 17 '12 at 14:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.