{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T03:59:29Z","timestamp":1648526369467},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4852,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Nat. Lang. Eng."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Inside parsing is a best parse parsing method based on the Inside algorithm that is often used in estimating probabilistic parameters of stochastic context free grammars. It gives a best parse in <jats:italic>O(N<jats:sup>3<\/jats:sup>G<jats:sup>3<\/jats:sup>)<\/jats:italic> time where <jats:italic>N<\/jats:italic> is the input size and <jats:italic>G<\/jats:italic> is the grammar size. Earley algorithm can be made to return best parses with the same complexity in <jats:italic>N<\/jats:italic>.<\/jats:p><jats:p>By way of experiments, we show that Inside parsing can be more efficient than Earley parsing with sufficiently large grammar and sufficiently short input sentences. For instance, Inside parsing is better with sentences of 16 or less words for a grammar containing 429 states. In practice, parsing can be made efficient by employing the two methods selectively.<\/jats:p><jats:p>The redundancy of Inside algorithm can be reduced by the topdown filtering using the chart produced by Earley algorithm, which is useful in training the probabilistic parameters of a grammar. Extensive experiments on Penn Tree corpus show that the efficiency of Inside computation can be improved by up to 55%.<\/jats:p>","DOI":"10.1017\/s1351324900000127","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T07:21:29Z","timestamp":1221204089000},"page":"147-161","source":"Crossref","is-referenced-by-count":1,"title":["Best parse parsing with Earley's and Inside algorithms on probabilistic RTN"],"prefix":"10.1017","volume":"1","author":[{"given":"Young S.","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Key-Sun","family":"Choi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S1351324900000127_ref010","unstructured":"Jelinek R , Lafferty J. D. , and Mercer R. L. , (1990) Basic methods of probabilistic context free grammars. IBM RC 16374. IBM Continuous Speech Recognition Group."},{"key":"S1351324900000127_ref006","unstructured":"Charniak E. , Hendrickson C. , Jacobson N. , and Perkowitz M. , (1993) Equations for part-of-speech tagging. In proceedings, AAAl Conference."},{"key":"S1351324900000127_ref018","unstructured":"Wright J. , Wrighley E. , and Sharman R. , (1991) Adaptive probabilistic generalized LR parsing. In Proceedings, 2nd International Workshop on Parsing Technologies, Cancun, Mexico. Pp. 154\u201363."},{"key":"S1351324900000127_ref004","unstructured":"Carroll J. , and Briscoe T. , (1992) Probabilistic normalization and unpacking of packed parse forests for unification-based grammars. In proceedings, AAAl Fall Symposium Series: Probabilistic Approaches to Natural Language. Cambridge. Pp. 33\u20138."},{"key":"S1351324900000127_ref008","unstructured":"Han Young S. , and Choi Key-Sun . (1993) Lexical concept acquisition from collocation map. In Proceedings, a workshop of SIGLEX: Acquisition of Lexical Knowledge from Text. Ohio. Pp. 22\u201331."},{"key":"S1351324900000127_ref001","volume-title":"The Theory of Parsing, Translation, and Compiling","volume":"I","author":"Aho","year":"1972"},{"key":"S1351324900000127_ref002","volume-title":"Natural Language Understanding","author":"Allen","year":"1994"},{"key":"S1351324900000127_ref015","doi-asserted-by":"crossref","unstructured":"Schabes Y. , (1992) Stochastic lexicalized tree-adjoining grammars. In Proceedings, the 15th International Conference on Computational Linguistics.","DOI":"10.3115\/992133.992136"},{"key":"S1351324900000127_ref007","unstructured":"Glenn C , and Charniak E. , (1992) Learning probabilistic dependency grammars from labelled texts. In Proceedings, AAAl Fall Symposium Series: Probabilistic Approaches to Natural Language. Cambridge. Pp. 25\u201332."},{"key":"S1351324900000127_ref009","unstructured":"Han Young S. , and Choi Key-Sun . (1994) A Reestimation algorithm for probabilistic transition network. In proceedings of COLING. Kyoto. Pp. 859\u201364."},{"key":"S1351324900000127_ref011","first-page":"175","volume-title":"The Design of Interpreters, Compilers, and Editors for ATN","author":"Kochut","year":"1983"},{"key":"S1351324900000127_ref013","doi-asserted-by":"crossref","unstructured":"Lafferty J. , Sleator D. , and Temperley D. , (1992) Grammatical trigrams: a probabilistic model of link grammar. In Proceedings, AAAI Fall Symposium Series: Probabilistic Approaches to Natural Language. Cambridge. Pp. 89\u201397.","DOI":"10.21236\/ADA256365"},{"key":"S1351324900000127_ref012","doi-asserted-by":"crossref","unstructured":"Kupiec J. , (1991) A Trellis-based algorithm for estimating the parameters of a hidden stochastic context-free grammar. In Proceedings, Speech and Natural Language Workshop,sponsored by DARPA.Pacific Grove. Pp. 241\u20136.","DOI":"10.3115\/112405.112448"},{"key":"S1351324900000127_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0885-2308(90)90022-X"},{"key":"S1351324900000127_ref016","doi-asserted-by":"publisher","DOI":"10.1145\/355598.362773"},{"key":"S1351324900000127_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90060-O"},{"key":"S1351324900000127_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0885-2308(90)90013-V"},{"key":"S1351324900000127_ref003","first-page":"25","article-title":"Generalized probabilistic LR parsing of natural language (Corpora) with unification-based grammars","volume":"19","author":"Briscoe","year":"1993","journal-title":"Computational Linguistics"}],"container-title":["Natural Language Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1351324900000127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T17:42:12Z","timestamp":1557769332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1351324900000127\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["S1351324900000127"],"URL":"https:\/\/doi.org\/10.1017\/s1351324900000127","relation":{},"ISSN":["1351-3249","1469-8110"],"issn-type":[{"value":"1351-3249","type":"print"},{"value":"1469-8110","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}