JP2011180862A - Method and device of extracting term, and program - Google Patents

Abstract

The present invention provides a term extraction method that takes into account fluctuations of terms and the like at high speed.
The term extraction method of the present invention includes a term WFST creation process, a fluctuation WFST conversion process, a converter synthesis process, a WFST storage process, and a WFST decoding process. The term WFST creation process creates a term WFST in which each term in the term list input from the outside is WFST-represented. The fluctuation model conversion process converts the fluctuation probability of a term or the fluctuation probability of a transliteration into fluctuation WFST which is a fluctuation model. Then, in the WFST decoding process, terms including notation fluctuations and different notations are extracted from the input character string using the synthesized WFST obtained by synthesizing the fluctuation WFST and the term WFST.
[Selection] Figure 2

Description

  The present invention relates to a term extracting method, an apparatus, and a program for extracting terms from text.

  As the simplest example of the conventional term extraction method, there is a method of preparing a term list in advance and extracting a term that matches a given text with a character string. Since this method collates the text with each word of the term list one by one, it requires an extraction time proportional to the number of terms in the term list.

  For the purpose of reducing the extraction time, for example, a method of managing dictionary data in a tree structure format called “trie” is known (Non-Patent Document 1). In this method, in the case of a term having a length of k characters, the registered term can be extracted by k times of processing, so that the extraction time can be shortened compared to the method of collating each word in the word list one by one. In addition, there is also known an improved method for avoiding unnecessary collation for the purpose of avoiding collation with all partial character strings of text (Non-Patent Document 2).

Edited by Makoto Nagao, Satoshi Sato, "Iwanami Course Software Science, Natural Language Processing", Iwanami Shoten, p250 Kenji Kita and Kazuhiko Tsuda “Information Search Algorithm” Kyoritsu Shuppan, January 2002, p108

  The conventional method described above has a problem that only terms that completely match the term list can be extracted. For example, even when “violin” is registered in the term list, the notation fluctuation “violin” cannot be extracted. In addition, there is a problem that it is impossible to extract different notations such as “violin”.

  To successfully collate “violin” and “violin” in the terminology list, for example, collate both notations with dynamic programming (reference: “Japanese Information Processing” p40, edited by IEICE). Can be considered. However, this method is not practical because it requires a matching time proportional to the number of terms in the term list as in the conventional method. In addition, transliteration probabilities for each phoneme such as “Bi-vi”, “O-o”, and “Lin-lin” are obtained to match “violin”, and the transliteration probability of “violin-violin” exceeds the threshold. A method of extracting can also be considered. However, this method is not practical because it requires a matching time proportional to the number of terms in the term list.

  The present invention has been made in view of such problems, and it is an object of the present invention to provide a term extraction method, an apparatus thereof, and a program capable of performing collation at high speed and extracting terms in consideration of notation fluctuations. To do. The term extraction method of the present invention uses a weighted finite state transducer (hereinafter referred to as WFST) that is an extension of a finite state automaton.

  The term extraction method of the present invention includes a term WFST creation process, a fluctuation model conversion process, a converter synthesis process, a WFST storage process, and a WFST decoding process. The term WFST creation process creates a term WFST, which is a term list expressed in WFST from each term in the term list input from the outside, separating each term for each character and using each character as an input character. The fluctuation model conversion process converts the fluctuation probability of a term or the fluctuation probability of a transliteration into fluctuation WFST which is a fluctuation model. The converter combining process combines the terms WFST and fluctuation WFST and outputs a combined WFST. In the WFST storage process, the composite WFST is stored in the WFST storage unit. In the WFST decoding process, the WFST storage unit is referenced to decode the character string of the transition sequence that maximizes the cumulative weight for the input character string.

  According to the term extraction method of the present invention, the fluctuation probability of terms and the fluctuation probability of transliteration are expressed in WFST, and the fluctuation WFST and the term WFST created from each term in the term list are synthesized. By using the synthesized WFST, terms including notation fluctuations and different notations are extracted. Therefore, since all the term candidates are compressed and stored in this synthesized WFST, it is possible to extract terms in consideration of notation fluctuations and the like at a high speed by one collation.

The figure which shows the structural example 100 which implement | achieves the term extraction method of this invention. The figure which shows the operation | movement flow of the vocabulary extraction method of this invention. It is a figure which shows the example of the term list | wrist 1, (a) shows only a term, (b) shows the example which provided identification ID to the term. The figure which shows the example of the term WFST of the term list 1. The figure which shows the example of the fluctuation probability 2 of a term. The figure which shows the example of fluctuation WFST (term). The figure which shows the example of the fluctuation probability 3 of transliteration. The figure which shows the example of fluctuation WFST (transliteration). The figure which shows the example of synthetic | combination WFST. The figure which shows the example of a process of the WFST decoding part. The figure which shows the function structural example of the vocabulary extraction apparatus 200 of this invention. The figure which shows the operation | movement flow of the term extraction apparatus 200.

  Embodiments of the present invention will be described below with reference to the drawings. The same reference numerals are given to the same components in a plurality of drawings, and the description will not be repeated.

  FIG. 1 shows a functional configuration example 100 for realizing the term extraction method of the present invention. The operation flow is shown in FIG. The functional configuration example 100 includes a term WFST creation unit 10, a model conversion unit 20, a converter synthesis unit 30, a WFST storage unit 40, and a WFST decoding unit 50. Each of these units or all the functions are realized by, for example, reading a predetermined program into a computer including a ROM, a RAM, a CPU, and the like, and executing the program by the CPU.

  The term WFST creation unit 10 creates a term WFST, which is a term list expressed in WFST from each term in the term list 1 inputted from the outside, separating each term into characters and using each character as an input character (step) S10).

The model conversion unit 20 converts the fluctuation probability 2 of the term or the fluctuation probability 3 of the transliteration into a fluctuation WFST that is a fluctuation model (step S20). The converter combining unit 30 combines the term WFST created by the term WFST creating unit 10 and the fluctuation WFST converted by the model converting unit 20 and outputs a synthesized WFST (step S30). The WFST storage unit 40 stores the combined WFST (step S40). The WFST decoding unit 50 refers to the WFST storage unit 40 and decodes the character string of the transition sequence that maximizes the cumulative weight for the input character string (step S50).
As described above, according to the term extraction method described above, a specific term can be extracted from an input character string at high speed in consideration of notation fluctuation. Hereinafter, the operation of the present invention will be described in more detail by showing specific examples of the term WFST and the fluctuation WFST.

[Term WFST]
FIG. 3 shows an example of the term list 1. FIG. 3A shows “violin”, “earring”, and “boring” as specific examples. As shown in FIG. 3B, an identification ID may be given to each term.

  FIG. 4 shows an example of the term WFST created by the term WFST creation unit 10 from the term list 1 of FIG. Since there are an infinite number of equivalent WFSTs, FIG. 4 is an example. In FIG. 4, a circle represents a state, and a number in the circle represents a state number. Arrows indicate state transitions. The character string appended to the arrow represents “input character: output character / weight”. The output character ε means an empty character.

The initial state is the state (0), and the acceptance state is the state (5) indicated by a double circle. Conversion from the term list 1 to the term WFST is performed by dividing each term into characters and setting a state transition with each character as an input character.
When the input character “B” is given in the initial state (0), the state transitions from the state (0) to the state (1). The state transition at that time is an input character “B”, an output character “Violin”, and a weight 1.0. The input character for the state transition from state (1) to state (2) is "I", the output character is ε (empty character), the input character for state transition from state (2) to state (3) is "o", and the output character Is ε (null character), state (3) → state (4) state transition input character is “li”, output character is ε (null character), state (4) → state (5) state transition input character is “N”, the output character is ε (empty character), and the acceptance state (5) is reached. Similarly, the term WFST shown in FIG. 4 is created for the other terms boring and earring.

In FIG. 4, the character string of each term is described in the state transition immediately after the initial state (0), but the equivalent term WFST is obtained even if it is described in any state transition in the same term. When an identification ID (FIG. 3B) is assigned to each term, the identification ID is described in the state transition immediately after the initial state (0) instead of each term.
When probability values are handled as weights, weights are accumulated by multiplication. In that case, all the weights are set to 1. When logarithmic probabilities are treated as weights, weights are accumulated by addition. In that case, all the weights may be set to 0.

[Fluctuation WFST]
FIG. 5 shows an example of the fluctuation probability 2 of terms. As fluctuation notation for the original notation “ba”, for example, there are two “ba” and “va”, and their appearance probabilities are 0.7 and 0.3. This appearance probability may be given by a person or may be obtained mechanically (for example, reference: Japanese Patent No. 4084515).

  FIG. 6 shows an example in which the term fluctuation probability (FIG. 5) is converted into a fluctuation model WFST which is a fluctuation model. The fluctuation WFST is a converter (transducer) that rewrites the fluctuation notation to the original notation, and the integration of the weights when transitioning from the initial state (0) to the acceptance state (4) becomes the probability value shown in FIG. The conversion from the term fluctuation probability to the fluctuation WFST performed by the model conversion unit 20 is performed by setting a state transition in which the fluctuation notation is divided in units of characters and each character string is included in the input character one character at a time.

  With respect to the input character of fluctuation notation “B”, the output state of “B” for the output character “B” is a state transition with a weight of 0.7 (B: B / 0.7), initial state (0) → accepted state (4) Transition with. In addition, with respect to an input character of fluctuation notation “va”, a weight for outputting the output character “ba” is 0.3, and a state transition for transition from the initial state (0) to the acceptance state (4) is provided in parallel. ing. Similarly, a state transition (A: A / 0.9), a state transition (YA: A / 0.1), etc., for which the output character “A” is output with respect to the fluctuation notation “A” are 0.9. It is provided in parallel. The process automatically returns from the acceptance state (4) to the initial state (1) without input (ε: ε).

  FIG. 7 shows an example of the fluctuation probability 3 of transliteration of alphabetic characters. There are two transliteration fluctuation notations for the original notation “ba”, for example, “ba” and “va”, and their appearance probabilities are 0.7 and 0.3. FIG. 8 shows an example in which the transliteration fluctuation probability (FIG. 7) is converted to fluctuation WFST. The transliteration fluctuation WFST is performed by dividing the fluctuation notation in units of characters and setting a state transition in which each character string is one character at a time as in the case of the term fluctuation. Transliteration fluctuation WFST is used for an input character string of alphabet characters.

[Synthetic WFST]
FIG. 9 shows an example of a combined WFST in which the term WFST in FIG. 4 and the fluctuation WFST (term) in FIG. 5 are synthesized. Composition is one of the typical operations of WFST, and is to make two WFSTs into one WFST. For example, reference: author “Fernando CNPereira, Michael Riley” title “Speech Recognition by Composition of Weighted Finite Automata” source “In Emmanuel Roche and Yves Schabes, editors, Finite-State Devices for Natural Language Processing, chapter 15 , pp.431-453. MIT Press, Cambridge, Massachusetts, 1997.
The state (14) of FIG. 9 changes from the state (0) of the term WFST (FIG. 4) to the state (1), and from the state (0) of the fluctuation WFST (FIG. 6) with the input character “V”. A state transition ((0) → (1) → (4)) with a transition probability of 0.3 is a state added as a result of the synthesis. Further, the state transition (c: ε / 0.2) added from the state (6) to the state (7) in FIG. 9 is the state transition ((0) → (3) → () of the fluctuation WFST (FIG. 6). 4)) is the result of the synthesis.

  The combined WFST in which the term WFST and the fluctuation WFST are combined as described above is stored in the WFST storage unit 40. As for the transliteration fluctuation WFST, the synthesized WFST synthesized in the same manner as the term fluctuation is stored in the WFST storage unit 40.

[WFST decoding unit]
The WFST decoding unit 50 may be anything as long as it can output a character string of a transition sequence that has the maximum cumulative weight with respect to the input character string. For example, the WFST encoding unit 50 performs the process shown in FIG.
Here, an example in which the input character string is input in units of words will be described.

  First, the initial state is put in a queue (Step S51). The state is data composed of (character position, state number, output character string, cumulative weight). The queue can be a simple stack or FIFO. When only one maximum likelihood solution is obtained, a priority queue is used. The initial state is (the beginning of the character string, the start state number, the empty character string, the initial weight). The initial weight is 1 if the weight integration is multiplication and 0 if the addition is addition.

  Next, one state candidate is acquired from the queue (step S52). Then, the character corresponding to the character position in the acquired state is acquired from the input character string and set as the next character (step S54).

  All transitions in which the acquired next character matches the input character are acquired with reference to the WFST storage unit 40 (step S55). In addition, a transition in which the input character is an empty character (ε) and whether the current state number is an accepted state number are also acquired from the WFST storage unit 40.

If the current state number is an acceptance state number, the acceptance state is registered in the result list (step S57). For example, when a queue with priority is used and only one maximum likelihood solution needs to be obtained, the process ends here (Yes in step S58).
In the acceptance determination (step S56), a term that matches the input character string is extracted. If only exact matching terms are to be extracted, it is only necessary to determine whether the character position is at the end of the input character string.

  Next, all the obtained transition destination states are added to the queue (step S59). Of the transition destination states, the next character position is the same as the current character position if the input character is an empty character (ε), and is the position advanced by one character otherwise. The next state number is a transition destination state number acquired from the WFST storage unit 40. The output character string is a concatenation of the current output character string and the output character string acquired from the WFST storage unit 40. The cumulative weight is obtained by integrating the current cumulative weight and the cumulative weight acquired from the WFST storage unit 40.

  The processes in steps S52 to S59 are repeated until no state candidate can be acquired (No in step S53). The character string stored in the result list at the time when the state candidate cannot be acquired is the output of the WFST decoding unit 50 (Yes in step S53). When the input character string is input in units of words as in this example, term matching is more suitable than actual term extraction. Such a term matching method can be used as a keyword input filter of a search engine, for example.

[Term Extractor]
FIG. 12 shows a functional configuration example of the term extracting device 200 of the present invention. The operation flow is shown in FIG. The term extraction device 200 includes the WFST storage unit 40 and the WFST decoding unit 50 shown in FIG.
The WFST decoding unit 50 is configured to output a forward match. The extracted terms are stored in the result list. When prohibiting the same term from being extracted a plurality of times, the extraction of the term may be terminated when it is first extracted.

  The WFST decoding unit 50 takes in a character string that constitutes the entire text (step S201). Then, the WFST decoding unit 50 executes the above-described WFST decoding process from the first character of the input character taken in to the end of the input character string while updating the input character (steps S50, S202, S203). In the WFST decoding process, the extracted term is output to the result list every time the acceptance state number is detected (step S50).

  The term extraction device 200 extracts terms using the synthesized WFST obtained by synthesizing the fluctuation WFST and the term WFST created from each term in the term list. Can be extracted.

  When the processing means in the above apparatus is realized by a computer, the processing contents of the functional units that each apparatus should have are described by a program. Then, by executing this program on the computer, the processing means in each apparatus is realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used. Specifically, for example, as a magnetic recording device, a hard disk device, a magnetic tape, or the like, and an optical disc, a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), a CD-ROM (Compact Disc Read Only Memory), Using CD-R (Recordable) / RW (ReWritable), etc., magneto-optical recording medium, MO (Magneto Optical disc), etc., semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), etc. it can.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Further, the program may be distributed by storing the program in a recording device of a server computer and transferring the program from the server computer to another computer via a network. In addition, the functional configuration unit of each device may be configured by causing a predetermined program to be executed on a computer, or at least a part of these processing contents may be realized in hardware.

Claims (3)

A term WFST creation process for creating a term WFST, which is a term list expressed in WFST, with each character being separated for each character from each term of the term list input from outside,
A fluctuation model conversion process for converting a fluctuation probability of a term or a fluctuation probability of a transliteration into a fluctuation model WFST,
A converter combining step of combining the term WFST and the fluctuation WFST and outputting the combined WFST;
A WFST storage process of storing the composite WFST in a WFST storage unit;
A WFST decoding process of decoding a character string of a transition sequence in which the cumulative weight with respect to the input character string is maximized with reference to the WFST storage unit;
A term extraction method including: A combined WFST in which a term list WFST expressed as a WFST expression using each character created from each term in the term list as an input character and a fluctuation WFST that is a fluctuation probability of a term or a fluctuation probability of a transliteration is stored. A WFST storage unit;
A WFST decoding unit that decodes a character string of a transition sequence in which the cumulative weight with respect to the input character string is maximized with reference to the WFST storage unit;
A term extraction device comprising:   An apparatus program for causing a computer to execute the function of each unit of the term extracting apparatus according to claim 2.

Images