ruby 51 lines · 9 steps

Building a ranked fuzzy search in Ruby

A small class that scores candidate strings against a query and returns the best matches in ranked order.

Explained by highlit

Intermediate fuzzy-matching levenshtein ranking string-algorithms

1require "set"
2 
3class FuzzySearch
def initialize(candidates)
  @candidates = candidates
end
7 
def search(query, limit: 10)
  normalized = query.downcase.strip
  return [] if normalized.empty?
11 
  @candidates
    .map { |item| [item, score(normalized, item.downcase)] }
    .reject { |_, s| s.nil? }
    .sort_by { |item, s| [-s, item.length, item.downcase] }
    .first(limit)
    .map(&:first)
end
19 
private
21 
def score(query, target)
  return 100 if target == query
  return 80 if target.start_with?(query)
  return 60 if target.include?(query)
  return nil unless subsequence?(query, target)
27 
  distance = levenshtein(query, target)
  max_len = [query.length, target.length].max
  similarity = 1.0 - (distance.to_f / max_len)
  (similarity * 50).round
end
33 
def subsequence?(query, target)
  chars = target.each_char
  query.each_char.all? { |c| chars.any? { |t| t == c } }
end
38 
def levenshtein(a, b)
  rows = (0..a.length).to_a
  b.each_char.with_index(1) do |bc, j|
    prev = rows[0]
    rows[0] = j
    a.each_char.with_index(1) do |ac, i|
      cost = ac == bc ? 0 : 1
      prev, rows[i] = rows[i], [rows[i] + 1, rows[i - 1] + 1, prev + cost].min
    end
  end
  rows.last
end
51end

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Tiered scoring lets exact, prefix, and substring matches outrank looser fuzzy ones.
2Sorting by a tuple key breaks ties deterministically instead of leaving ordering to chance.
3A rolling single-row Levenshtein keeps edit-distance memory linear in string length.

Related explainers

ruby

module RequestTagging
  class Middleware
    def initialize(app)
      @app = app

Per-request context with CurrentAttributes in Rails

middleware thread-safety logging

Intermediate 7 steps

ruby

class Spellchecker
  ALPHABET = ('a'..'z').to_a.freeze
 
  def initialize(dictionary)

Building a Norvig-style spellchecker in Ruby

edit-distance levenshtein dynamic-programming

Advanced 10 steps

ruby

class Order < ApplicationRecord
  belongs_to :customer
  has_many :line_items
  has_many :products, through: :line_items

How scopes compose in a Rails model

scopes activerecord subqueries

Intermediate 7 steps

ruby

require "charlock_holmes"
 
class TextFileNormalizer
  DEFAULT_CONFIDENCE = 60

Normalizing text files to clean UTF-8 in Ruby

encoding text-processing file-io

Intermediate 8 steps

ruby

require 'date'
require 'set'
 
class BusinessDayCalculator

Counting business days in Ruby

dates sets ranges

Intermediate 8 steps

ruby

class Document < ApplicationRecord
  class StaleObjectError < StandardError
    def initialize(id)
      super("Document ##{id} was modified by another process")