Efficient Error-Correcting Viterbi Parsing.
AbstractThe problem of Error-Correcting Parsing (ECP) using an insertion-deletion-substitution error model and a Finite State Machine is examined. The Viterbi algorithm can be straightforwardly extended to perform ECP, though the resulting computational complexity can become prohibitive for many applications. We propose three approaches in order to achieve an efficient implementation of Viterbi-like ECP which are compatible with Beam Search acceleration techniques. Language processing and shape recognition experiments which assess the performance of the proposed algorithms are presented.
Introduction
The problem of Error-Correcting Parsing (ECP) is fundamental in Syntactic Pattern
Recognition (SPR) [11, 13], where data is generally distorted or noisy. It also arises
in many other areas such as Language Modeling [23, 6], Speech Processing [7, 22],
OCR [18], Grammatical Inference [20], Coding Theory [8, 15] and Sequence Comparison
[21]. As in many other problems arising in several research areas, ECP is
related to finding the best path through a trellis, a problem that is solved by the
Viterbi algorithm (VA) [10] as is well-known. McEliece [19] makes a good description
of the operation and complexity of the VA with application to decoding linear block
codes. On the other hand, Wiberg et al [24] use an alternative decoding scheme
based on Tanner graphs rather than trellises. Nevertheless, only the work described
in [8, 15] seems to specifically deal with the ECP problem as stated in Sect. 2.
Henceforth we shall be concerned with the application of ECP in SPR that is, it
will be assumed that both a stochastic Finite State Model (FSM) and an (stochas-
tic) error model accounting for insertions, substitutions and deletions of symbols are
given 1 . These symbols belong to some alphabet \Sigma, which stands for the set of primitives
or features that characterise a given pattern we aim to recognise. Therefore,
objects are represented by strings of symbols belonging to \Sigma. On the other hand,
the FSM accounts for the (generally infinite) set of different strings corresponding to
the several ways a given object can be represented, while the error model accounts
for the typical variations that pattern strings tend to exhibit with regard to their
"standard" forms as represented by the FSM.
If no error model is given, the recognition problem amounts to a simple problem
of Finite-State parsing. Given an input string of symbols, we have to compute the
probability that this string belongs to the language generated by the FSM. From
this point of view, we are only interested in the maximum likelihood derivation
("Viterbi-like") of the string, instead of the sum of the likelihoods of every derivation
("Forward-like"). In a multiclass situation, where one FSM is provided for each
class, these probabilities can be used for recognition using the maximum likelihood
classification rule: the string is classified into the class represented by the FSM
whose probability of generating the string is maximum. However, in many cases,
test strings cannot be exactly parsed through any of these FSMs, leading to zero
probabilities for all the classes. This can often be solved through ECP.
If the FSM is deterministic, (non error-correcting) parsing is trivial. Otherwise,
the VA can be used. If an error model is provided, the same Viterbi framework
can be adopted for ECP, but at the expense of a higher computational cost. Unfor-
1 Note that this work is also related to the problem of (approximately) matching regular expres-
sions, since they are equivalent to FSMs. See [2] for an introduction to this problem.
tunately, this higher cost can become prohibitive in many applications of interest.
The computational problem of ECP is outlined in the next section. Solutions to this
problem are proposed in Sects. 3, 4 and 5. Sect. 6 describes the adaptation of the
well-known Beam Search technique [17] to further accelerate the parsing process.
Sect. 7 presents the experiments that have been carried out to test the performance
of the distinct approaches.
2 The Computational Problem of ECP
In general, the problem of Finite-State parsing with no error correction can be
formulated as a search for the "minimum cost" path 2 through a trellis diagram
associated to the FSM and the given input string, x. This trellis is a directed acyclic
multistage graph, where each node q j
k corresponds to a state q j in a "stage" k. The
stage k is associated with a symbol, x k , of the string to be parsed and every edge of
the trellis, t
stands for a transition between the state q i in stage k and
the state q j in stage k Thanks to the acyclic nature of this graph,
Dynamic Programming (DP) can be used to solve the search problem, leading to
the well-known Viterbi algorithm.
The trellis diagram can be straightforwardly extended to parse errors produced
by changing one symbol for another symbol and errors produced by inserting a
symbol before or after each symbol in the original string. In this way, taking only
substitution and insertion errors into account, efficient ECP can be implemented
because such an extended trellis diagram still has the shape of a directed acyclic
multistage graph (Fig. 1 (a) (b)).
Unfortunately, the extension of this trellis diagram to also parse errors produced
by deletion of one or more (consecutive) symbol(s) in the original string results in a
kind of graph with edges between nodes belonging to the same stage k (Fig. 1 (c)).
Nevertheless, if the FSM has no cycles, the resulting graph is still acyclic and DP
negative log probabilities and sums rather than products are used to avoid underflows.
(d)
(c)
(b)
(a)
K K
K K

Figure

1: Trellis a) Substitution and proper FSM transitions b) Insertion transitions
c) Deletion transitions in an acyclic FSM d) Deletion transitions in a cyclic FSM.
Each edge is actually labelled with a symbol of \Sigma
can still be applied, leading to an efficient algorithm that can be implemented as a
simple extension of VA [3]. However, if cycles exist in the FSM, then DP can no
longer be directly used and the problem becomes one of finding a minimum cost
path through a general directed cyclic graph (Fig. 1 (d)). As noted in [15], we can
still take advantage of the fact that most of the edges of this kind of graphs have a
left-to-right structure and consider each column as a separate stage like in the VA.
3 Solving the Problem by Score Ordering
Bouloutas et al [8] formulate an interesting recurrence relation to solve the problem
stated in Sect. 2. In our notation it is as follows:
l ) in stage k
8l in stage k
(1)
) is the cost of the minimum cost path from any of the initial states
to state q i in stage k;
is the inverse of the transition function, ffi, of the FSM;
k+1 ) is the cost of the minimum cost transition from state q i in stage k to
state q l in stage k
k+1 ) is the cost of the minimum cost path from
state q l to state q j , both of which are in stage k + 1. Its correctness lies in i , since
for each pair of states of the FSM its evaluation yields the cost of the minimum
cost deletion path between them. Fig. 2 shows the algorithm, called EV1, which we
developed from (1), with Q being the set of states of the FSM. Lines 1-3 will be
referred to as init-block, lines 12-16 as ins-subs-block and line as ret-block in the
remainder of the paper.
1. for each j 2 Q do
2. if j is an initial state then C(q j
InitialCost else C(q j
3. endfor
4. for to jxj do
5.
do
7.
8. for each
9. C(q j
10. endfor
11. endwhile
12. for each i 2 Q do
13. for each l 2 ffi(q i ) do
14. C(q l
C(q l
15. endfor
16. endfor
17. endfor
18. return argmin
for each final state i

Figure

2: Algorithmic scheme for EV1 and EV1PQ
Given that there are no transitions with a negative cost, Dijkstra's strategy is
followed in order to compute i (lines 6-11 in Fig. 2). All transitions from a state to
itself can be discarded to perform this computation. The state q l whose score in a
given parsing stage is minimum is chosen and the score of each j 2 ffi(q l ) is updated.
Again, the minimum-score state is chosen and the scores of its direct successors are
updated, and so on, until there are no states whose score could be updated. An
input string x can be parsed in \Theta(jxj \Delta using EV1 if no care about the
implementation of Q 0 is taken.
This algorithm can be further improved by using priority queues [1] in the implementation
of Q 0 . In this implementation, the scores (therefore the positions) of
the states in the heap need to be dynamically changed. This can be done by simply
storing the pointer to each state in the heap in order to perform a heapify operation
from the position of the state whose score has changed. The worst-case time complexity
of the loop in lines 6-11 of Fig. 2 is, in this case, O(jQj
given that at most jQj \Delta B operations will be performed in the heap [1], and with
B being the "Branching Factor" or maximum number of transitions associated to
each state in Q. Since B ! jQj in many cases, the worst-case time complexity of
this version of EV1 (called EV1PQ throughout the paper) to parse an input string
x is O(jxj log jQj). Note that if the FSM is a fully-connected graph, then
and the performance of EV1PQ can be worse than that of EV1.
4 Solving the Problem Iteratively
Another approach for coping with the deletion problem consists in performing consecutive
iterations to compute the minimum cost path to each state in any parsing
stage k (line 9 in Fig. 2), using only deletion transitions (Fig. 1 (c) (d)). If this iterative
procedure is performed until no score updating is produced then the properness
of the overall computation is guaranteed. This idea was independently proposed
in [20] and [15], though the paper by Hart and Bouloutas is more comprehensive.
Their work deals with many kinds of error rules and efficiently copes with their
associated computational problems. The resulting algorithm, called EV2, is shown
in Fig. 3.
Let T be the number of iterations to be done at lines 3-9 in Fig. 3. The time
complexity of these lines is O(T \Delta jQj \Delta B). T would be 1 if no deletion transition
changed the score of any state of the FSM [5]. If, at least, one deletion transition
per state changed the score of any other state through consecutive iterations then
T would be jQj can be produced if the states are traversed in reverse
topological or score order [5]). EV2 can thus parse an input string x in O(jxj \Delta jQj \Delta B)
1. init-block
2. for to jxj do
3. repeat
4. for each l 2 Q do
5. for each j 2 ffi(q l ) do
7. endfor
8. endfor
9. until C(q j
k ) has not been changed for any j 2 Q
10. ins-subs-block
11. endfor
12. ret-block

Figure

3: Algorithmic scheme for EV2
and O(jxj \Delta jQj 2 \Delta B) in the best and worst cases, respectively. Its performance in the
average case strongly depends on following some order of the states of the FSM as
closely as possible when parsing deletion transitions and on the number of "effective"
deletion transitions [5].
5 Solving the Problem by Depth-First Ordering
Here, we propose an algorithm based on a recurrence relation which extends previous
ideas of [20] for ECP with acyclic FSMs to general FSMs:
l ) in stage k
(2)
are the same as in equation (1);
is a generalisation
of function
which returns, for a given state q, the set of states that are
"topological predecessors" of q in the FSM, that is
is an initial state
and W T (q l
k+1 ) is the minimum cost path from state q l to state q j , both of
which are in stage k + 1, which only includes states that are topological predecessors
of state q j . The computation of W T can be performed by following a "topological
order" of the states of the FSM when parsing deletion transitions.
If the FSM has cycles, a depth-first "topological sort" of its states can be computed
by detecting the back-edges [3] (i.e., transitions which produce cycles in the
FSM). This leads to a fixed order for the traversal of the list of states of the FSM
during the parsing process. Backtracking becomes necessary to ensure the correctness
of the overall computation only if some back-edge coming from a state q i to
another state q j updates the cost of q j .
This is a solution for the problem stated in Sect. 2, but, unfortunately, it is not
directly compatible with Beam Search (BS) techniques. When using BS the list
of states to be traversed can be different in almost every parsing stage; therefore
large computational overheads could be introduced during the parsing process if
we had to compute a depth-first sort of the list of "visited states" in each parsing
stage. This can be avoided by depth-first sorting the states as they are visited, using
bucketsort (binsort) techniques [1]. We only need to use an adequate ordering key.
Our proposal is to compute and store the ordering key \Psi i 8i 2 Q as shown in Fig. 4.
1. for each i 2 Q do
2.
#back-edges coming to i
3. endfor
4. for each i such that ae do
5. for each such that the edge (q is not a back-edge do
7. ae
8. endfor
9. endfor

Figure

4: Computation of \Psi i 8i 2 Q. Both \Psi and ae have been implemented as arrays
It can be easily shown that the relation  on the set \Psi i 8i 2 Q is a partial
order [1]. Therefore, no pair of states q i and q j such that \Psi exists having a
transition (path) from q i to q j and vice versa. A permutation that maps Q into a
nondecreasing sequence \Pi(Q) can be found using \Psi by means of bucketsort. The
number of buckets to be used is max
. The depth-first traversal of the FSM, along
with the computation of \Psi i 8i 2 Q, can be performed in a preprocessing stage taking
only O(jQj \Delta B) computing steps [4, 5].
Once \Pi(Q) has been found, the only thing to worry about in a given parsing
stage is to find out when a back-edge is parsed. If
a back-edge is being parsed. Backtracking is performed only if the score of q j
is changed. Two algorithms based on equation (2), EV3 and EV3.V2, have been
developed [5]. In both algorithms \Pi(Q) has been implemented as a hash table. Fig. 5
shows EV3 algorithm. EV3.V2 is similar but it uses only the list \Pi(Q), performing
the parsing of insertion, substitution and deletion errors at once, while EV3 uses
both the (unsorted) list Q (for BS purposes, see next section) in the parsing of
insertions and substitutions and the list \Pi(Q) in the parsing of deletions.
1. init-block
2.
3. for to jxj do
4. for each l 2 \Pi(Q) do
5. for each j 2 ffi(q l ) do
7. if j 62 \Pi(Q) then Add j to bucket \Psi j in \Pi(Q) endif
8. if C(q j
k ) has been changed and \Psi
9. then backtrack to bucket \Psi j in \Pi(Q) endif
10. endfor
11. endfor
12. for each i 2 Q do
13. for each l 2
14. C(q l
C(q l
15. if l 62 \Pi(Q) then Add l to bucket \Psi l in \Pi(Q) endif
16. endfor
17. endfor
18. endfor
19. ret-block

Figure

5: Algorithmic scheme for EV3
The time complexity of lines 4-11 in Fig. 5 is the time of finding \Pi(Q) times the
maximum branching factor (B). \Pi(Q) is found using bucketsort. The complexity
of bucketsort to sort n elements is O(n +m), with m being the number of buckets.
In this case
\Psi i is clearly bounded by jQj (see Fig. 4). In
the best case (no back-edge requires a backtracking recomputation) the resulting
time complexity is, therefore, O(jQj \Delta B). In the worst case there will be a linear-on-
jQj number of back-edges requiring a backtracking recomputation of all the paths
already computed 3 [20], leading to O(jQj 2 \Delta B) time complexity.
EV3 and EV3.V2 can parse an input string x in O(jxj \Delta jQj \Delta B) and O(jxj \Delta jQj 2 \Delta B) in
the best and worst cases, respectively. The performance on the average case not only
depends on the structure of FSMs but also on the number of back-edges that require
a backtracking computation from the state that is reached by them. A theoretical
formulation of this average cost is very difficult and it requires assumptions on
probabilistic distributions over the space of possible FSMs, which is not always
feasible.
6 Beam Search
Beam Search [17] (BS) is a classical acceleration technique for VA. This search technique
often yields approximately optimal (or even optimal) solutions while drastically
cutting down the search space [22, 5]. In this respect, BS is comparable to
other "clever" strategies based on A   search, such as that proposed in [14]. The idea
is to keep only a "beam" of "promising" paths at each stage of the trellis. The beam
width is a constant value to be empirically tuned to achieve an adequate tradeoff
between the efficiency and the accuracy of the search. The lower this parameter,
the lower the accuracy and the lower the computing time, and vice versa.
The implementation of BS consists in keeping only the paths ("visited states")
with a score which is lower than a given bound. For the sake of efficiency, this bound
is implemented by adding the currently found lowest score to the beam width [22].
Q is implemented as a double linked list, leaving the first place for this lowest-score
state, to avoid overhead. This strategy generally results in no significant differences
3 This upper bound is quite pessimistic since it assumes that after the depth-search ordering,
the resulting number of back-edges that change the score of some state is linear on jQj.
with regard to a strict implementation of BS. The extension of the algorithms EV1,
EV1PQ and EV2 to perform BS is straightforward [4, 5]. In the case of EV3 and
EV3.V2 the extension is easy thanks to the ordering key \Psi, which allows for building
the list \Pi(Q) as the states are visited (see Sect. 5). EV1, EV1PQ and EV2 use the
linked list, but slight differences in the number of visited states can exist due to the
fact that EV1 and EV1PQ parse deletion transitions in score order. EV3 also uses
the linked list to be able to tightly follow this BS strategy. Again, slight differences
can exist, but only due to the fact that EV3 parses only the deletions in "topological"
order while EV3.V2 parses all transitions following this order. This is a problem for
the computation of the first bound value to be used in the next parsing stage k
since it is likely that the first state in \Pi(Q) is not the minimum-score one. EV3.V2
overcomes this problem by computing an approximate bound value as the minimum
cost edge of the lowest-score state found in parsing stage k plus the beam width. In
practice, the differences in the number of visited states among all algorithms prove
to be negligible [5].
7 Experiments and Results
Two series of experiments were carried out in order to assess both the effectiveness
(parsing results) of ECP and (mainly) the efficiency (speed) of the algorithms previously
discussed. In the first case, ECP was used to "clean" artificially distorted
sentences from a Language Learning task called "Miniature Language Acquisition"
In the second case, ECP was applied to recognise planar shapes (hand-
written digits), coded by chain-coding the contours of the corresponding images [18].
In both cases, the required stochastic FSMs were automatically learned by means
of the k-TSI Grammatical Inference algorithm proposed in [12]. This algorithm
infers a (stochastic) FSM that accepts the smallest k-Testable Language in the
Strict Sense (k-TS language) that contains the training sentences. Stochastic k-TS
4 This consists in a pseudo-natural language for describing simple visual scenes, with a vocabulary
of 26 words.
languages are equivalent to the languages modeled by the well-known N-GRAMS,
with Increasing values of k from 2 to 10 (2 to 7) were used in the first
(second) series of experiments. This yielded increasing size FSMs as required for
studying the computational behaviour of the different algorithms. In all cases, only
roughly hand-tuned error-model parameters were used. All the experiments were
carried out on an HP9000 Unix Workstation (Model 735) performing 121 MIPS.
7.1 Language Processing Experiments
A set of nine stochastic FSMs, ranging from 26 to 71; 538 states, which were automatically
learned from 50; 000 (clean) sentences of the MLA task [9] were used in
these experiments. The test set consisted of 1; 000 sentences different from those
used in training. It was distorted using a conventional distortion model [16] in order
to simulate the kinds of errors typically faced in speech processing tasks. This
generally resulted in sentences which no longer belonged to the languages of the
learned FSMs. Three different percentages of global distortion, which were evenly
distributed among insertion, deletion and substitution parameters, were used:
5% and 10%.
The effectiveness of ECP is summarised in Table 1. The quality of parsing was
measured in terms of both word error rate (WER) 5 between the original (undis-
torted) test sentences and those obtained by ECP (from the corresponding distorted
sentences), and test-set Perplexity (PP) 6 . These results were obtained without
BS and were identical for all the algorithms. For adequately learned k-TS models
the distortion (WER) of test sentences was reduced by a factor ranging
from 2 to 3; the best results obtained by the 6-TS model with 3; 231 states.
Perplexity figures closely follow the tendency of WER. Values of k greater than 6
tended to degrade the results, due to the lack of generalisation usually exhibited
5 minimum number of insertions, substitutions and deletions.
6 2 to the power of the Cross-Entropy, which is the sum of the maximum log-likelihood score for
each input distorted test sentence divided by the overall number of parsed words [23].
by k-TS models as k is increased beyond a certain value (6 in this case). This is
explicitly assessed by the column labelled N in Table 1, which shows the number
of original (undistorted) test sentences that would not have been accepted by the
corresponding k-TS models without ECP 7 .

Table

1: Parsing results in terms of Word Error Rate (WER-%) and test-set Perplexity
(PP) for each FSM without BS in the LP experiments
Distortion 1% Distortion 5% Distortion 10%
jQj (value of
26 (2) 0 0.43 4.36 2.19 5.55 4.80 7.28
71; 538 (10) 475 3.73 3.48 4.87 4.15 6.32 5.29

Table

2: WERs and PPs for each Beam width using the FSM with 3; 231 states
in the LP experiments
Distortion WER PP WER PP WER PP
5% 3.46 4.23 1.70 3.87 1.70 3.87
10% 6.08 5.71 3.59 5.17 3.32 5.15

Table

2 shows the effect of using BS in the ECP process for the 6-TS model
(3; 231 states) using EV1. Only negligible differences were observed for the other
algorithms, due to the distinct ways BS is implemented [5]. Four increasing values
of beam width (ff) were tested: 5, 10, 20 and 40 (1 means no BS). Setting ff to 20
provided results identical to those achieved by a full search (see also Table 1), while
a further decreasing of ff gracefully degrades the results.
Fig. 6 shows the relative efficiency of the different algorithms for increasing FSM
7 It is notable that even with almost 50% undistorted test sentences rejected without ECP, a
noticeable distortion reduction is still achieved for 10% and 5%-distorted sentences. Therefore,
proves useful not only in dealing with imperfect input, but also in improving the effectiveness
of imperfect FSMs.
Computation
time
(in
centiseconds)
Number of states in FSM

Figure

Average computing times (in centiseconds) of the different algorithms measured
without BS for 10% of distortion in the LP experiments
sizes without BS. Only results for 10% of distortion are reported; the results were
similar for 5% and 1%. The variance observed in these results was negligible. More
specifically, the standard deviation of the computing time per symbol parsed was
never greater than the 6:7% of the average computing time per symbol parsed. This
means that, with a probability close to 1, the real computing times will match their
corresponding expected values. A dramatically higher computational demand of
EV1 is clear in this figure. The use of priority queues (EV1PQ) to compute i
contributes to alleviating the computational cost, though the resulting jQj: log jQj
time complexity is still exceedingly high. The two implementations of EV3 show a
much better (linear-on-jQj) performance 8 . EV2 also shows linear time complexity
but with a slope which is larger than that of EV3. This is due to the number of
iterations required for the parsing of deletion transitions [5].
Figs. 7 and 8 show the impact of BS in the performance of the different algorithms.
Fig. 7 shows the effect of increasing the distortion rate for a fixed ff 9 (20; i.e., results
8 The observed computing times of the preprocessing stage for EV3 and EV3.V2 (see Sect. 5)
were negligible, ranging from less than a centisecond (for the smallest FSM) to 36 centiseconds
(for the largest FSM).
9 Differences between scores through consecutive parsing stages tend to level as larger errors are
produced. Therefore, an increase in the distortion produces an increase in the rate of visited states
1% dist.0,2
0,4
0,6
Computation
time
(in
centiseconds)
Number of states in FSM0,51,52,53,54,55,5
Computation
time
(in
centiseconds)
Number of states in FSM
5% dist.0,51,52,53,54,55,50 10000 20000 30000 40000 50000 60000 70000 80000
Computation
time
(in
centiseconds)
Number of states in FSM
10% dist.

Figure

7: Average computing times observed for each distortion rate and in the
LP experiments
identical to full search). With 1% of distortion, the number of visited states is very
small and all the algorithms perform fairly well. With 5% and 10% of distortion, EV1
is again highly cost-demanding. EV1PQ also tends to have higher computational
costs. EV2 and EV3 show the best performance and, by also using BS, EV3 gets
the best results for the larger FSMs. Finally, Fig. 8 shows the effect of the different
ff for the highest distortion rate (10%). Significant differences exist for ff  20. It
should be taken into account that when ff is smaller than 20, only suboptimal results
are produced (see Tables 1 and 2). The best results are systematically achieved by
EV3 and EV2, although EV3 clearly outperforms EV2 when the number of visited
states is higher than a certain bound. See [5] for further details on this experimental
study.
7.2 OCR Experiments
In these experiments, 2; 400 images of handwritten digits were used. Strings representing
these images were obtained by following their outer contour using a chain-code
of eight directions [18]. The resulting string corpus was randomly split into
(for a given ff).
0,4
0,6
Computation
time
(in
centiseconds)
Number of states in FSM
0,4
0,6
Computation
time
(in
centiseconds)
Number of states in FSM
Computation
time
(in
centiseconds)
Number of states in FSM
Computation
time
(in
centiseconds)
Number of states in FSM

Figure

8: Average computing times (in centiseconds) observed for 10% of distortion and
Beam width values 5, 10, 20 and 40 in the LP experiments
disjoint training and test sets of the same size. The training set was used to automatically
learn six different stochastic k-TS FSMs per digit using values of k from
2 to 7. For each value of k, the 10 k-TS models learned for each of the 10 classes
(digits) were merged into a whole global model, with class-dependent labelled final
states. This resulted in six stochastic FSMs of increasing size, ranging from 80 to
states. Testing was carried out using the maximum likelihood classification
rule as mentioned in Sect. 1. Table 3 shows the overall recognition rates achieved
with ECP without BS. The FSM with 18; 416 states gets the best results;
further decreasing of the value of k tended to degrade the effectiveness. Informal
tests show that recognition rates without ECP drop below 50% for all the models.

Table

3: Recognition rate (%) achieved in the OCR experiments for each FSM
jQj (value of
Recog. rate 75.8 90.8 95.1 97.2 97.2 97.5
Computation
time
(in
centiseconds)
Number of states in FSM

Figure

9: Average computing times (in centiseconds) of the different algorithms measured
without BS in the OCR experiments
Fig. 9 shows the observed average parsing times for each ECP algorithm without
BS. The observed variance was also negligible (the observed standard deviation
of the computing time per symbol parsed was never greater than the 7:2% of the
average computing time per symbol parsed). Again, the performance achieved by
much better than that of the other algorithms. The performance of EV2
was, in this case, worse than the one observed in the previous set of experiments (in
even EV1PQ outperformed EV2). This is because EV2 significantly depends
on specific conditions of data (see [5]).
The impact of BS was studied for the model supplying the best recognition results;
namely the 7-TS model with 18; 416 states (see Table 3). The results are shown in

Table

4. In this case, none of the values of ff tested yielded identical recognition
rate as that achieved by full search (97:5%). However, a width of 30 appears to be
a good tradeoff between efficiency and recognition rate. The fastest performance
using BS was again achieved by EV2 and EV3. The differences among the different
algorithms were more significant for the widest beam (30). In this case, EV3 was
about 1.5 times faster than EV2 and 1.7 times faster than EV1PQ.
10 The observed computing times of the preprocessing stage for EV3 and EV3.V2 were again
negligible, ranging from less than a centisecond to 7 centiseconds.

Table

4: Impact of using BS in recognition rate (%) and computing time (centiseconds)
in the OCR experiments
ff Recog. rate EV3 EV3.V2 EV2 EV1PQ EV1
Concluding Remarks
Several techniques have been proposed for a cost-efficient implementation of Finite-State
Correcting Viterbi Parsing. This is a key process in many applications
in areas such as Syntactic Pattern Recognition, Language Processing, Grammatical
Inference, Coding Theory, etc. A significant improvement in parsing speed with regard
to previous approaches can be achieved by the EV3 algorithm which is proposed
here. Furthermore, a dramatic acceleration can be achieved by applying suboptimal
Beam Search strategies to the proposed algorithms. All the algorithms developed
allow for integration with this search strategy, although minor differences in the rate
of visited states lead to small differences in performance. In this case, EV3 has also
exhibited better behaviour than all the other algorithms.
9

Acknowledgements

The authors wish to thank the anonymous reviewers for their careful reading and
valuable comments. Work partially funded by the European Union and the Spanish
CICYT under contracts IT-LTR-OS-30268 and TIC97-0745-C01/02.



--R

The Design and Analysis of Computer Algorithms.
"Algorithms for Finding Patterns in Strings"
"Fast Viterbi decoding with Error Correction"
"Two Different Approaches for Cost-efficient Viterbi Parsing with Error Correction"
"Different Approaches for Efficient Error-Correcting Viterbi Parsing: An Experimental Comparison"
"Simplifying Language through Error-Correcting Decoding"
"Decoding for Channels with Insertions, Deletions and Substitutions with Applications to Speech Recognition"
"Two Extensions of the Viterbi Algorithm"
"Miniature Language Acquisition: A touchstone for cognitive science"
"The Viterbi algorithm"

"Inference of k-testable languages in the strict sense and application to
An Introduction.
"Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes"
"Correcting Dependent Errors in Sequences Generated by Finite-State Processes"
"Evaluating the performance of connected-word speech recognition systems"
"The Harpy Speech Recognition System"
"A Comparison of Syntactic and Statistical Techniques for Off-Line OCR"
"On the BCJR Trellis for Linear Block Codes"

Time Warps
"Fast and Accurate Speaker Independent Speech Recognition using structural models learnt by the ECGI Algorithm"

"Codes and Iterative Decoding on General Graphs"
--TR

--CTR
Christoph Ringlstetter , Klaus U. Schulz , Stoyan Mihov, Orthographic Errors in Web Pages: Toward Cleaner Web Corpora, Computational Linguistics, v.32 n.3, p.295-340, September 2006
Juan-Carlos Amengual , Alberto Sanchis , Enrique Vidal , Jos-Miguel Bened, Language Simplification through Error-Correcting and Grammatical Inference Techniques, Machine Learning, v.44 n.1-2, p.143-159, July-August 2001
Francisco Casacuberta , Enrique Vidal, Learning finite-state models for machine translation, Machine Learning, v.66 n.1, p.69-91, January   2007
depth-first topological sort;shape recognition;viterbi algorithm;priority queues;error-correcting parsing;beam search;sequence alignment;language processing;bucketsort