ruby 56 lines · 10 steps

Building a Norvig-style spellchecker in Ruby

Generate every one- and two-edit variation of a word, keep the ones in the dictionary, and rank them by edit distance.

Explained by highlit
Advanced edit-distance levenshtein dynamic-programming sets candidate-generation
1class Spellchecker
2 ALPHABET = ('a'..'z').to_a.freeze
3 
4 def initialize(dictionary)
5 @dictionary = dictionary.map(&:downcase).to_set
6 end
7 
8 def correct(word)
9 word = word.downcase
10 return word if @dictionary.include?(word)
11 
12 candidates = known(edits1(word)) || known(edits1(word).flat_map { |e| edits1(e) })
13 return word unless candidates&.any?
14 
15 candidates.min_by { |c| [levenshtein(word, c), -word_score(c)] }
16 end
17 
18 def suggestions(word, limit: 5)
19 word = word.downcase
20 pool = known(edits1(word)) || known(edits1(word).flat_map { |e| edits1(e) }) || []
21 pool.sort_by { |c| [levenshtein(word, c), -word_score(c)] }.first(limit)
22 end
23 
24 private
25 
26 def known(words)
27 found = words.select { |w| @dictionary.include?(w) }.uniq
28 found.empty? ? nil : found
29 end
30 
31 def word_score(word)
32 word.length
33 end
34 
35 def edits1(word)
36 splits = (0..word.length).map { |i| [word[0...i], word[i..]] }
37 deletes = splits.filter_map { |l, r| l + r[1..] unless r.empty? }
38 transposes = splits.filter_map { |l, r| l + r[1] + r[0] + r[2..] if r.length > 1 }
39 replaces = splits.flat_map { |l, r| r.empty? ? [] : ALPHABET.map { |c| l + c + r[1..] } }
40 inserts = splits.flat_map { |l, r| ALPHABET.map { |c| l + c + r } }
41 (deletes + transposes + replaces + inserts).uniq
42 end
43 
44 def levenshtein(a, b)
45 prev = (0..b.length).to_a
46 a.chars.each_with_index do |ca, i|
47 curr = [i + 1]
48 b.chars.each_with_index do |cb, j|
49 cost = ca == cb ? 0 : 1
50 curr << [prev[j + 1] + 1, curr[j] + 1, prev[j] + cost].min
51 end
52 prev = curr
53 end
54 prev.last
55 end
56end
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Generating candidates then filtering against a set is often simpler than searching a dictionary for near-matches.
  2. 2A Set makes membership tests O(1), which matters when you check thousands of generated candidates.
  3. 3Sorting by a tuple key lets you rank on a primary metric and break ties with a secondary one in one pass.

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 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")

Optimistic locking with retries in Rails

optimistic-locking concurrency transactions
Advanced 8 steps
ruby 
class BackfillUsersFullName < ActiveRecord::Migration[7.1]
  disable_ddl_transaction!
 
  BATCH_SIZE = 5_000

How to backfill a column safely in Rails

migrations batching backfill
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a Norvig-style spellchecker in Ruby — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code