{'fraction_non_alphanumeric': 0.032549805895652914, 'fraction_numerical': 0.011347638752612943, 'mean_word_length': 4.3988945186549975, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parsing Russian: a hybrid approach

We present an approach for natural language parsing in which dependency and constituency parses are acquired simultaneously. This leads to accurate parses represented in a specific way, richer than constituency or dependency tree. It also allows reducing parsing time complexity. Within the proposed approach, we show how to treat some significant phenomena of the Russian language and also perform a brief evaluation of the parser implementation, known as DictaScope Syntax.


Introduction
A syntactic parser inputs a sentence and produces information on syntactic relationships between parts of the sentence. It is an open question which method is the most convenient one to represent these relationships. In this paper, we are focusing on two of those methods. The first one, a constituency tree (CT), is a representation of a sentence by a set of nested fragments -groups, each group corresponding to a syntactically coherent phrase. The second one, a dependency tree (DT), expresses relationships by a set of syntactic links between pairs of tokens. Figure 1 demonstrates correspondence between CT and DT: one is clearly derivable from another. In applications, one usually needs to transform CT into DT due to the following fact: if a tree is correct, then subjects, objects and adverbials of some predicate X are always direct children of the node X in DT. With a traditional CT framework these children can be obtained in much less intuitive way by browsing up and down through constituents, as shown in Figure 1 by dotted lines. According to this comparison, DT transparently maps onto the level of semantic representation, Figure 1: A constituency tree (upper) and a dependency tree (lower) for a sentence "A blue ball lies on the sand". thereby DT-s are considered most appropriate in applications (Jurafsky and Martin, 2009) like sentiment analysis and fact extraction.
Constituency parsing. Despite the usefulness of DT-s, CT-s have a longer history of application as a computational model. For now, probabilistic constituency parser by (Charniak, 1997) and its derivatives are considered the state of the art for English. Unfortunately, the framework of constituency parsing, taken alone, is not productive for languages such as Russian. It turns out that the number of rules in a grammar start to grow fast if one tries to describe an inflecting language with a free word order explicitly. As a result, pure constituency parsers are not well known for Russian. It has recently been confirmed by a Russian syntactic parsers task at the Dialogue conference (see http://www.dialog-21.ru), at which several parsers were presented and all of them used DT formalism as a basis. 1 In examples, we put indices for words in correspondence with English translation (often with omitted articles "a", "the"), refer to any word by its index, and to a phrase by indices of its starting and finishing word.
2 Dependency tree is called projective if each subtree corresponds to a continuous fragment of the source sentence. There is evidence that more than 80% of the sentences are usually projective in European natural languages. A famous example of nonprojectivity for Russian is 1 2 3 4 5 "I1've raised4 a monument2 for myself3 not made by hands5" from Pushkin, where link 4→1 overlaps 2→5. Toward the hybrid approach. It would be possible to resolve problems with homogenous parts if additional vertices could be added to the DT, like in Figure 2.G, representing supplementary constituents with synthesized grammar values. Unfortunately, known approaches for dependency parsing assume that all vertices are predefined before the algorithm starts, so it is impossible to include new vertices on the fly without inventing new parsing methods.
The idea of combining dependencies and constituencies directly is not a new one. For Russian, (Gladkij, 1985) suggested designating a standard relation between predicate and subject by a syntactic link, along with adding a separate constituent for compound predicative groups like from 1 2 3 4 "The driver 4 must 2 give 3 way 1 (to smb.). . . ", which has a nonprojective DT. This solution immediately reduces the number of overlapping dependency links for compound predicates, because links that tend to over-lap are packed inside the constituent. In (Kurohashi and Nagao, 1994) constituents for groups of homogenous parts are prebuilt to be treated as single units during the next step by a dependency parser for Japanese. In (Okatiev et al., 2010) preprocessing of certain tokens connected to constituents is performed before the dependency parsing. In (Wang and Zong, 2010) a third-party black-box dependency parser is used to improve the results of author's constituency parser, achieving 10% boost in F 1 . Additionally, there is evidence that ABBYY Compreno (Anisimovich et al., 2012) tracks the order in sequences of consecutive tokens so it actually exploits some kind of constituents throughout the process of dependency parsing.
In this paper, we propose a method of representing a parse tree, which is a combination of CT and DT and eliminates some disadvantages of both. Then we describe syntactic rules that guide the process of simultaneous bottom-up acquisition of multiple syntactically ambiguous DT-s and CTs for a given sentence, ranked by syntactic relevance. In addition, we discuss some properties of the rule base that is built in the framework of proposed rules description language. After that, we show that it is possible to extend the classical Cocke-Younger-Kasami algorithm (Kasami, 1965) to use grammar rules of arbitrary arity without grammar binarization and to exploit intermediate DT-s to increase efficiency. Moreover, we demonstrate how to achieve a reasonable ranking of solutions without using any additional statistical information. In conclusion, we discuss possible extensions of the approach.

Representing the Parse Tree
Our goal is to achieve the most complete representation of syntactic relations between words and/or chunks of a given sentence. The subject of semantic representation, e.g. semantic labeling of predicate participants or questions on the edges, are not discussed further. We assume that such information can be surfaced either during the process of analysis or directly afterwards by semantic interpretation of resulting parse trees.
As it was mentioned, it is possible to avoid disadvantages of DT-s if one finds a way to bring additional vertices to these trees. Though it is not natural for DT-s to have such vertices, it is common for constituents in CT-s to acquire derived grammar values. Thereafter, instead of building a parse tree of a completely new type, we obtain the representation that consists of three components: 1) constituency tree -CT, 2) dependency tree -DT, 3) hybrid tree -HT. CT strictly corresponds to a system of syntactic rules given preliminarily, and DT is built by instructions from rules at each step of the bottom-up analysis driven by this system. A hybrid representation, HT, that is based on DT but depicts homogenous parts, dependent clauses and nested sentences in a particular way. As a next step, we declare a balanced system of agreements between these different representations.
Assumptions for a constituency tree. We only require that CT correctly corresponds to the given sentence, and phrases of CT do not need to correspond to the expected expressions of VP, NP, AP etc. E.g., one can declare a specific rule that generates a constituent that simultaneously corresponds to a subject and a verb, e.g.
. Such a phrase corresponds both to VP and NP and is atypical, but the corresponding rule can produce a proper fragment of a nonprojective DT and HT, which is the main goal in this context. To summarize, in the proposed model constituencies play an utilitarian role, they are treated like carriers for parts of DT and are borrowed at certain decision points to form a resulting HT.
Assumptions for a dependency tree. During the parsing, a hypothesis of syntactic locality is considered, that states: tokens that are close linearly in a sentence are more likely to have a syntactic relationship. If there are several methods to represent a syntactic phenomenon, we choose a method that fits it best. Recalling Figure 2, one can observe that in 2.A and 2.B two links correspond to different linear distances between corresponding vertices, while in C-F each link corresponds to a unity distance. Let us call the latter kind of homogeneity representation "a chain scheme" and require syntactic rules to follow it.
The following assumptions are made: 1) prepositions become roots of the corresponding prepositional phrases; 2) subordinate conjunctions become roots of the corresponding dependent clauses; 3) punctuation marks, quotes and coordination conjunctions are removed from DT and will be properly presented in HT.
The following link types are expected: agreement (Adj+Noun, Noun+Noun, etc), control (Verb+Noun, prepositional phrases etc), contiguity (for adverbs, particles etc.), isolation for dependent clauses and coordination for chains of homogenous parts. For cases when a synthesized grammar value is needed like in Figure 2.G, we do not expect a special new vertex to be introduced in DT. Instead, each vertex of DT contains a reference to the corresponding constituency in CT, which holds its own grammar value. By default, this value is inherited from the head element of the constituent, but can be overridden, which is the case for homogeneity.
Assumptions for a hybrid tree are revealed by the example in Figure 3, where an XML-file is represented for a HT of a sentence with two dependent clauses 8-11 and 12-19, a nested sentence 1-19 and homogenous nouns 17 and 19. Only significant details are shown in the figureshortened grammar values (N for Noun etc) as GV and wordforms as W. Full representation also includes normal forms, detailed grammar values, tokens' positions and link types.
Subordinate clauses are presented under Subord tag as a nested group, while nested sentences are located under S tag. The group of two homogenous nouns is placed under Coord, but, unlike corresponding DT, homogenous members do not form a chain and are located on a single level inside a special Group tag. Such Group can have any number of dependent elements which are placed between </Group> and </Coord> (shown in Figure 4 below). There, the agreement by number between the group of two nouns 2-4 and the adjective 1 is taken into account, and the adverb 10 adjoins to the group of verbs 6 and 9 but not to a single verb.

The Rule Base
Linguistic data. We use a set of subcategorization frames for about 25 000 verbs, deverbatives and other predicative words, which is collected at our side through standard techniques of collocations and lexics aquisition from (Manning and Schütze, 1999). A morphological dictionary consists of about 5 mln wordforms.
Morphological hierarchy. In many cases, it is useful to unite different parts of speech into one metapart which possesses some common properties. E.g., participles share properties of verbs and adjectives. For verbs, the class ComVerb is introduced, which includes Verb in both finite and infinite forms, Participle and Transgressive, for adjectives -the class ComAdj with FullAdj, ShortAdj and Participle. This concept leads to the reduction in the number of syntactic rules.
The language of syntactic rules is shown by an example that describes a coordination relation between an adjective and a noun: Section T declares that a template should check grammar values of consecutive phrases PH1 and PH2, while section C checks required properties of them. If phrases fit T and C, then a DT is built according to L section by a link from the main word of the second constituent to the main word of the first, plus trees of PH1 and PH2. The second phrase is declared the head one (Main: 2) for the new phrase built by AgreeNounAdj rule.
Coordination. It is possible to override grammar value of a new phrase PH, which is shown by an example of homogenous nouns: Ambiguous compounds. Some compounds in Russian have their own grammar values in certain contexts. E.g., "by reason of" is sometimes a preposition equivalent to ¹ "because of" (as preposition): ℄℄℄ "judged on reason and consequence" vs. ℄ ℄ "was late by reason of traffic jams". In contrast to context rules for such constructions, we use pure syntactic rules for testing both versions, introducing a compound version by the rule: Nonprojective parses for compound predicates are processed by the following rule which produces a nonprojective DT. Despite nonprojectivity, it brings no problem for CT parsing process: Punctuation. Roles of junctions guide the parsing process. E.g., we consider that a junction that has exactly one role, which is ending isolator, is equivalent to a whitespace. Let us see how the rule AgreeNounAdj will parse the example under this assumption: 4 "shade 4 , as blue 1 as 2 a sea 3 ". One can verify that, due to consideration, the second comma no longer prevents this phrase from being covered by AgreeNounAdj. Another way to track these roles is to reject false control in genitive, e.g.
Overall base. For Russian, we have built a rule base with 90 rules, divided into 7 groups, one for each type of syntactic relations to be included into DT. These rules exploit 20 predicates in criterion sections and 10 additional phrase properties.

The Algorithm
We provide a modification of the Cocke-Yanger-Kasami algorithm (CYK) to find DT-s by corresponding CT-s that can be derived by rules described above and that are best in a specified way.
In our interpretation, CYK has the following structure. It inputs a sentence of n tokens. Empty n × n matrix M is set up and its main diagonal is filled with one-token phrases, each phrase at a cell M [i][i] takes some grammar value from the ith token of the sentence, i = 1, . . . , n as its head. CYK iterates all diagonals from the main diagonal of M to its upper-right cell M [1] [n]. Each cell on the diagonal of length k ∈ {n−1, . . . , 1} will contain only phrases of exactly k consecutive tokens, so M [1][n] will contain exactly those phrases that correspond to consecutive tokens, i.e. the entire sentence.
For CYK, it is traditionally assumed that each rule has exactly two nonterminals, and grammars formed by such rules are called binarized grammars (also known as "in Chomsky normal form"). Now consider the binarized rule R : P h 1 P h 2 → P h. If one wants to derive a phrase P h of consecutive tokens by this rule, then one should look at consecutive phrases P h 1 and P h 2 with properties defined by R and of j and k − j tokens correspondently. So, standing at M [i][i + n − k], i ∈ {1, . . . , k}, CYK searches for P h 1 in j cells in the current row to the left and then for P h 2 in k−j lower diagonals in the current column to the bottom, checking them by R if both P h 1 and P h 2 are found for some j and storing corresponding P h in Figure 5 shows M at the moment when CYK has finished for a particular input. Rules of arbitrary arity. Surprisingly, the extension of CYK for grammars that are not binarized is not widely discussed in literature. Instead, issues of binarization and special classes of grammars that do not lead to exponential growth of the binarized version are proposed (Lange and Leiß, 2009). Indeed, due to the author's experience, researchers argue to reject using CYK, because the increase in the size of the grammar through binarization degrades the performance significantly. Although it is true, we further show that it is not necessary at all to binarize grammar to use CYK.
To use the rule system proposed earlier, we modify CYK in the following way. Consider the rule R : P h 1 P h 2 . . . P h r → P h. One can treat it as a rule R ′ : P h 1 P hL → P h, where P hL = P h 2 P h 3 . . . P h r . In this way, the problem reduces to the former case of binarized grammar. When a reduction is applied to P hL recursively and finally some P h r is fixed, a set of P h 1 , . . . , P h r can be checked against R. This check is performed as described in Section 3. One can verify that modification increases the worst run time of CYK by a polynomial multiplier O(n r ), and it is always an overestimation for natural languages, for which the case r ≥ 4 is rare. Moreover, a big room for optimization is left. E.g., it is possible to extract checks from R that correspond to P h 1 , . . . , P h m , m < r, and apply them before all r phrases are collected to be checked. Figure 5 two final parses are derived by two different ways but these parses correspond exactly to the same phrase with no syntactic ambiguity. When n > 5, matrix cells' content becomes too large due to this effect, which leads to a significant decrease in CYK performance. Let us recall that the main goal of the process is to obtain correct DT-s. Let us notice then that two parse results in M [1][3] from Figure 5 carry the same DT. Therefore it is necessary to merge phrases in a cell if they carry identical DT-s. Let us assume that CYK had already put S phrases in a cell, and a new phrase P is pending. CYK then checks P against all elements of S and declines to add P in S at the first time when it finds some p ∈ P that carry the same DT as P .

Equivalency of phrases. In
Notice that it is insufficient to merge two phrases only by properties of the head. E.g., for Shallow weighting. Due to a high level of ambiguity in natural languages, a huge amount of phrases can be obtained in subcells even when the merging of phrases takes place as described above. Therefore it is necessary to delete some portion of irrelevant phrases from subcells.
For every phrase that arises in any step of CYK, let us add a weight to this phrase by the following scheme. For each edge e = (i, j) of the corresponding DT that forms a link from i-th to j-th word of a sentence, we attach a weight |j − i| q . The weight W of the phrase is a sum of weights of all of the edges of its DT.
For every cell of M , after the set of phrases S is complete by CYK, S is sorted by the weights of phrases. After S is sorted, it turns out to be separated into layers by the weights. Finally, only α top layers are left in a cell. Our evaluation has showed that q = 2 and α = 2 are sufficient.
Processing mistypings as if the correction variants were additional grammar values of tokens, being incorporated into the algorithm by a scheme given by (Erekhinskaya et al., 2011), improves F 1 up to 20% on real-world texts from the Internet without significant loss in the performance.
Partial parses in case there is an error in an input that are good enough and look much like ones from pure dependency parsers can be obtained by the proposed algorithm, in contrast to shift-reduce approaches, in which only some left part of the sentence with an error is parsed.

Evaluation
There is a lack of corpora for Russian to evaluate parsers. In 2012, a task for Russian syntactic parsers was held during the Dialogue conference. The evaluation was conducted as follows: every parser processed a set of thousands of separate sentences from news and fiction, and then a "golden standard" of 800 sentences was selected and verified by several assessors. During evaluation, some mistakes, such as prepositional phrase attachment, were not taken into account as syntactic parsers are originally not intended to deal with semantics. Ignoring this, the method of evaluation was exactly UAS (unlabeled attach score, i.e. a number of nodes in a DT that have correct parents, see (McDonald et al., 2005)).
Our previous version of DictaScope Syntax parser, which was based on a modification of Eisner's algorithm (Erekhinskaya et al., 2011), took part in that task in 2012, resulting with 5th place out of 7 (systems have been ranged by F 1 ), with 86,3% precision, 98% recall and 0,917 F 1 . Our current evaluation of the new version of DictaScope Syntax parser, based on methods proposed in this paper, follows the technique from the Dialogue-2012 task (Toldova et al., 2012). We took 800 entries from the same set of sentences and marked them up in HT XML format. In evaluation we followed the same principles as described in (Toldova et al., 2012), reaching 93.1% precision, 97% recall and 95% F 1 , which correspond to the 3rd place out of 7, with a lag of half percent from the second place. We have also marked up a corpus from Internet-forums and Wikipedia of 300 sentences, reaching 87% F 1 .
Note on complexity. It is known that for a sentence of n tokens CYK is O(n 3 ) algorithm by worst case complexity, and this complexity can be reduced to O(n 2.38 ) by algebraic tricks (Valiant, 1975). We have performed a time complexity evaluation of our parser on a corpus of 1 mln Russian sentences from Internet-news, averaging the time for every fixed length of the sentence. We evaluated sentences with lengths from 3 to 40 tokens, 12 tokens average length. Evaluation has showed the performance of 25 sentences per second average for one kernel of 3GHz Intel Quad. The evaluation has also led to a plot given in Figure 6. It can be verified that the plot corresponds only to An 2 for some A, but not to An 3 . We can explain it in the following way. With our grammar and Russian language, we have noticed that for a completed upper-triangular matrix of CYK, nonempty cells on each row are denser near the main diagonal. Following this, for the part of the row that forms m cells to the right of the main diagonal, the density of nonempty cells in it is p m ≤ c m for some c. Now assume that 1) the maximum cost of the rule checking operation and 2) the maximum number of phrases' combinations that need to be verified against the rule base are some constants which depend on rules, 3) τ is the number of rules which are stored in a vocabulary with a key formed by grammar values from templates. Then, the total number of rule checks is T total ≤ c · 1 k=n−1 k i=1 n−k j=1 p n−k · log τ ≤ ≤ c · log τ · n−1 k=1 k i=1 n−k j=1 C n−k = = c · C · log τ · n−1 k=1 k = O n 2 log τ .

Discussion
In this paper we proposed a method of parsing Russian, based on a hybrid representation of the result, which is derived from a dependency tree with elements of the corresponding constituency tree to model phenomena like homogenous members, nested sentences and junction roles. This approach led to the elimination of some disadvantages of both representations. We also presented a rule system and an algorithm to acquire a ranked set of syntactically ambiguous representations of that kind for a given sentence. Properties of the Cocke-Younger-Kasami algorithm and its modifications, remarkable for natural language parsing, are particularly discussed. The DictaScope Syntax parser, based on the proposed results, is embedded in a commercial NLP system, that is adopted in Kribrum.ru -a service for Internet-based reputation management.
The natural question is whether this approach can be extended to parse other languages. We perform the development of rule systems for English and Arabic, and preliminary evaluation demonstrates results comparable to those for Russian.
We also intend to propose the described HT XML format as a standard markup language for syntax parse trees by building the freely available corpus for languages that lack such linguistic resources, e.g. for Russian.