Language modelling system and a fast parsing method

• US 7,603,651 B2
• Filed: 05/28/2003
• Issued: 10/13/2009
• Est. Priority Date: 11/21/2000
• Status: Expired due to Fees

• Current Assignee: Filip D.E. Brabander
• Original Assignee: Filip D.E. Brabander
• Inventors: De Brabander, Filip
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Neway; Samuel G
• Application Number:
  US10/446,193
• Publication Number:
  US 20040243387A1
• Time in Patent Office: 2,330 Days
• Field of Search: None
• US Class Current: 717/105
• CPC Class Codes: G06F 8/34 Graphical or visual programming

Abstract

The described methods and systems allow to develop RTN-compatible grammatical models, for syntax or other linguistical levels, within one integrated development software environment (IDE) that is efficient, controllable and overviewable, because editing is done through a 2D/3D graphical user interface (GUI) with a pointing device (e.g. a mouse). Instantaneous evaluation of any fresh change to the grammar is carried out by re-parsing a test corpus of typically thousands of sentences, functioning as language examples to try to comply with, yielding immediate statistical feedback on parsability, thanks to an integrated new fast parsing method. Problematic corpus sentences can automatically be brought under the user'"'"'s attention, who can visually zoom in on a problem spot in the model or the sentence without losing the overview. All this increases efficiency and quality in grammar model development. The integrated parser can also be used separately, for instance for machine translation, and is based on efficient concatenation of pre-calculated partial pathways through the RTN grammar. These are exhaustively calculated within reasonable preset limits.

Claims

1. A language processing system taking as input a grammar model for a language, formulated as an RTN and, secondly, one or more partially overlapping sequences at a time, of concatenable terminals, or more specifically language elements, said set of input sequences together formulated as a sequence-chart of such elements, said system delivering as output a parse result for each incoming sequence-chart, obtained by applying a parse operation on said sequence-chart, characterised in that said system comprises:

memory access to store and consult a set of phonological, morphological, syntactical and/or semantic rules for a language, formulated as an RTN data-structure;

memory access to store and consult a plurality of n-Swings, in which n represents an integer number being at least 2, organised in lists of finite length, each list labelled with an n-fold of said language elements, and each n-Swing being defined as a unique path segment that is a contiguous part of at least one partial parse pathway (passing over transitions and jumps for FSM calling and returning), thus a Link sequence complying with the RTN, and that comprises one terminal transition at the start of the segment and one terminal transition at the end of the segment, and includes n-2 terminal transitions in between;

derivation means to derive said lists of n-Swings for a given n from the RTN, while limiting the length of the n-Swings to a predetermined number of transitions to prevent infinite lengths, by applying the following algorithms for deriving n-Swings in three phases,

the first phase being the generation of all possible Links in every FSM of said RTN,

the second phase being the generation of all possible Bi-Swings in the RTN, the Bi-Swings being limited by a fixed limit on the length of its sequence of Links and/or by a limit of the call level span;

the optional third phase being the generation of all possible n-Swings for a predetermined integer n>

2, which are calculated by induction in recursive incremental phases, starting by calculating 3-Swings, by either left or right attachment of matching Bi-Swings to (n−

1)-Swings,

parsing means provided to derive a parse result from said supplied token sequence-chart of concatenable language elements by using said lists of n-Swings, said parsing means being provided to build all possible parses, by building a list of every n-Swings that matches a full sequence of N language elements that is derivable from said input sequence-chart;

an optional means to derive a parse result from said supplied token sequence-chart of concatenable language elements, by seeding the set of possible parses, each regarded as Link sequences, from the set of n-Swings of the n-Swing list associated with an n-fold of n subsequent language elements, as occurs at the start or the end of a sequence comprised in the sequence-chart, and by trying to extend each seed of a parse by repeatedly attaching matching subsequent n-Swings at the begin or the end of the open ended sides of its Link sequences, while taking the subsequent n-Swings from lists that are associated with a sequence of n language elements as they occur directly at the one, respectively the other side of those language elements in the supplied sequence as derived from the sequence chart, that have not yet been associated with a set of n-Swings, said parsing means being also provided to multiply the built-up Link sequences each time multiple possibilities exist for extension, such that every extension possibility is generated and every possibility is unique and for rejecting extensions that contain non-matching call correspondences at any call level and for rejecting extensions that contain below zero calling levels, and for rejecting extensions that would contain call level differences exceeding a predetermined threshold value and for rejecting Link sequences that can'"'"'t be extended, said parsing means being further provided to form a list of parse result contributions, being a list of only those Link sequences that span the longest length of the supplied sequence and for organising each parse result contribution as a tree structure, said parsing means provided to further add all parse trees for each possible element sequence possible according to the supplied input sequence-chart and finally summarising the entire parse result in one parse forest, containing all parse trees or no parse tree if no full parse was found, or in, equivalently, a parse tree chart.

2. A method to generate all Links and Bi-Swings in an RTN for use in a language processing system as claimed in claim 1, according to the following pseudo algorithm, in which loops are marked as for and conditions as if and parentheses delimit looped or conditional blocks, and in which a sequence of Links is called a path:

Generate All Links function { for every FSM in the RTN { start a path from the entry state set the entry state as the current state call Recursively Generate Links the current FSM and for the current entry state and the current path } } Recursively Generate Links function for an FSM, a State and a current path { for every transition starting from the current state { if it'"'"'s a calling transition, calling another FSM2 { if the path started at the entry state generate a Link of type 8 for the currently obtained path else if the path started at a terminal transition generate a Link of type 2 for the currently obtained path else (the past must have started at a calling transition) generate a Link of type 5 for the currently obtained path } else if it'"'"'s a terminal transition { if the path started at the entry state, generate a Link of type 7 for the currently obtained path else if the path started at a terminal transition generate a Link of type 1 for the currently obtained path else (the past must have started at a calling transition), generate a Link of type 4 for the currently obtained path } else it must be a zero transition { if the path hasn'"'"'t yet reached a predetermined maximal length { append the zero transition at the end of the path and set the current state to the state at the other side of the zero transition;

call Recursively Generate Links function for the current FSM, state and path remove the zero transition again from the end of the current path } if the current state is the exit state { if the path started at a terminal transition, generate a Link of type 3 for the currently obtained path else (the past must have started at a calling transition), generate a Link of type 6 for the currently obtained path } } } } Generate All Bi-Swings function for a given RTN { for every nonzero terminal1 in the RTN { for every Link starting with a terminal1 transition { start a path (a sequence of Links ) from this Link, choose it as the current path. call Recursively Generate Bi-Swings for the current path and terminal 1 } } } Recursively Generate Bi-Swings function for a current path and terminal 1 { consider the transition on which the last link of the current path ends for all links that start from this same transition { if Link is not climbing regarding call level OR (Link is climbing AND there is a corresponding Link in the down slope of the Link path) { append the Link at the end of the current path if the Link doesn'"'"'t end on a terminal 2 { if the level span of the path isn'"'"'t too high { call Recursively Generate Bi-Swings function for the current path and terminal 1 } } else (the Link ends on terminal

     2) { generate a Bi-Swing from the current path add the Bi-Swing to the Bi-Swing list for (Terminal 1,Terminal

     2) } remove the Link again from the end of the path } } }.

3. A method to parse an input sequence of N elements for use in a language processing system as claimed in claim 1, that assumes availability of at least all possible Bi-Swings for the given RTN, each calculated and stored from before, said method in a first phase dividing up the entire sequence in contiguous non-overlapping sub-sequences of at least length 2, such that for each sub-sequence of length m there is a corresponding complete set of m-Swings pre-calculated, stored and available, and said method, in a second phase gradually multiplying and unifying neighbouring m- and m′

-Swing-sets by controlling if a combination of both matches and if so by joining them to into all possible combined (m+m′

)-Swings corresponding to sub -sequences of length (m+m′

) of the input sequence, taking into account that if n-Swings correspond with sub-sequences that include the first or last element in the sequence, matching includes base call-level checking, said method resulting in a final list of 0 or more N-Swings matching the entire sequence of N elements, each of which is equivalent with a parse tree.

4. A language processing system as claimed in claim 1, characterised in that the stored and accessible RTN data-structure is supplemented with accessible storage for probabilistic weights attached to all transitions leaving from every state, in every FSM of the RTN, and that said input sequence chart is potentially supplemented with probabilities attached to each arc, said parsing means being provided to take into account said probabilities into each full parse alternative within the parse result, by applying the statistical laws on such probabilities, and optionally other available probabilistic information, along the way and assigning a resulting probability to each individual parse.