Simple fuzzy search algorithm similar to sublimeText

README

Simple fuzzy search algorithm similar to sublimeText

this is a simple algorithm to give a similar result
as SublimeText search feature, if you don't use sublimeText
i think you should just give it a shot from here :
http://www.sublimetext.com

to know more about fuzzy search you should check this wiki page:
http://en.wikipedia.org/wiki/Fuzzy_string_searching

the idea is simple, when you search for a text and you can't remember
only part of it or you miss some characters while typing the search should
be smart enough to show you what you're searching for, so your algorithm
should search for the query characters and allow any character to 
be followed by any other character sequence.

after you get strings that contain your query the fuzzy why,
you should rank them, i choose the simple one, if you found your
exact query your matching pattern will be the least of them in length
and if another patter has query plus one character you missed it
will be the second in search, and so on.

so i sorted ascending order by the matching pattern length.

a smarter algorithm should check if there are 2 matching and get the best one
also should check if you wrote a wrong character, and if you switched two characters
and so on of the operations mentioned in wikipedia.

fuzzy-search.rb

#!/usr/bin/env ruby

# this is a simple fuzzy search algorithm
# similar to sublimeText and atom search 
# this search for insertion operations only
# amore complex one should search for replace
# delete and transpose as mentioned in 
# http://en.wikipedia.org/wiki/Fuzzy_string_searching
# also kudos to :
# http://www.quora.com/Algorithms/How-is-the-fuzzy-search-algorithm-in-Sublime-Text-designed

strings_to_query = [
	"/how_to/build/your/own/gems.rb",
	"How to build your google.rb own custom source control",
	"Public methods are your grub public API and be",
	"this text should be at the end"
]

query = 'grb'
query_reg = /#{query.split('').join('.*?')}/

sorted = []
strings_to_query.each do |string|
	match = query_reg.match string
	sorted << {string: string, rank: match.to_s.length} if match
end

sorted.sort_by! {|i| i[:rank] }

sorted.each do |pair|
	puts "#{pair[:rank]} : #{pair[:string]}"
end

# ublic methods are your grub public API and be
# How to build your google.rb own custom source control
# /how_to/build/your/own/gems.rb
# this text should be at the end

Nice!

See also:

• https://github.com/tajmone/fuzzy-search