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 
require "shellwords"
require "open3"
 
module Backup

Building safe shell commands in Ruby

shell-out subprocess command-injection
Intermediate 7 steps
ruby 
class UserAgentParser
  BROWSERS = [
    [/Edg\/([\d.]+)/, "Edge"],
    [/OPR\/([\d.]+)/, "Opera"],

Parsing user-agent strings in Ruby

regex pattern-matching lookup-tables
Intermediate 8 steps
ruby 
class LogAggregator
  BUCKET_FORMAT = "%Y-%m-%dT%H:%M"
 
  def initialize(entries)

Bucketing log entries by the minute in Ruby

aggregation hashing enumerable
Intermediate 5 steps
ruby 
class WeeklySignupsReport
  DEFAULT_WEEKS = 12
 
  def initialize(weeks: DEFAULT_WEEKS, source: User.all)

Building a weekly signups report in Rails

service object aggregation group by
Intermediate 7 steps
ruby 
class ApplicationController < ActionController::Base
  EXPERIMENTS = {
    checkout_button_color: %w[control blue green],
    onboarding_flow: %w[control streamlined]

How A/B test cohorts are assigned in Rails

a-b-testing cookies hashing
Intermediate 8 steps
ruby 
class SnippetHighlighter
  CONTEXT_RADIUS = 60
  MAX_TERMS = 8
 

Building search-result snippets in Ruby

regular-expressions text-processing search
Intermediate 9 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