{'fraction_non_alphanumeric': 0.03926861403001382, 'fraction_numerical': 0.017545550949580643, 'mean_word_length': 4.6335988414192615, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simple, Accurate Parsing with an All-Fragments Grammar

We present a simple but accurate parser which exploits both large tree fragments and symbol refinement. We parse with all fragments of the training set, in contrast to much recent work on tree selection in data-oriented parsing and tree-substitution grammar learning. We require only simple, deterministic grammar symbol refinement, in contrast to recent work on latent symbol refinement. Moreover, our parser requires no explicit lexicon machinery, instead parsing input sentences as character streams. Despite its simplicity, our parser achieves accuracies of over 88% F1 on the standard English WSJ task, which is competitive with substantially more complicated state-of-the-art lexicalized and latent-variable parsers. Additional specific contributions center on making implicit all-fragments parsing efficient, including a coarse-to-fine inference scheme and a new graph encoding.


Introduction
Modern NLP systems have increasingly used dataintensive models that capture many or even all substructures from the training data. In the domain of syntactic parsing, the idea that all training fragments 1 might be relevant to parsing has a long history, including tree-substitution grammar (data-oriented parsing) approaches (Scha, 1990;Bod, 1993;Goodman, 1996a;Chiang, 2003) and tree kernel approaches (Collins and Duffy, 2002). For machine translation, the key modern advancement has been the ability to represent and memorize large training substructures, be it in contiguous phrases (Koehn et al., 2003) or syntactic trees (Galley et al., 2004;Chiang, 2005;Deneefe and Knight, 2009). In all such systems, a central challenge is efficiency: there are generally a combinatorial number of substructures in the training data, and it is impractical to explicitly extract them all. On both efficiency and statistical grounds, much recent TSG work has focused on fragment selection (Zuidema, 2007;Cohn et al., 2009;Post and Gildea, 2009).
At the same time, many high-performance parsers have focused on symbol refinement approaches, wherein PCFG independence assumptions are weakened not by increasing rule sizes but by subdividing coarse treebank symbols into many subcategories either using structural annotation (Johnson, 1998;Klein and Manning, 2003) or lexicalization (Collins, 1999;Charniak, 2000). Indeed, a recent trend has shown high accuracies from models which are dedicated to inducing such subcategories (Henderson, 2004;Matsuzaki et al., 2005;Petrov et al., 2006). In this paper, we present a simplified parser which combines the two basic ideas, using both large fragments and symbol refinement, to provide non-local and local context respectively. The two approaches turn out to be highly complementary; even the simplest (deterministic) symbol refinement and a basic use of an all-fragments grammar combine to give accuracies substantially above recent work on treesubstitution grammar based parsers and approaching top refinement-based parsers. For example, our best result on the English WSJ task is an F1 of over 88%, where recent TSG parsers 2 achieve 82-84% and top refinement-based parsers 3 achieve 88-90% (e.g., Table 5).
Rather than select fragments, we use a simplification of the PCFG-reduction of DOP (Goodman, 1996a) to work with all fragments. This reduction is a flexible, implicit representation of the fragments that, rather than extracting an intractably large grammar over fragment types, indexes all nodes in the training treebank and uses a compact grammar over indexed node tokens. This indexed grammar, when appropriately marginalized, is equivalent to one in which all fragments are explicitly extracted. Our work is the first to apply this reduction to full-scale parsing. In this direction, we present a coarse-to-fine inference scheme and a compact graph encoding of the training set, which, together, make parsing manageable. This tractability allows us to avoid selection of fragments, and work with all fragments.
Of course, having a grammar that includes all training substructures is only desirable to the extent that those structures can be appropriately weighted. Implicit representations like those used here do not allow arbitrary weightings of fragments. However, we use a simple weighting scheme which does decompose appropriately over the implicit encoding, and which is flexible enough to allow weights to depend not only on frequency but also on fragment size, node patterns, and certain lexical properties. Similar ideas have been explored in Bod (2001), Collins and Duffy (2002), and Goodman (2003). Our model empirically affirms the effectiveness of such a flexible weighting scheme in full-scale experiments.
We also investigate parsing without an explicit lexicon. The all-fragments approach has the advantage that parsing down to the character level requires no special treatment; we show that an explicit lexicon is not needed when sentences are considered as strings of characters rather than words. This avoids the need for complex unknown word models and other specialized lexical resources.
The main contribution of this work is to show practical, tractable methods for working with an all-fragments model, without an explicit lexicon. In the parsing case, the central result is that accuracies in the range of state-of-the-art parsers (i.e., over 88% F1 on English WSJ) can be obtained with no sampling, no latent-variable modeling, no smoothing, and even no explicit lexicon (hence negligible training overall). These techniques, however, are not limited to the case of monolingual parsing, offering extensions to models of machine translation, semantic interpretation, and other areas in which a similar tension exists between the desire to extract many large structures and the computational cost of doing so.

All-Fragments Grammars
We consider an all-fragments grammar G (see Figure 1(a)) derived from a binarized treebank B. G is formally a tree-substitution grammar (Resnik, 1992;Bod, 1993) wherein each subgraph of each training tree in B is an elementary tree, or fragment f , in G. In G, each derivation d is a tree (multiset) of fragments (Figure 1(c)), and the weight of the derivation is the product of the weights of the fragments: ω(d) = f ∈d ω(f ). In the following, the derivation weights, when normalized over a given sentence s, are interpretable as conditional probabilities, so G induces distributions of the form P (d|s).
In models like G, many derivations will generally correspond to the same unsegmented tree, and the parsing task is to find the tree whose sum of derivation weights is highest: t max = arg max t d∈t ω(d). This final optimization is intractable in a way that is orthogonal to this paper (Sima'an, 1996); we describe minimum Bayes risk approximations in Section 4.

Implicit Representation of G
Explicitly extracting all fragment-rules of a grammar G is memory and space intensive, and impractical for full-size treebanks. As a tractable alternative, we consider an implicit grammar G I (see Figure 1(b)) that has the same posterior probabilities as G. To construct G I , we use a simplification of the PCFG-reduction of DOP by Goodman (1996a). 4 G I has base symbols, which are the symbol types from the original treebank, as well as indexed symbols, which are obtained by assigning a unique index to each node token in the training treebank. The vast majority of symbols in G I are therefore indexed symbols. While it may seem that such grammars will be overly large, they are in fact reasonably compact, being linear in the treebank size B, while G is exponential in the length of a sentence. In particular, we found that G I was smaller than explicit extraction of all depth 1 and 2 unbinarized fragments for our ! SYMBOLS: X, for all types in treebank "

SYMBOLS:
Base: X for all types in treebank " Indexed: X i for all tokens of X in "

RULES:
Begin: i for all X i in " Continue: X i j Z k for all rule-tokens in " End: Figure 1: Grammar definition and sample derivations and fragments in the grammar for (a) the explicitly extracted all-fragments grammar G, and (b) its implicit representation G I . treebanks -in practice, even just the raw treebank grammar grows almost linearly in the size of B. 5 There are 3 kinds of rules in G I , which are illustrated in Figure 1(d). The BEGIN rules transition from a base symbol to an indexed symbol and represent the beginning of a fragment from G. The CONTINUE rules use only indexed symbols and correspond to specific depth-1 binary fragment tokens from training trees, representing the internal continuation of a fragment in G. Finally, END rules transition from an indexed symbol to a base symbol, representing the frontier of a fragment.
By construction, all derivations in G I will segment, as shown in Figure 1(d), into regions corresponding to tokens of fragments from the training treebank B. Let π be the map which takes appropriate fragments in G I (those that begin and end with base symbols and otherwise contain only indexed symbols), and maps them to the corresponding f in G. We can consider any derivation d I in G I to be a tree of fragments f I , each fragment a token of a fragment type f = π(f I ) in the original grammar G. By extension, we can therefore map any derivation d I in G I to the corresponding The mapping π is an onto mapping from G I to 5 Just half the training set (19916 trees) itself had 1.7 million depth 1 and 2 unbinarized rules compared to the 0.9 million indexed symbols in G I (after graph packing). Even extracting binarized fragments (depth 1 and 2, with one order of parent annotation) gives us 0.75 million rules, and, practically, we would need fragments of greater depth.
G. In particular, each derivation d in G has a nonempty set of corresponding derivations . Therefore, the set of derivations in G is preserved in G I . We now discuss how weights can be preserved under π.

Equivalence for Weighted Grammars
In general, arbitrary weight functions ω on fragments in G do not decompose along the increased locality of G I . However, we now consider a usefully broad class of weighting schemes for which the posterior probabilities under G of derivations d are preserved in G I . In particular, assume that we have a weighting ω on rules in G I which does not depend on the specific indices used. Therefore, any fragment f I will have a weight in G I of the form: where b is the BEGIN rule, r are CONTINUE rules, and e are END rules in the fragment f I (see Figure 1(d)). Because ω is assumed to not depend on the specific indices, all f I which correspond to the same f under π will have the same weight ω I (f ) in G I .
In this case, we can define an induced weight Figure 2: Rules defined for grammar G I and weight schema for the DOP1 model, the Min-Fragments model (Goodman (2003)) and our model. Here s(X) denotes the total number of fragments rooted at base symbol X.

RULE TYPES WEIGHTS
for fragments f in G by where now b , r and e are non-indexed type abstractions of f 's member productions in G I and Under the weight function ω G (f ), any derivation d in G will have weight which obeys and so the posterior P (d|s) of a derivation d for a sentence s will be the same whether computed in G or G I . Therefore, provided our weighting function on fragments f in G decomposes over the derivational representation of f in G I , we can equivalently compute the quantities we need for inference (see Section 4) using G I instead.
3 Parameterization of Implicit Grammars

Classical DOP1
The original data-oriented parsing model 'DOP1' (Bod, 1993) is a particular instance of the general weighting scheme which decomposes appropriately over the implicit encoding, described in Section 2.3. Figure 2 shows rule weights for DOP1 in the parameter schema we have defined. The END rule weight is 0 or 1 depending on whether A is an intermediate symbol or not. 6 The local fragments in DOP1 were flat (non-binary) so this weight choice simulates that property by not allowing switching between fragments at intermediate symbols. The original DOP1 model weights a fragment f in G as ω G (f ) = n(f )/s(X), i.e., the frequency of fragment f divided by the number of fragments rooted at base symbol X. This is simulated by our weight choices (Figure 2) where each fragment f I in G I has weight ω I (f I ) = 1/s(X) and therefore, . Given the weights used for DOP1, the recursive formula for the number of fragments s(X i ) rooted at indexed symbol X i (and for the CONTINUE rule where s(Y j ) and s(Z k ) are the number of fragments rooted at indexed symbols Y j and Z k (nonintermediate) respectively. The number of fragments s(X) rooted at base symbol X is then Implicitly parsing with the full DOP1 model (no sampling of fragments) using the weights in Figure 2 gives a 68% parsing accuracy on the WSJ dev-set. 7 This result indicates that the weight of a fragment should depend on more than just its frequency.

Better Parameterization
As has been pointed out in the literature, largefragment grammars can benefit from weights of fragments depending not only on their frequency but also on other properties. For example, Bod (2001) restricts the size and number of words in the frontier of the fragments, and Collins and Duffy (2002) and Goodman (2003) both give larger fragments smaller weights. Our model can incorporate both size and lexical properties. In particular, we set ω CONT (r) for each binary CON-TINUE rule r to a learned constant ω BODY , and we set the weight for each rule with a POS parent to a 6 Intermediate symbols are those created during binarization. 7 For DOP1 experiments, we use no symbol refinement. We annotate with full left binarization history to imitate the flat nature of fragments in DOP1. We use mild coarse-pass pruning (Section 4.1) without which the basic all-fragments chart does not fit in memory. Standard WSJ treebank splits used: sec 2-21 training, 22 dev, 23 test.
q(e) Figure 3: Inference: Different objectives for parsing with posteriors. A, B, C are base symbols, Ax, By, Cz are indexed symbols and i,j,k are between-word indices. Hence, (Ax, i, j) represents a constituent labeled with Ax spanning words i to j. I(Ax, i, j) and O(Ax, i, j) denote the inside and outside scores of this constituent, respectively. For brevity, we write c ≡ (A, i, j) and e ≡ (A → B C, i, k, j). Also, tmax is the highest scoring parse. Adapted from Petrov and Klein (2007).
constant ω LEX (see Figure 2). Fractional values of these parameters allow the weight of a fragment to depend on its size and lexical properties. Another parameter we introduce is a 'switching-penalty' c sp for the END rules ( Figure 2). The DOP1 model uses binary values (0 if symbol is intermediate, 1 otherwise) as the END rule weight, which is equivalent to prohibiting fragment switching at intermediate symbols. We learn a fractional constant a sp that allows (but penalizes) switching between fragments at annotated symbols through the formulation c sp (X intermediate ) = 1 − a sp and c sp (X non−intermediate ) = 1 + a sp . This feature allows fragments to be assigned weights based on the binarization status of their nodes.
With the above weights, the recursive formula for s(X i ), the total weighted number of fragments rooted at indexed symbol X i , is different from The formula uses ω LEX in place of ω BODY if r is a lexical rule (Figure 2).
The resulting grammar is primarily parameterized by the training treebank B. However, each setting of the hyperparameters (ω BODY , ω LEX , a sp ) defines a different conditional distribution on trees. We choose amongst these distributions by directly optimizing parsing F1 on our development set. Because this objective is not easily differentiated, we simply perform a grid search on the three hyperparameters. The tuned values are ω BODY = 0.35, ω LEX = 0.25 and a sp = 0.018. For generalization to a larger parameter space, we would of course need to switch to a learning approach that scales more gracefully in the number of tunable hyperparameters. 8 8 Note that there has been a long history of DOP estimators. The generative DOP1 model was shown to be inconsis-

Efficient Inference
The previously described implicit grammar G I defines a posterior distribution P (d I |s) over a sentence s via a large, indexed PCFG. This distribution has the property that, when marginalized, it is equivalent to a posterior distribution P (d|s) over derivations in the correspondingly-weighted all-fragments grammar G. However, even with an explicit representation of G, we would not be able to tractably compute the parse that maximizes P (t|s) = d∈t P (d|s) = d I ∈t P (d I |s) (Sima'an, 1996). We therefore approximately maximize over trees by computing various existing approximations to P (t|s) (Figure 3). Goodman (1996b), Petrov and Klein (2007), and Matsuzaki et al. (2005) describe the details of constituent, rule-sum and variational objectives respectively. Note that all inference methods depend on the posterior P (t|s) only through marginal expectations of labeled constituent counts and anchored local binary tree counts, which are easily computed from P (d I |s) and equivalent to those from P (d|s). Therefore, no additional approximations are made in G I over G.
As shown in Table 1, our model (an allfragments grammar with the weighting scheme tent by Johnson (2002). Later, Zollmann and Sima'an (2005) presented a statistically consistent estimator, with the basic insight of optimizing on a held-out set. Our estimator is not intended to be viewed as a generative model of trees at all, but simply a loss-minimizing conditional distribution within our parametric family. shown in Figure 2) achieves an accuracy of 88.5% (using simple parent annotation) which is 4-5% (absolute) better than the recent TSG work (Zuidema, 2007;Cohn et al., 2009;Post and Gildea, 2009) and also approaches state-of-theart refinement-based parsers (e.g., Charniak and Johnson (2005), Petrov and Klein (2007)). 9

Coarse-to-Fine Inference
Coarse-to-fine inference is a well-established way to accelerate parsing. Charniak et al. (2006) introduced multi-level coarse-to-fine parsing, which extends the basic pre-parsing idea by adding more rounds of pruning. Their pruning grammars were coarse versions of the raw treebank grammar. Petrov and Klein (2007) propose a multistage coarse-to-fine method in which they construct a sequence of increasingly refined grammars, reparsing with each refinement. In particular, in their approach, which we adopt here, coarse-to-fine pruning is used to quickly compute approximate marginals, which are then used to prune subsequent search. The key challenge in coarse-to-fine inference is the construction of coarse models which are much smaller than the target model, yet whose posterior marginals are close enough to prune with safely.
Our grammar G I has a very large number of indexed symbols, so we use a coarse pass to prune away their unindexed abstractions. The simple, intuitive, and effective choice for such a coarse grammar G C is a minimal PCFG grammar composed of the base treebank symbols X and the minimal depth-1 binary rules X → Y Z (and with the same level of annotation as in the full grammar). If a particular base symbol X is pruned by the coarse pass for a particular span (i, j) (i.e., the posterior marginal P (X, i, j|s) is less than a certain threshold), then in the full grammar G I , we do not allow building any indexed symbol X l of type X for that span. Hence, the projection map for the coarse-to-fine model is π C : X l (indexed symbol) → X (base symbol).
We achieve a substantial improvement in speed and memory-usage from the coarse-pass pruning. Speed increases by a factor of 40 and memoryusage decreases by a factor of 10 when we go 9 All our experiments use the constituent objective except when we report results for max-rule-sum and maxvariational parsing (where we use the parameters tuned for max-constituent, therefore they unsurprisingly do not perform as well as max-constituent). Evaluations use EVALB, see http://nlp.cs.nyu.edu/evalb/. No Pruning (PT = -inf) 89.8 Figure 5: Effect of coarse-pass pruning on parsing accuracy (WSJ, training ≤ 20 words, tested on dev-set ≤ 20 words). This graph shows that the fortuitous improvement due to pruning is very small and that the peak accuracy is almost equal to the accuracy without pruning (the dotted line). from no pruning to pruning with a −6.2 log posterior threshold. 10 Figure 4 depicts the variation in parsing accuracies in response to the amount of pruning done by the coarse-pass. Higher posterior pruning thresholds induce more aggressive pruning. Here, we observe an effect seen in previous work (Charniak et al. (1998), Petrov and Klein (2007), ), that a certain amount of pruning helps accuracy, perhaps by promoting agreement between the coarse and full grammars (model intersection). However, these 'fortuitous' search errors give only a small improvement and the peak accuracy is almost equal to the parsing accuracy without any pruning (as seen in Figure 5). 11 This outcome suggests that the coarsepass pruning is critical for tractability but not for performance.
tree-to-graph encoding Figure 6: Collapsing the duplicate training subtrees converts them to a graph and reduces the number of indexed symbols significantly.

Packed Graph Encoding
The implicit all-fragments approach (Section 2.2) avoids explicit extraction of all rule fragments. However, the number of indexed symbols in our implicit grammar G I is still large, because every node in each training tree (i.e., every symbol token) has a unique indexed symbol. We have around 1.9 million indexed symbol tokens in the word-level parsing model (this number increases further to almost 12.3 million when we parse character strings in Section 5.1). This large symbol space makes parsing slow and memory-intensive.
We reduce the number of symbols in our implicit grammar G I by applying a compact, packed graph encoding to the treebank training trees. We collapse the duplicate subtrees (fragments that bottom out in terminals) over all training trees. This keeps the grammar unchanged because in an tree-substitution grammar, a node is defined (identified) by the subtree below it. We maintain a hashmap on the subtrees which allows us to easily discover the duplicates and bin them together. The collapsing converts all the training trees in the treebank to a graph with multiple parents for some nodes as shown in Figure 6. This technique reduces the number of indexed symbols significantly as shown in Table 2 (1.9 million goes down to 0.9 million, reduction by a factor of 2.1). This reduction increases parsing speed by a factor of 1.4 (and by a factor of 20 for character-level parsing, see Section 5.1) and reduces memory usage to under 4GB.
We store the duplicate-subtree counts for each indexed symbol of the collapsed graph (using a hashmap). When calculating the number of frag-   ments s(X i ) parented by an indexed symbol X i (see Section 3.2), and when calculating the inside and outside scores during inference, we account for the collapsed subtree tokens by expanding the counts and scores using the corresponding multiplicities. Therefore, we achieve the compaction with negligible overhead in computation.

Character-Level Parsing
The all-fragments approach to parsing has the added advantage that parsing below the word level requires no special treatment, i.e., we do not need an explicit lexicon when sentences are considered as strings of characters rather than words. Unknown words in test sentences (unseen in training) are a major issue in parsing systems for which we need to train a complex lexicon, with various unknown classes or suffix tries. Smoothing factors need to be accounted for and tuned. With our implicit approach, we can avoid training a lexicon by building up the parse tree from characters instead of words. As depicted in Figure 7, each word in the training trees is split into its corresponding characters with start and stop boundary tags (and then binarized in a standard rightbranching style). A test sentence's words are split up similarly and the test-parse is built from training fragments using the same model and inference procedure as defined for word-level parsing (see Sections 2, 3 and 4). The lexical items (alphabets, digits etc.) are now all known, so unlike word-level parsing, no sophisticated lexicon is needed.
We choose a slightly richer weighting scheme  for this representation by extending the twoweight schema for CONTINUE rules (ω LEX and ω BODY ) to a three-weight one: ω LEX , ω WORD , and ω SENT for CONTINUE rules in the lexical layer, in the portion of the parse that builds words from characters, and in the portion of the parse that builds the sentence from words, respectively. The tuned values are ω SENT = 0.35, ω WORD = 0.15, ω LEX = 0.95 and a sp = 0. The character-level model achieves a parsing accuracy of 88.0% (see Table 3), despite lacking an explicit lexicon. 12 Character-level parsing expands the training trees (see Figure 7) and the already large indexed symbol space size explodes (1.9 million increases to 12.3 million, see Table 2). Fortunately, this is where the packed graph encoding (Section 4.2) is most effective because duplication of character strings is high (e.g., suffixes). The packing shrinks the symbol space size from 12.3 million to 1.1 million, a reduction by a factor of 11. This reduction increases parsing speed by almost a factor of 20 and brings down memory-usage to under 8GB. 13

Basic Refinement: Parent Annotation and Horizontal Markovization
In a pure all-fragments approach, compositions of units which would have been independent in a basic PCFG are given joint scores, allowing the representation of certain non-local phenomena, such as lexical selection or agreement, which in fully local models require rich state-splitting or lexicalization. However, at substitution sites, the coarseness of raw unrefined treebank symbols still creates unrealistic factorization assumptions. A standard solution is symbol refinement; Johnson (1998) presents the particularly simple case of parent annotation, in which each node is 12 Note that the word-level model yields a higher accuracy of 88.5%, but uses 50 complex unknown word categories based on lexical, morphological and position features (Petrov et al., 2006). Cohn et al. (2009) also uses this lexicon.
13 Full char-level experiments (w/o packed graph encoding) could not be run even with 50GB of memory. We calculate the improvement factors using a smaller experiment with 70% training and fifty 20-word test sentences.  Table 4: F1 for a basic PCFG, and incorporation of basic refinement, all-fragments and both, for WSJ dev-set (≤ 40 words). P = 1 means parent annotation of all non-terminals, including the preterminal tags. H = 1 means one level of markovization. Results from Klein and Manning (2003). marked with its parent in the underlying treebank. It is reasonable to hope that the gains from using large fragments and the gains from symbol refinement will be complementary. Indeed, previous work has shown or suggested this complementarity. Sima'an (2000) showed modest gains from enriching structural relations with semi-lexical (prehead) information. Charniak and Johnson (2005) showed accuracy improvements from composed local tree features on top of a lexicalized base parser. Zuidema (2007) showed a slight improvement in parsing accuracy when enough fragments were added to learn enrichments beyond manual refinements. Our work reinforces this intuition by demonstrating how complementary they are in our model (∼20% error reduction on adding refinement to an all-fragments grammar, as shown in the last two rows of Table 4). Table 4 shows results for a basic PCFG, and its augmentation with either basic refinement (parent annotation and one level of markovization), with all-fragments rules (as in previous sections), or both. The basic incorporation of large fragments alone does not yield particularly strong performance, nor does basic symbol refinement. However, the two approaches are quite additive in our model and combine to give nearly state-of-the-art parsing accuracies.

Additional Deterministic Refinement
Basic symbol refinement (parent annotation), in combination with all-fragments, gives test-set accuracies of 88.5% (≤ 40 words) and 87.6% (all), shown as the Basic Refinement model in Table 5. Klein and Manning (2003) describe a broad set of simple, deterministic symbol refinements beyond parent annotation. We included ten of their simplest annotation features, namely: ditional Refinement, Table 5) improves the testset accuracies to 88.7% (≤ 40 words) and 88.1% (all), which is equal to a strong lexicalized parser (Collins, 1999), even though our model does not use lexicalization or latent symbol-split induction.
6 Other Results

Parsing Speed and Memory Usage
The word-level parsing model using the whole training set (39832 trees, all-fragments) takes approximately 3 hours on the WSJ test set (2245 trees of ≤40 words), which is equivalent to roughly 5 seconds of parsing time per sentence; and runs in under 4GB of memory. The character-level version takes about twice the time and memory. This novel tractability of an allfragments grammar is achieved using both coarsepass pruning and packed graph encoding. Microoptimization may further improve speed and memory usage. Figure 8 shows how WSJ parsing accuracy increases with increasing amount of training data (i.e., percentage of WSJ sections 2-21). Even if we train on only 10% of the WSJ training data (3983 sentences), we still achieve a reasonable parsing accuracy of nearly 84% (on the development set, ≤ 40 words), which is comparable to the fullsystem results obtained by Zuidema (2007), Cohn et al. (2009) and Post and Gildea (2009).

Other Language Treebanks
On the French and German treebanks (using the standard dataset splits mentioned in Petrov and Klein (2008)), our simple all-fragments parser achieves accuracies in the range of top refinementbased parsers, even though the model parameters were tuned out of domain on WSJ. For German, our parser achieves an F1 of 79.8% compared to 81.5% by the state-of-the-art and substantially more complex  work. For French, our approach yields an F1 of 78.0% vs. 80.1% by . 14

Conclusion
Our approach of using all fragments, in combination with basic symbol refinement, and even without an explicit lexicon, achieves results in the range of state-of-the-art parsers on full scale treebanks, across multiple languages. The main takeaway is that we can achieve such results in a very knowledge-light way with (1) no latent-variable training, (2) no sampling, (3) no smoothing beyond the existence of small fragments, and (4) no explicit unknown word model at all. While these methods offer a simple new way to construct an accurate parser, we believe that this general approach can also extend to other large-fragment tasks, such as machine translation.