search

words / levenmorpher

Morph one word into another, one letter at a time
MIT License
18 stars 4 forks source link

[improvement] Precompute all the pairs of words one edit away from another #1

Closed lsb closed 4 years ago

lsb commented 9 years ago

Then you can do a super fast shortest path through the graph, at the expense of storing a large graph (especially if the word list is bound to change)

moos commented 9 years ago

Some back of the envelope: average english word length is 5 characters. 5^26 ~ 11M possible combinations, but only about 275K actual words, or 2.3%. The 1-"bit" difference in a 5-"bit" sequence of Hexavigesimal (yup, there is a word for it!) digits is 25 * 5=125, which at a nominal rate of 2.3% is ~2.87 or about 3 "1-edit" words per word. (boy I'd like to see that confirmed!).

That's a very good trade-off of time for memory, esp. since the operation is O(n) and n is rather large (FGKO in Hexchamacallit). In fact, if A is 1-edit from B, then B is 1-edit from A. So one of the 3 spaces can actually be eliminated, but that would make implementation much harder.

Anyway -- kudos @zeke. This is a clever idea. Methinks there is a great word game here!!

zeke commented 9 years ago

Hey thanks for chiming in. Fun facts!

I simplified the code a bit last night. It's smaller, faster, and now deterministic. It's not perfect though. It aggressively seeks the shortest path, but can sometimes hit a dead end as a result. See https://github.com/zeke/levenmorpher/blob/5e67fb2f7406dfe830d645dfa7617bb68cc0cb6e/index.js#L33

If you have ideas about how to recover from a dead-end, please advise. :)

wooorm commented 4 years ago

PRs welcome for improvements!