Apparatus and computerised method for determining constituent words of compound word

The present invention provides a collection of documents, a means for determining the number of documents containing a compound word from the collection of documents, and a means for determining the number of documents containing words constituting the compound word from the collection of documents. The present invention relates to a device for determining words constituting a compound word having. The present invention also relates to an information retrieval system incorporating a device for determining words constituting such a compound word and a computerized method.

Compound words are common in multiple languages such as German, Dutch, Danish, Greek, Norwegian, Icelandic, and Finnish. Since compound words can be freely combined, the vocabulary size is enormously increased by compound words. The above languages may contain very long words that are not found in any dictionary of that language. A typical example of such a word is the German compound word "Abschreibungsmoglichkeiten". This compound word is composed by concatenating the two words "Abschreibung" and "moglichkeiten" with the combined morpheme "s". In the following description of the present invention, decomposing a compound word into its constituent words and (if any) combined morphemes is referred to as subdividing the compound word or separating the words constituting the compound word, and the symbol "+". It is represented by a character string separated by ". For example, the compound word "Abschreibungsmoglichkeiten" is expressed as "Abschreibung + s + moglichkeiten". As other binding morphemes, "-", "es" and the like are used. Decoding the words, the language smell a positive way to create a new word. This challenges multiple applications (CLEF2001: http://www.ercim.org/publication/ws-proceedings/CLEF2/) such as machine translation, speech recognition, text classification, information extraction, and information retrieval. .. It turns out that it is difficult to figure out the words that make up a compound word. There are basically three known solutions in this area.

<p> The first solution is to keep a list of "all" compound words that exist in a language and how to divide the compound words. The disadvantage is that it is not possible to keep a list of all compound words in a language. Because the amount of compound words in a language is endless. Because of this, the accuracy of this solution is low and this method is tedious. This technique applies to one language.</p><p> The second solution is to find out the words that make up the compound word based on the rules, which is simple. This rule may be combined with statistical data that indicates when to split. The problem here is that this method often divides a compound word into non-existent words or combinations of words that have nothing to do with the meaning of the compound word. This works for common compound words, but it's not powerful. This technique applies to one language.</p><p> The third (final) solution uses a digital dictionary. Based on the dictionary and some rules, the words that make up the compound word are indexed. An example of this final solution is disclosed in US Patent Publication No. 03/0097252, a method of determining the words that make up a compound word. The constituent words are determined based on the stochastic point cloud of the compound word. Breakpoint weights are assigned to break points in compound words based on an analysis of n-graphs drawn from the appropriate vocabulary. This method finds out the words in a compound word. The main drawback is that incorrect word splits can occur.</p><p> In order to overcome the shortcomings of the prior art, one of the objects of the present invention is to determine the words that make up a compound word.</p>

<p> This is a device described in a preamble, and further means for obtaining a ratio between the number of documents containing a compound word and the number of documents containing the constituent words constituting the compound word, and when the ratio is smaller than the threshold value. It is realized by a device having a means for dividing the compound word into the constituent words.</p><p> The device observes that when the ratio of the number of documents containing a compound word to the number of documents containing the constituent words that make up the compound word is less than the threshold, the compound word is accurately divided into the found constituent words. It is based on.</p><p> In another embodiment, the device according to the invention further comprises means for detecting a binding morpheme in the compound term. Detecting combined morphemes in compound words is essential for finding constituent words.</p><p> In another embodiment, the device according to the invention further comprises a word list obtained from a collection of the documents and means for finding the constituent words by using the word list. Detection of constituent words that make up a compound word is more effective when a word list containing all the words in the collection of the above documents is speculatively prepared.</p><p> In the next embodiment, the apparatus according to the present invention further includes a word list obtained from the collection of the above documents, and a means for obtaining the number of documents including the compound words from the word list. It is efficient to have a word list that can guide the number of documents that contain compound words.</p><p> In the next embodiment, the apparatus according to the present invention further includes a word list obtained from a collection of the above documents, and a means for obtaining the number of documents including the constituent words constituting the compound word from the word list. It is efficient to have a word list that can derive the number of documents that contain the constituent words that make up a compound word.</p><p> In the next embodiment, the device according to the present invention is incorporated in the information retrieval system. The user inputs a search item, and if this item is a compound word, it is divided into constituent words and the search is executed for the divided constituent words. In this way, the operator can create a search that finds all documents that are constituent words that make up a compound word and that include constituent words that meet the division criteria.</p><p> In the next embodiment, the device according to the invention is selected with the threshold value depending on the collection of the documents. This makes it possible to select a threshold value according to the collection of documents used. This optimizes compound word splitting.</p><p> In another embodiment, the device according to the present invention has the above threshold value of 3. This indicates that it is the optimal threshold for a collection of Dutch documents.</p><p> In another embodiment, in the device according to the present invention, the compound word and the constituent word belong to a noun grammatically.</p><p> In another embodiment, the device according to the invention includes the singular and plural forms of each word in the word list. This will find all the constituent words that make up the compound word.</p>

Hereinafter, the present invention will be described with reference to the following exemplary embodiments of the present invention, and will be illustrated with reference to the drawings. These embodiments are intended to illustrate the invention and should not be construed as limiting the invention.

Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

FIG. 1 shows an embodiment of an information retrieval system according to the present invention. Here, the information retrieval system is, for example, a document management system, a web search system, or the like.

The document management system has an operator console (101), a search engine front end (104), a search engine (105), and a document database (106). The operator console provides a user interface for the system according to the present invention. The operator console includes a display (102) and data entry means, such as a keyboard (103). The search engine front end (104) translates all data received from the operator console into a search performed by the search engine. The search engine (105) performs this search on the database and arranges for the search results to be returned to the submitter. The database (106) contains the documents to be searched. Various modifications of this system can be considered. As a first modification, all the components of FIG. 1 may be built into one personal computer. As another variant, a search engine (105), a search engine front end (104), and a document database (106) are implemented in one server, and many operator consoles (101) are implemented as workstations. May access the server as a client and use a web browser as a means of accessing the server.

FIG. 2 shows an embodiment of a search engine (105) and a document database (106) according to the present invention. A collection of documents can include all forms of textual information such as reports, newspaper articles, and web pages. Before starting the actual search process, all the words in a collection of documents (201) are collected, for example by the semantic network (202), and ordered as a word list (203). The best results for automatic translation or information retrieval are obtained by considering only the words that exist in the collection of documents. This is done by collecting all the words from a collection of documents and arranging these words in order in a word list.

The search process begins when the search engine (105) receives a search from the search engine front end (104). An example of a search containing T items is t₁And t₂And ... t_TIs. Where item t_iIs one of the items used (t)_i (t₁ T_T)). One item may be any word. Arbitrary logical operators such as AND (and), OR (or), and NOT can be used between items. As will be apparent to those skilled in the art, the search consists of T items. Where T is at least 1. As will be apparent to those skilled in the art, one or more items may be processed in the search as an embodiment of the present invention.

The split compound determination module (204) determines for all items in a search whether the item contains a plurality of constituent words that should be separated in the search.

The result of the split compound judgment module (204) is a modified search that includes the words that make up the compound word as separate bodies. The Document Retrieval and Ranking Module (205) uses this modified search and word list to retrieve reference documents, calculate relevance scores for each reference document, and rank the reference documents found. This ranked reference document is communicated to the search engine front end (103) along with their relevance score. FIG. 3 shows an embodiment of the division compound determination module (204) according to the present invention. The split compound determination module (204) determines for each item ti of one search whether or not the item is a compound word and whether or not the words that compose them should be separated. When starting from the start position 301, the item counter i is first set to the value 1 in step 302. In step 303, item t_iIs the item t_iIt is determined whether or not it contains the words that make up. These constituent words are derived from the word list (204). There can be multiple combinations of words that make up the same compound word. Each combination is called a constituent word group. The word list is used to find the combinations of words that make up a compound word. When the constituent word is found (Y in step 303), the constituent word group counter j is initialized to the value 1 in step 304. The next step 305 is the compound word t_iDetermine the number of documents that contain. This function is called DT (i). Step 305 finds the number DP (i, j) of documents containing the constituent word group j. The functional results of DT (i) and DP (i, j) can be found using a word list, as will be explained later with examples. In step 306, the division criterion DT (i) &lt;3 * DP (i, j) is determined for each j-th constituent word group. If DT (i) &lt;3 * DP (i, j) is satisfied (Y), then in step 307, the compound word t_iThe word group j that composes is separated into disjointed words. If DT (i) &lt;3 * DP (i, j) is not satisfied in step 306 (N), the process proceeds to S308. The division judgment criteria are all items t_iIs determined and finally a modified search is obtained. The value j of the constituent word group counter is incremented by 1 in step 308, and it is determined in step 309 whether or not all the constituent word groups have been processed. If some constituent words have not been processed (N), this method is repeated in step 305 for the next constituent words. When all the constituent words have been processed (Y), the item counter value i is incremented by 1 in step 310. The same applies when step 303 is repeated without finding the words that make up the compound word in step 303 (N). In the next step 311 all items t_iIs determined whether or not has been processed. All items t_iWhen is not processed (N), the method returns to step 303. All items t_iWhen has been processed (Y), the method is stopped at step 312.

As will be apparent to those skilled in the art, as one embodiment of the present invention, one or more items in the search may be processed to separate items that are constituent words that meet the division criteria of step 306. A compound word is created by combining multiple existing words. When combining words, a combined morpheme can be inserted at the junction. There is no simple rule about when such a combined morpheme can be inserted, so a check must be made between all two words. In German compound words, "s" and "es" are used as linking morphemes. In Dutch, "s" is possible as a binding morpheme.

Figure 4 shows item t_iThe flow chart of the embodiment of the method (step 303) of determining the words constituting the above is shown. The embodiment of FIG. 4 is a typical example for Dutch because it considers only "s" as the binding morpheme. As will be apparent to those skilled in the art, it is possible to check for other binding morphemes and two or more binding morphemes for other complex languages and deal with them accordingly. This method starts from step 401. In step 402, item t_iIs the string w₁^LWill be copied to. Where L is the item t_iIndicates the total number of characters in. In addition, the word character start position s is set to 1, the word level counter value is set to 1, the flag is set to "false", and the last character position c (level = 0) of a potential word on the word level is set to a value of 0. , The word character end position c (level = 0) is initialized to the value 2. In step 403, the character position c (level) is the character string w._s^LWhen the penultimate character of is not reached, that is, when Lc (level) 2 (Y), in step 404, referring to the word list, the character string w_s^{c (level)}Determine if is a word. w_s^{c (level)}When is not a word (N in S404), in step 408, the value c (level) of the word character end position is incremented by one. When is a word (Y in S404), in step 405, the word is stored as a word store on the actual word level. For example, the first word found (hence its level is level 1) word w_s^{c (level)}Is stored as the store Word (level = 1). After that, this level value is updated to the next word level, and the value of the character position on the new level c (level) value is initialized to c (level-1). In the next step 406, the value of the situation, which is one of the eight situations described in detail later, is obtained, and the process proceeds to step 407. In step 407, which depends on the status and flag values, the word character start position s and the word character end position c (level) are adapted to the new character position, and in some cases one word is found, as described in detail later. Some actions are performed, such as being remembered. After step 407, the method proceeds to step 403. In step 403, the character string w_s^LWhen the penultimate character of is reached, that is, when Lc (level) &lt;2 (N), the method proceeds to step 409. Step 409 becomes affirmative (Y) when the flag status is "true", and the process proceeds to step 407. This is, for example, the word w^L_{c (level) +1}Attempts to split the word w^L_{c (level) +2}For example, when trying to divide. After that, when the flag becomes "false" and step 409 becomes negative (N), the process proceeds to step 410. In step 410, the word level is reduced by one. In step 411, it is checked whether all word levels are determined to have found other words. When the word level&gt; 0 (Y in S411), this process first increases the value c (level) of the word character end position by 1 in step 412, and increases the value s of the word character start position by c (level) +1. Expand the word to another word by updating and proceed to step 403. When the check in step 411 determines that all word levels have been extended to another word (N), in step 413, t_iIt is checked whether or not the words constituting the above are found, and then the method ends in step 413.

FIG. 5 shows in detail one embodiment inside Table 1 (S406) and Table 2 (S407). In Table 1 (S406), four judgment criteria judge the situation value. These criteria are flag status (true / false), the rest w^L_{c (level) +1}Is a word (yes / no), character position w_{c (level) +1}^{c (level) +1}Is "s" (yes / no) and the rest w^L_{c (level) +2}Is a word (yes / no). The fifth column of Table 1 (S406) shows the assigned status values. As shown in the last cell of the last row, there is no status value update when the flag value is true. After that, the final status after the update is entered in Table 2 (S407). In Table 2 (S407), two criteria: the situation value ( {1,2, ···, 8}) and the flag status (yes / no) are used to determine the required action. The "flags" of the judgment criteria in Table 2 (S407) are the same as the "flags" of the judgment criteria in Table 1 (S406). The indicator CONSTITUENT () in Table 2 (S407) in Fig. 5 shows the word group {word (h) that was determined to compose a compound word._{h = 1}^{h = level}} Indicates that it is added to the constituent word group list as a set. For example, if status = 1 and flag = false are entered in Table 2 (S407), the flag will be (later w).^L_{c (level) +2}True set (so that you can split) the word w^L_{c (level) +1}Is copied into the store word (level), the constituent words are added to the constituent word group list as a set, then the word wLc (level) +2 is copied into the store word (level), and the constituent words are composed as a set. Added to the word group list. After that, the character position values c (level) +2 and c (level) +3 are later (first the word w).^L_{c (level) +1}Word w after trying to split^L_{c (level) +2}Are stored as helper constants "sf" and "cf" for use (to attempt to split into two words), and the character position values s and c (level) are c (level) +1 and c (level), respectively. ) +2, this method leaves the table, goes to step 403, word w^L_{c (level) +1}Attempts to separate the two words.

(Specific example) In order to explain the mechanism of this system, we will introduce some specific examples of determining constituent words that satisfy the division judgment criteria within compound words.

(Specific example 1) In the first specific example, the search is the item t in Dutch._i: Includes "basketbalkampioenschappen". Here, i = 1. The English translation is "basketball championships". The split compound judgment module (202) finds all the constituent nouns that make up a compound word using a word list containing all the nouns extracted from the collection of documents. As an example, the word list in FIG. 6 is used. The first column of this word list contains all the nouns available in the collection of documents in alphabetical order. The second column contains, for each noun, all reference documents that contain that noun in the collection of documents. The third column contains the number of documents containing the noun in the collection of documents. As an embodiment of the word list, only the first two columns may be included. The third column can be obtained from the second column. As will be apparent to those skilled in the art, the word list may be expanded with additional information such as column 3 or may include other word types such as verbs, with nouns indicated by noun indicators. It is possible. As is clear from Figure 6 to those skilled in the art, the compound word t_iThe number of documents (third column) including (first column) can be obtained from this word list.

In this embodiment, in the first main step (S303), the word list (205) of FIG. 6 is used to determine the possibility of all constituent words called the groups that make up the "basketbalkampioenschappen". For the Dutch compound word "basketbalkampioenschappen", the split compound judgment module (202) finds eight constituent nouns. In Figure 7, all eight constituent words found are shown in the second column. The first found constituent word group (j = 1): "basketbal" + "kampioenschappen" is shown in the second cell of the second row of Fig. 7. In step 305, the compound word t_i: The number of documents DT (i) including "basket balkampioen schappen" is calculated. The compound word "basketbalkampioenschappen" is not found in any document in the collection of documents (207) by the semantic network module (206). In the first column of the word list in FIG. 6, the compound word "basketbalkampioenschappen" is not available, so DT (i) = 0. The next action in step 305 is to find the number of documents DP (i, j) containing all the constituent words j. The number of documents DP (i, j = 1) containing the constituent words separately in one document can be derived from the word list shown in FIG. In this word list, the noun "basketbal" is used in documents [1]-[8], and the noun "kampioenschappen" is used in documents [1]-[6] and [9]. From this word list, it is derived that these two nouns are both used in documents [1] and [6], so DP (i, j = 1) = 6. Doing the same for the remaining seven constituent words leads to DP (i, j) = 0. The DP (i, j) values are shown in the fourth column of Figure 7. In step 306, the division criterion DT (i) &lt;3 * DP (i, j) is determined for each constituent word group j. The result of this determination is shown in the fifth column of FIG. Only the first (j = 1) constituent words meet this criterion. In this example, only the constituent words "basketbal" + "kampioenschappen" meet the split criteria and are split into separate "basketbal" and "kampioenschappen" in step 307. The results of step 307 in this example are shown in column 6 of FIG.

When the search item "basketbalkampioenschappen" is applied to the search engine (105) without using the split compound judgment module, the modified search cannot be obtained and no related documents can be found in the collection of documents. However, when the split compound judgment module is applied to the search item "basketbalkampioenschappen", the modified search becomes, for example, ("basketbal" AND "kampioenschappen"). Here, for example, ("basketbal" AND "kampioenschappen") OR "basketbalkampioenschappen" is also valid.

This modified search finds related documents [1], [2], [3], [4], [5], and [6], sometimes with the help of the word list in Figure 6.

(Specific example 2) Here, the compound word t is given as an example of Hollande._iExplain how the constituent words of are found in step 303. The English translation of this word is "course of life".

<maths num="1"><img file="JP2005293582A_D0001.tif" /></maths>Multiple events can be identified while finding a constituent word. These events are shown in Table 1. Note that the word list does not define "levens". The English translation is "life".

<tables num="1"><img file="JP2005293582A_D0002.tif" /></tables>The events in Table 1 include the event status of the (noun) level, the noun start position s, and the word character end position c (level) for the two levels c (level = 1) and c (level = 2). Can be placed in Table 2.

<tables num="2"><img file="JP2005293582A_D0003.tif" /></tables> (Specific example 3) Another example is given.

<maths num="2"><img file="JP2005293582A_D0004.tif" /></maths>Multiple events shown in Table 3 can be identified while finding the constituent words. Here, the word list does not include the noun "verkeers plan" (English: "traffic plan").

<tables num="3"><img file="JP2005293582A_D0005.tif" /></tables>In Table 4, the noun level, the noun start position s, and the word character end positions c (level) for the three levels c (level = 1), c (level = 2), and c (level = 3), Event status is given.

<tables num="4"><img file="JP2005293582A_D0006.tif" /></tables> Although the present invention has been described above, it is clear that the present invention can be changed in many ways. Such variations should not be considered to deviate from the intent and scope of the invention, and all such modifications are apparent to those skilled in the art and may be included in the claims. Intended.

<figref num="1">It is a block diagram of one Embodiment of the apparatus which concerns on this invention.</figref><figref num="2">It is a block diagram of one Embodiment of the search engine and the document database which concerns on this invention.</figref><figref num="3">It is a flow chart of one Embodiment of the division compound judgment module.</figref><figref num="4">It is a flow chart of one Embodiment of the method of determining the word which constitutes a compound word.</figref><figref num="5">It is one embodiment of Tables 1 and 2.</figref><figref num="6">It is an embodiment of an example of a word list.</figref><figref num="7">It is a figure which shows one embodiment of the method intermediate result about the compound word "basketbalkampioenschappen".</figref>

Code description

101 Operator Console 102 Display 103 Keyboard 104 Search Engine Front End 105 Search Engine 106 Document Database 201 Document Collection 202 Semantic Network 203 Word List 204 Split Composite Judgment Module 205 Document Search and Ranking Module