Fuzzy String Matching Algorithm

This is a discussion on Fuzzy String Matching Algorithm within the C++ Programming forums, part of the General Programming Boards category; I've looked everywhere for a good explanation of an algorithm for fuzzy string matching. Anyone have a link to a ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    23

    Fuzzy String Matching Algorithm

    I've looked everywhere for a good explanation of an algorithm for fuzzy string matching. Anyone have a link to a good tutorial on it?

    Thanks,
    Shane

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    lol.

    If you've looked everywhere, where are we supposed to look?
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,496
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Oct 2005
    Posts
    23
    Sorry for the brevity of my initial post. I was in a bit of a rush when I wrote it. It makes me sound as if I'm looking for you to do the searching for me, which isn't the case.

    Quote Originally Posted by Salem View Post
    That's kind of along the lines of what I was looking for, but I was more thinking of something where I could find a percent of similarity between two strings...

    Say, for instance, that I compare the strings "how are you?" and "how do you do?". I'm looking for an algorithm that could tell me whether the two strings have a roughly matching meaning in the form of a percentage... Do you understand what I'm asking for? Anyone have any ideas?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It all depends on how you want to match the two strings:
    Character matching:
    "how are you?" and "how do you do?" - about 50% similarity. While strings are the same, count "similar". If strings differ, use some method to find a similar point again.

    Word-wise:
    Roughly the same as character matching, but instead of matcing characters, parse the string and split into words, and compare words.

    The difference between character and word matching omes when matching something like:
    "How do you do?"
    with
    "Howling on you?" [Sorry, silly example, but had to come up with something starting with "How..."]

    Linguistically:
    "how are you?" and "how do you do?" - not much in common at all (one is asking a genuine question, the other is a formality in greething someone - and no one is genuinely interested in either case ]. This is of course much more complicated than the method of word or character matching, because it has to do with the meaning of the words.


    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,496
    Soundex returns a number (of sorts), converting it to a %'age can't be that hard surely.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. OOP Question DB Access Wrapper Classes
    By digioz in forum C# Programming
    Replies: 2
    Last Post: 09-07-2008, 04:30 PM
  2. String Construction Algorithm Wanted...
    By anirban in forum C Programming
    Replies: 14
    Last Post: 08-07-2007, 09:27 AM
  3. Custom String class gives problem with another prog.
    By I BLcK I in forum C++ Programming
    Replies: 1
    Last Post: 12-18-2006, 02:40 AM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 02:23 PM
  5. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 01:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21