simstring
Approximate string matching in Ruby. Find the near-matches that an exact lookup would miss.
Technologies: Ruby, Search, Algorithms
Finding the almost-right word
simstring is a Ruby implementation of the SimString approximate string matching algorithm. Instead of requiring an exact string match, it searches for strings that meet a similarity threshold.
A query can return a collection of matches or a ranked set with similarity scores. This makes it possible to explore close matches while keeping the threshold explicit.
Similarity as a choice
The implementation supports cosine, Dice, exact, Jaccard, and overlap similarity measures. N-gram construction and the chosen measure determine how strings are compared.
The public repository demonstrates this with a small database containing words such as foo, food, and floor. Searching for fooo with different thresholds changes which candidates are returned.
What this project explores
- Approximate lookup using n-gram representations.
- Multiple definitions of string similarity.
- Ranked results and configurable match thresholds.
- A pure Ruby implementation, published as the
simstring_puregem.