2
$\begingroup$

I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?

$\endgroup$
  • $\begingroup$ Asking for a simple explanation is OK. I actually tried to do that (I could have said it in about ten lines). The problem is that I do not know at what level. You should put that information in your profile, if you wish people to take it into account. If this is for academic work, it is useful to know what you are supposed to have learned. If it is your own initiative, it may be that you do not have yet enough background. Do you know about GSM mapping? Do you know about intersection construction for FSA? Do you want any one of the closest matches, or all the closest matches? ... $\endgroup$ – babou Nov 17 '14 at 10:32
  • $\begingroup$ I don't know about GSM mapping, intersection construction for FSA and I want all the closest matches if there exists more than 1 closest match. I've updated my profile to let people know that I'm just an undergraduate student. $\endgroup$ – user2908849 Nov 17 '14 at 11:09
  • $\begingroup$ Finite automata? $\endgroup$ – Raphael Nov 17 '14 at 11:19
  • $\begingroup$ TANSTAAFL ... Some problems require a bit of technical knowledge to be addressed. How much work are you prepared to put in this? Do you know how to transform a NFA into an equivalent DFA? A very similar construction is needed for your problem. Also I give you a fairly simple construction of an automaton $R_L$: do you understand it? Note that it also has a cost counter, and output a correct string as it reads the incorrect one. Then using this automaton to get one answer is not too hard. Getting all answers is somewhat more difficult, and requires some transformations. $\endgroup$ – babou Nov 17 '14 at 12:44
  • $\begingroup$ @babou Well I'll need to put a lot of work in since it's for a project I'm doing at uni. I know how to transform NFA to DFA. It's the first time I've encountered the notation RL but I do understand what L(R) is from your other post. I haven't worked with a cost counter with automatons but I have with other types of graphs. $\endgroup$ – user2908849 Nov 17 '14 at 17:34
2
$\begingroup$

You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:

  1. $A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ [insertion].
  2. $A'(\ell+1,s)$ is the minimum of the following quantities:

    • $A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w_{\ell+1}$.
    • $A(\ell,t)+1$ if there is some transition from $t$ to $s$ [substitution].
    • $A(\ell,s)+1$ [deletion].
  3. $A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA [insertion].

Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is the all-pairs-shortest path matrix different from the matrix produced by the Levenshtein distance algorithm? I'm new to this kind of stuff. $\endgroup$ – user2908849 Nov 17 '14 at 1:51
  • $\begingroup$ The Levenshtein distance algorithm doesn't involve a finite automaton, so the two matrices can't be the same. They also don't have the same dimensions. The all-pairs-shortest-path matrix is not even a dynamic programming table. $\endgroup$ – Yuval Filmus Nov 17 '14 at 1:53
  • $\begingroup$ Sorry for late reply, I've been working on other things in the mean time. For the shortest paths does this assume every transition has a weight of 1? Are there any things you would recommend I read? Also I'm trying to implement this in Java so if there are any current implementations of this in Java that would help me understand better too. $\endgroup$ – user2908849 Nov 29 '14 at 17:31
  • $\begingroup$ @user2908849 The weight of the transition doesn't figure in anywhere. I'm not aware of any implementation, but I'd say it's at the level of an exercise. $\endgroup$ – Yuval Filmus Nov 29 '14 at 18:13
  • $\begingroup$ Would you be able to demonstrate an easy example or show what the pseudocode compared to the Levenshtein distance algorithm would be like? I slightly understand how the adopted way is similar but I'm not sure how to transform to Levenshtein distance algorithm into this. $\endgroup$ – user2908849 Nov 30 '14 at 23:08
2
$\begingroup$

I am assuming that you mean finite-state automaton (FSA) when you say automaton. Actually, this can work for other automata, notably for Push-Down Automata (PDA) and is a nice way to do syntax-error recovery in programming languages compilers. But string matching is usually defined with regular expressions.

The answer to your question is called Levenshtein distance and Viterbi selection. The Levenshtein automata, as defined in wikipedia, will not directly help you, but they are close to the idea. The point is that you actually have 3 automata in this problem, and there are different ways to combine them depending on what you want to achieve.

Here is a hopefully intuitive explanation.

I call $R$ the FSA that is supposed to do the string matching.

Levenshtein distance (or edit distance) to a word in $\mathcal L(R)$ can be computed non-deterministically by a weighted non-deterministic FSA (NFA) $R_L$ that is doing the following. It has the same number of states as $R$, and all the transitions of $R$ with weight 0. Then for every transition in $R$ labeled with input symbol $a$ it has an $\epsilon$-transition between the same state, with a weight corresponding to the cost of a missing $a$ in the input. For every state $q$, and every input symbol $a$, $q$ has an $a$-transition to itself with a weight corresponding to the cost of an extra $a$ in the input string. Finally, for any pair of transitions $\delta(q,a)=q'$ and $\delta(q,b)=q''$ in $R$, add two transitions $\delta(q,b)=q'$ and $\delta(q,a)=q''$, weighted respectively by the cost of replacing $a$ by $b$, and replacing $b$ by $a$.

A computation of $R_L$ can recognize any word an give a distance for that word to some word to be matched in $\mathcal L(R)$. It could at the same time output the corrected word that has been approximated.

This does not help you very much, because what you want is a word with the least cost.

So you have to simulate all possible non-deterministic computations, each with its distance counter (and its corrected string), so as to keep the best answers. Here, dynamic programming is your friend as any prefix of a least cost computation is a least cost computation.

If your weighted NFA $R_L$ has $n$ states, there are only $n$ different states you may be in after reading some prefix $w$ of the input. Since you are only interested in the closest match, you keep only for each state the minimum value of the counter for all computations on $w$ that lead to that state. That is only $n$ state-counter pairs to keep, and from which to do a transition at each reading step.

But what you are computing is only the edit distance, and you may want a bit more than that: the string of the language your input is actually approximating. This again is easy: add to each counter value the corrected input string corresponding to that computational path.

So you keep triples, adding to each pair one of the corrected strings that corresponds to a computation leading to that state-weight pair.

When the input has been scanned and all non-scanning transitions followed, the string associated with accepting states are some of the strings most closely approximated by the input. However, since they may not have the same cost, you want to keep only those with minimum cost. You get only some as you keep only one string with each state. But it is possible to keep them all.

So that is the general idea. Note that the algorithms for measuring the distance for two strings, suggested by Alu's answer is just a special case of this when the FSA recognizes only a singleton set, a single word.

Now this can be obtained more simply by using classical cross product of finite state automata. The idea is that the errors that you wish to accept and correct, with cost, can be formalized by a weighted finite state transducer (or GSM) $T$. Then the automaton you want is obtained by a cross product construction between your initial automaton $R$ and your transducer $T$.

The advantage of this formalization is that it defines easily many different kinds of distances. corresponding to errors that you are willing to accept, such as $a$ can replace $b$ only when following a $c$, with cost $k$. But complex error systems are costly to compute with because of the cross-product that increases the number of states.

I do not have much time right now for details, but I may be adding it later.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

The levenshtein distance is what you want. It calculates the diference between two strings. It counts the characteroperations to transform the one string into the other.

For Example:

test and taste:
replace 'e' with 'a'    -> +1
then add a trailing 'e' -> +1

-> The levenshtein distance is 2

You can find implementations in many languages here

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm aware of what Levenshtein distance is but in my problem I only have my input string and an automaton which could accept a large number of string and I need to find an efficient way to find a closest match for my input. Levenshtein distance simply compares 2 known strings but I don't know the string to compare my input to, since that's the point of my problem. $\endgroup$ – user2908849 Nov 16 '14 at 12:54
  • $\begingroup$ Okay, i try to understand the problem. You have a automaton which accepts or declines a given string. In the case of decline you want to find the closest string to the input, which would have been accepted?! I would try to implement a feedback mechanism in the automaton. For example: If state X would decline the string, try to alter it, so it would be accepted and parse on. In the end return a "decline" and all changes what are done to the string. $\endgroup$ – Alu Nov 16 '14 at 13:13
  • 1
    $\begingroup$ @David Disagree. The question is how to calculate the Levenshtein distance (or perhaps some other metric) between a word and a regular language. The OP already knows about Levenshtein distance. $\endgroup$ – Yuval Filmus Nov 16 '14 at 15:53
  • $\begingroup$ This is actually a reasonable answer. It does not solve the problem, but solving it for an FSA is just a generalisation of solving it for a single string. Not even a very complex generalization. It does not deserve a downvote IMHO. $\endgroup$ – babou Nov 17 '14 at 12:36
  • $\begingroup$ @user2908849 Do you understand how the algorithm suggested by Alu in his reference actually work? $\endgroup$ – babou Nov 17 '14 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.