String likeness algorithms

Question

I have two strings (they're going to be descriptions in a simple database eventually), let's say they're

1. String A: "Apple orange coconut lime jimmy buffet"
2. String B: "Car bicycle skateboard"

What I'm looking for is this. I want a function that will have the input "cocnut", and have the output be "String A"

We could have differences in capitalization, and the spelling won't always be spot on. The goal is a 'quick and dirty' search if you will.

Are there any .net (or third party), or recommend 'likeness algorithms' for strings, so I could check that the input has a 'pretty close fragment' and return it? My database is going to have liek 50 entries, tops.

Answer 1

What you’re searching for is known as the edit distance between two strings. There exist plenty of implementations – here’s one from Stack Overflow itself.

Since you’re searching for only part of a string what you want is a locally optimal match rather than a global match as computed by this method.

This is known as the local alignment problem and once again it’s easily solvable by an almost identical algorithm – the only thing that changes is the initialisation (we don’t penalise whatever comes before the search string) and the selection of the optimum value (we don’t penalise whatever comes after the search string).