Going the Distance
summary
Demonstrates concrete implementations of Levenshtein distance and Hamming distance in Ruby, shows the dynamic programming matrix version that drops a recursive 1647 comparison blowup to 48 comparisons, and describes a Rails generator PR plus using Heroku and the did_you_mean gem as real deployments. Claims Levenshtein yields correct edits for Saturday→Sunday with cost three, contrasts wrong-fast Hamming, and shows caching and trie ideas Google uses for spelling suggestions and when each algorithm is actually practical.
AI-written summary · about
chapters (13)
- 0:00Start
- 5:38Algorithms solve problems
- 8:08Hamming Distance
- 8:50Does not include: Insertion Deletion
- 10:21How do we calculate Distance?
- 11:43What about when characters match?
- 12:06Recursive Levenshtein Distance!
- 13:36"Recursive" took 1647 comparisons
- 14:50Matrix: Levenshtein Distance
- 22:20Machines don't understand tired
- 24:44Get edit distance between input and dictionary
- 27:13longest common subsequence Distance
- 29:00Give an algorithm talk
