Es gibt ja bereits funktionierende Levenstein implementationen z.B. in Lucene und anderen Suchindexern. Wenn man die Rückwärts benutzen kann, kannst Du die einfach benutzen. Erfahrung hab ich leider auch keine, aber google hat mir dazu z.B. das hier geschmissen: https://stackoverflow.com/questions/26529445/autocorrect-using-apache-lucene
evtl. hilft es ja weiter.
VG Hans