Abstract:
A method and system for generating a Directed Acyclic Graph (DAG) from an initial multi-chain, subject to a constraint. The initial multi-chain is expressed as a string serving as a current input string to which the constraint is subsequently applied. A provided string P expresses the constraint. P is applied to the current input string to generate at least one output string, wherein each generated output string violates the constraint to a lesser extent than does the input string or does not violate the constraint. Each generated output string violating the constraint serves as a current input string to which the constraint is subsequently applied. P is recursively applied to each current input string that had been determined from applying P previously, until applying P does not generate any more output strings violating the constraint. A set of the generated output strings not violating the constraint represents the DAG.

Description:
TECHNICAL FIELD  
       [0001]     The present invention relates to Natural Language Processing in general and in particular to a system and method for text analysis.  
       BACKGROUND OF THE INVENTION  
       [0002]     The key insights of Natural Language Processing (NLP) studies through the use of computational techniques has allowed to apply such field to the resolution of nowadays real-world problems, such as information retrieval or Web-based services, to name a few.  
         [0003]     However, the complexity of the human language has led to make separate linguistic analysis to offer performant NLP systems, and one of these is the morphosyntactic analysis of sentences, which is also known as the tagging. In fact, due to the high ambiguity of the human language where one word may have different grammatical values (such as being a verb or a noun), it is of utmost importance to correctly resolve ambiguities in order to avoid misinterpretations. To solve those issues, several approaches have emerged and particularly: 
        statistical Part Of Speech (POS) Taggers which generally use the so-called Hidden Markov Model (HMM) and the Viterbi algorithm;     formal rule systems;     or a mix of the two.        
 
         [0007]     The POS systems available on the market work quite well and offering a very high rate of success, for instance above 80% for Written Standard English.  
         [0008]     However statistical POS are very dependent on the corpus they use to learn the trigram or bigram frequencies they use, besides they need a human operator tagging by hand a very large corpus to produce sufficient learning set.  
         [0009]     Among the POS taggers, the ones using Constraint Grammars are of a particular interest because of their speed, their robustness and their accuracy. Most of the Constraint Grammars based systems intersect a Directed Acyclic Graph (DAG) that represents a text having ambiguity with a Directed Graph (a Finite State Transducer) that represents a set of constraints. However, a major drawback of such implementation is that the graph representation is very complex to deal with, requiring complex algorithms difficult to program and often machine dependent in their implementation. These problems limit the use of such systems to the specific language they are developed for.  
         [0010]     Thus, what is needed is a system and method for overcoming the deficiencies of the conventional technology as discussed above.  
       SUMMARY OF THE INVENTION  
       [0011]     It is therefore an object of the invention to provide a computer implemented system and method that allows simpler, faster and more portable text analysis.  
         [0012]     This object is achieved by the present invention wherein the Direct Acyclic Graphs are represented by ‘DAG’ strings to be processed with a simple finite state automata.  
         [0013]     In a preferred embodiment, the method of the invention is operable in a computer system having means for building a Directed Acyclic Graph (DAG) representing at least one constraint applied on an initial string multi-chain. The method preferably comprises the steps of: 
        (a) building at least one regular expression from the at least one constraint;     (b) seeking in the initial string multi-chain where the at least one constraint applies using the at least one regular expression;     (c) splitting the initial string multi-chain in sub multi-chains with respect to where the at least one constraint applies; and     (d) applying steps (b) and (c) to each sub multi-chain until the at least one constraint does not apply.       
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]     The above and other objects, features and advantages of the invention will be better understood by reading the following more particular description of the invention in conjunction with the accompanying drawings wherein:  
         [0019]      FIG. 1  is a block diagram illustrating an exemplary hardware environment that may be used to implement the preferred embodiment of the invention.  
         [0020]      FIG. 2  is a flow chart that illustrates the steps performed by the method of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0021]      FIG. 1  is a block diagram illustrating an exemplary hardware environment that may be used to implement the preferred embodiment of the present invention. In the exemplary hardware environment, a computer  100  may include, inter alia, a processor  102 , memory  104  (e.g., random access memory (RAM)), input devices  106  (e.g., keyboard, mouse pointing device, voice activated input device, etc.), display devices  108  (e.g., CRT, LCD displays, etc.), as well as a data storage devices  110  (e.g., hard, floppy, and/or CD-ROM disk drives, etc.), and/or data communication devices  112  (e.g. modems, network interfaces, etc.). It is envisioned that attached to the computer  100  may be other devices, such as a read only memory (ROM), a video card, bus interface, printers, etc. Those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices known in the art, may be used with the computer  100 . The computer  100  operates under the control of an operating system (OS)  114 , such as OS/390™, MVS™, VM™, OS/2™, AIX™, UNIX™, WINDOWS™, MACINTOSH™, etc. The operating system  114  is booted into the memory  104  of the computer  100  for execution when the computer  100  is powered-on or reset. In turn, the operating system  114  then controls the execution of one or more computer programs, such as a constraint checker  120 . The constraint checker allows to build the novel DAG representation of the present invention both from regular expressions and strings multi-chains. The string multi-chains are generally obtained from initial multi-chains which are a common DAG representation of a phrase to be disambiguated and stored in a string multi-chains database  118 . The phrase may be a text stored in a text file on the data storage device  110  and/or entered interactively by a programmer from an input device  106 .  
         [0022]     The regular expressions are stored in regular expressions database  116 . A regular expression (generally abbreviated as regexp or regex) is a sequence of entities that describes a whole set of strings, according to certain syntax rules (also called the constraints). These expressions are used by many text editors and utilities to search bodies of text for certain patterns and, for example, replace the found strings with a certain other string. There are a few basic type of matching that will need to acquaint with: character matching, repetition matching, and position matching. Regular expressions are thus essentially a tiny, highly specialized programming language that allow to specify the rules for the set of possible strings that are to be matched. Regular expressions are used frequently in Unix operating system and Unix-like ones (Unix is a trademark of Unix System Laboratories). To learn more about regular expressions, the reader may refer to the book of A. Aho, R. Sethi and J. Ullman titled “Compilers, Principles, Techniques and Tools” ADDISON WESLEY.  
         [0023]     The regular expressions database  116 , string multi-chains database  118  and constraint checker  120  are comprised of logic and/or data which, when accessed, interpreted, and/or executed by the processor  102 , cause the computer  100  to perform the steps necessary to implement and/or use the present invention. Generally, the regular expressions database  116 , string multi-chains database  118  and constraint checker  120  are embodied in and/or readable from a device, carrier or media, such as memory  104 , data storage device  110 , and/or a remote device coupled to the computer  100  via the data communications device  112 . Thus, the present invention may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The term “article of manufacture” (or alternatively, “computer program product”) as used herein is intended to encompass logic and/or data embodied in and/or readable from any device, carrier, or media. Of course, those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope of the present invention. Those skilled in the art will recognize that the exemplary environment illustrated in  FIG. 1  is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative hardware environments and programs may be used without departing from the scope of the present invention.  
         [0024]     Before referring to  FIG. 2 , a background overview on Graph, Directed Graph and Directed Acyclic Graph is first made. A finite state machine (FSM) or finite state automaton (FSA) is an abstract machine used in the study of computation and languages that has only a finite, constant amount of memory (the state). It can be conceptualized as a directed graph. There are a finite number of states, and each state has transitions to zero or more states. There is an input string that determines which transition is followed. A graph describes a set of connections between objects. Each object is called a node. It can also be called a vertex. The connections themselves are called edges or arcs. A root node is the top node in a tree data structure. All data in a tree can be accessed through the root node. In some trees, the root node has special properties (like being allowed a greater or smaller than normal number of child nodes). A leaf node is a node of a tree that has zero children. Often leaf nodes are the nodes farthest from the root node. Some trees only store data in leaf nodes. A parent node or ancestor node is a node in a tree data structure that links to one or more child nodes. A child node or descendant node is a node in a tree data structure that is linked to by a parent node.  
         [0025]     A Directed Acyclic Graph (DAG) representing a phrase to be disambiguated is of certain form called a multi-chain as previously mentioned. And a multi-chain is a directed acyclic graph having the following properties: 
        A multi-chain has only one root and only one leaf.     Each vertex coming from a given node reaches the same node.        
 
         [0028]     Below is a graphical description of a multi-chain (MC) where node  1  is the root and node  6  is the leaf  
                         
 
         [0029]     From the above exemplary, let&#39;s explain how a constraint, i.e. given rule, applies on such a multi-chain. Let&#39;s state, as a constraint, that the sequence “ac” is to be excluded from the above multi-chain. The skilled man would easily represent this constraint by the following graph (CT):  
                         
 
 In this graph representation, the symbol @ means “any character except those labeling an edge coming from the same node”. Node  1  is a root (a start node) and node  2  is an end node. In addition node  3  represents a sink, i.e. a node having no issue. 
 
         [0030]     The intersection of the two previous graphs MC with CT leads to the resulting Directed Acyclic Graph (DAG):  
                         
 
 In this DAG, as an c expected result, there is no path containing the sequence “ac”. It can be decomposed into a set of five multi-chains (MC 1  to MC 5 ):  
                         
 
         [0031]     The skilled person will appreciate that each chain of the above resulting DAG (DAG) is found in one or more of the above former multi-chains (MC 1  to MC 5 ).  
         [0032]     The inventor has used a particular representation of the multi-chains in order to offer the present computer implemented simple method. Multi-chains are then represented in the form of “string” expressions which are more easily operable on computers. For instance, the first illustrated multi-chain (MC) may be expressed as the following string (ST):  
         [0033]     ST=&lt;a b c&gt;&lt;a b&gt;&lt;a b c&gt;&lt;a c&gt;&lt;a c&gt;, wherein 
 
 &lt;a b c&gt; means that two nodes are linked by the edges a, b and c. Then with this formalism, the string (ST) above means that node (or position)  2  is reached from node (or position)  1  by either edges a, b or c. Then position  3  is reached by edges a or b. Position  4  is reached by edges a, b or c. Position  5  is reached by edges a or c and at last position  6  is reached by edges a or c.  
                         
 
         [0034]     In the same way the other multi-chains (MC 1  to MC 5 ) obtained by applying the constraint stating to avoid the sequence “ac” may be expressed respectively by the following strings (ST 1  to ST 5 ): 
        ST 1 =&lt;a b c&gt;&lt;a b&gt;&lt;b&gt;&lt;c&gt;&lt;a c&gt;    ST 2 =&lt;a b c&gt;&lt;a b&gt;&lt;a b&gt;&lt;a&gt;&lt;a&gt;    ST 3 =&lt;a b c&gt;&lt;b&gt;&lt;a b c&gt;&lt;a&gt;&lt;a&gt;    ST 4 =&lt;a b c&gt;&lt;b&gt;&lt;b c&gt;&lt;a c&gt;&lt;a&gt;    ST 5 =&lt;a b c&gt;&lt;b&gt;&lt;b c&gt;&lt;c&gt;&lt;a c&gt;       
 
         [0040]     Referring now to  FIG. 2 , the inventor has devised a method to derive directly string multi-chains (ST 1  to ST 5 ) when applying a defined constraint ( 200 ) to an initial multi-chain (MC) represented as a string (ST) multi-chain ( 206 ). In a first operation ( 202 ), a regular expression is built allowing to detect the desired constraint ( 200 ) in a multi-chain. From the above example, where to detect the sequence “ac”, a corresponding regular expression may be built as follow:  
         [0000]     P=“&lt;”ˆ(@*“&gt;”@*)“a”ˆ(@*“&gt;”@*)“&gt;”“&lt;”ˆ(@*“&gt;”@*)“c”ˆ(@*“&gt;”@*)“&gt;” 
         [0000]     wherein,  
         [0000]    
       
         
           
              the symbol @ means any character;  
              ‘pattern’* is the well-known star operator which means 0 or several occurrences of the regular expression ‘pattern’, so @*0 or several occurrences any character;  
              ˆ(‘pattern’) means anything which doesn&#39;t match the regular expression ‘pattern’, in this way ˆ(@*“&gt;”@*) means any string which doesn&#39;t contain the character &gt;;  
              the concatenation of two expressions is implicit thus “&lt;”ˆ(@*“&gt;”@*)“a”ˆ(@*“&gt;”@*)“&gt;” means: character &lt;, followed by anything which doesn&#39;t contain the character &gt;, followed by the character a, followed by anything which doesn&#39;t contain the character &gt;, followed by character &gt;.  
           
         
       
     
         [0045]     Like this, regular expression P means something containing a between two delimiters &lt;and &gt; followed by something containing c between two delimiters &lt;and &gt;. Pattern P match, from position  1 , the substring &lt;a b&gt;&lt;a b c&gt; in initial string ST, and this substring violates the constraint because “ac” is a possible chain in the multi-chain &lt;a b&gt;&lt;a b c&gt;. The other chains (other than ac) in this multi-chain are contained in the two multi-chains: 
        &lt;b&gt;&lt;a b ca&gt;    &lt;a b&gt;&lt;a b&gt;       
 
         [0048]     On a next step, the constraint as expressed by the regular expression (block  204 ) is applied to the initial string ST ( 206 ), in a first run of the DAG builder algorithm of the present invention (block  208 ). This provides new strings, i.e. sub multi-chains, two in the discussed example, STA 1  and STA 2 : 
        STA 1 =&lt;a b c&gt;&lt;b&gt;&lt;a b c&gt;&lt;a c&gt;&lt;a c&gt;    STA 2 =&lt;a b c&gt;&lt;a b&gt;&lt;a b&gt;&lt;a c&gt;&lt;a c&gt;       
 
         [0051]     Pattern P match, from position  3 , the substring &lt;a b c&gt;&lt;a c&gt; in STA 1 . A second run of the DAG builder algorithm is operated on STA 1  and new strings STA 11  and STA 12  are obtained: 
        STA 11 =&lt;a b c&gt;&lt;b&gt;&lt;b c&gt;&lt;a c&gt;&lt;a c&gt;    STA 12 =&lt;a b c&gt;&lt;b&gt;&lt;a b c&gt;&lt;a&gt;&lt;a c&gt;       
 
         [0054]     Similarly, in string multi-chain STA 2 , pattern P match at position  3 , and by operating the DAG builder new strings STA 21  and STA 22  are obtained: 
        STA 21 =&lt;a b c&gt;&lt;a b&gt;&lt;b&gt;&lt;a c&gt;&lt;a c&gt;    STA 22 =&lt;a b c&gt;&lt;a b&gt;&lt;a b&gt;&lt;a&gt;&lt;a c&gt;       
 
         [0057]     The DAG builder is run on STA 11  where the pattern matches at position  4 , and new strings STA 111  and STA 112  are obtained: 
        STA 111 =&lt;a b c&gt;&lt;b&gt;&lt;b c&gt;&lt;c&gt;&lt;a c&gt;    STA 112 =&lt;a b c&gt;&lt;b&gt;&lt;b ca&gt;&lt;a c&gt;&lt;a&gt;       
 
         [0060]     Similarly, in string multi-chain STA 12 , pattern P match at position  4 , and by operating the DAG builder new strings STA 121  and STA 122  are obtained: 
        STA 121 =&lt;a b c&gt;&lt;b&gt;&lt;a b c&gt;&lt;a&gt;&lt;a&gt;    STA 122 =&lt;a b c&gt;&lt;b&gt;&lt;a b c&gt;&lt;&gt;&lt;a c&gt;    It is to be noted that STA 122  is not a valid string (because of empty brackets).        
 
         [0064]     As for STA 12 , the DAG builder is run on STA 21  where the pattern matches at position  4 , and new strings STA 211  and STA 212  are obtained: 
        STA 211 =&lt;a b c&gt;&lt;a b&gt;&lt;b&gt;&lt;c&gt;&lt;a c&gt;    STA 212 =&lt;a b c&gt;&lt;a b&gt;&lt;b&gt;&lt;a&gt;&lt;a&gt;       
 
         [0067]     Finally, the DAG builder is runned on STA 22  where the pattern matches at position  4 , and new strings STA 221  and STA 222  are obtained: 
        STA 221 =&lt;a b c&gt;&lt;a b&gt;&lt;a b&gt;&lt;&gt;&lt;a c&gt; which is not valid     STA 222 =&lt;a b c&gt;&lt;a b&gt;&lt;a b&gt;&lt;a&gt;&lt;a&gt;    And it is to be noted that STA 221  is not a valid string (because of empty brackets).        
 
         [0071]     The several previous operatings of the DAG builder have lead to final strings on which the pattern P doesn&#39;t match anymore. Some may be ignored as being invalid ones (STA 122  and STA 221 ) or as being duplicated (STA 212  as being included in STA 222 ). So the final valid strings obtained by the DAG builder are listed below: 
        STA 111 =&lt;a b c&gt;&lt;b&gt;&lt;b c&gt;&lt;c&gt;&lt;a c&gt;    STA 112 =&lt;a b c&gt;&lt;b&gt;&lt;b ca&gt;&lt;a c&gt;&lt;a&gt;    STA 121 =&lt;a b ca&gt;&lt;b&gt;&lt;a b c&gt;&lt;a&gt;&lt;a&gt;    STA 211 =&lt;a b c&gt;&lt;a b&gt;&lt;b&gt;&lt;c&gt;&lt;a c&gt;    STA 222 =&lt;a b ca&gt;&lt;a b&gt;&lt;a b&gt;&lt;a&gt;&lt;a&gt;       
 
         [0077]     And it is to be appreciated that these strings multi-chains correspond respectively to the string multi-chains (ST 1  to ST 5 ) representing the initial multi-chain (MC) when applying the defined constraint.  
         [0078]     A more generalised description of the invention is now made. It is well-known by skilled persons that constraint grammars use two main kind of rules: 
    Negative rules stating that a given expression cannot appear in a given context. In the formalism generally used such rules are expressed in the following way: 
        C&lt;=L_R     which means that regular expression C cannot appear between regular expression L and regular expression R.    
        Positive rules stating that a given expression is mandatory in a given context. In the formalism generally used such rules are expressed in the following way: 
        C=&gt;L_R     which means that regular expression C is mandatory between regular expression L and regular expression R.    
       
 
         [0085]     The regular expressions L, C and R are made on regular expressions describing basic connections between nodes, for instance: 
        &lt;b&gt;=“&lt;”ˆ(@*(“&gt;”|“&lt;b”|“b”)@*)(“&lt;b”|“b”)ˆ(@*(“&gt;”|“&lt;b”|“b”)@*)“&gt;”
 
 means that a connection between two nodes containing an edge labeled by b match, for instance, the connections: 
    &lt;b c&gt;, &lt;a b c&gt; or &lt;b&gt;
 
 But not: 
    &lt;a c&gt; or &lt;a&gt;       
 
         [0089]     Alternatively, the regular expression builder may be design to produce three kinds of strings: 
    For the first resulting string it&#39;ll rewrite only explicit expressions such as “&lt;”, “&gt;”, “&lt;b” or “b” and erase everything matched by the meta character @ in this way the evaluator behaves like the substitute command of the well known sed program in UNIX or the well known PERL program, it erases all characters except b and the delimiters &lt; and &gt;, it could be written in this formalism for this example s/&lt;[ˆ&lt;b]*b[ˆ&lt;b]*&gt;/&lt;b&gt;/. 
        For the second resulting string it&#39;ll rewrite only delimiters “&lt;” and “&gt;” and all characters except b. In the PERL language this can be written as: s/&lt;([ˆ&lt;b]*)b([ˆ&lt;b]*)&gt;/&lt;$1$2&gt;/.     The last resulting string is the matched string itself.    
       
 
         [0093]     Preferably, for each edge x which can be encountered in the multi-chains that are to be analyzed, corresponds a basic regular expression &lt;x&gt;. In this way, the example given in the paragraph above gives the basic regular expressions &lt;a&gt;, &lt;b&gt; and &lt;c&gt;. The rule preventing the sequence ac in this same example is then written: 
        &lt;a&gt;&lt;=_&lt;ca&gt;       
 
         [0095]     From this rule the following regular expression may be built: 
        0:“&lt;L&gt;”&lt;a&gt;0:“&lt;C&gt;”&lt;c&gt;0:“R&lt;R&gt;”
 
 where &lt;L&gt;, &lt;C&gt; and &lt;R&gt; are tags allowing to split the matched multi-chain in its left, center, and right parts (0:“xyz” means to generate the string “xyz”). This expression applied to the string: 
    MC=&lt;a b c&gt;&lt;a b&gt;&lt;a b c&gt;&lt;a c&gt;&lt;a c&gt;       
 
         [0098]     By runnning the builder gives from first position the three strings: 
        MC 1 -1=&lt;L&gt;&lt;a&gt;&lt;C&gt;&lt;&gt;&lt;R&gt;    MC 1 -2=&lt;L&gt;&lt;b c&gt;&lt;C&gt;&lt;a b&gt;&lt;R&gt; and     MC 1 -3=&lt;L&gt;&lt;a b c&gt;&lt;C&gt;&lt;a b&gt;&lt;R&gt;       
 
         [0102]     As the connection between &lt;C&gt; and &lt;R&gt; is empty, the rule fails from this position.  
         [0103]     From the second position the expression MC leads to: 
        MC 2 - 1 =&lt;L&gt;&lt;a&gt;&lt;C&gt;&lt;c&gt;&lt;R     MC 2 - 2 =&lt;L&gt;&lt;b&gt;&lt;C&gt;&lt;a b&gt;&lt;R&gt; and     MC 2 - 3 =&lt;L&gt;&lt;a b&gt;&lt;C&gt;&lt;a b c&gt;&lt;R&gt;       
 
         [0107]     From these three strings, the two multi-chains that are required to prevent the occurrence of the chain &lt;a&gt;&lt;ca&gt; in the multi-chain &lt;a b&gt;&lt;a b c&gt; may be built: 
        &lt;b&gt;&lt;a b c&gt; because everything following something else than &lt;a&gt; is not impacted by the rule; and     &lt;a&gt;&lt;a b&gt; because everything following &lt;a&gt; must not contain c.        
 
         [0110]     The overall algorithm is thus as follows: first a corresponding regular expression is build ( 202 ) for each rule of the constraint grammar ( 200 ):  
         [0000]     for each rule R=C&lt;=L_R or R=C=&gt;L_R  
         [0000]     build regular expression P=L 0:“&lt;L&gt;” C 0:&lt;“C&gt;” R 0:“&lt;R&gt;” 
         [0111]     Then for a multi-chain MC to analyze ( 206 ), let set that “Branches” are an empty list of multi-chain, “Position” an empty double entry list giving for each rule number and each branch of analysis number the position where to apply the rule in the branch and “Rules” the list of regular expressions built formerly from the set of rules coming with an indicator of the nature of the rule (positive or negative).  
         [0112]     The present method preferably implements a function “applyRule” ( 204 ) which performs the operations described above taking as argument a rule from the Rules list, a branch of analysis from Branches and the position from Position where to apply the rule on the branch.  
         [0113]     Then the DAG builder function ( 208 ) is run on the Multi-chain to analyze, as detailed previously, as long as the rule matches. The process stops when the final strings are obtained, i.e. the last remaining branches.  
         [0114]     While the algorithm has been described in its basic mode, many modifications and improvements may be made in many ways, such as for instance efficiently looking for the first position a rule can be applied on a branch, or by taking advantage of the left context of the rules grouping them by the same left context. Moreover, as another alternative, the management of the positions and branches can be improved taking into account the branches marked as inoperative.  
         [0115]     The advantage of this approach belongs to its simplicity and its portability as only strings of characters are required to implement it. The principle of the invention rests on the use of simple pattern matching techniques on strings commonly described in the literature, the main idea being that the DAGs may be described by a set of strings representing multi-chains.  
         [0116]     Finally, it is to be appreciated by those skilled in the art that while the invention has been particularly shown and described with reference to a preferred embodiment thereof, various changes in form and details may be made without departing from the spirit and scope of the invention.