In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton after inputting something that is not accepted by said automaton.
It uses A* search to efficiently search for the closest match and has a heuristic function f = g + h, where g is the cost (0 or 1) of an edit operation needed to transform character at index i and h is the number of characters from the input word which is not found along the path from the current state.
I'm not sure if I'm correct in my understanding, but for the function f=g+h, g is the cost of the edit operation depending on the path it takes, so it can only be 0 or 1 while h is the number of non matching future characters from the list when compared to the next state's list of symbols?
What would the process be like for a word such as ddddat or hhhhat? I don't think I read anything about this sort of case being handled unless I missed it.
