Patent Publication Number: US-11386267-B2

Title: Analysis method, analyzer, and computer-readable recording medium

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation application of International Application No. PCT/JP2018/010810, filed on Mar. 19, 2018 which claims the benefit of priority of the prior Japanese Patent Application No. 2017-097670, filed on May 16, 2017, the entire contents of each are incorporated herein by reference. 
    
    
     FIELD 
     The embodiment discussed herein is related to, for example, an analysis method. 
     BACKGROUND 
     Unlike alphabetical writing in which word boundaries are indicated by delimiters such as blank spaces, characters of Chinese, Japanese, and Korean languages, or CJK characters, are processed after boundaries between morphemes are specified. As an example of related techniques of analyzing the boundaries between morphemes in target character data and outputting character strings of dividable words, morphological dictionaries of, for example, MeCab and ChaSen, and Trie and Double-Array are known. 
     Examples of techniques that use the results of morpheme segmentation analysis include Word2Vec by which words in the target character data are assigned corresponding vectors. Such related techniques are disclosed in, for example, Japanese Laid-open Patent Publication No. 2010-146273, Japanese Laid-open Patent Publication No. 10-222511, Japanese Laid-open Patent Publication No. 2014-106707, and International Publication Pamphlet No. WO2009/063925. 
     SUMMARY 
     According to an aspect of the embodiments, a non-transitory computer-readable recording medium stores therein an analysis program that causes a computer to execute a process including: generating an index based on a dictionary for use in morphological analysis, the index relating to morphemes registered in the dictionary, the index including flags by which a beginning and an end of each morpheme registered in the dictionary are determinable; and extracting a plurality of dividable words from input character data by using the index. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram for describing example processing of an analyzer according to an embodiment; 
         FIG. 2  is a functional block diagram illustrating a configuration of the analyzer according to the embodiment; 
         FIG. 3  is a diagram illustrating an example data structure of character string data; 
         FIG. 4  is a diagram illustrating an example data structure of dictionary data; 
         FIG. 5  is a diagram illustrating an example data structure of array data; 
         FIG. 6  is a diagram illustrating an example data structure of an index; 
         FIG. 7  is a diagram for describing hashing of the index; 
         FIG. 8  is a diagram illustrating an example data structure of index data; 
         FIG. 9  is a diagram for describing an example process of restoring a hashed index; 
         FIG. 10  is a first diagram for describing an example process of extracting CJK words; 
         FIG. 11  is a second diagram for describing the example process of extracting CJK words; 
         FIG. 12  is a flowchart illustrating the procedure of a setting unit of the analyzer; 
         FIG. 13  is a flowchart illustrating the procedure of an extraction unit of the analyzer; and 
         FIG. 14  is a diagram illustrating an example hardware configuration of a computer that implements the same functions as those of the analyzer. 
     
    
    
     DESCRIPTION OF EMBODIMENT 
     The related techniques above, however, can fail to analyze the boundaries between morphemes at high speed with reduced file size. 
     In the field of analysis such as Word2Vec, which uses the results of the morphological analysis, the importance of accurate morpheme segmentation has been emphasized than ever before. 
     To meet this demand, the related techniques have increased the entries included in a morphological dictionary to extract a plurality of dividable word candidates. However, more entries in a morphological dictionary can lead to a rapid increase in size of Trie and Double-Array, thereby increasing the time for retrieval and determination processing. 
     For example, to morphologically segment a CJK character string “ ”, the segmentation is performed based on a determination not only that this character string includes a morpheme “ ” but also that the character string is not divided into “ ” and “ ”. 
     To assign target character data corresponding vectors by using Word2Vec, the results of the morphological analysis on the target character data have to be smallest meaningful units of character strings. When target character string data is segmented as preprocessing before Word2Vec, the related morphological analysis can fail to segment the data into smallest meaningful units of character strings and can thus fail to satisfy the conditions of Word2Vec. 
     For example, a proper noun “   ” and a new word “ ” minimum meaningful units of character strings by themselves, but the related morphological analysis fails to segment the character strings in this way. When, for example, target character data “   ” is segmented into morphemes by using MeCab, the character string “   ”, which is a meaningful CJK character string by itself, is segmented into “ ”, “ ”, “UFJ”, “ ”, “ ”, “ ”, and “ ”. When target character data “ ” is segmented into morphemes by using MeCab, the character string “ ”, which is a meaningful CJK character string by itself, is segmented into “ ” and “ ”. 
     Morphological analysis may be configured to output proper nouns as unknown words, but this configuration can segment the words based on the registered words or can eliminate useful information. The results of such morphological analysis may be insufficient for use in Word2Vec. 
     Preferred embodiments will be explained with reference to accompanying drawings. The embodiment described herein is not intended to limit the scope of the present disclosure. 
       FIG. 1  is a diagram for describing an example processing of an analyzer according to an embodiment of the present disclosure. When the analyzer extracts dividable word candidates from character string data  140   a , the analyzer executes the following processing as illustrated in  FIG. 1 . The character string data  140   a  is, for example, data of a document including CJK characters. The CJK characters correspond to Chinese, Japanese, or Korean characters. 
     The analyzer compares the character string data  140   a  with dictionary data  140   b . The dictionary data  140   b  includes definitions of words (morphemes) to be used as dividable word candidates. 
     The analyzer scans the character string data  140   a  from the beginning and extracts hit character strings found in the words defined in the dictionary data  140   b , and then stores the extracted character strings in array data  140   c.    
     The array data  140   c  includes words that are the character strings included in the character string data  140   a  and defined in the dictionary data  140   b . To indicate a boundary between words, a unit separator, or &lt;US&gt;, is registered. The analyzer compares the character string data  140   a  with the dictionary data  140   b . When, for example, character strings “ ”, “ ” and “ ” registered in the dictionary data  140   b  are found in this order, the analyzer generates the array data  140   c  illustrated in  FIG. 1 . 
     After generating the array data  140   c , the analyzer generates an index  140   d  corresponding to the array data  140   c . The index  140   d  is information associating characters with respective offsets. An offset indicates a position of a character in the array data  140   c . For example, when a character “ ” is at the n 1 th position from the beginning of the array data  140   c , a flag “1” is set at the position of an offset n 1  in a row (bitmap) corresponding to the character “ ” in the index  140   d.    
     In the index  140   d  in the present embodiment, the positions of the “beginning” and the “end” of the words and the position of &lt;US&gt; are associated with respective offsets. For example, the beginning of a word “ ” is “ ”, and the end thereof is “ ”. When the character “ ”, which is the beginning of the word “ ”, is at the n 2 th position from the beginning of the array data  140   c , a flag “1” is set at the position of an offset n 2  in a row corresponding to the beginning in the index  140   d . When the character “ ”, which is the end of the word “ ”, is at the n 3 th position from the beginning of the array data  140   c , a flag “1” is set at the position of an offset n 3  in a row corresponding to the “end” in the index  140   d.    
     When “&lt;US&gt;” is at the n 4 th position from the beginning of the array data  140   c , a flag “1” is set at the position of an offset n 4  in a row corresponding to “&lt;US&gt;” in the index  140   d.    
     The analyzer can specify the positions of the characters in a word included in the character string data  140   a  and can determine whether the character is the beginning or the end, and can specify the boundaries (&lt;US&gt;) of the characters by referring to the index  140   d . In this regard, character strings in the character string data  140   a  that can be defined by the beginning and the end in the index  140   d  are words that are dividable. 
     The analyzer determines the longest matching character string based on the index  140   d  with the character strings defined by the beginning and the end being segmentation units to extract the dividable words from the character string data  140   a . An extraction result  140   e  illustrated in  FIG. 1  includes extracted words “ ”, “ ”, and “ ”. 
     As described above, the analyzer generates, based on the character string data  140   a  and the dictionary data  140   b , the index  140   d  relating to words (morphemes) defined in the dictionary data  140   b  and sets flags by which the beginning and the end of each word can be determined. The analyzer then extracts a plurality of dividable words from the character string data  140   a  by using the index  140   d . For example, the index  140   d  includes a chunk of dividable words defined in the dictionary data  140   b . Each word can be specified by the beginning and the end flags. The analyzer determines the longest matching character string with the character strings defined by the beginning and the end flags being segmentation units to extract the dividable words. This configuration allows the analyzer to specify the dividable words and perform analysis using values assigned to the words. 
     Examples of analysis using the values assigned to the words include vector operation on the character string data  140   a . The vector operation uses the words extracted by the analyzer as a unit of processing. 
       FIG. 2  is a functional block diagram illustrating a configuration of the analyzer according to the embodiment. As illustrated in  FIG. 2 , this analyzer  100  includes a communication unit  110 , an input unit  120 , a display unit  130 , a storage unit  140 , and a controller  150 . 
     The communication unit  110  is a processor that communicates with other external devices via a network. The communication unit  110  corresponds to a communication device. For example, the analyzer  100  may receive, for example, the character string data  140   a  and the dictionary data  140   b  from an external device and store the received data in the storage unit  140 . 
     The input unit  120  is an input device for use in inputting various types of information to the analyzer  100 . The input unit  120  corresponds to, for example, a keyboard, a mouse, and a touch panel. 
     The display unit  130  is a display device that displays various types of information output from the controller  150 . The display unit  130  corresponds to, for example, a liquid crystal display and a touch panel. 
     The storage unit  140  stores therein the character string data  140   a , the dictionary data  140   b , the array data  140   c , index data  145 , and the extraction result  140   e . The storage unit  140  corresponds to a semiconductor memory device such as a flash memory or a storage device such as a hard disk drive (HDD). 
     The character string data  140   a  is document data to be processed.  FIG. 3  is a diagram illustrating an example data structure of the character string data. As illustrated in  FIG. 3 , the character string data  140   a  is data written in, for example, CJK characters. 
     The dictionary data  140   b  is definition information on CJK words to be used as dividable word candidates.  FIG. 4  is a diagram illustrating an example data structure of the dictionary data. The CJK words listed in  FIG. 4  are presented for illustrative purposes only. The examples of the CJK words listed in  FIG. 4  are nouns, but the dictionary data  140   b  includes adjectives, verbs, adverbs, and other parts of speech of the CJK words. With regard to verbs, the verb forms are defined. 
     The array data  140   c  includes CJK words that are the character strings included in the character string data  140   a  and defined in the dictionary data  140   b .  FIG. 5  is a diagram illustrating an example data structure of the array data. The example array data  140   c  in  FIG. 5  includes CJK words that are segmented by &lt;US&gt;. The numbers above the array data  140   c  each indicate an offset from the beginning of the array data  140   c  to which an offset “0” is allocated. 
     The index data  145  corresponds to the index  140   d  that has been described with reference to  FIG. 1 . As will be described later, the index  140   d  is hashed and stored in the storage unit  140  as the index data  145 . 
     The extraction result  140   e  is a result of dividable word candidates extracted from the character string data  140   a  by the processing of the controller  150 , which will be described later. 
     The controller  150  includes a setting unit  150   a  and an extraction unit  150   b . The controller  150  can be implemented by, for example, a central processing unit (CPU) or a micro processing unit (MPU). The controller  150  can be implemented by a hardwired logic such as an application specific integrated circuit (ASIC) or a field programmable gate array (FPGA). 
     The setting unit  150   a  generates the array data  140   c  based on the character string data  140   a  and the dictionary data  140   b , and generates the index data  145  based on the array data  140   c.    
     The following describes example processing of the setting unit  150   a  for generating the array data  140   c  based on the character string data  140   a  and the dictionary data  140   b . The setting unit  150   a  compares the character string data  140   a  with the dictionary data  140   b . The setting unit  150   a  scans the character string data  140   a  from the beginning and extracts hit character strings found in the CJK words registered in the dictionary data  140   b , and then stores the extracted character strings in array data  140   c . When the setting unit  150   a  stores a hit character string in the array data  140   c  and then stores the next hit character string in the array data  140   c , the setting unit  150   a  sets &lt;US&gt; next to the preceding character string and then stores the next hit character string next to the set &lt;US&gt;. The setting unit  150   a  repeatedly executes the processing above and generates the array data  140   c.    
     After generating the array data  140   c , the setting unit  150   a  generates the index  140   d . The setting unit  150   a  scans the array data  140   c  from the beginning and associates CJK characters with offsets, the beginning of the CJK character strings with offsets, the end of the CJK character strings with offsets, and &lt;US&gt; with offsets, and generates the index  140   d.    
       FIG. 6  is a diagram illustrating an example data structure of the index. As illustrated in  FIG. 6 , the index  140   d  includes bitmaps  21  to  31  corresponding to CJK characters, &lt;US&gt;, the beginning, and the end. For example, the bitmaps  21  to  28  correspond to the CJK characters “ ”, “ ”, “ ”, “ ”, “ ”, “ ”, “ ”, and “ ”, respectively.  FIG. 6  eliminates the bitmaps corresponding to other CJK characters. 
     A bitmap  29  corresponds to &lt;US&gt;. A bitmap  30  corresponds to the “beginning” of the characters. A bitmap  31  corresponds to the “end” of the characters. 
     In the array data  140   c  illustrated in  FIG. 5 , for example, a CJK character “ ” is positioned at offsets “6, 11, 19” of the array data  140   c . The setting unit  150   a  sets flags “1” at the offsets “6, 11, 19” of the bitmap  21  in the index  140   d  illustrated in  FIG. 6 . Similarly, the setting unit  150   a  sets flags for other CJK characters and &lt;US&gt;. 
     In the array data  140   c  illustrated in  FIG. 5 , the beginning of each CJK word is positioned at the offsets “6, 11, 19” of the array data  140   c . The setting unit  150   a  sets flags “1” at the offsets “6, 11, 19” of the bitmap  30  in the index  140   d  illustrated in  FIG. 6 . 
     In the array data  140   c  illustrated in  FIG. 5 , the end of each CJK word is positioned at the offsets “9, 17, 26” of the array data  140   c . The setting unit  150   a  sets flags “1” at the offsets “9, 17, 26” of the bitmap  31  in the index  140   d  illustrated in  FIG. 6 . 
     After generating the index  140   d , the setting unit  150   a  generates the index data  145  by hashing the index  140   d  in order to reduce the amount of data of the index  140   d.    
       FIG. 7  is a diagram for describing hashing of the index. The following describes the procedure of hashing on a bitmap  10  included in, for example, the index. 
     For example, the setting unit  150   a  generates a base-29 bitmap  10   a  and a base-31 bitmap  10   b  from the bitmap  10 . The bitmap  10   a  is generated such that the bitmap  10  is segmented at every 29 offsets, and flags “1” at offsets from the beginning of each segmented portion are represented by flags at the offsets 0 to 28 of the bitmap  10   a.    
     The setting unit  150   a  copies the information on the offsets 0 to 28 of the bitmap  10  to the bitmap  10   a . The setting unit  150   a  processes the information on the offsets 29 and later of the bitmap  10   a  in the following manner. 
     A flag “1” is set at the offset “35” of the bitmap  10 . Since the offset “35” is the offset “28+7”, the setting unit  150   a  sets “(1)” at the offset “6” of the bitmap  10   a . Note that the initial offset is 0. A flag “1” is set at the offset “42” of the bitmap  10 . Since the offset “42” is the offset “28+14”, the setting unit  150   a  sets a flag “(1)” at the offset “13” of the bitmap  10   a.    
     The bitmap  10   b  is generated such that the bitmap  10  is segmented at every 31 offsets, and flags “1” at offsets from the beginning of each segmented portion are represented by flags at offsets 0 to 30 of the bitmap  10   b.    
     A flag “1” is set at the offset “35” of the bitmap  10 . Since the offset “35” is the offset “30+5”, the setting unit  150   a  sets “(1)” at the offset “4” of the bitmap  10   b . Note that the initial offset is 0. A flag “1” is set at the offset “42” of the bitmap  10 . Since the offset “42” is the offset “30+12”, the setting unit  150   a  sets a flag “(1)” at the offset “11” of the bitmap  10   b.    
     The setting unit  150   a  performs the processing above to generate the bitmaps  10   a  and  10   b  from the bitmap  10 . These bitmaps  10   a  and  10   b  are the results of hashing the bitmap  10 . The bitmap  10  has the length of 0 to 43 in this example, but if the bitmap  10  having the length of 43 or greater, the flags “1” in the bitmap  10  can be represented by those in the bitmap  10   a  and the bitmap  10   b.    
     The setting unit  150   a  generates the index data  145  by hashing the bitmaps  21  to  31  illustrated in  FIG. 6 .  FIG. 8  is a diagram illustrating an example data structure of the index data. For example, the setting unit  150   a  hashes the bitmap  21  in the index  140   d  illustrated in  FIG. 6  to generate bitmaps  21   a  and  21   b  illustrated in  FIG. 8 . The setting unit  150   a  hashes the bitmap  22  in the index  140   d  illustrated in  FIG. 6  to generate bitmaps  22   a  and  22   b  illustrated in  FIG. 8 . The setting unit  150   a  hashes the bitmap  29  in the index  140   d  illustrated in  FIG. 6  to generate bitmaps  29   a  and  29   b  illustrated in  FIG. 8 . The other hashed bitmaps are eliminated from  FIG. 8 . 
     Referring back to  FIG. 2 , the extraction unit  150   b  generates the index  140   d  based on the index data  145  and extracts a plurality of dividable CJK words based on the index  140   d.    
     The following describes example processing of the extraction unit  150   b  for generating the index  140   d  based on the index data  145 .  FIG. 9  is a diagram for describing an example process of restoring a hashed index. The following describes an example process of restoring the bitmap  10  based on the bitmap  10   a  and the bitmap  10   b . The bitmaps  10 ,  10   a , and  10   b  correspond to those described with reference to  FIG. 7 . 
     Processing at Step S 10  is described. The extraction unit  150   b  generates the bitmap  11   a  based on the base-29 bitmap  10   a . The information on flags set at the offsets 0 to 28 in the bitmap  11   a  is identical to the information on flags set at the offsets 0 to 28 in the bitmap  10   a . The information on flags set at the offsets 29 and later in the bitmap  11   a  is the repetition of the information on flags set at the offsets 0 to 28 in the bitmap  10   a.    
     Processing at Step S 11  is described. The extraction unit  150   b  generates the bitmap  11   b  based on the base-31 bitmap  10   b . The information on flags set at the offsets 0 to 30 in the bitmap  11   b  is identical to the information on flags set at the offsets 0 to 30 in the bitmap  10   b . The information on flags set at the offsets 31 and later in the bitmap  11   b  is the repetition of the information on flags set at the offsets 0 to 30 in the bitmap  10   b.    
     Processing at Step S 12  is described. The extraction unit  150   b  performs the logical AND operation between the bitmap  11   a  and the bitmap  11   b  and generates the bitmap  10 . In the example illustrated in  FIG. 9 , flags “1” are set at the offsets “0, 5, 11, 18, 25, 35, 42” in the bitmap  11   a  and the bitmap  11   b . Accordingly, flags “1” are set at the offsets “0, 5, 11, 18, 25, 35, 42” in the bitmap  10 . This bitmap  10  is a restored bitmap. The extraction unit  150   b  repeatedly performs the same processing on the other bitmaps to restore the bitmaps and generate the index  140   d.    
     After generating the index  140   d , the extraction unit  150   b  extracts dividable CJK words based on the index  140   d .  FIGS. 10 and 11  are diagrams for describing an example process of extracting the CJK words. The character string data  140   a  includes a phrase starting as “ ” in the example illustrated in  FIGS. 10  and  11 , and the extraction unit  150   b  reads, from the index  140   d , bitmaps corresponding to the respective characters in the character string data  140   a  from the first character and performs the following processing. 
     Processing at Step S 20  is described. The extraction unit  150   b  reads a bitmap  30  corresponding to the beginning, a bitmap  31  corresponding to the end, and a bitmap  21  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  30  corresponding to the beginning and the bitmap  21  corresponding to the character “ ” to specify whether the character is at the beginning position. The result of the logical AND operation between the bitmap  30  corresponding to the beginning and the bitmap  21  corresponding to the character “ ” is output as a bitmap  30 A. In the bitmap  30 A, flags “1” are set at the offsets “6, 11, 19”, and this indicates that the beginning of the CJK words is at the offsets “6, 11, 19”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  21  corresponding to the character “ ” to specify whether the character is at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  21  corresponding to the character “ ” is output as a bitmap  31 A. The bitmap  31 A includes no flag “1”, which means that “ ” is not an end candidate. 
     Processing at Step S 21  is described. The extraction unit  150   b  shifts the bitmap  21  corresponding to the character “ ” by one to the left to generate a bitmap  21 A. The extraction unit  150   b  reads a bitmap  22  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  21 A and the bitmap  22  and generates a bitmap  50  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  50  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  50  corresponding to the character string “ ” is output as a bitmap  31 B. The bitmap  31 B includes no flag “1”, which means that the character string “ ” has no end candidate. 
     Processing at Step S 22  is described. The extraction unit  150   b  shifts the bitmap  50  corresponding to the character string “ ” by one to the left to generate a bitmap  50 A. The extraction unit  150   b  reads a bitmap  23  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  50 A and the bitmap  23  and generates a bitmap  51  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  51  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  51  corresponding to the character string “ ” is output as a bitmap  31 C. The bitmap  31 C includes no flag “1”, which means that the character string “ ” has no end candidate. 
     Processing at Step S 23  is described. The extraction unit  150   b  shifts the bitmap  51  corresponding to the character string “ ” by one to the left to generate a bitmap  51 A. The extraction unit  150   b  reads a bitmap  24  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  51 A and the bitmap  24  and generates a bitmap  52  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  52  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  52  corresponding to the character string “ ” is output as a bitmap  31 D. The bitmap  31 D includes a flag “1”, which means that the character string “ ” has an end candidate “ ”. The extraction unit  150   b  extracts the character string “ ” from the beginning character “ ” specified at Step S 20  to the end character “ ” specified at Step S 23  as a dividable CJK word candidate. 
     Processing at Step S 24  is described. The extraction unit  150   b  shifts the bitmap  52  corresponding to the character string “ ” by one to the left to generate a bitmap  52 A. The extraction unit  150   b  reads a bitmap  25  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  52 A and the bitmap  25  and generates a bitmap  53  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  53  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  53  corresponding to the character string “ ” is output as a bitmap  31 E. The bitmap  31 E includes no flag “1”, which means that the character string “ ” has no end candidate. 
     Processing at Step S 25  is described. The extraction unit  150   b  shifts the bitmap  53  corresponding to the character string “ ” by one to the left to generate a bitmap  53 A. The extraction unit  150   b  reads a bitmap  26  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  53 A and the bitmap  26  and generates a bitmap  54  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  54  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  54  corresponding to the character string “ ” is output as a bitmap  31 F. The bitmap  31 F includes no flag “1”, which means that the character string “ ” has no end candidate. 
     Processing at Step S 26  is described. The extraction unit  150   b  shifts the bitmap  54  corresponding to the character string “ ” by one to the left to generate a bitmap  54 A. The extraction unit  150   b  reads a bitmap  27  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  54 A and the bitmap  27  and generates a bitmap  55  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  55  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  55  corresponding to the character string “ ” is output as a bitmap  31 G. The bitmap  31 G includes a flag “1”, which means that the character string “ ” has an end candidate “ ”. The extraction unit  120   b  extracts the character string “ ” from the beginning character “ ” specified at Step S 20  to the end character “ ” specified at Step S 26  as a dividable CJK word candidate. 
     Processing at Step S 27  is described. The extraction unit  150   b  shifts the bitmap  55  corresponding to the character string “ ” by one to the left to generate a bitmap  55 A. The extraction unit  150   b  reads a bitmap  28  corresponding to a character “ ” from the index  140   d . The extraction unit  150   b  performs the logical AND operation between the bitmap  55 A and the bitmap  28  and generates a bitmap  56  corresponding to a character string “ ”. 
     The extraction unit  150   b  performs the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  56  corresponding to the character string “ ” to specify whether the characters are at the end position. The result of the logical AND operation between the bitmap  31  corresponding to the end and the bitmap  56  corresponding to the character string “ ” is output as a bitmap  31 H. The bitmap  31 H includes a flag “1”, which means that the character string “ ” has an end candidate “ ”. The extraction unit  120   b  extracts the character string “ ” from the beginning character “ ” specified at Step S 20  to the end character “ ” specified at Step S 27  as a dividable CJK word candidate. 
     The extraction unit  150   b  shifts the bitmap  56  of the character string “ ” by one to the left to generate a bitmap  56 A. Since the index  140   d  includes no bitmap corresponding to a character string “ ”, the extraction unit  150   b  generates a bitmap  29  with all the flags being “0”. In this case, the extraction unit  150   b  outputs the previous bitmap  56  as a bitmap corresponding to “ ”. 
     The extraction unit  150   b  performs the processing from Step S 20  to Step S 27  and extracts dividable CJK words “ ”, “ ”, and “ ” included in the character string data  140   a . The extraction unit  150   b  stores the information on the extracted CJK words in the storage unit  140  as the extraction result  140   e.    
     Described next is an example procedure of the analyzer  100  according to the present embodiment.  FIG. 12  is a flowchart illustrating the procedure of the setting unit of the analyzer. As illustrated in  FIG. 12 , the setting unit  150   a  of the analyzer  100  compares the character string data  140   a  with the CJK words in the dictionary data  140   b  (Step S 101 ). 
     The setting unit  150   a  registers hit character strings (CJK words) in the array data  140   c  (Step S 102 ). The setting unit  150   a  generates the index  140   d  of the characters (CJK characters) based on the array data  140   c  (Step S 103 ). The setting unit  150   a  hashes the index  140   d  and generates the index data  145  (Step S 104 ). 
       FIG. 13  is a flowchart illustrating the procedure of the extraction unit of the analyzer. As illustrated in  FIG. 13 , the extraction unit  150   b  of the analyzer  100  restores the index  140   d  from the hashed index data  145  (Step S 201 ). 
     The extraction unit  150   b  sets a bitmap corresponding to the first character from the beginning of the character string data  140   a  to be a first bitmap and sets a bitmap corresponding to the second character from the beginning to be a second bitmap (Step S 202 ). 
     The extraction unit  150   b  performs the logical AND operation between the first bitmap and the bitmap corresponding to the beginning. If the result of the operation includes “1”, the extraction unit  150   b  determines that the character corresponding to the first bitmap is the beginning character (Step S 203 ). 
     The extraction unit  150   b  performs the logical AND operation between the first bitmap and the bitmap corresponding to the end. If the result of the operation includes “1”, the extraction unit  150   b  determines that the character corresponding to the first bitmap is the end character and extracts a dividable word candidate (Step S 204 ). 
     If the process reaches the end of the character string data  140   a  (Yes at Step S 205 ), the extraction unit  150   b  stores the extraction result  140   e  in the storage unit  140  (Step S 206 ). If the process has not reached the end of the character string data  140   a  (No at Step S 205 ), the extraction unit  150   b  proceeds to Step S 207 . 
     The extraction unit  150   b  shifts the first bitmap by one to the left (Step S 207 ). The extraction unit  150   b  performs the logical AND operation between the first bitmap and the second bitmap and sets a resulting bitmap to be a new first bitmap (Step S 208 ). 
     The extraction unit  150   b  sets a bitmap corresponding to a character next to the character of the second bitmap to be a new second bitmap (Step S 209 ), and the process returns to Step S 203 . 
     Described next are the effects of the analyzer  100  according to the present embodiment. The analyzer  100  generates the index  140   d  relating to words (morphemes) defined in the dictionary data  140   b  based on the character string data  140   a  and the dictionary data  140   b  and sets flags by which the beginning and the end of each word can be specified. The analyzer  100  then extracts a plurality of dividable words from the character string data  140   a  by using the index  140   d . For example, the index  140   d  includes a chunk of dividable words defined in the dictionary data  140   b . Each word can be specified by the beginning and the end flags. The analyzer  100  determines the longest matching character string with the character strings defined by the beginning and the end flags being segmentation units to extract the dividable CJK words. The analyzer  100  specifies the dividable CJK words by using the index  140   d  and this configuration allows the analyzer  100  to perform a high-speed analysis with a reduced file size. 
     The analyzer  100  performs the logical AND operation between a bitmap corresponding to a combination of characters included in the character string data  140   a  and the bitmaps corresponding to the beginning and the end. The analyzer  100  then determines the beginning position and the end position of a dividable CJK word. This configuration allows the analyzer  100  to determine the beginning and the end of dividable CJK words by using the index  140   d  and the logical AND operation, which can reduce calculation costs. The analyzer  100  hashes the index  140   d  and generates the index data  145  and stores the generated data in the storage unit  140 . This configuration can reduce the amount of data stored in the storage unit  140 . 
     Described next is an example hardware configuration of a computer that implements the same functions as those of the analyzer  100  described in the embodiment above.  FIG. 14  is a diagram illustrating an example hardware configuration of a computer that implements the same functions as those of the analyzer. 
     As illustrated in  FIG. 14 , this computer  200  includes a CPU  201  that performs various types of calculation processing, an input device  202  that receives inputs of data from a user, and a display  203 . The computer  200  includes a reader  204  that reads, for example, a computer program from a storage medium and an interface device  205  that transmits or receives data to or from other computers via a wired or wireless network. The computer  200  includes a random access memory (RAM)  206  serving as temporary storage for various kinds of information and a hard disk drive  207 . The devices  201  to  207  are connected to a bus  208 . 
     The hard disk drive  207  stores therein a setting program  207   a  and an extraction program  207   b . The CPU  201  reads the setting program  207   a  and the extraction program  207   b  and loads them on the RAM  206 . 
     The setting program  207   a  functions as a setting process  206   a . The extraction program  207   b  functions as an extraction process  206   b.    
     The setting process  206   a  corresponds to the processing of the setting unit  150   a . The extraction process  206   b  corresponds to the processing of the extraction unit  150   b.    
     The computer programs  207   a  and  207   b  are not necessarily stored in the hard disk drive  207  from the beginning. For example, the computer programs may be stored in a “portable physical medium” such as a flexible disk (FD), a compact disc read only memory (CD-ROM), a digital versatile disc (DVD), a magneto-optical disc, and an integrated circuit (IC) card to be inserted in the computer  200 . The computer  200  may be configured to read and execute the computer programs  206   a  and  206   b.    
     Using the index allows the analyzer to perform high-speed analysis with a reduced file size. 
     All examples and conditional language recited herein are intended for pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventors to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.