Complexity of ambiguous parsing?

Question

Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w_1,\ldots,w_k$ and $w$ is the concatenation of the corresponding words).

The problem has an interesting variant which is the search of spoonerisms: we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.

So my question is: under what condition on the language $S$ can the above problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.

(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)

Answer 1

Here is the first part of the answer (without swapping). I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.

Introduction to the problem and its practical importance

I do not know the motivation for the question, as it was not given. However this is a known problem of natural language processing (NLP), and specifically of speech processing. The problem is that phonems are not always clearly identifiable, nor are the boundaries between lexical elements (words), which is a little bit more general than the question. As a consequence, there can be several ways to cut the spoken sentence into words of the language. In order to account for that, the single linear stream of phonems is actually transformed into what is called a "word lattice" which may be seen as a directed acyclic graph or as an acyclic DFA (though even the acyclicity is also a topic for discussion in some cases - see my remark on whether the empty word can be in $W$). This word lattice corresponds to all the ways the sentence can be cut into recognizable words. This is often based on probabilities and Markov models.

Well known examples of the need for word lattices are holorime verses. See for example "Phonological ambiguity that changes the syntactic structure".

The word lattices are then used in various way for further linguistic processing. One use is to do syntax analysis with respect to a syntactic definition of the language, the identified lexical elements (or their lexical category, called "part of speech") being used as alphabet symbols at that syntactic level. In the question asked, the collection $S$ or sentences plays the role of the language syntax that defines allowed sentences. The set $W$ is the collection of acceptable spoken language words that can be built from the phonems in $\Sigma$. It is a bit simplified from the real speech processing situation. For example, the set $W$ is finite, while in speech processing it is considered open (actually finite, but so large ...). This is dealt with by replacing all the words of a given category by that category considered as a whole (I skip many details).

Many modern parsing techniques can be readily extended to the parsing of word lattices, as most syntactic formalisms are closed under intersection with regular sets. See for example "Recognition can be Harder than Parsing".

The problem addressed by word lattices (and by this question) is lexical ambiguity: the ambiguity resulting from the fact that the sequence of lexical elements that can correspond to the analyzed string is not unique. This can be opposed to syntactic ambiguity du to the fact that the lexical sequence can be generated syntactically in two different ways, as in ambiguous context-free grammars.

The issue of character swapping, here supposedly to detect "spoonerisms", is part of various techniques to deal with input ill-formedness that can be modeled by finite state tranducers. Here again, closure properties are more than helpful.

A solution without swap, linear in each parameter

The set $W$ may be considered finite, as only a finite number of words in $W$ can be used to form the alphabet for sentences. We assume furthermore that the empty word is not in $W$. It is not strictly necessary for the construction given here, but it could make the parsing yield an arbitrarily long sequence, independently of the length of the string $w$ being parsed, possibly giving a false idea of the complexity.

We associate with each word $w\in W$ a unique symbol $\hat w$. Let $\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may avoid confusion as to what is the alphabet.

Then you build a trie, as a DFA that recognizes the words in $W$. Each final state recognizing a word $w_k\in W$ is then labeled with $\hat w_k$ (cf Moore machines). Then an $\epsilon$-transition is added from each final state to the initial state, turning the DFA into a NFA that recognizes sequences of words in $W$, and which can output $\hat w_k$ whenever $w_k$ has been recognized. Then you apply the powerset construction to turn this NFA into a DFA $T_W$, such that the states of this new DFA have all the labels of the trie final states they contain.

This construction, though expensive because of the powerset construction, is done only once, independently of the sentence $w$, and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).

Given a string $w\in\Sigma^*$ you build a DFA $L_{W,w}=(\{q_i\mid 0\leq i\leq |w|\},\hat W,q_0,q_n,\tau_{W,w})$ as follow:

• $q_0$ and $q_n$ are respectively initial and final state

• the number of states is $n+1$

• there is a transition on input $\hat w_k$ from state $q_i$ to state $q_j$ iff $w[i:j]=w_k$ where $w_k \in W$

The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to index $j$, the first letter having index $1$.

This finite state automaton $L_{W,w}$, called a word lattice in speech processing, generates or recognizes all sentences that are sequences of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.

To build the transitions, you apply the DFA $T_W$ to the string $w$. Whenever you enter a state that has a label $\hat w_k$ (It may have several labels), it means that you have just recognized the string $w_k\in W$. If you have read $j$ letters, it means that $w[i:j]=w_k$ for $i=j-|w_k|$. Thus you add the corresponding transition to the word lattice.

The DFA $T_W$ executes no more than $|w|$ transition steps, and at each step adds at most $|W|$ transitions to the word lattice. Hence the complexity is $O(|W|\times|w|)$

Now we have to find out which sentences in the language recognize by the language of $L_{W,w}$ are also recognized by the DFA $M_S$ on alphabet $\hat W$ recognizing $S$.

In other words we want the intersection of the two languages. This can be obtained by the usual cross product construction of the two automata, which are both DFA. The resulting automaton is a recognizer for the solutions, and can be used to generate them non deterministically.

Since the set $S$ is a regular set, potentially infinite, each solution must be given explicitely as a word in $\hat W^*$, with corresponding cost, rather than being named in constant time. However, if the empty word is not in $W$, the length of each solution is bound by the length of $w$.

The cross product construction gives a number of states that is the product of that number for each automaton: $|Q_S|\times(|w|+1)$. Each of the $|\tau_S|$ of the DFA $M_S$ is associated with each of the $O(|W|\times|w|)$ transitions of the word lattice to determine the transitions of the cross product.

Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M_S|)$

The cross-product DFA is noted $F_{W,S,w}$. Its construction is such that its mimics exactly the DFA $S$, but only for the sentences in $\hat W^*$ accepted by the word lattice, i.e. all those corresponding to the sentence $w$. Hence, it does give all the sentences in $S$ as words in $\hat W^*$ that are equal letter-wise to $w$.

Enumerating the solutions

Here is how you can enumerate the solutions with the DFA $F_{W,S,w}$ to be conformant to the constraint that the enumeration should be linear in the size of a trie of all solutions.

We suppose the symbols in $\hat T$ are totally ordered, for example by the lexicographic order of the corresponding words in $T$. We also assume that the DFA $F_{W,S,w}$ has been pruned of all states that do not have a path to an accepting state, and of transitions to and from these states (this does not have to exceed the cost of building the DFA). The missing transitions will be considered as virtually going to a dead state; they are not needed here.

Let $d$ be the length of the string $w$. Since we excluded the empty word from $T$, all solutions have a length less than $d$. Hence the DFA $F_{W,S,w}$ is acyclic, i.e. represented by an edge labeled DAG.

Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing the words to be enumerated, and a cursor $c$ indexing the last modified letter of $\mathcal S$.

Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0 to $d$, storing the states followed to produce/recognize the current content of $\mathcal S$. The cursor $c$ indexes also the last visited state.The array $\mathcal Q$ is initialised with the initial state of the DFA $F_{W,S,w}$ at index 0.

Both arrays are used as pushdown stacks, the cursor $c$ pointing at the top.

Then perform a simulation of a Depth First Search (DFS) on a virtual version of the trie of all solutions recognized by the DFA $F_{W,S,w}$, by updating only the top of the stacks.

When a transition of the DFA is followed, its label is pushed on $\mathcal S$ and the next state is pushed on $\mathcal Q$.

When a state $q$ has just been pushed on the stack $\mathcal Q$:

• If $q$ is an accepting state the content of stack $\mathcal S$ is a solution;

• if $q$ has transitions, follow the one with the smallest label;

• if there are no transitions, then pop both stacks.

When the stacks are popped, let $\hat w$ be the symbol just popped from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.

• if $q$ has transitions with a label greater than $\hat w$, follow the one with the smallest label;

• otherwise pop both stack.

When all transitions of the initial state at the bottom of stack $\mathcal Q$ have been followed, the enumeration terminates.

This algorithm is essentially a virtual traversal of the trie of all solutions, because the finite automation $F_{W,S,w}$ is deterministic and pruned of unproductive states and transitions. Therefore the time cost is linear in the size of that trie. The solutions are given in lexicographic order with respect to $\hat V$.

However, though I have not explored the issue, I fear that the size of that trie may far exceed the size of the DFA $F_{W,S,w}$. Even if S is finite, it may be represented by a DFA that is much smaller than its trie (precisely our problem).

Note:
$S$ does not have to be a regular set.

The essential ingredients for the solution presented and its complexity are the deterministic real-time character of the automaton and the cross product construction. Hence it should be applicable with the same complexity result if $S$ were a real-time deterministic context-free language.

More generally, all kinds of languages families may be considered, with a complexity that depends on recognition complexity of the family. For example, if $S$ is a context-free language, then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get then more complex: parsing with respect to a regular set for $S$ just means recognizing $\hat W$-strings in $S$ that expand to the word $w$. However, if S is a context-free language, one may be satisfied with a recognizer as in the regular case, but one may also want to have some or all parses with respect to a specific grammar which may itself be ambiguous. The complexity analysis may then depend somewhat on what is actually desired, on language properties or on grammar properties. And this extend to a variety of other grammatical formalisms.

Allowing to swap letters

To come later. It can be done also with finite state techniques.

Answer 2

Here is one algorithm. It runs in time at most $O(|S|*|w| + c)$, and probably runs much faster for many inputs.

We create a directed graph $G$. The graph $G$ has a vertex $(s,i,j)$ for any $s \in S$ and any indices $i,j$ such that $s=w[i..j]$. Then the graph has a directed edge from $(s,i,j)$ to $(s',i',j')$ whenever $i'=j+1$. Finally, the graph has two additional vertices, a source and a sink. There is a directed edge from the source to any vertex of the form $(s,0,j)$ and from any vertex of the form $(s,0,|w|)$ to the sink.

Now notice that the directed paths from the source of the sink correspond exactly to the parsings of $w$. So it's enough to enumerate all (source,sink)-paths in $G$, which can be done in time $O(|G'|+c)$. Note that the graph $G$ kind of represents all the parsings, so for many applications you wouldn't even have to enumerate them explicitly.

Answer 3

This is not an answer but an extended reply to babou's comment.

I suggest looking at some literature on constant-delay enumerators, this can usually be done with 'in place' modification. The simplest example is the lexicographical enumeration of a set of the form $[D]^n$ where $D,n$ are integers. If you identify an element of $[D]^n$ with an $n$-digit word in base $D$, it is easy to see that by starting with the word $(0,\ldots,0)$ and by repeatedly apply the successor operation you get an enumerator with amortized constant delay. The intuition is that a chain of $i$ carry propagations happen with probability $1/D^i$, and thus the average time is $\sum_{i = 1}^{n} i (1/D)^{i-1} (1-\frac{1}{D})$ which is bounded by a function of $D$ only.

More generally, here is how it would work with a trie. Let $d$ be the depth of the trie $T$, initialize an array $w$ of length $d$ storing the words to be enumerated, and a cursor $c$ pointing to the last modified letter of $w$. Perform a dfs of $T$ by updating only the last letter and the cursor: when going back to a parent node move $c$ to the left, when going to a child node write its label under $c$ and move $c$ to the right. It is clear that you get the desired result in time linear in the size in $T$. But this example is not so interesting as it corresponds to a finite language, so the next step would be to look at a star-free language represented by a trie $T$ with self-loops: in that case can you enumerate the words of length $n$ in time $O(|T|+c)$ where $c$ is the number of such words?