Efficient Semiring-Weighted Earley Parsing

This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley's O N 3 |G||R| , which is unworkable for the large grammars that arise in natural language processing, to O N 3 |G| , which matches the runtime of CKY on a binarized version of the grammar G. Here N is the length of the sentence, |R| is the number of productions in G, and |G| is the total length of those productions. We also provide a version that achieves runtime of O N 3 |M| with |M| ≤ |G| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars. https://github.com/rycolab/ earleys-algo 7 All methods in this paper can be also applied directly to lattice parsing, in which i, j, k range over states in an acyclic lattice of possible input strings, and 0 and N refer to the unique initial and final states. A lattice edge from j to k labeled with terminal a is then encoded by the axiom [j, k, a]. 8 Assuming that all nonterminals B ∈ N are generating, i.e., ∃x ′ ∈ Σ * such that B * ⇒ x ′ . To ensure this, repeatedly mark B ∈ N as generating whenever R contains some B → ρ such that all nonterminals in ρ are already marked as generating. Then delete any unmarked nonterminals and their rules. 9 Earley (1970) also generalized the algorithm to prove this item only if it can appear in a proof of some string that begins with x 0:(j+∆) , for a fixed ∆. This is lookahead of ∆ tokens.