Suggest algorithm optimization: Levenshtein distance

[aarondandy]

Because this is a port of the original library, I don't want to get too creative with the algorithms. For suggest, especially, these brute forcing nested loops can really hurt as the x64 compilers don't put the same amount of up-front effort into optimizations. Maybe something like Levenshtein distance, which I don't even know if I spelled correctly, could be of use without changing the results?

If something can be improved there, the benefits could impact #33, #40, and #43 .

Learning resources from https://github.com/Turnerj/Quickenshtein#learning-resources

• https://turnerj.com/blog/levenshtein-distance-part-1-what-is-it
• https://turnerj.com/blog/levenshtein-distance-part-2-gotta-go-fast
• https://turnerj.com/blog/levenshtein-distance-part-3-optimize-everything
• https://turnerj.com/blog/levenshtein-distance-with-simd
• https://www.youtube.com/watch?v=JiOYajl2Mds

[aarondandy]

I'm not really sure if this can help with the ngram substring performance but will re-open if I learn more.