>From a superficial glance at spell.lua:
> yield( splits[i-1]..word[i+1]..word[i]..splits[i+2] )
Do you really need to concatenate here, or could you instead pass a table with separate entries and concatenate only when needed?
Also, you could try using table.concat() instead of .. (it could be faster... or not).
You could also keep an eye on memory usage to see if this is really an allocation problem
Lots of temporary strings seem to be created (e.g. by word_str:sub(...)); perhaps the code could be restructured to reduce their number as much as possible?
Last but not least:
> for i=1,#word_str do for j=1,#alphabet do
I did not try to follow the code, so I may be dead wrong, but nested loops like this usually raise a O(n^2) efficiency red flag, especially because you perform string concatenation inside them.
This can be a big set. For a word of length n, there will be n deletions, n-1 transpositions, 26n alterations, and 26(n+1) insertions, for a total of 54n+25 (of which a few are typically duplicates). For example, len(edits1('something')) -- that is, the number of elements in the result of edits1('something') -- is 494.