2 Formal background

We assume that the reader is familiar with the basic notions of formal language theory as described, e.g., by Hopcroft, Motwani and Ullman (2000) or Kozen (Reference Kozen1997). More background on transducers and their use can be found in Roche and Schabes (Reference Roche, Schabes, Roche and Schabes1997). In the remainder of the paper, the symbols Σ and Δ always denote finite alphabets. As usual, Σ* (resp. Σ⁺) denotes the set of all (resp. all non-empty) strings over Σ, and similarly for Δ. The symbol ε denotes the empty word. If w is any string, then |w| denotes the length of w. The concatenation of the strings u and w is written u.w or uw. If f is any function, then Dom(f) denotes the domain of f.

2.1 Dictionary-based text rewriting with leftmost-longest-skip strategy

Definition 2.1 A rewriting dictionary is a partial function D :Σ⁺ → Σ* with finite domain. By an entry of D, we mean an element w of Dom(D). If w is an entry of D, the string D(w) is called the substitute for w. The set CoDom(D) := D(w) w ∈ Dom(D) is called the codomain of D.

In this paper, the terms “string” and “text” are used synonymously.

Definition 2.2

By an occurrence of a dictionary entry w in the t∈Σ*, we mean a triple 〈u,w,v〉ε(σ*)³ such that t=uwv. The strings u and v are respectively called the pre-text and the post-text of the occurrence.

Definition 2.3

The occurrence 〈u,w,v〉ε(Σ*)³ is called leftmost iff its pre-text is minimal with respect to all pre-texts of occurrences of dictionary entries in t. It is called leftmost-longest if it is leftmost and if w is of maximal length among all leftmost occurrences of dictionary entries in t. If there is any occurrence of a dictionary entry in t, then there exists a unique leftmost-longest occurrence, denoted lml _D(t).

Example 2.4

Consider the rewriting dictionary D given by the mapping

and the text t=abcbbbabccb. Among nine distinct occurrences of dictionary entries in t, there are two occurrences of ab, which respectively have the form 〈ε, ab, cbbbabccb〉 and 〈abcbbb, ab, ccb〉. We have 〈ε, ab, cbbbabccb〉 = lml _D(t).

Definition 2.5

The set of all leftmost-longest-skip occurrences of dictionary entries in t, denoted Lmls _D(t) is recursively defined in the following way:

Remark 2.6

It is simple to see that two distinct occurrences 〈u, w, v〉, 〈u', w', v'〉 ∈ Lmls _D(t) are always disjoint in the sense that either |u'|≥|uw| or |u|≥|u'w'|. Hence there exists a unique representation of t in the form t=u ₁. w ₁ . . . u _k. w _k. u _k+1 where w _i are entries of D (1≤ i≤ k) and u _j ∈ Σ* (1≤ j≤ k+1) such that

Example 2.7

Let D denote the dictionary from Example 2.4, let t = abcbbbabccb. Then Lmls _D(t) is the set with the following tuples:

Definition 2.8

The canonical lmls-extension of D is the function D ^lmls: Σ*→Σ* recursively defined in the following way:

Example 2.9

Let D denote the dictionary given in Example 2.4, let t= abcbbbabccb. Then D ^lmls (t) = ε · ε · bb · 4 ε · 5 b = 25bb45b.

The following corollaries follow immediately.

Corollary 2.10

Let 〈 u, w, v〉 ∈ Lmls _D(t) where t= u. w. v. Then D ^lmls (t) = D ^lmls (u. w). D ^lmls (v).

Corollary 2.11

Let a ₁ ∈ Σ. Assume that no prefix of t=a ₁. t' is in the domain of D. Then D ^lmls (t) = a ₁. D ^lmls (t').

2.2 Subsequential transducers

Definition 2.12

A subsequential transducer is a tuple = 〈 Σ,Δ,Q, q ₀, F, δ, λ, ε〉, where:

• • Σ is a finite input alphabet;

• • Δ is a finite output alphabet;

• • Q is a finite set of states;

• • q ₀ ∈ Q is the start state;

• • F Q is the set of final states;

• • δ : Q × Σ → Q is a partial function called the transition function;

• • λ : Q × Σ → Δ* is a partial function called the transition output function; we have Dom(λ) = Dom(δ);

• • ε : F → Δ* is the state output function.

The extended transition function δ*: Q×Σ*→ Q is defined in the usual way:

Since δ is partial, the same holds for δ*, the definition is restricted to input strings that can be consumed by the transducer. Similarly we define the extended transition output function λ*: Q ×Σ*→ Δ* in the following way:

Also λ* is a partial function. The set L() = { t ∈ Σ* δ* (q ₀, t)∈ F is called the input language of the transducer . The subsequential transducer maps each word of the input language to an output word. The output function of the transducer is defined as follows:

Denition 2.13

A subsequential transducer is said to represent the function f: Σ* → Δ* iff .

3 Informal description of the algorithm

Before we turn to the formal details of the algorithm, we use the dictionary

introduced in Example 2.4 to illustrate the main idea. The construction of the transducer for text-rewriting based on the dictionary D proceeds in two steps. The first step is straightforward.

First Step. We construct a tree-shaped transducer that represents (in the sense of Definition 2.13) the dictionary. To this end, we compute the trie for the domain Dom(D) of D. The output of each transition is set to the empty word. If w is an entry of D, then the final state corresponding to w emits the output D(w). Figure 1 shows the subsequential transducer trie _D for the rewriting dictionary D introduced in Example 2.4.

Fig. 1.

Subsequential transducer trie for the rewriting dictionary D introduced in Example 2.4.

Obviously the number of states in the resulting transducer _D does not exceed the total number of symbols in the list of all dictionary entries. In what follows, if q is any state of _D, then α_q denotes the sequence of input transition labels of _D for the unique path leading from the start state q ₀ to q.

Second Step. Given _D we construct a transducer that represents (in the sense of Definition 2.13) the canonical lmls-extension D ^lmls of D. The set of states of _D is not modified. Similarly the output of the final states of _D is not changed. Furthermore, each transition of _D remains a transition of . Hence, _D is only extended. Since must accept any text, we must be able to depart from any state with any symbol of the input alphabet. This means that suitable failure transitionsFootnote ⁴. have to be added. Furthermore, each state has to be treated as a final state. The main difficulty is the definition of the output of failure transitions and final states. The reader should keep in mind that the output of a final state q is only emitted if we reach q at the end of the input string.

To introduce missing transitions and to define suitable outputs, we visit all states q of _D. For any state p, let d(q ₀, p) denote the number of transitions in _D that are needed to reach p, starting from q ₀. When we visit a state p we always assume that all states p' such that d(q ₀, p') < d(q ₀, p) have been visited before. We assume that a list (p ₁, p ₂., p _h) is given that describes one possible visiting order for the states of Q _D that respects this constraint. Note that q ₀=p ₁.

We begin with q ₀. When reading a text t, we want to be in state q ₀ at text position k only if k corresponds to an offset point where the naïve algorithm starts a new subscan. This means that position k is not inside a relevant left-most occurrence of an entry of D. Furthermore, the output for the prefix of the text ending at k is completed. State q ₀ is declared to be final and the output is the empty string. For all letters σ where we do not have a transition from q ₀ in _D, we add a transition σ with output σ to the transducer. Recall that the naïve algorithm outputs σ and immediately starts a new scan from position k+1. In our example, we have to add a transition for input letter d.

Definition of state outputs

The state output for a state q ≠ q ₀, reached with the non-empty string α_q, encodes the translation result D ^lmls(α_q). A compositional description of D ^lmls(α_q) can be obtained, analyzing how the naïve algorithm processes the string α_q). Since α_q represents a prefix of an entry of D, the algorithm proceeds in single forward move until the end of the string is found. At this point, a suitable output v is produced and the algorithm continues from a new offset point l > 0. The offset point l defines a partitioning of α_q = u ₁u ₂ into substrings u ₁, u ₂ in the obvious way, cf. Figure 2.

Fig. 2.

Scanning a string α_q representing a prefix of an entry of D.

Both v and l depend on the form of α_q. If some prefix of α_q represents an entry of D, and if u _l is the maximal prefix of this form, then v = D(u _l) and l marks the end of u _l (for u ₁ = α_q, position l marks the end of the text.) Otherwise, if no prefix of α_q is an entry of D, then v is the first letter of α_q and l=k+1. Note that in both cases we have v= D ^lmls (u ₁).

The output v represents a first component of the state output D ^lmls(α_q) for q. The second component of D ^lmls(α_q) corresponds to D ^lmls(u ₂), the output of the naïve algorithm when processing u ₂. The important point to note is that u ₂ is shorter than α_q. This guarantees that starting from q ₀, all transitions for input u ₂ are defined, and also the state output for the final state p' that is reached is already encoded in the present transducer. This leads to the following compositional description of the state output for q:

Using the partially defined transducer, all components are already available.

As an example, consider the situation in Figure 3, where states q ₀ = p ₁,. . . p ₆ have been visited. For q=p ₇ we have α_q = abc, u ₁=ab, u ₂ = c. The state p' reached with u ₂ = c is p' = p ₄. Following the above equations, the state output for p ₇ is D(ab).ε. 5=25. For q=p ₈ we have α_q = bab, u ₁=b, u ₂=ab, p'=p ₅. Hence the output of p ₈ is b. ε 2=b2.

Fig. 3.

Construction of the subsequential transducer for the canonical lmls extension of the dictionary given in Example 2.4. Situation after states q ₀ = p ₁,. . . p ₆ have been visited.

Definition of target states and outputs for failure transitions. Consider a state q and a symbol Σ where we do not have a transition from q with Σ in _D. We first explain how to define the target state of the transition. When scanning α = _qσ, the naïve algorithm proceeds in a forward move until it finds the letter Σ. Since by assumption α = _qσ is not a prefix of an entry of D, the algorithm produces some output v and continues from a new offset point l>0. The offset point l defines a partition of α_q =u ₁u ₂ in the obvious way. The situation is depicted in Figure 5. As above we have v = D ^lmls (u ₁). Now assume that we process input u ₂ (resp. u ₂σ) with the transducer defined so far. Since u ₂ is shorter than α_q all needed transitions are already defined. We arrive at state p' (resp. q'). In this situation, q' represents the target state for the failure transition from q with Σ. Note that in general the path from q ₀ to p' and q' may contain several failure transitions.

It may be shown that the string α_q' represents a suffix of α_qσ = w.α_q' (cf. Part 1 of Lemma 5.2 below). The translation resultw of the corresponding prefix w, D ^lmls(w), represents the output of the failure transition. As above, for the algorithm we need a compositional description of D ^lmls(w).

Clearly, u _l is a prefix of w=u ₁. w ₂. The choice of l as a backtracking point guarantees that D ^lmls(w)= D ^lmls (u ₁). D ^lmlsw ₂). We shall see in Lemma 5.2. Part 2, that D ^lmls(w ₂) is the transition output of the transducer for input w ₂.α_q' = u ₂.σ. Hence we obtain the following description of the output for the transition with letter σ from state q:

As above, using the partially defined transducer, all components are already available.

Again consider the situation in Figure 3, where states q ₀=p ₁. . ., p ₆ have been visited. For q=p ₇ and σ =d we have α_q = abc, u ₁=ab, u ₂=c. The state p' reached with u ₂=c (resp. u ₂σ) is p ₄ (resp. q ₀). Hence the failure transition for q, d leads to q ₀. Following the above equations, the transition output for the transition is 2. ε· 5d=25d. For q=p ₈ and σ = d we have α_q = bab, u ₁=b, u ₂=ab. The state p' reached with u ₂ (resp. u ₂σ) is p'=p ₅ (resp. q ₀). Hence the failure transition for q, d again leads to q ₀. The transition output is b. ε. 2d=b2d.

The transducer that is obtained after visiting all states of _D is shown in Figure 4.

Fig. 4.

The subsequential transducer for the canonical lmls extension of the dictionary given in Example 2.4.

Fig. 5.

Scanning substring α_q·σ.

4 The algorithm

We now formally describe the construction of the subsequential transducer for text rewriting based on a dictionary D. As we made clear in the previous section, the constructions proceeds in two steps.

4.1 Construction of the subsequential transducer trie for the dictionary

The following construction of the subsequential transducer trie for a given rewriting dictionary D is well-known and only described for convenience and to fix notation. We assume that D is represented as a finite list of pairs of words of the form

Here α_i ε Σ+, β_iε Δ* and α_i not = α_j for 1 ≤ i, j ≤ n, i≠ j. We start with the empty transducer ₀, which is defined as the tuple

Each of the following steps adds a new word pair to the subsequential transducer. Let us assume that we have constructed the subsequential transducer

representing the dictionary D _k-1 = {〈α_i, β_i〉 ∈ D | i ∈ 1, 2,. . ., k−1}} for some k, 1 ≤ k ≤ n. We next have to add the pair 〈αk, β_k to the transducer. Let α_k = a ₁ . . . a _m and let a ₁. . . a _l denote the maximal prefix of α_k such that δ_k-1*(a ₁. . . a _l) is defined. Here l≤ m. We introduce a set q' with m−l new states q _l+1, q _l+2, . . ., q _m and define

where

and

Obviously, _k represents the dictionary D _k = {〈α_i, β_i〉 ∈ D | 1 ≤ i ≤ k}. Hence, after n steps we obtain the transducer

which represents D. _D is tree-shaped, output is only produced when reaching a final state after completely consuming the input. Furthermore, each state q∈ Q _D can be reached with exactly one word. As before, by α_q we denote the unique string in Σ* such that δ*_D(q ₀, α_q) = q and d(q _0,q)= | α_q | denotes the number of transitions in _D that are needed to reach q, starting from q ₀ (q∈ Q _D).

4.2 Canonical lmls-extension of _D

To define the transducer for text rewriting based on the given dictionary D we visit all states of _D. When visiting a state q, we declare q to be final, define the state output and add missing transitions such that for each σ∈ Σ we have exactly one transition departing from q with input letter σ. As described above, when visiting q we always assume that all states q' such that d (q ₀, q') < d (q ₀, q) have been visited before. We assume that a list (p ₁, p ₂, . . ., p _h) is given that describes a possible visiting order for the states of Q _D that respects this constraint. Note that q ₀=p ₁.

The transducer that results from our visit at q ₀ is

where

Let us assume that after visiting p _i (where 1 ≤ i < h) we have constructed the transducer

Let q=p _i+1 denote the next state on our list of states to be visited. Let α_q = a ₁. . . a r. For 1 ≤ j ≤ r, let q _j := δ_D*(q ₀, a ₁. . . a _j). Hence q ₀,. . ., q _r denotes the sequence of states on the path of _D leading from q ₀ to q. We distinguish two cases:

Case 1: Path q ₀, q ₁,. . ., q _r does not contain a final state of _D. In this case, p′ := δ_i′*(q ₀, a ₂a ₃ . . . a _r) is defined, by choice of the visiting order. Let p′ := δ′_i*(q ₀, a ₂a ₃ . . . a _r) and γ := a ₁ . . . λ′_i*(q ₀, a ₂a ₃ . . . a _r). We define

where

Case 2: Path q ₀, q ₁,. . ., q _rcontains a final state of _D. Let q _f denote the last final state of _D on this path.Footnote ⁵ This means that δ_D*(q ₀, a ₁a ₂ . . . a _f) = q _f ∈ F_D and q _f+1, q _f+2,. . ., q _r cap F _D = ∅. Let p′ := δ′_i*(q ₀, a _f+1a _f+2 . . . a _r) and γ' := ε_D(q _f) . . . λ'_i* (q ₀, a _f+1a _f+2. . . s a _r). We define

where

The transducer

obtained after the final step h represents the output of our algorithm.

5 Correctness of the algorithm

We now show that the above algorithm is correct.

theorem 5.1

Let D be a rewriting dictionary. Then the transducer computed by the above algorithm represents the canonical lmls-extension D ^lmls of D, in the sense of Definition 2.13.

The theorem follows immediately from Part 5 of the following Lemma.

Lemma 5.2

Let t = σ₁. . . σ_n ∈ Σ*. Let q := δ*(q ₀, t). Let α= α_q denote the unique word such that δ^D* (q ₀, α) = q. Then

1. 1. α is a suffix of t.

Furthermore, if t = t₀ · α, then

proof

We first remark that Property 5 is a consequence of the given partitioning of t and Properties 2-4. In fact, with α₀ := α we obtain

To verify Properties 1-4 we use induction on the length n of the text t. If n=0, then t=t ₀=α is the empty string and all claims are trivial. Assume that the claims are correct for n.

Let t' :=σ₁. . .σ_nσ_n+1 and q' := δ*(q ₀, t'). Let t=σ₁. . .σ_n, q, t ₀ and α as in the lemma.

Case 1. δ_D (q, σ_n+1) is defined. Then q' = δ_D (q, σ_n+1) and δ_D(q ₀,α. . . σ_n+1) = q'. Obviously α = α σ_n+1 is a suffix of t' = t ₀ . . . α', hence Claim 1 is satisfied. In what follows we consider the partitioning t' = t ₀ α' of t'. We have λ (q,σ_n+1) = ε. Induction hypothesis 2 for t yields

which shows that Claim 2 is satisfied. Claim 3 is trivial. We prove Claim 4. Let α' have the form a ₁a _r. This means that a ₁,. . ., a _r is the sequence of input transition labels on the path of _D from q ₀ to q'.

Subcase 1.1. First assume that there is no final state of _D on the path from q ₀ to q′. In this case our construction implies that

Furthermore, no prefix of a ₁ . . . a _r belongs to the domain of D. Hence Corollary 2.11 yields D ^lmls(α) = D ^lmls (a ₁. . . a r) = a ₁D ^lmls (a ₂. . . a _r). Applying the induction hypothesis to the text a ₂. . . a _r we get (cf. Claim 5)

Hence D ^lmls(α')= ε(q'), which shows that Claim 4 is satisfied.

Subcase 1.2. There exists a final state of _D on the path from q ₀ to q'. Let q _f denote the last state on the given path that is final. Let a ₁. . . a _f denote the sequence of input transition labels from q ₀ to q _f. In this case our construction implies that

Furthermore, since a ₁. . . a _f is a leftmost-longest occurrence within α' = a ₁. . . a _r it follows from Corollary 2.10 (or from the recursive Definition 2.8) that D ^lmls(α′) = D ^lmls (a ₁. . . a _r)= D(a ₁. . .a _f). . .D ^lmls (a _f+1. . . a _r). Since the output of the final states of _D is not changed in we have D(a ₁. . . a _f)= ε(q _f). Since q ₀≠ q _f, the induction hypothesis (Claim 5) applied to a _f+1. . . a _r yields

Hence D ^lmls(α′) = Ψ(q′), which shows that Claim 4 is satisfied.

Case 2.1. δ_D(q,σ_n+1) is not defined and there is no final state of _Don the path from q ₀ to q. Let a ₁. . .a _r denote the sequence of labels on the path from q ₀ to q. In this case our construction yields q′ = δ(q,σ_n+1) = δ*(q ₀,a ₂. . .a _rσ_n+1) and λ(q,σ_n+1)= a ₁· λ*(q ₀,a ₂. . .a _rσ_n+1). Let α′ denote the unique word such that δ_D(q ₀,α′) = q′. The induction hypothesis applied to a ₂. . .a _rσ_n+1 shows that α′ is a suffix of a ₂. . .a _rσ_n+1 = α″·α′, hence α′ is a suffix of t′ = t ₀ · a ₁ · α″ · α′, which shows that Claim 1 holds. Let t ₀′ := t ₀ · a ₁ · α″. Applying the induction hypothesis (Claim 3, α₀ := a ₁·α″) we get D ^lmls(t ₀′) = D ^lmls(t ₀) · D ^lmls(a ₁ · α″). Our assumption implies that no prefix of a ₁ · α″ is in the domain of D. Corollary 2.11 shows that D ^lmls(a ₁ · α″) = a ₁ · D ^lmls(α″), hence D ^lmls(t ₀′) = D ^lmls(t ₀) · a ₁ · D ^lmls(α″). The induction hypothesis (Claim 2) for t yields D ^lmls(t ₀) = λ*(q ₀,t). The induction hypothesis (Claim 2) for a ₂. . .a _rσ_n+1 yields D ^lmls(α″) = λ*(q ₀,a ₂. . .a _rσ_n+1). From the definition of the λ_i′-functions we get a ₁ · λ*(q ₀,a ₂. . .a _rσ_n+1)=λ(q,σ_n+1), hence we obtain

which proves Claim 2.

We prove Claim 3. Let γ ∈ σ*, let α₀ be any prefix of α′·γ. By induction hypothesis (3) for t we have D ^lmls(t ₀′·α₀) = D ^lmls(t ₀ · a ₁ · α″·α₀) = D ^lmls(t ₀) · D ^lmls(a ₁ · α″·α₀). Our assumption implies that no prefix of a ₁ · α″·α₀ is in the domain of D. Corollary 2.11 shows that D ^lmls(a ₁ · α″·α₀)= a ₁ · D ^lmls(α″·α₀). Induction hypothesis (3) for a ₂. . .a _rσ_n+1 implies that D ^lmls(α″·α₀) = D ^lmls(α″) · D ^lmls(α₀). Hence we have D ^lmls(t ₀′·α₀) = D ^lmls(t ₀) · a ₁ · D ^lmls(α″) · D ^lmls(α₀). As above it follows that D ^lmls(t ₀) · a ₁ · D ^lmls(α″)= D ^lmls(t ₀′), which proves Claim 3.

Since q′ = δ*(q ₀,a ₂. . .a _rσ_n+1) the induction hypothesis for a ₂. . .a _rσ_n+1 yields D ^lmls(α′) = Ψ(q′), which shows that Claim 4 is satisfied.

Case 2.2. δ_D(q,σ_n+1) is not defined and there is a final state of _D on the path from q ₀to q. Let a ₁. . .a _r denote the sequence of labels of the path from q ₀ to q, let q _f denote the last final state on the path and let a ₁. . .a _f denote the sequence of labels of the path from q ₀ to q _f.

In this case we have q′ = δ(q,σ_n+1) = δ*(q ₀,a _f+1. . .a _rσ_n+1) and λ(q,σ_n+1)= Ψ_D(q _f) · λ*(q ₀,a _f+1. . . a _rσ_n+1). Let α′ denote the unique word such that δ_D(q ₀,α′) = q′. The induction hypothesis applied to a _f+1. . .a _rσ_n+1 shows that α′ is a suffix of a _f+1. . .a _rσ_n+1=α″·α′, hence α′ is a suffix of t′ = t ₀ · a ₁ . . . a _f · α″ · α′, which shows that Claim 1 holds. Let t ₀′ := t ₀ · a ₁ . . . a _f · α″. Applying the induction hypothesis (Claim 3, α₀ := a ₁ . . . a _f · α″) we get D ^lmls(t ₀′) = D ^lmls(t ₀) · D ^lmls(a ₁ . . . a _f · α″). Our assumption implies that a ₁ . . . a _f represents a longest leftmost occurrence within a ₁ . . . a _f · α″. Corollary 2.10 shows that D ^lmls(a ₁ . . . a _f · α″) = D ^lmls(a ₁ . . . a _f) · D ^lmls(α″)=Ψ_D(q _f) · D ^lmls(α″), hence D ^lmls(t ₀′) = D ^lmls(t ₀) · Ψ_D(q _f) · D ^lmls(α″). The induction hypothesis (Claim 2) for t yields D ^lmls(t ₀) = λ*(q ₀,t). The induction hypothesis (Claim 2) for a _f+1. . .a _rσ_n+1 yields D ^lmls(α″) = λ*(q ₀,a _f+1. . .a _rσ_n+1). We obtain

which proves Claim 2.

We prove Claim 3. Let γ ∈ Σ*, let α₀ be any prefix of α′·γ. By induction hypothesis (3) for t we have D ^lmls(t ₀′·α₀) = D ^lmls(t ₀ · a ₁. . . a _f · α″·α₀) = D ^lmls(t ₀) · D ^lmls(a ₁. . . a _f · α″·α₀). Our assumption and Corollary 2.11 show that D ^lmls(a ₁. . . a _f · α″·α₀)= Ψ_D(q _f) · D ^lmls(α″·α₀). Induction hypothesis (3) for a _f+1. . . a _rσ_n+1 implies that D ^lmls(α″·α₀) = D ^lmls(α″) · D ^lmls(α₀). Hence we have D ^lmls(t ₀′·α₀) = D ^lmls(t ₀) · Ψ_D(q _f) · D ^lmls(α″) · D ^lmls(α₀). As above it follows that D ^lmls(t ₀) · Ψ_D(q _f) · D ^lmls(α″) = D ^lmls(t ₀′), which proves Claim 3.

Since q′ = δ*(q ₀,a _f+1. . .a _rσ_n+1) the induction hypothesis for a _f+1. . .a _rσ_n+1 yields D ^lmls(α′) = Ψ(q′), which shows that Claim 4 is satisfied.

6 Complexity analysis and implementation details

In this section we show that a naïve representation of the transducer output function needs cubic space. We then introduce a pointer-based representation with linear space requirement. Even with this step, a straightforward implementation would lead to quadratic running time. In the last subsection we present a queue-based iterative transducer construction which computes the intended rewriting transducer in linear time and space.

6.1 Cubic space complexity of transducer output function

It is simple to see that the number of states of the resulting transducer for an input dictionary D is bounded by the size (number of symbols) of the domain of D. In fact, states of represent states of the transducer trie, which correspond to prefixes of entries of D. Since the alphabet is fixed, the number of transitions of is linear in the size of Dom(D). The following example shows that the size of the output functions can become cubic in the size (number of symbols) of D when using the standard representation for output strings.

Example 6.1

Let n ≥ 1. Consider the rewriting dictionary D of the form

where 1ⁿ (a ⁿ) denotes a sequence of n symbols 1 (a). Then the size of a single transition/state output is quadratic, which means that the size of the transition/state output function is cubic. The corresponding transducer for n=4, which illustrates this phenomenon, is shown in Figure 6.

Fig. 6.

The subsequential transducer for the canonical lmls-extension of the dictionary given in Example 6.1.

The following proposition shows that the size of the output functions is at most cubic in the size of D. As before, for any state q, by α_q we denote the unique word in Σ* such that δ_D*(q ₀,α_q)=q.

Proposition 6.2

Let λ and Ψ respectively denote the transition and state output function of , let q∈ Q, σ∈ σ. Let i=| α_q |. Then

1. 1. Ψ(q) can be represented as a concatenation of ≤ i strings representing either elements of CoDom(D) or symbols from Σ, and

2. 2. λ(q,σ) can be represented as a concatenation of ≤ i+1 strings representing either elements of CoDom(D) or symbols from Σ.

Proof

Part 1 directly follows from Part 4 of Lemma 5.2. Here α represents the input of length i leading from q ₀ to q. Clearly D ^lmls(α) can be represented in the described form.

Part 2: It is simple to see that λ*(q ₀,α_q)=ε since the relevant transitions are already present in the transducer trie for D, _D. Hence we have λ*(q ₀,α_qσ)=λ(q,σ). We consider the text t= α_qσ. Let q′ = δ*(q ₀,t). By Part 1 of Lemma 5.2, αq' is a suffix of t. The corresponding prefix w of t= w · α_q′ has length ≤ i+1. Part 2 of Lemma 5.2 now yields λ(q,σ) = λ*(q ₀,t)=D ^lmls(w). Clearly D ^lmls(w) can be represented in the described form.

6.2 Linear representation of the output function

A closer inspection of the recursive definition of the output functions given in Section 4.2 shows that a linear representation of the output function is possible. The key idea is to use pointers to represent the strings γ′ defined in Cases 1 and 2 of the construction of _i+1′ (here and in what follows we use the notation introduced in Section 4.2). We write γ_q′ for γ′ in order to make the correspondence to q (the state for which γ′ is defined) more obvious.

In the algorithm, “old” outputs of the final states of the transducer trie and the empty transition outputs already defined in the trie are not modified. In Case 1 of the transducer construction (cf. Section 4.2), “new” state and transition outputs for q are respectively defined as

In Case 2, new state and transition outputs for q are respectively defined as

Recall that the states p′ and q _r−1 are closer to the start state than q. From these equations we see that the following representation is possible. We will construct the output string using a record, which contains either a conventional string, a symbol from Σ, or two pointers to other records. Let π₁ and π₂ be pointers. Assume that π₁ points to the location of π₂. By redirecting π₁ we mean the process where we let π₁ point to the same address as π₂.

• • “Old” outputs of the final states of the transducer trie and the empty transition outputs already defined in the transducer trie are represented as pointers to records containing conventional strings.

• • To represent a new state output Ψ(q) we use a pointer to a new record with two pointers. The first (second) pointer points to a record representing γ′_q (resp. Ψ(p′)). If γ′_q or Ψ(p′) is empty, the corresponding pointer is suppressed and Ψ(q) is redirected to the record pointed by the other pointer. If both γ′_q and Ψ(p′) are empty, Ψ(q) is redirected to point to the empty word record.

• • To represent the output of a new transition, λ(q,σ), we use a pointer to a new record with two pointers. The first (second) pointer points to a record representing γ′_q (resp. λ(p′,σ)). If γ′_q or λ(p′,σ) is empty, the corresponding pointer is suppressed and λ(q,σ) is redirected to the record pointed by the other pointer. If both γ′_q and λ(p′,σ) are empty, λ(q,σ) is redirected to point to the empty word record.

• • In the case where r=1 (Case 1) or r=f (Case 2) γ′_q is represented by a pointer to a new record containing the letter a ₁ (Case 1) or a pointer to the record pointed by Ψ(q _f) (Case 2). For r > 1 (Case 1) or r > f (Case 2) γ′_q is represented by a pointer to a new record which contains two pointers. The first one points to the record pointed by γ_{q r−1}′ (Cases 1,2). The second pointer points to the record pointed by λ(δ*(q ₀,a _x. . .,a _r−1),a _r) where x=2 in Case 1 and x=f+1 in Case 2. If γ_{q r−1}′ or λ(δ*(q ₀,a _x. . .,a _r−1),a _r) is empty, the corresponding pointer is suppressed and γ′_q is redirected to the record pointed by the other pointer. If both γ_{q r−1}′ and λ(δ*(q ₀,a _x. . .,a _r−1),a _r) are empty, then γ′_q is redirected to point to the empty word record.

Example 6.3

In Figure 7 we see the subsequential transducer for the local extension of the dictionary given in Example 6.1 with the pointer-based representation of output functions. The string γ′_q for each state q is written below q. Small numbers in bold face denote pointers. Pointer addresses/values are written in brackets. For example, the state reached from the initial state with input a has state output 1111. Pointer 3 points to 1111. The state output of the state q reached with input aa, which is written 3.3 in the pointer-based representation, thus has the form 1111 · 1111. The output of the transition from q with input letter b is written 3.4. Decoding pointers we obtain 3.4 = 3.3.2 = 1111 · 1111 · b.

Fig. 7.

The subsequential transducer for the canonical lmls-extension of the dictionary given in Example 6.1 with the pointer-based representation of output functions.

In fact, concatenating the strings that are found when following the pointers in the obvious order yields the correct output strings. As to the representation size, the important point to note is that we need a constant number of pointers per state q. Besides the pointers, each output of the trie transducer (i.e., each element of the codomain of D) and each letter of the alphabet needs to be represented once. It follows that the representation size of the transducer is linear in the size of D.

Since each member of a pair of pointers always points to a non-empty string, and since there are no chains of single pointers, when applying the transducer to a text t the number of pointers that have to be processed to produce a partial output string β is bounded by the length of β plus 1 (1 for empty output). Hence the complexity of text rewriting O(|t|+|t′|) is not affected by this special technique for representing outputs.

6.3 Linear computation of the rewriting transducer

It is not completely obvious how to modify the algorithm described in Section 4 in order to obtain the correct pointer representation for the outputs. Furthermore, a naïve implementation of the algorithm leads to a time complexity which is quadratic in the worst case. The problem is that the calculation of p' and γ′ (cf. Cases 1 and 2) requires a traversal of the transducer with a suffix a ₂. . . a _r (Case 1) or a _f+1. . . a _r (Case 2) of the word α_q. The length of α_q, as the length of the suffix, may be linear in the input, and it seems necessary to do the traversal for each state.

To overcome these problems, during the breadth-first traversal of the trie we maintain a queue. The queue contains triples with the following entries:

1. 1. the state to be processed – q,

2. 2. the state p' which is reached by traversing the transducer with the string obtained by removing the first symbol, or the string on the path from the last final state, depending on the case, and

3. 3. a pointer to the representation of γ_q′.

In the algorithm, triples are calculated in constant time from predecessor triples, using the equations given in the previous subsection.

Consider the situation presented in Figure 8. The triple 〈q _old, p _old′, γ_old′ has been calculated. Reaching state q _new with letter a _r in the trie, we want to define the new triple. We distinguish two cases.

Fig. 8.

Calculation of a triple from the predecessor triple.

Situation I: If q _new is not a final state of _D (situation depicted in Figure 8), then p _new′=δ(p′_old,a _r) and γ′_new = γ′_old · λ(p′_old,a _r). The equation for γ′_new follows directly from the above equivalences (cases r > 1, r > f). The equation for p′_new directly follows from the definition of the state p' in Section 4.2. It is important to note that the transition from p′_old to p′_new may be a failure transition.

Situation II: If q _new is a final state in the trie, then we define p′_new=q ₀ and γ′_new=Ψ(q _new). Both equations follow directly from the second case distinguished in Section 4.2 where f=r.

We give the pseudo-code of the algorithm in a Pascal-like language (like the language used in (Aho et al. 1983)). We assume that an implementation for the Abstract Data Type (ADT) “Transducer State” is given. Later we presume that NULL is the null constant for an arbitrary abstract data type.

On Transducer State we will need the following types and operations:

1. 1. FIRST_CHAR, LAST_CHAR – these are the first and the last character in the input alphabet;

2. 2. STATE – a pointer to a structure representing a transducer state;

3. 3. function NEW_STATE : STATE; – function returning a new state;

4. 4. function FINAL(STATE) : boolean; – returns true if the state is final and false otherwise;

5. 5. procedure SET_FINAL(STATE, boolean); – defines the finality of the state in accordance with the boolean parameter;

6. 6. function TRANSITION(STATE, char) : STATE; – returns the state to which the transducer transits from the parameter state with the parameter char;

7. 7. procedure SET_TRANSITION(STATE, char, STATE); – the procedure defines the transition from the first state by the char to the second state;

8. 8. function STATE_OUTPUT(STATE) : POutString; – returns the output string of a final state;

9. 9. procedure SET_STATE_OUTPUT(STATE, POutString); – defines the output string of a final state;

10. 10. function OUTPUT(STATE, char) : POutString; – returns the output string for the transition given by the state and the char;

11. 11. procedure SET_OUTPUT(STATE, char, POutString); – defines the output string for the transition given by the state and the char;

12. 12. procedure SAVE_TRANSDUCER(file, STATE); – saves the transducer to the file, starting from the initial state.

Now we are ready to present the pseudo-code of our algorithm.

• 

Below the special representation of the output strings is given. An output string is either a character, or a substitute for a dictionary entry, or a concatenation of two already defined strings represented by pointers. In line 11 we define the type for the queue records as triples containing two states and one pointer to OutString.

• 

Here we define the global variables used in the algorithm.

• 

  

The next three functions below are used to efficiently concatenate two OutStrings, save an ordinary string in an OutString, and to represent a character as an OutString. The first of the three functions – ConcatOutStrings – checks the two parameters. If both of them point to the empty string, then the empty string is returned. If one of the parameters points to the empty string, then a pointer to the other one is returned. In the remaining case, the function returns a pointer to a new structure with exactly two pointers pointing to the two input parameters respectively. The second function – StringToOutString – returns a pointer to a structure containing a given input string. The last of the three functions – CharToOutString returns a pointer to a structure containing a given input character.

• 

The following procedure describes the treatment of one triple from the queue. Processing a triple means to declare q to be final, to add state output of q, failure transitions for state q and to maintain the queue by adding triples for the trie successor states. For the definition of state outputs and failure transitions see Section 4.2 and the above equations. In lines 46–56, for each letter c an appropriate action is taken: either a failure transition is added or a new triple is calculated and added to the queue.

• 

The main program has three parts.

First (lines 58–79), the transducer trie is computed by reading the input dictionary line by line.

Second (lines 80–95), the initial state q ₀ is treated. We set its output to the empty string and add loops for all symbols σ of the alphabet for which there are no outgoing transitions from the starting state. The transition outputs are identical to the corresponding input symbol σ (line 87). If there is already an outgoing transition with the given symbol σ in the trie, then we put the following triple in the queue: the state q reached from q ₀ with σ, the starting state (here playing the role of p'), and the representation for γ′, which here is either σ (line 92) or the output of q if this state represents a final state of the trie (line 90), depending on the situation.

Third (lines 96–99), the triples in the queue are processed. As seen above the procedure Process_State adds new triples to the queue. The queue is used in order to process the states in ascending distance from the starting state.

• 

  

Clearly the above algorithm implements the method described in the previous sections. Reading the input dictionary takes time proportional to the size of the dictionary. The procedure for building the trie has time complexity proportional to the number of trie states. The number of steps required for processing a single state in the Complement_State procedure is proportional to the alphabet size. The space requirements for a state are proportional to the alphabet size as well. Thus the space and time complexity of the given algorithm is O(|D|+m+|Σ| · m), where m is the number of states in the trie transducer. Obviously m < Σ_{〈αi,βi〉∈ D}|α_i| thus the time complexity of the algorithm is proportional to the size of the dictionary for a fixed alphabet.

7 Empirical results

We implemented both the algorithm described in Section 4 and the naïve algorithm described in the introduction. For the latter implementation, a trie is used to encode the dictionary. In this way we may efficiently check if a string is a prefix of a dictionary word. When the naïve algorithm is applied to a text, any new input symbol gives rise to a single transition step in the trie. We obtain an efficient realization since we have to go back only in the cases where we went too far in the trie.

To compare both methods, we made a series of experiments, varying the size of the input alphabet, the number of dictionary entries, and the average length of dictionary entries. All dictionary words were randomly generated, varying both the length and the form using a regular distribution. We then measured the time for rewriting a randomly generated text. Table 1 presents the speed-up factor (ratio of times) of our method compared to the naïve algorithm. For three of the entries the rewriting transducer was too large to be hold in the operating memory.

Table 1.

Results for text rewriting using random rewriting dictionaries, speed-up factors (ratio of times) w.r.t. naïve algorithm

The algorithm is currently applied in the context of OCR-correction (Strohmaier et al., Reference Strohmaier, Ringlstetter, Schulz and Mihov2003a; Strohmaier et al., Reference Strohmaier, Ringlstetter, Schulz and Mihov2003b), using rewriting dictionaries that rewrite erroneous words into correction suggestions. We successfully compiled transducers for a variety of rewriting dictionaries. For the experiments we used a conventional PC (Intel(R), Pentium IV, CPU 3.2 GHz with 1 GB RAM main memory running Linux). The largest dictionary had 221,681 entries. The number of states of the transducer was 737,792. The number of transitions was 737,792× 42 (alphabet size 42). The construction time for the transducer was 33.60 seconds. Using the constructed transducer, 134 MB of text (18,470,101 tokens) were rewritten in 7.71 seconds. For the sake of comparison, the same text was rewritten with the naïve algorithm, which took 12.79 seconds (speed-up factor 1.66x). The size of the rewriting subsequential transducer is 278 MB. The size of the minimal subsequential transducer representing the dictionary without rewriting (constructed using the method presented in Mihov and Maurel (Reference Mihov and Maurel2001)) is 4.3 MB.

8 Related work

Applications of finite state transducers for different problems of natural language processing are described, e.g., in Kaplan and Kay (Reference Kaplan and Kay1994), Mohri (Reference Mohri1996, Reference Mohri1997) and Roche and Schabes (Reference Roche, Schabes, Roche and Schabes1997). Rewriting dictionaries as discussed in this paper can be considered as a special form of rewriting rules in the sense of Kaplan and Kay (Reference Kaplan and Kay1994). Ignoring weighted versions (Mohri Reference Mohri, Junqua and Noord2001), such a rewriting rule has the form α↦ β /λ_ρ. The rule expresses that occurrences of α that are immediately preceded by an occurrence of λ (left context) and directly followed by an occurrence of ρ (right context) are replaced by β. Here α, β, λ and ρ are regular expressions, which implies that in general we have a proper rewriting relation (as opposed to a rewriting function). In order to formally define the rewriting relation, distinct modes of applying the rule must be distinguished: left-to-right versus right-to-left application, optional versus obligatory application. Kaplan and Kay (Reference Kaplan and Kay1994) proved that all these rewriting relations are rational, i.e., they can be encoded by a finite state transducer. Kartunnen (1997) describes a similar approach. In Karttunen (Reference Karttunen1996), also the difference between longest match versus shortest match strategies is considered. For the leftmost-longest match strategy, the construction described in Kaplan and Kay (Reference Kaplan and Kay1994) has been improved by Gerdemann and van Noord (Reference Gerdemann and van Noord1999). Another improvement of Kaplan and Kay (Reference Kaplan and Kay1994), applicable also for weighted rewrite rules, is presented by Mohri and Sproat (Reference Mohri and Sproat1996) and Mohri et al. (1996). It should be noted that the above approaches lead to non-deterministic transducers.

Theoretically the above techniques can be applied for the construction of a subsequential transducer that represents D ^lmls. To this end, a determinization procedure (Roche and Schabes 1995) must be used. This would lead, however, to a much more indirect and complex construction, which in practice could be applied only for very small dictionaries.

Roche and Schabes (1995) show how the contextual rewrite rules used in Brill's tagger (Brill Reference Brill1992) can be compiled into subsequential finite state transducers. The rules have the form w↦ v /λ_ρ where w,v are tags and the context conditions λ and ρ restrict the previous and next tags. Hence the rules represent a special form of the above rewrite rules. Roche and Schabes show that any rewriting relation represented as a finite state transducer ₁ can be transformed into a transducer ₂ that represents the “local extension” of ₁: If ₁ produces output w for input v, and if u and x are any strings where ₁ does not apply, then ₂ rewrites uvx into uwx. Hence, ₂ is used to perform all possible ₁-replacements inside a given text. Recall that our transducer uses the more restricted leftmost-longest replacement strategy with skips. From the theoretical results proved at the end of Roche and Schabes (1995) it follows that the lmls-extension D ^lmls of a finite rewriting dictionary D can be represented as a subsequential transducer. But at this point no explicit construction is given.

The problem considered in the present paper is more restricted in the sense that our rewrite rules ignore contextual conditions. Furthermore, we only consider one fixed application mode (obligatory leftmost-longest replacement strategy with skips). For this specific problem, a simple and efficient solution directly leading to a deterministic transducer is given.

The problem of how to represent a given rewriting dictionary D (as opposed to the canonical lmls-extension D ^lmls) as a minimal subsequential transducer is discussed in Mohri (Reference Mohri1996). This construction provides a very fast dictionary lookup as well as compact storage. An on-line algorithm for constructing the minimal subsequential transducer for a given dictionary is presented in Mihov and Maurel (Reference Mihov and Maurel2001), building up on ideas from Mihov (Reference Mihov1998) and Daciuk et al. (2000).

The wide variety of text rewriting applications mentioned in the introduction, which could be extended by further examples from compiler construction, computer virus/worm detection, and network traffic intrusion detection, explains that many techniques have been established for solving algorithmic tasks similar to the one studied above. An exhaustive comparison is outside the scope of the paper. Yet, subtle differences have to be taken into account that explain why methods from one domain cannot be naively transferred to the present task. For example, text rewriting in translation and compiler construction is based on tokenized text, hence problems with overlapping originals do not occur.