Damerau-Levenshtein is a significant upgrade from the default Levenshtein algorithm used as it also picks up the very common transposition error much more efficiently for not a lot of extra code.
https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_di...
Typed arrays would also probable speed thing up quite a bit.
Tokenizing may not be faster. Set the first row of weights to ZERO. When you're done, look for the lowest value in the final array. This also saves the trouble of trying to tokenize properly for every language as it's only concerned with the bytes themselves.
https://stackoverflow.com/questions/8139958/algorithm-to-fin...
Performance of that algorithm also suffers a LOT with very long strings. For those, we went with one more like the fuzzy search used in Sublime text. Basically, you iterate the string one time and look for the search characters to appear in order. To go more advanced add a weight to each match type. Stuff like consecutive characters that match, cases match, or immediately transposed characters next to each other give higher weights to the resulting string.
https://www.forrestthewoods.com/blog/reverse_engineering_sub... (this looks like a decent overview of sublime fuzzy search).