Lexical text correction relies on a central step where ap- proximate search in a dictionary is used to select the best correction suggestions for an ill-formed input token. In pre- vious work we introduced the concept of a universal Lev- enshtein automaton and showed how to use these automata for efficiently selecting from a dictionary all entries within a fixed Levenshtein distance to the garbled input word. In this paper we look at refinements of the basic Levenshtein distance that yield more sensible notions of similarity in distinct text correction applications, e.g. OCR. We show that the concept of a universal Levenshtein automaton can be adapted to these refinements. In this way we obtain a method for selecting correction candidates which is very ef- ficient, at the same time selecting small candidate sets with high recall.