Simple fuzzy text search algorithm

Question

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.

Answer 1

• Blocks longer than one line are conventionally written using do…end 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
  

Answer 2

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.