99% accuracy on transpositions, but struggling with deletions/substitutions. Any advice?

Hi everyone! I'm an undergrad who just started my first Natural Language Processing course this semester and really enjoy it! In one of the early lectures, we were talking about the Levenshtein distance and other algorithms, and I was astonished to learn that most string distance function are O(n*m) and get painfully slow.

I tought to myself "What if we represented each word as a vector instead of comparing raw character sequences?" So we could just do a fast vector search using FAISS and other similar libraries.

I started tinkering a lot, way too much! and almost missed important deadline, but I was having a blast trying different approaches!

I ended up building a working prototype, it encodes each dictionary word into a fixed-size vector using character frequencies, average positions, and what typically comes before and after each letter.

Here’s the interesting part: when I broke down accuracy by error type, I found my algorithm was really good at transpositions (near 99% accuracy) and insertions, but really bad at deletions and substitutions. I found a way to increase performance on both deletions and substitutions a bit, but I know it’s still not great.

Has anyone experimented with a vector representation that preserves positional information better, maybe to handle deletions?

I'd love any feedback (or even criticism), I made a few benchmarks and publish my code for anyone to check on github at /alexis-brosseau/DPVS (it's in the dpvs file, can't share the full link unfortunately)

Thanks for reading!

PS: Sorry if my english is not the best! I'm still learning :-)