Patent Publication Number: US-7917353-B2

Title: Hybrid text segmentation using N-grams and lexical information

Description:
FIELD OF THE INVENTION 
     The present invention relates to the field of text analysis, segmentation, and tokenization. 
     BACKGROUND OF THE INVENTION 
     Search engines and document classification systems typically rely on lexical analysis or n-gram tokenization of source document text in the construction of their search indices or classifiers. In text segmentation using lexical analysis, tokenization rules, lexicons, and morphological rules are consulted in order to identify words and other tokens. In n-gram tokenization a source text is broken up into tokens of one or more contiguous characters, optionally taking the letters or ideogram characteristics into account. In both cases the tokens are then indexed or classified. For Indo-European languages, the text segmentation takes advantage of separators that appear between words, such as blank spaces and punctuation characters. However, in Asian languages such as Chinese and Japanese, these separators are rarely used, and therefore either n-gram tokenization or lexical analysis tokenization is typically performed. 
     One disadvantage of employing an index or classifier built using lexical analysis tokenization is that it tends to provide partial results, since the lexicon is often incomplete, and a query that includes a word that is not in the lexicon will not be typically found in the index or classifier. One disadvantage of employing an index or classifier built using n-gram tokenization is that it tends to provide spurious results, such as where unrelated words have one or more n-grams in common. 
     SUMMARY OF THE INVENTION 
     The present invention in embodiments thereof discloses novel systems and methods for text segmentation using hybrid n-gram/lexical analysis tokenization. 
     In one aspect of the present invention a hybrid n-gram/lexical analysis tokenization system is provided including a lexicon, and a hybrid tokenizer operative to perform both N-gram tokenization of a text and lexical analysis tokenization of a text using the lexicon, and construct either of an index and a classifier from the results of both of the N-gram tokenization and the lexical analysis tokenization, where the hybrid tokenizer is implemented in at least one of computer hardware and computer software and is embodied within a computer-readable medium. 
     In another aspect of the present invention the hybrid tokenizer is operative to omit from either of the index and the classifier any n-grams generated for a segment of the text where a word is identified by the hybrid tokenizer as corresponding to the segment of the text. 
     In another aspect of the present invention the hybrid tokenizer is operative to perform the N-gram tokenization and the lexical analysis tokenization at least partially concurrently. 
     In another aspect of the present invention a hybrid n-gram/lexical analysis tokenization method is provided including performing N-gram tokenization of a text, performing lexical analysis tokenization of the text, and constructing either of an index and a classifier from the results of both of the N-gram tokenization and the lexical analysis tokenization. 
     In another aspect of the present invention further includes omitting from either of the index and the classifier any n-grams generated for a segment of the text where a word is identified during the performing lexical analysis tokenization step as corresponding to the segment of the text. In another aspect of the present invention the performing steps are performed at least partially concurrently. 
     In another aspect of the present invention a computer program is provided embodied on a computer-readable medium, the computer program including a first code segment operative to perform N-gram tokenization of a text, a second code segment operative to perform lexical analysis tokenization of the text, and a third code segment operative to construct either of an index and a classifier from the results of both of the N-gram tokenization and the lexical analysis tokenization. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention in embodiments thereof will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which: 
         FIG. 1  is a simplified illustration of a hybrid lexical analysis/n-gram tokenization system, constructed and operative in accordance with an embodiment of the invention; and 
         FIG. 2  is a simplified illustration of an exemplary method of operation of the system of  FIG. 1 , operative in accordance with an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention is now described within the context of one or more embodiments, although the description is intended to be illustrative of the invention as a whole, and is not to be construed as limiting the invention to the embodiments shown. It is appreciated that various modifications may occur to those skilled in the art that, while not specifically shown herein, are nevertheless within the true spirit and scope of the invention. 
     Reference is now made to  FIG. 1 , which is a simplified illustration of a hybrid n-gram/lexical analysis tokenization system, constructed and operative in accordance with an embodiment of the invention, and additionally to  FIG. 2 , which is a simplified illustration of an exemplary method of operation of the system of  FIG. 1 , operative in accordance with an embodiment of the invention. In the system of  FIG. 1  and method of  FIG. 2 , a computer  100  is configured with a hybrid tokenizer  102  which performs hybrid tokenization on text of one or more documents  104  as follows. N-gram tokenization is performed on the text using conventional techniques, such as by converting the text into bigrams or trigrams. Before, during, or after performing n-gram tokenization, lexical analysis tokenization of the same text is also performed using conventional techniques, such as where hybrid tokenizer  102  employs a lexicon  106  to identify words. Hybrid tokenizer  102  then constructs an index  108  and/or a classifier  110  from the results of both the lexical analysis tokenization and the n-gram tokenization. However, where a word is identified for a particular segment of text during lexical analysis, any n-grams generated for the same text segment during n-gram tokenization may optionally be omitted when constructing the index or classifier. 
     When performing a search query on index  108 , the hybrid lexical analysis tokenization and n-gram tokenization method described hereinabove is preferably performed on the query text, the results of which are used to search index  108  using conventional techniques. Similarly, when performing document classification using classifier  110 , the hybrid method is preferably performed on the text to be classified. 
     The hybrid approach of the present invention is believed to be superior to the individual approaches of n-gram tokenization versus lexical analysis tokenization given their disadvantages as described hereinabove. 
     It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention. 
     While the methods and apparatus disclosed herein may or may not have been described with reference to specific computer hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in computer hardware or software using conventional techniques.