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.

  • 3
    $\begingroup$ Please extend your question such that we could understand it without reading the paper. $\endgroup$
    – Danny
    Nov 25, 2014 at 22:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.