Redundancy-free Island Parsing of Word Graphs

1 Introduction

Island parsing is a parsing strategy for context free grammars, mostly used in speech applications ([Ageno, 2003], [Gallwitz et al., 1998], [Thanopoulos et al., 1997], [Mecklenburg et al., 1995], [Brietzmann, 1992]). It is a bidirectional strategy, in that incomplete parse items, which encode partially filled right hand sides of a context free rule, may extend in both directions. Furthermore, parsing starts at some highly ranked input items called seeds and tries to explore the "islands of certainty" first.

Since island parsing starts building all possible derivations from every seed in both directions, provisions must be taken so as to avoid multiple computation of identical subderivations, which would lead to spurious ambiguities and reduced efficiency. To my knowledge, there is only one description of an efficient fully redundancy free algorithm for island parsing, contained in an article comparing different bidirectional parsing approaches for context-free grammars, namely [Satta and Stock, 1994].

This algorithm splits up the chart into consecutive regions such that the region borders correspond to chart nodes and every region contains exactly one seed item. Derived chart items lying entirely within a region have been constructed starting at the seed in a manner similar to Earley parsing, which guarantees that they are build in a unique way. Items crossing region borders are a possible source of redundancy, because the same derivation could be build starting either at the right or the left seed (see figure 2 for an illustration). By fixing the expansion direction of those items when they combine for the first time, duplicate derivations are avoided.

This paper extends the original algorithm in two aspects that make it more feasible for speech applications.

Firstly, the original algorithm deals only with string input. Because many speech applications require the direct analysis of word graphs, it is desirable to extend the method to word graph input. Word graphs are acyclic directed graphs of input items with exactly one source node and one sink node (a node with in-degree resp. out-degree zero). They encode ambiguous input using possibly overlapping sub-paths, which lead to more complicated input configurations and require a modification of the original algorithm. The word graph in figure 1, for example, can not be split into more than one region because every border at an inner node would cross an input item, thus inhibiting the use of more than one seed.

A modified algorithm must be able to deal with these configurations without losing efficiency, since speech applications are typically time critical and often have limited space resources. Therefore, care has been taken to preserve the efficiency and the redundancy avoidance of the original.

Secondly, instead of picking all seeds in advance, the modified version integrates their selection into the search inherent to the parsing process. Since a lower number of seeds may result in faster parsing, it is advantageous to be able to base seed selection also on information created during parsing, namely, on already constructed items and their quality.

Selecting a seed becomes one of the actions the parser can take, like the combination or creation of other parse items. This provides full flexibility in the design of the search strategy, which in resource-limited applications can have a big impact on the quality of the, possibly partial, results. Picking all seeds in advance is then just one of the possible options.

Furthermore, dynamic selection of seeds is performed such that all sub-paths of the word graph will be be properly explored to arrive at a complete solution, which might not be the case if seeds were picked disadvantageously. If, for example, the seeds in figure 1 were the items labeled hat and tea, it might happen that the sub-path containing forty would not be considered.

The modified algorithm does not fix regions for the whole word graph in advance. The resulting chart configurations are rather such that every path through the word graph has its own regions, and the borders of the different paths can, but need not, coincide. Since similar properties hold for the chart items with respect to the per-path regions as they do for the string version, the modified algorithm is still correct, complete and free of redundancy.

2 The Original Algorithm

Because [Satta and Stock, 1994] aim at describing bidirectional context-free parsing in more generality, the formulation of the island parsing algorithm itself is somewhat complicated and its implementation is not obvious at first glance. To facilitate the description of the modifications, the original algorithm is presented first, albeit in an alternative, but equivalent form. Similar notation is used as far as possible to stress the connection between the two formulations. In many respects, it is an ordinary chart parsing algorithm, that is only complicated by the bookkeeping necessary to avoid redundant computations. After introducing the notation, the algorithm is presented as a set of pseudo-code procedures.

The algorithm uses a context free grammar a0 ✁ ✂ ✄ ✆ ✞ ✆ ✡ ✆ ✌ ✎ , where ✄ and ✞ are finite sets of terminal and nonterminal symbols, respectively, ✡ is the set of rules ✑ ✒ ✁ ✔ ✕ ✗ ✙ ✕ ✜ ✢ ✣ ✣ ✣ ✙ ✕ ✜ ✧ ★ , where ✔ ✕ ✪ ✞ and each ✙ ✕ ✜ ✭ ✪ ✄ ✯ ✞ . ✲ ✕ is the number of symbols on the right hand side of rule ✑ . ✌ ✪ ✞ is the start symbol of the grammar. The grammar must not contain empty rules, i.e, rules of the form ✳ ✗ ✴ . The input is a string of ✶ terminal symbols ✷ ✢ ✆ ✸ ✸ ✸ ✆ ✷ ✹ . The algorithmuses a chart of size ✶ ✻ ✽ : a two-dimensional array ✿ ✭ ✜ ❁ , ❂ ✆ ❃ ✪ ❄ ❆ ✆ ✸ ✸ ✸ ✆ ✶ ❉ , where each ✿ ✭ ✜ ❁ contains a set of two kinds of items: complete and incomplete items.

A complete chart item is a triple ✂ ✞ ● ✆ ❂ ✆ ❃ ✎ with ✞ ● ✪ ✄ ✯ ✞ being the terminal or nonterminal category, ❂ and ❃ the index of the start and end node of the item, respectively.

For incomplete items, we introduce symbols ❏ ❑ ✜ ▼ ✕ that represent dotted items (partial derivations) of a rule ✑ ✪ ✡ :

with ❘ ✆ ❙ ✪ ❄ ❆ ✆ ✸ ✸ ✸ ✆ ✲ ✕ ❉ and ❘ ❯ ❙ . Let ❏ ❲ be the set of all symbols ❏ ❑ ✜ ▼ ✕ for the dotted items of grammar a0 . Analogous to complete items, incomplete items are triples ✂ ❏ ❑ ✜ ▼ ✕ ✆ ❂ ✆ ❃ ✎ , where ❘ ❩ ❆ or ❙ ❭ ✲ ✕ , or both.

The island seeds are represented by a set of indices ❪ ✁ ❄ ❂ ✢ ✆ ✸ ✸ ✸ ✆ ❂ ❫ ❉ of the corresponding input symbols. For the island parsing algorithm, the chart is divided into regions, such that every region contains exactly one seed. The indices of the region borders are named ❵ ❑ , with ❵ ❛ ✁ ❆ , ❵ ❫ ✁ ✶ and ❂ ❑ ❯ ❵ ❑ ❭ ❂ ❑ a80 ✢ ✆ ❘ ✪ ❄ ✽ ✆ ✸ ✸ ✸ ✆ ❡ ❢ ✽ ❉ . The region between a seed and its left border is called right substring, because items in this region are built in a right-to-left top-down fashion. Analogously, there is a left substring to the right of a seed, where items are built from left-to-right, respectively.

The algorithm is started by adding all tuples ✂ ✷ ✭ ✆ ❂ ❢ ✽ ✆ ❂ ✎ to ✿ ✭ ✐ ✢ ✜ ✭ and then calling add complete for all of them. The program terminates whenever a derivation from the start symbol to the input string was found and the exit statement in add new was reached, or else, if there are no more items to add, in which case the string is rejected.

Although items can potentially combine with other items at both sides, their expansion direction is restricted dynamically to avoid redundant computation of sub-derivations. These restrictions are implemented using two additional twodimensional ✶ ✻ ✽ ❦ ✶ ✻ ✽ arrays block left and block right, that contain symbols of ✞ ✯ ✄ ✯ ❏ ❲ . If, for example, ✳ ✪ block right ✂ ❂ ✆ ❃ ✎ , the item ✂ ✳ ✆ ❂ ✆ ❃ ✎ ✪ ✿ ✭ ✜ ❁ cannot combine with any item adjacent to its right.

To illustrate the algorithm, figure 2 shows an example chart that will be referred to throughout the next paragraphs. Complete and incomplete items are represented by solid respectively dashed arcs, bearing symbols from ✞ , ✄ , and ❏ ❲ as labels. Input items ✷ ✢ and ✷ ♣ are the seeds, the border between them is at p ✢ ✁ a113 . The little blocks at the end of the arcs depict the values of block left and block right, respectively.

The blocking of a complete item is based on its relation to the seeds. Items dominating a seed, i.e., items whose yield contains at least one seed, are blocked on both sides and will only be extended by the projection step in the procedure add complete below. This is the case for all seed items, but also for the item ✂ a115 ✆ ❆ ✆ a113 ✎ which projects to the incomplete item ✂ ✌ ✗ ❖ a115 ❖ ✈ ✷ ♣ ✷ ✇ ✆ ❆ ✆ a113 ✎ . Complete items in a right substring, like the items labeled ✈ , ✳ , or ✷ ① , are blocked at the left side and can therefore only combine with active items to their right. Thus, items in a right substring will be built right-to-left starting at the seed. Complete items in a left substring are treated analogously.

An unusual feature of this algorithm is that two incomplete items can be combined (see the second and fourth for loop in procedure add incomplete), while other chart parsing algorithms only allow the combination of an incomplete with a complete item. At the borders, these are the only possible combinations, since all complete items have been blocked.

When incomplete items are created, they can at first extend in both directions, except for those where one of the dots is at its outermost position. Incomplete items are blocked when combinedwith another item for the first time. If they combine to the right, they will be forced to combine to the right from that time on by blocking them at the left side, and vice versa.

In figure 2, incomplete items ✂ ✌ ✗ ❖ a115 ❖ ✈ ✷ ♣ ✷ ✇ ✆ ❆ ✆ a113 ✎ and ✂ ✌ ✗ a115 ❖ ✈ ✷ ♣ ✷ ✇ ❖ ✆ a113 ✆ ② ✎ have been combined to the complete item ✂ ✌ ✆ ❆ ✆ ② ✎ and were then blocked at the left resp. right side, with no effect because of the dot positions. Alternatively, ✂ ✌ ✗ ❖ a115 ❖ ✈ ✷ ♣ ✷ ✇ ✆ ❆ ✆ a113 ✎ and ✂ ✌ ✗ a115 ❖ ✈ ✷ ♣ ❖ ✷ ✇ ✆ a113 ✆ ④ ✎ could have been combined. The second item would have been blocked at the right side (instead of left as in the figure) and ✂ ✌ ✗ a115 ❖ ✈ ✷ ♣ ✷ ✇ ❖ ✆ a113 ✆ ② ✎ could not have been built. Instead, the resulting incomplete item ✂ ✌ ✗ ❖ a115 ✈ ✷ ♣ ❖ ✷ ✇ ✆ ❆ ✆ ④ ✎ would combine with the input item ✂ ✷ ✇ ✆ ④ ✆ ② ✎ to produce ✂ ✌ ✆ ❆ ✆ ② ✎ .

This mechanism synchronizes incomplete items, especially those that cross region borders, which guarantees that items whose yield contains more than one seed are built in exactly one manner.

proc add complete ⑥ ⑦ ⑧ ⑩ ❶ ⑩ ❸ ❹ ❻ if ❶ ❼ ❶ ❿ ➀ ❸ for some ➁ then /* seed dominating: block both sides */ block right ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ⑦ ⑧ ➈ block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ⑦ ⑧ ➈ /* project step: add ➊ ➋ ➌ ➍ ➍ ➍ ➎ ➋ ➏ ➐ ➑ ⑦ ⑧ ➑ ➎ ➋ ➏ ➐ ➒ ➓ ➍ ➍ ➍ */ for ➔ ➐ ➏ ➐ ➒ → ➋ ↔ ➔ ↕ with ➎ ➋ ➏ ➐ ➒ → ➅ ⑦ ⑧ do add new ⑥ ➔ ➐ ➏ ➐ ➒ → ➋ ⑩ ❶ ⑩ ❸ ❹ else if ➜ ❿ ➝ → ❼ ❶ ❼ ❸ ❼ ❶ ❿ for some ➁ then /* right substring : block complete item left */ block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ⑦ ⑧ ➈ /* combine with ➊ ➋ ➌ ➍ ➍ ➍ ⑦ ⑧ ➑ ➎ ➋ ➏ ➐ ➒ → ➍ ➍ ➍ ➑ ➍ ➍ ➍ */ for ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ with ➎ ➋ ➏ ➐ ➅ ⑦ ⑧ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block left ⑥ ❸ ⑩ ➠ ❹ do block right ⑥ ❸ ⑩ ➠ ❹ ➃ ➅ block right ⑥ ❸ ⑩ ➠ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ add new ⑥ ➔ ➐ ➝ → ➏ ➟ ➋ ⑩ ❶ ⑩ ➠ ❹ else /* ❶ ❿ ➀ ❶ ❼ ❸ ➀ ➜ ❿ ➒ → for some ➁ */ /* left substring : block complete item right */ block right ⑥ ❶ ⑩ ❸ ❹ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ⑦ ⑧ ➈ /* combine with ➊ ➋ ➌ ➍ ➍ ➍ ➑ ➍ ➍ ➍ ➎ ➋ ➏ ➟ ➑ ⑦ ⑧ ➍ ➍ ➍ */ for ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with ➎ ➋ ➏ ➟ ➒ → ➅ ⑦ ⑧ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block right ⑥ ➠ ⑩ ❶ ❹ do block left ⑥ ➠ ⑩ ❶ ❹ ➃ ➅ block left ⑥ ➠ ⑩ ❶ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ add new ⑥ ➔ ➐ ➏ ➟ ➒ → ➋ ⑩ ➠ ⑩ ❸ ❹ end proc add incomplete ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ❻ /* ➔ ➐ ➏ ➟ ➋ ➃ ➊ ➋ ➌ ➳ ➳ ➳ ➎ ➋ ➏ ➐ ➑ ➎ ➋ ➏ ➐ ➒ → ➳ ➳ ➳ ➎ ➋ ➏ ➟ ➑ ➎ ➋ ➏ ➟ ➒ → ➳ ➳ ➳ */ if ➜ ❿ ➝ → ➀ ❶ ❼ ❶ ❿ for some ➁ then l-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ❹ if ❶ ❿ ➀ ❸ ➀ ➜ ❿ for some ➁ then r-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❸ ❹ if ➻ ➼ ➽ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block left ⑥ ❶ ⑩ ❸ ❹ then /* combine to the left with complete items */ for ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with ➎ ➋ ➏ ➐ ➦ ↔ block right ⑥ ➠ ⑩ ❶ ❹ do block right ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ add new ⑥ ➔ ➐ ➝ → ➏ ➟ ➋ ⑩ ➠ ⑩ ❸ ❹ /* combine to the left with incomplete items */ for ⑥ ➔ ➾ ➏ ➐ ➋ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with ➔ ➾ ➏ ➐ ➋ ➦ ↔ block right ⑥ ➠ ⑩ ❶ ❹ do /* block both incomplete items appropriately */ block left ⑥ ➠ ⑩ ❶ ❹ ➃ ➅ block left ⑥ ➠ ⑩ ❶ ❹ ➆ ➇ ➔ ➾ ➏ ➐ ➋ ➈ block right ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ add new ⑥ ➔ ➾ ➏ ➟ ➋ ⑩ ➠ ⑩ ❸ ❹ if ➪ ❼ ➶ ➋ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block right ⑥ ❶ ⑩ ❸ ❹ then

/* combine to the right with complete items */ for ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ with ➎ ➋ ➏ ➟ ➒ → ➦ ↔ block left ⑥ ❸ ⑩ ➠ ❹ do block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ add new ⑥ ➔ ➐ ➏ ➟ ➒ → ➋ ⑩ ❶ ⑩ ➠ ❹ /* combine to the right with incomplete items */ for ⑥ ➔ ➟ ➏ ➾ ➋ ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ with ➔ ➟ ➏ ➾ ➋ ➦ ↔ block left ⑥ ❸ ⑩ ➠ ❹ do block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ block right ⑥ ❸ ⑩ ➠ ❹ ➃ ➅ block right ⑥ ❸ ⑩ ➠ ❹ ➆ ➇ ➔ ➟ ➏ ➾ ➋ ➈ add new ⑥ ➔ ➐ ➏ ➾ ➋ ⑩ ❶ ⑩ ➠ ❹ end proc add new ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ❻ if ➴ ➅ ➔ ➬ ➏ ➮ ★ ➋ then if ➊ ➋ ➅ ✃ ➥ ❶ ➅ ➽ ➥ ❸ ➅ ❐ then exit ⑥ accept ❹ if ⑥ ➊ ➋ ⑩ ❶ ⑩ ❸ ❹ ➦ ↔ ➡ ➭ ➏ ➢ then ➡ ➭ ➏ ➢ ➃ ➅ ➡ ➭ ➏ ➢ ➆ ➇ ⑥ ➊ ➋ ⑩ ❶ ⑩ ❸ ❹ ➈ add complete ⑥ ➊ ➋ ⑩ ❶ ⑩ ❸ ❹ else if ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➦ ↔ ➡ ➭ ➏ ➢ then ➡ ➭ ➏ ➢ ➃ ➅ ➡ ➭ ➏ ➢ ➆ ➇ ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➈ add incomplete ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ end proc l-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ❹ ❻ if ➎ ➋ ➏ ➐ ↔ ⑦ ➥ ➎ ➋ ➏ ➐ ➦ ↔ predict left ⑥ ❶ ❹ then predict left ⑥ ❶ ❹ ➃ ➅ predict left ⑥ ❶ ❹ ➆ ➇ ➎ ➋ ➏ ➐ ➈ for ➔ ➮ ❮ ➏ ➮ ❮ ❰ with ➊ ❰ ➅ ➎ ➋ ➏ ➐ do add incomplete ⑥ ➔ ➮ ❮ ➏ ➮ ❮ ❰ ⑩ ❶ ⑩ ❶ ❹ l-predict ⑥ ➔ ➮ ❮ ➏ ➮ ❮ ❰ ⑩ ❶ ❹ end proc r-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ❹ ❻ if ➎ ➋ ➏ ➟ ➒ → ↔ ⑦ ➥ ➎ ➋ ➏ ➟ ➒ → ➦ ↔ predict right ⑥ ❶ ❹ then predict right ⑥ ❶ ❹ ➃ ➅ predict right ⑥ ❶ ❹ ➆ ➇ ➎ ➋ ➏ ➟ ➒ → ➈ for ➔ ➬ ➏ ➬ ❰ with ➊ ❰ ➅ ➎ ➋ ➏ ➟ ➒ → do add incomplete ⑥ ➔ ➬ ➏ ➬ ❰ ⑩ ❶ ⑩ ❶ ❹ r-predict ⑥ ➔ ➬ ➏ ➬ ❰ ⑩ ❶ ❹

end

The procedures l-predict and r-predict recursively generate top down predictions for an incomplete item, to both sides, if the item is dominating a seed, to the left, if it is in a right substring, and to the right otherwise. They keep track of the predictions generated so far using two arrays of length ✶ ✻ ✽ , storing the nonterminals for which left or right predictions have been introduced at a specific chart node.

The loops at chart node 3 and 4 in figure 2 have been generated by l-predict. Items that lie completely in right or left substrings stem from these top down predictions, like the item labeled with ✈ ✗ ✳ ❖ ✷ a208 ❖ or the complete itemwith label ✈ .

[Satta and Stock, 1994] give a more formal description of the algorithm, including an invariant describing its behaviour.

3 Modified Algorithm

In the modified algorithm, instead of fixing seed and border indices in advance, every chart item is assigned a state, which is one of right substring, left substring or seed dominating (right, left and seed in the pseudo-code, respectively). Additionally, complete items with a terminal category, i.e., input items, can have neutral state, in fact, they are given this state during initialization.

Because the search strategy of the parser shall be adaptable, a priority is assigned to every item, which is used in connection with a priority queue (an agenda) to expand the best items first. The assignment of priority values is omitted here for the sake of clarity.

During initialization, all input items are added to the chart, their state is set to neutral and they are added to the priority queue. Parsing then continues by taking the highest ranked item from the priority queue and expanding it. A seed is selected when a neutral terminal item is retrieved from the queue. Its state is updated to seed dominating, i.e., the item itself becomes a seed. This puts seed selection on a level with the expansion of items, simplifying the implementation of a search strategy, owing to uniformity.

If terminal items are neutral when they are combined with another item in the first or third for loop of the modified add incomplete procedure, they change state accordingly, either to left or right, depending on whether the incomplete item grew to the left, in which case the item is now member of a right substring, or vice versa. When such a terminal item is retrieved from the priority queue later during parsing, its state is already set and it does not become a seed.

Any other complete or incomplete combined items inherit their state from their daughters: if at least one of the daughters is seed dominating, the new item becomes seed dominating too, otherwise all daughters are members of the same substring, and the new item gets assigned the same state.

All conditionals that use the seed and border indices in the original algorithm are replaced by conditionals checking the state of the items. As a consequence, the seed and border indices are no longer needed.

Instead of a string with ✶ elements, the parser gets a word graph as input. A word graph is an acyclic directed graph a209 of terminal items ✂ ✷ ✆ ❂ ✆ ❃ ✎ with exactly one source and one sink node (nodes with in-degree resp. out-degree zero). The start and end node indices of the input items are typically in topological order, so that the source node gets index zero and the sink the maximal end node index of all input items, which in the modified version becomes the value of ✶ .

Parsing stops when either a complete derivation was found or the priority queue becomes empty, which means that the word graph must be rejected. Since all input items were added to the priority queue in the beginning, it is also guaranteed that every sub-path of the word graph has been processed properly if parsing should stop with a failure. Every input item will then have a non-neutral state, which means that it at least took part in some of the derivations.

The procedures l-predict and r-predict are the same as in the original algorithm, and are omitted here.

proc add complete ⑥ ⑦ ⑧ ⑩ ❶ ⑩ ❸ ❹ ❻ if state ⑥ ⑦ ⑧ ⑩ ❶ ⑩ ❸ ❹ ➅ seed then /* project step: add ➊ ➋ ➌ ➍ ➍ ➍ ➎ ➋ ➏ ➐ ➑ ⑦ ⑧ ➑ ➎ ➋ ➏ ➐ ➒ ➓ ➍ ➍ ➍ */ for ➔ ➐ ➏ ➐ ➒ → ➋ ↔ ➔ ↕ with ➎ ➋ ➏ ➐ ➒ → ➅ ⑦ ⑧ do add new ⑥ ➔ ➐ ➏ ➐ ➒ → ➋ ⑩ ❶ ⑩ ❸ ⑩ seed ⑩ seed ❹ elsif state ⑥ ⑦ ⑧ ⑩ ❶ ⑩ ❸ ❹ ➅ right then /* combine with ➊ ➋ ➌ ➍ ➍ ➍ ⑦ ⑧ ➑ ➎ ➋ ➏ ➐ ➒ → ➍ ➍ ➍ ➑ ➍ ➍ ➍ */ for ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ with ➎ ➋ ➏ ➐ ➅ ⑦ ⑧ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block left ⑥ ❸ ⑩ ➠ ❹ do add new ⑥ ➔ ➐ ➝ → ➏ ➟ ➋ ⑩ ❶ ⑩ ➠ ⑩ right ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❸ ⑩ ➠ ❹ ❹ block right ⑥ ❸ ⑩ ➠ ❹ ➃ ➅ block right ⑥ ❸ ⑩ ➠ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ elsif state ⑥ ⑦ ⑧ ⑩ ❶ ⑩ ❸ ❹ ➅ left then /* combine with ➊ ➋ ➌ ➍ ➍ ➍ ➑ ➍ ➍ ➍ ➎ ➋ ➏ ➟ ➑ ⑦ ⑧ ➍ ➍ ➍ */ for ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with ➎ ➋ ➏ ➟ ➒ → ➅ ⑦ ⑧ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block right ⑥ ➠ ⑩ ❶ ❹ do add new ⑥ ➔ ➐ ➏ ➟ ➒ → ➋ ⑩ ➠ ⑩ ❸ ⑩ left ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ➠ ⑩ ❶ ❹ ❹ block left ⑥ ➠ ⑩ ❶ ❹ ➃ ➅ block left ⑥ ➠ ⑩ ❶ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ end proc add incomplete ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ❻ /* ➔ ➐ ➏ ➟ ➋ ➃ ➊ ➋ ➌ ➳ ➳ ➳ ➎ ➋ ➏ ➐ ➑ ➎ ➋ ➏ ➐ ➒ → ➳ ➳ ➳ ➎ ➋ ➏ ➟ ➑ ➎ ➋ ➏ ➟ ➒ → ➳ ➳ ➳ */ if state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ↔ ➇ seed ⑩ right ➈ then l-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ❹ if state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ↔ ➇ seed ⑩ left ➈ then r-predict ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❸ ❹ if ➻ ➼ ➽ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block left ⑥ ❶ ⑩ ❸ ❹ then /* combine to the left with complete items */ for ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with state ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ↔ ➇ right ⑩ neutral ➈ do if state ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ➅ neutral then state ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ➃ ➅ right add new ⑥ ➔ ➐ ➝ → ➏ ➟ ➋ ⑩ ➠ ⑩ ❸ ⑩ state ⑥ ➎ ➋ ➏ ➐ ⑩ ➠ ⑩ ❶ ❹ ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ❹ block right ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ /* combine to the left with incomplete items */ for ⑥ ➔ ➾ ➏ ➐ ➋ ⑩ ➠ ⑩ ❶ ❹ ↔ ➡ ➤ ➏ ➭ with ➔ ➾ ➏ ➐ ➋ ➦ ↔ block right ⑥ ➠ ⑩ ❶ ❹ do add new ⑥ ➔ ➾ ➏ ➟ ➋ ⑩ ➠ ⑩ ❸ ⑩ state ⑥ ➔ ➾ ➏ ➐ ➋ ⑩ ➠ ⑩ ❶ ❹ ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ❹ block left ⑥ ➠ ⑩ ❶ ❹ ➃ ➅ block left ⑥ ➠ ⑩ ❶ ❹ ➆ ➇ ➔ ➾ ➏ ➐ ➋ ➈ block right ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block right ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ if ➪ ❼ ➶ ➋ ➥ ➔ ➐ ➏ ➟ ➋ ➦ ↔ block right ⑥ ❶ ⑩ ❸ ❹ then /* combine to the right with complete items */ for ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ with state ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ↔ ➇ left ⑩ neutral ➈ do if state ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ➅ neutral then state ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ➃ ➅ left add new ⑥ ➔ ➐ ➏ ➟ ➒ → ➋ ⑩ ❶ ⑩ ➠ ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ⑩ state ⑥ ➎ ➋ ➏ ➟ ➒ → ⑩ ❸ ⑩ ➠ ❹ ❹ block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ /* combine to the right with incomplete items */ for ⑥ ➔ ➟ ➏ ➾ ➋ ⑩ ❸ ⑩ ➠ ❹ ↔ ➡ ➢ ➏ ➤ ➥ a211 block left ⑥ ➔ ➟ ➏ ➾ ➋ ⑩ ❸ ⑩ ➠ ❹ do add new ⑥ ➔ ➐ ➏ ➾ ➋ ⑩ ❶ ⑩ ➠ ⑩ state ⑥ ➔ ➐ ➏ ➟ ➋ ⑩ ❶ ⑩ ❸ ❹ ⑩ state ⑥ ➔ ➟ ➏ ➾ ➋ ⑩ ❸ ⑩ ➠ ❹ ❹ block left ⑥ ❶ ⑩ ❸ ❹ ➃ ➅ block left ⑥ ❶ ⑩ ❸ ❹ ➆ ➇ ➔ ➐ ➏ ➟ ➋ ➈ block right ⑥ ❸ ⑩ ➠ ❹ ➃ ➅ block right ⑥ ❸ ⑩ ➠ ❹ ➆ ➇ ➔ ➟ ➏ ➾ ➋ ➈

end

proc add new ⑥ ➴ ⑩ ❶ ⑩ ❸ ⑩ a212 ➡ a213 ➡ a214 a215 ⑩ a212 ➡ a213 ➡ a214 a216 ❹ ❻ if ➴ ➅ ➔ ➬ ➏ ➮ ★ ➋ then ➴ ➃ ➅ ➊ ➋ if ➴ ➅ ✃ ➥ ❶ ➅ ➽ ➥ ❸ ➅ ❐ then exit ⑥ accept ❹ if ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➦ ↔ ➡ ➭ ➏ ➢ then if a212 ➡ a213 ➡ a214 a215 ➅ seed a218 a212 ➡ a213 ➡ a214 a216 ➅ seed then state ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ seed else if a212 ➡ a213 ➡ a214 a215 ➅ right then state ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ right else state ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ left ➡ ➭ ➏ ➢ ➃ ➅ ➡ ➭ ➏ ➢ ➆ ➇ ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➈ push ⑥ ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ⑩ p queue ❹ end proc main ⑥ a219 ❹ ❻ for ⑥ a213 ⑩ ❶ ⑩ ❸ ❹ ↔ a219 do ➡ ➭ ➏ ➢ ➃ ➅ ➡ ➭ ➏ ➢ ➆ ➇ ⑥ a213 ⑩ ❶ ⑩ ❸ ❹ ➈ state ⑥ a213 ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ neutral push ⑥ ⑥ a213 ⑩ ❶ ⑩ ❸ ❹ ⑩ p queue ❹ while a211 empty ⑥ p queue ❹ do ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ pop max ⑥ p queue ❹ if ➴ ↔ a221 ➥ state ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➅ neutral then state ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ ➃ ➅ seed if ➴ ↔ ⑦ ➆ a221 then add complete ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ else add incomplete ⑥ ➴ ⑩ ❶ ⑩ ❸ ❹ exit ⑥ reject ❹

end

4 Correctness of the modified algorithm

If a209 contains only string input and priorities are set appropriately to select the right seeds, the modified algorithm works like the original. This is achieved by using the maximal priority value for all seed input items, the minimal value for all other input items, and priority values strictly between these values for all other items. Thus, seeds will be considered first and appropriately marked, and other input items will be considered after all possible combinations have been tried in some order, which is consistent with the original.

It remains to be shown that in case of true word graph input, the algorithm will still be correct and redundancy-free. New situations arise from the fact that there are parallel subpaths of neutral input items to previously treated regions of the chart, and new, possibly derived items can now interact with existing ones created from previous expansions.

The argumentation will be based on the respective properties of the original, which can not be shown here. It is clear that sub-derivations with equal span and item label may be produced because of the ambiguity in the word graph input. These items are not redundant because they have different yields. The type of redundancy that must be avoided is the multiple creation of identical items with both identical derivation and yield, which could be produced by an incorrect implementation of the island algorithm due to bidirectionality and multiple seeds. Redundancy can therefore only occur relative to a path through the word graph. 1

Although there are six cases in total to be considered (three each for left and right substrings), the treatment of left and right substrings will be completely analogous, so we will content ourselves with the discussion of the former.

1 For an in-depth description of the redundancy problem on strings and formal proofs, see [Satta and Stock, 1994]

4.1 A new left substring ends in a right substring

In this situation, which is depicted in fig. 3, node ❃ behaves like a new border node between seed a222 ❛ and a222 ⑤ . Because of the completeness of the original algorithm, all possible derivations compatible with the seed a222 ❛ must be available at node ❃ , although some of themmay be blocked. Assume we lose a complete derivation because of an indispensable incomplete item that is blocked on the left side (like the item labeled ✳ in fig. 3). If this is the case, there must be ancestor items of ✳ whose creation caused the blocking. One of these ancestors, ultimately the one that ends in the sink node 2 , is available for combination at node ❃ , which is a contradiction.

As was argued above, redundant items can only occur relative to a path of input items through the word graph. Since the same synchronization of items was used for the path through a222 ⑤ and a222 ❛ with border ❃ as in the stringmethod, the chart must be free of redundancy for this path too.

A special case of the configuration described in this section is given when the new sub-path hits the old border node (e.g., node ❘ in fig. 3). In this case, it is obvious that all, and only the correct derivations will be created.

4.2 A new left substring ends in a left substring

All complete items starting at node ❃ in figure 4 are available to the new sub-path. Every derivation starting at ❃ that is compatible with the new seed a222 ⑤ but not with the old one ( a222 ❛ ) will be constructed by the appropriate predictions and expansions, and since the predict methods keep track of which nonterminals have already been predicted, no work is duplicated and thus, no redundancy is produced. For blocked incomplete items, the same argumentation as in 4.1 applies, which guarantees completeness.

2 Incomplete items ending in the sink node can not be blocked at the left side because there is no item to the right they can combine with.

4.3 An alternative left substring path overruns a seed

This situation, which is shown in figure 5, is almost the same as in section 4.2, except that the new items ending in node ❃ do not come from a new seed on the parallel path, but from an alternative path from seed a222 ❛ . Therefore, the same argumentation applies as in 4.2 above.

4.4 Worst Case Complexity

The number of symbols ❏ ❑ ✜ ▼ ✕ is bounded by ✲ ⑤ ❲ a223 ✡ a223 where ✲ ❲ is the maximal length of a rule ✑ ✪ ✡ . On the chart, and on the agenda, can not be more than a224 ⑤ ✂ a223 a0 a223 ✻ ✲ ⑤ ❲ a223 ✡ a223 ✎ items, where a224 ❯ a223 a209 a223 is the highest chart index and a223 a0 a223 ✁ a223 ✞ ✯ ✄ a223 .

The function add complete is called at most a224 ⑤ a223 a0 a223 times, and the second and third for loops in this function are executed atmost a224 ✲ ⑤ ❲ a223 ✡ a223 times, while the first is executed at most ✲ ❲ a223 ✡ a223 times, which makes this function a226 ✂ a224 ① a223 a0 a223 ✲ ⑤ ❲ a223 ✡ a223 ✎ .

The function add incomplete is called at most a224 ⑤ ✲ ⑤ ❲ a223 ✡ a223 times. The second and fourth for loops, where active items are combined, can be executed at most a224 ✲ ❲ a223 ✡ a223 times, which makes the whole function a226 ✂ a224 ① ✲ ① ❲ a223 ✡ a223 ✎ , while the first and third are executed at most a224 a223 a0 a223 times.

These two functions clearly dominate the prediction functions, which makes the whole algorithm a226 ✂ a224 ① a223 a0 a223 ✲ ⑤ ❲ a223 ✡ a223 ✎ or a226 ✂ a224 ① ✲ ① ❲ a223 ✡ a223 ✎ , whichever is dominant.

5 Conclusion and further considerations

An efficient island parsing algorithm for string input was generalized to make it more feasible for the use in speech applications. The new version deals with word graphs as input without losing the beneficial properties of the original. It also integrates the selection of seeds into the parser's search process, which, in addition to more uniformity, provides the user with more flexibility in the design of the search strategy.

The data structures for blocking and keeping the state of an item can be implemented as bit vectors, which produces minimal space and time overhead for all the blocking and state conditionals.

The modified algorithm has been implemented for context free grammars with annotated feature structures. This implementation also provides pluggable search strategies to facilitate experimentation.

From the point of view of the search strategy, the atomic action of the modified algorithm (one parsing task) is the expansion of an item, like, for example, in [Caraballo and Charniak, 1998]. To be able to define a more fine grained strategy, the parser could be changed such that the tasks are instead combination of two items, projection and prediction, or a subset of the three ([Kay, 1986], [Erbach, 1991]).

The price to pay for the increased flexibility is a larger agenda, maybe prohibitively large, if the word graphs are big and/or the grammar is highly ambiguous. The changes to the algorithm are obvious, and it will depend on the specific task, whether the more elaborate search strategy will achieve better results or improved parsing efficiency.

Acknowledgments

I am very indebted to Giorgio Satta for his help in fully understanding the bits and pieces of the original algorithm, for the discussions and for his patience. I also want to thank Berthold Crysmann and Melanie Siegel for their help in preparing this paper and the anonymous reviewers for their constructive comments. This research was supported by the German Ministry for Education and Research under grant no. 01 IM D01, to the project SmartWeb.