GitHub - purplejacket/Levenshtein: Create a Levenshtein clique for a word in a list of words

purplejacket / Levenshtein Public

Notifications You must be signed in to change notification settings
Fork 0
Star 1

Create a Levenshtein clique for a word in a list of words

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 23 Commits
.gitignore		.gitignore
3.word.list		3.word.list
36.word.list		36.word.list
README		README
clique.rb		clique.rb
levenshtein.rb		levenshtein.rb
levenshtein_spec.rb		levenshtein_spec.rb
perimeter_words.rb		perimeter_words.rb
perimeter_words_spec.rb		perimeter_words_spec.rb
word.list		word.list

Repository files navigation

This git repository was inspired by the following problem I solved:

Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network  consists of all of its friends, plus all of their friends, and all of their friends' friends, and so on. I want a program to tell us how big the social network for the word "causes" is, using this word list.

This is the wikipedia entry on Levenshtein distance: http://en.wikipedia.org/wiki/Levenshtein_distance
This is the word list: https://github.com/causes/puzzles/raw/master/word_friends/word.list

BK-Trees can be used to find near matches to words based on Levenshtein distance:
http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees