# Simple fuzzy text search algorithm

Basically, this code takes a keyword and an array of strings, then sorts them based on two things: the number of characters shared with the key, and the distance between them.(As a side note, would this properly be called a sort, not a search?)

def search(key, list)
# Format for everything pushed to out:
# Should this be a class?
# {
#   val: the string in question,
#   shared_chars: [{char: shared char of key list elem,
#                   index: index of shared char,
#                   kindex: index of shared char in key
#                   distance: how close the shared chars are}]
# }
out = []
key = key.downcase

list.each { |l|
l.downcase!
shared_chars = []

keyi = 0
key.each_char { |c|
index = /#{c}/ =~ l

if index != nil
shared_chars.push char: c, index: index, kindex: keyi
end

# Inelegant?
keyi += 1
}

# Calulate total distance between shared_chars
distance = 0
odistance = 0

shared_chars.each_index { |i|
unless i == shared_chars.length-1
distance += (shared_chars[i+1][:index] - shared_chars[i][:index]).abs
odistance += (shared_chars[i+1][:kindex] - shared_chars[i][:kindex]).abs
end
}

distance -= odistance
distance = distance.abs

out.push val: l, shared_chars: shared_chars, distance: distance
}

out.sort_by! { |e|
# 100 is arbitrary
100 + e[:distance] - e[:shared_chars].length*3
}

out
end


Specifically I would like to know if any part of it could be made more efficient and/or elegant, but general critique is of course welcome.

• Blocks longer than one line are conventionally written using doend rather than braces.
• Code of the form

out = []
list.each { |l| ... out.push(something) }


… would be better expressed as

out = list.collect { |l| something }


Besides being slightly more compact, there is a subtle difference in thinking: the former feels like "do this, then this, then this to build a result"; the latter says "transform each element like this", and it's easier to see that there is a one-to-one correspondence between input elements and output elements.

• Within that block,

out = list.collect do |l|
# Calling l.downcase! would have the side-effect of modifying
# strings in the original list, which is impolite.
l = l.downcase

shared_chars = []
key.split.each_with_index do |c, keyi|
index = l.index(c)
# Actually, char:c is never used and could be eliminated
shared_chars.push(char: c, index: index, kindex: keyi) if index
end

distance, kdistance = 0, 0
shared_chars.each_cons(2) do |a, b|
distance += (b[:index] - a[:index]).abs
kdistance += (b[:kindex] - a[:kindex]).abs
end

{ val: l, shared_chars: shared_chars, distance: (distance - odistance).abs }
end

• Furthermore,

out.sort_by! { |e| ... }
out


could just be

out.sort_by { |e| ... }


(.sort_by is defined because an Array is an Enumerable.)

• I think that the whole function would be better as one chained expression:

def search(key, list)
key = key.downcase

list.collect do |l|
...
end.sort_by do |e|
# There's no point in adding 100 to each element
e[:distance] - 3 * e[:shared_chars].length
end
end

• Excellent answer. Note that the bad indentation only happened when I pasted to stackexchange – starscape Dec 23 '13 at 19:16
• do ... end can make problems because of operator precedence. – Nakilon Dec 24 '13 at 12:05
• @Nakilon As can {....}. The difference in precedence between do...end and {...} matters mostly in internal DSLs, where parentheses are, by convention, frequently omitted from method calls. As used in this answer, it's not an issue. – Wayne Conrad Jan 9 '14 at 9:48

Here's one way to modify your code:

def sort_list_by_key(key, list)
key_arr = key.downcase.chars.each_with_index.to_a
metric = list.each_with_object([]) do |l, m|
w = l.downcase
ndx = key_arr.each_with_object({w: [], k: []}) do |(c, i), h|
if (j = w.index(c))
h[:w] << j
h[:k] << i
end
end
m << (distance(ndx[:w]) - distance(ndx[:k])).abs - 3 * ndx[:w].size
end
list.zip(metric).sort_by(&:last).map(&:first)
end

def distance(ndx)
ndx.each_cons(2).to_a.reduce(0) {|d, (i,j)| d + (i-j).abs}
end


Let's look at an example:

key = "match"
list = %w[The cat had kittens] # => ["the", "cat", "had", "kittens"]


We know we will need the index of each character of key for each word in list, so we first construct key_arr:

key_arr # => [["m", 0], ["a", 1], ["t", 2], ["c", 3], ["h", 4]]


We now ask Enumerable#each_with_object (available since Ruby 1.9) to iterate a block for each element of list, and return the results in an array, denoted by the block variable m. This array will be captured by the variable metric. each_with_object creates this (initially empty) array. Each element is the ordering metric for the corresponding member of list.

Consider the first element of list: l => "The". We use String#downcase to change "The" to "the" (not downcase!, because we don't want to change list). We again use each_with_object, this time to create a hash that will contain two arrays that are needed to calculate the ordering metric. These arrays contain indices of matching characters, for "the" (ndx[:w]) and "match" (ndx[:k]), respectively. The calculation key_arr.each... proceeds as follows:

w => "the"
[c, i]    j=index(c)    ndx[:w]    ndx[:k]
['m', 0]         nil         []         []
('a', 1]         nil         []         []
['t', 2]          0         [0]        [2]
['c', 3]         nil        [0]        [2]
['h', 4]          1       [0,1]      [2,4]


A similar calculation is done for "cat", "had" and "kittens". The results are as follows:

                                   distance
w           ndx[:w]   ndx[:k] list  key |diff| 3*size  metric
'the'          [0,1]     [2,4]    1    2     1      6     -5
'cat'      [1, 2, 0] [1, 2, 3]    3    2     1      9     -8
'had'         [1, 0]    [1, 4]    1    3     2      6     -4
'kittens'        [2]       [2]    0    0     0      3     -3

metric # => [-5, -8, -4, -3]


These index arrays provide the information needed to calculate the ordering metric for each word, shown in the last column of this table. For w => "cat", the ordering metric is:

(distance([1,2,0]) - distance[1,2,3]).abs - 3 * [1,2,0].size


For distance([1,2,0])

[1,2,0].each_cons(2).to_a # => [[1, 2], [2, 0]]
[[1, 2], [2, 0]].reduce(0) {|d, (i,j)| d + (i-j).abs} # => 3


(Recall that reduce and inject are synonyms.)

Similarly, distance([[1, 2, 3]]) => 2 and 3 * [1,2,0].size => 9, so

(distance([1,2,0]) - distance[1,2,3]).abs - 3 * [1,2,0].size => |3 - 2| - 9 => -8


We can now construct

list.zip(metric) # => [["The", -5], ["cat", -8], ["had", -4], ["kittens", -3]]


which we sort on the second (last) value of each array to obtain:

=> [["cat", -8], ["The", -5], ["had", -4], ["kittens", -3]]


Lastly, we return the first element of each array:

 => ["cat", "The", "had", "kittens"]


I invite corrections and suggestions for improvements.