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
4 def initialize(candidates)
5 @candidates = candidates
6 end
7 
8 def search(query, limit: 10)
9 normalized = query.downcase.strip
10 return [] if normalized.empty?
11 
12 @candidates
13 .map { |item| [item, score(normalized, item.downcase)] }
14 .reject { |_, s| s.nil? }
15 .sort_by { |item, s| [-s, item.length, item.downcase] }
16 .first(limit)
17 .map(&:first)
18 end
19 
20 private
21 
22 def score(query, target)
23 return 100 if target == query
24 return 80 if target.start_with?(query)
25 return 60 if target.include?(query)
26 return nil unless subsequence?(query, target)
27 
28 distance = levenshtein(query, target)
29 max_len = [query.length, target.length].max
30 similarity = 1.0 - (distance.to_f / max_len)
31 (similarity * 50).round
32 end
33 
34 def subsequence?(query, target)
35 chars = target.each_char
36 query.each_char.all? { |c| chars.any? { |t| t == c } }
37 end
38 
39 def levenshtein(a, b)
40 rows = (0..a.length).to_a
41 b.each_char.with_index(1) do |bc, j|
42 prev = rows[0]
43 rows[0] = j
44 a.each_char.with_index(1) do |ac, i|
45 cost = ac == bc ? 0 : 1
46 prev, rows[i] = rows[i], [rows[i] + 1, rows[i - 1] + 1, prev + cost].min
47 end
48 end
49 rows.last
50 end
51end
01 / 01
STEP 01

Walkthrough

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

Related explainers

ruby 
def collatz_lengths
  Enumerator.new do |y|
    n = 1
    loop do

Building infinite sequences with lazy enumerators

lazy-evaluation enumerators infinite-sequences
Intermediate 8 steps
ruby 
class SearchIndexReconciler
  DEBOUNCE_WINDOW = 5.seconds
 
  def self.schedule(record)

Debouncing search reindex jobs in Rails

debouncing background-jobs caching
Advanced 7 steps
ruby 
class ParamCoercer
  TYPES = {
    integer: ->(v) { Integer(v) },
    float:   ->(v) { Float(v) },

Coercing request params by schema in Ruby

lambdas type-coercion lookup-table
Intermediate 7 steps
ruby 
module Api
  module V2
    class ArticlesController < Api::BaseController
      before_action :set_article, only: %i[show update destroy]

Building a versioned JSON API controller in Rails

rest-api serialization pagination
Intermediate 10 steps
ruby 
class ArticlesController < ApplicationController
  before_action :set_article, only: %i[show edit update destroy publish]
 
  def edit

Policy-based authorization in a Rails controller

authorization policy-object before-action
Intermediate 9 steps
ruby 
class ArticlesController < ApplicationController
  DEFAULT_LIMIT = 25
  MAX_LIMIT = 100
 

Cursor-based pagination in a Rails controller

pagination cursor query-building
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a ranked fuzzy search in Ruby — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code