JP5249848B2 - Information retrieval method and apparatus, program, and computer-readable recording medium - Google Patents

Description

  The present invention relates to an information search method, apparatus and program, and a computer-readable recording medium, and in particular, performs phrase search and compound word search using position information of words appearing in a document of an accumulated document group. The present invention relates to an information search method and apparatus and program for creating a search index that is performed at high speed and in a memory-saving manner, and a computer-readable recording medium.

  FIG. 10 shows a configuration of a general information search apparatus.

  The information search apparatus shown in FIG. 1 creates an index, specifies an index creation unit 1 to be stored in the search index storage unit 3, refers to the created index in the search index storage unit 3, identifies a search result set, and retrieves the search results. The search result set identifying unit 2 that returns The index creating unit 10 includes a morphological analyzer 11, a transposed list creating unit 12, and a transposed index adding unit 13.

  Here, focusing on the index creation unit 1 that is the subject of the present invention, in order to efficiently search for phrases and compound words, generally, the positional information of words is held in a transposed index. This list of position information is called a “transposition list”. The simplest transposition list holding method is a transposition list that stores word position information as shown in FIG. 11 (see, for example, Non-Patent Document 1). This method indicates that the word word_1 appears four times in the document ID 1 and its position information is [1, 3, 54, 58]. The index of this method holds the number of occurrences of word position information from the beginning of the document. This position information is used when the search word is a compound word or a phrase. For example, if you search for the phrase “Tokyo” and word_1 is “Tokyo” and word_2 is “Tokyo”, the document with ID1 is word_1 for the first word and word_2 for the second word. It can be seen that "City" appeared as a phrase. On the other hand, in the document with ID 144, since word_1 and word_2 do not appear next to each other, it can be seen that the words “Tokyo” and “city” co-occur in the document but do not appear in the phrase. The process of checking whether or not the phrase appears is called “joining process”.

  Specifically, a method for creating a transposed list will be described by taking a case where the following document is input as an example.

Example sentences:
ID = 1: “The Tokyo Governor Election was held in Tokyo. …. Three people from Tokyo who were running as governors of Tokyo ... ”
In the above example, create a transpose list in Tokyo. FIG. 12 shows a detailed flow of creating an inverted index.

  First, the morphological analysis unit 11 of the index creation unit 1 divides the character string into words (step 10).

  As a division method, morphological analysis such as “mecab (http://mecab.sourceforege.net/)” or “chasen (http://chasen.naist.jp/hiki/ChaSen/)” which is an existing technology is used. The following is the result of dividing the above example sentence into words by morphological analysis.

Example sentences:
ID = 1: Tokyo / de / Tokyo / metro / governor / election / ga / done / do / ta /. /.../. / Tokyo / Born / De / Tokyo / Metro / Governor / Ni / Candidate / Done / Has / 3 /
The section delimited by the slash is a word.

  Next, the transposed list creating unit 12 creates an empty transposed list with i = 0 (step 11).

  An inverted list is each element of an inverted index.

  It is determined whether the i-th word word (i) is at the end of the line (the end of the document) (step 12). If it is not the end, i is added to the transposition list corresponding to word (i) (step 13). The value of i at this time represents position information. For example, when the above document is input, word (1) is “Tokyo”, not the end of the line, so position information i is added to the transposed list of word (i).

  Next, i is incremented by 1 (step 14), and the process is repeated from step 12.

  In step 12, when the end of the line is reached, the inverted list created in the entire inverted index in step 15 is added to the search index storage unit 300. Specifically, if the above example sentence is document number 1 and word_1 is “Tokyo”, “Tokyo” appears as the first, third, 65th, and 69th morphemes. It can be seen that the transposed list is as shown in FIG. By repeating this for all documents, a transposed index for search is created.

  As described above, the inverted index of the prior art stores the position information as many times as it appears in the document, which causes an increase in index size.

Witten et.al., Managing Gigabytes, Morgan Kaufmann publishers, 1999.

  However, in the case of the index format of the above prior art, the position information and the memory used for the concatenation process are large, and it is necessary to examine all words appearing in the document when the concatenation process is performed. There is a problem that the speed is slow.

  The present invention has been made in view of the above points, and provides an information search method and apparatus, a program, and a computer-readable recording medium capable of reducing the index size although misdetection of concatenation processing can occur. With the goal.

  FIG. 1 is a diagram for explaining the principle of the present invention.

This onset Ming, information retrieval indexed from documents stored in the document database, stored in the search index storage means for storing an inverted index, which identifies the result set to return as a search result from the index created A method,
A document is read from the document database, the character string of the document is divided into words (step 1), and the number of position information indicating how many positions each word is counted from the top is set to a predetermined fixed length. Aggregating with the following numerical values and storing them in the first storage means (Step 2):
A mapping step (step 3) of acquiring a sequence of position information obtained in the position information aggregation step from the first storage means and mapping it to one transposed list of the second storage means;
The transposed list mapped in the mapping step is acquired from the second storage unit, and the transposed index adding step (step 4) for adding to the transposed index storage unit is performed.

  FIG. 2 is a principle configuration diagram of the present invention.

The present invention (claim 1 ) creates an index from a document group stored in the document database 30, stores an index creation unit 00 in a search index storage unit 300 that stores a transposed index, and a search result from the created index. A search result set specifying means 200 for specifying a search result set to be returned as an information search device,
The index creation means 100
A word dividing unit 110 that reads a document from the document database 30 and divides the character string of the document into words;
A position information aggregating unit 130 that aggregates the number of pieces of position information indicating how many positions each divided word is counted from the head with a numerical value that is equal to or less than a preset fixed length and stores it in the first storage unit. When,
A position information mapping means 140 for acquiring a position information column obtained by the position information aggregating means 130 from the first storage means and mapping it to one transposed list of the second storage means;
An inverted index adding unit 150 that acquires the inverted list mapped by the positional information mapping unit 140 from the second storage unit and adds the inverted list to the inverted index storage unit 300;

Further, the present invention (Claim 2 ) includes position information aggregating means including means for aggregating the number of position information using arbitrarily designated delimiters instead of using a fixed length when aggregating position information. 130.

The present invention (Claim 3 ) is an information retrieval program for causing a computer to function as each means constituting the information retrieval apparatus according to Claim 3 or 4.

The present invention (Claim 4 ) is a computer-readable recording medium storing the information search program according to Claim 3 .

  As described above, in the present invention, the position information stored in each word is divided into segments, and the position information is aggregated into a number counted from the beginning of the segment using a fixed length, thereby preventing erroneous detection of the concatenation process. The index size can be greatly reduced.

  In addition, by using a delimiter character, it is possible to prevent the operation as if they are connected even when they are not connected.

It is a figure for demonstrating the principle of this invention. It is a principle block diagram of this invention. It is a block diagram of the information processing search apparatus in the 1st Embodiment of this invention. It is an example of creation of an inverted index in the 1st embodiment of the present invention. It is a structural example of the transposed index in the 1st Embodiment of this invention. It is a flowchart of transposition index creation in the 1st embodiment of the present invention. It is a block diagram of the information processing apparatus in the 2nd Embodiment of this invention. It is a structural example of the transposed index using the delimiter in the 2nd Embodiment of this invention. It is a flowchart of transposition index creation in the 2nd embodiment of the present invention. It is a block diagram of a general information search device. It is an example of the structure of the inverted index by a prior art. It is a flowchart of transposition index creation by a prior art.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 3 shows the configuration of the information processing apparatus according to the embodiment of the present invention.

  The information processing apparatus of the present invention includes an index creation unit 100, a search result set identification unit 200, and a search index storage unit 300, as in the conventional information retrieval apparatus shown in FIG. Is different.

  The index creation unit 100 of the present invention reads a document group from the external document DB 30 and divides it into words for each document, and creates a transposition list composed of a transposition index and word position information for each word. , A transposition list creation unit 120 stored in a memory (not shown), and aggregating the number of pieces of position information of each word stored in the memory (not shown) and collecting the position information stored in the memory (not shown) Section 130, position mapping section 140 that acquires position information from a memory (not shown) and maps it to an array, and transposed index adding section 150 that additionally writes the mapped array to transposed index storage section 300. That is, the configuration shown in FIG. 10 includes a location information aggregating unit 130 that aggregates the number of location information included in a document, and a location information mapping unit 140 that maps the location information to an array.

  Since the above-described conventional inverted index stores the position information as many times as it appears in the document, the index size increases. In the present invention, the absolute value of the position information is compressed to a fixed length L. Specifically, this is realized by setting a fixed length L in advance and collecting the indexes so that the indexes are within the fixed length.

  FIG. 4 shows an example in which word_1 of the inverted index shown in FIG. 11 is aggregated with a fixed length L = 64. First, in the prior art, the position information “1, 3, 65, 69” is stored in the search index storage unit 3 for the document ID = 1, but in the present invention, this is stored in a numerical value of 64 or less. In addition, the position information aggregating unit 130 converts the numerical value of the positional information into a remainder of “64” and aggregates the numerical value with a fixed length L or less. For example, “65” becomes “1” when “64” is taken and the remainder is taken. Therefore, the column “1, 3, 1, 4” is obtained. This is mapped to one transposition list by the positional information mapping unit 140 to finally obtain the positional information “1, 3, 4” which is the transposed index of the present invention.

  FIG. 5 shows an example of an inverted index in which all numerical values are “64” or less using the present invention. The values of all position information in the figure are “64” or less. When using this to perform the same connection process as in the prior art, there is a possibility that the connection will not be connected even if the connection process is actually performed, but the index size and calculation amount can be greatly reduced. There is a merit.

  FIG. 6 is a flowchart for creating an index according to an embodiment of the present invention.

  Step 201) The morphological analysis unit 110 reads a document from the document DB 30, and divides the character string of the document into words. The method of morphological analysis is the same as in the prior art.

  Step 202) The transposed list creation unit 120 sets position = 0, i = 0, 1, and creates an empty index on a memory (not shown). The fixed length L can be given an arbitrary value, but the smaller the value, the smaller the index size, but the greater the misdetection of the concatenation process.

  Step 203) It is checked whether word_ (i) is at the end of the line. If it is not at the end of the line, the process proceeds to Step 204. If it is at the end of the line, the process proceeds to Step 209.

  Step 204) The position information aggregating unit 130 checks whether i is larger than the fixed length L. If i is larger, the process proceeds to Step 206. If smaller, the process proceeds to Step 205.

  Step 205) When the position information aggregating unit 130 is smaller than the fixed length L, the position information aggregating unit 130 advances the position by one, and proceeds to Step 207.

  Step 206) The position information aggregating unit 130 returns position to 0, and proceeds to Step 207.

  Step 207) The transposed list creation unit 120 adds position to the transposed list of word (i) on the memory (not shown).

  Step 208) Advance i by 1 and return to Step 203.

  Step 209) If the line is at the end in step 203, the position information mapping unit 130 reads the transposed list from the memory (not shown) and maps the position information. Mapping refers to combining the same location information into one. For example, in the case of the example of FIG. 4, when the position information [1, 3, 65, 69] (FIG. 4A) of the document ID = 1 is aggregated using the fixed length L, [1, 3, 1 , 4] (FIG. 4B), and mapping [ID = 1] that is the same position information results in [1, 3, 4] (FIG. 4C). The mapped location information is stored in a memory (not shown).

  Step 210) The inverted index adding unit 150 reads the mapped inverted list from the memory (not shown), adds the inverted list to the entire inverted index, stores it in the search index storage unit 300, and stores it in the index creating unit 100. End the processing on the side.

  As a result, a transposed index composed of position information having a fixed length L or less is created.

[Second Embodiment]
Since the above-described location information aggregation method limits L to a fixed length, there is a possibility that a sentence is divided. In the example sentence 1, when it is divided by the fixed length “4”, it is as follows.

Example sentences (ID = 1): / Tokyo / De / Tokyo / Miyako
/ Governor / election / ga / do
/ Re / ta /. /.../
Therefore, when searching for “Governor of Tokyo”, not only erroneous detection but also detection failure may occur. Therefore, in this embodiment, an index creation method using a delimiter instead of the fixed length used in the first embodiment is shown.

  FIG. 7 shows a configuration of an information search apparatus according to the second embodiment of the present invention.

  The information search apparatus shown in the figure is configured by providing a delimiter character position information aggregating unit 230 that aggregates position information using delimiters instead of the position information aggregating unit 130 of FIG.

  The delimiter can be specified arbitrarily, but when "." Is used as the delimiter, it is as follows.

Example sentence (ID = 1):
/ Tokyo / De / Tokyo / Tokyo / Governor / Election /

...
/ Tokyo / Born / De / Tokyo / Metro / Governor / Ni / Candidate / Done / Has / 3 /
As a result, erroneous detection may occur, but detection omission can be prevented.

  FIG. 8 shows an example in which position information is collected using delimiters. The difference from FIG. 4 is that even if the numerical value is 64 or less, the position information is collected when there is a sentence break. For example, the document ID = 170 is [2, 6, 8, 10] in the conventional inverted index, whereas the sixth word is a sentence break, so [2, 6, 2, 6] and finally mapped to [2, 6]. Since there is a high possibility that the same character string appears at the beginning of the sentence in this way, such mapping may contribute to index size reduction.

  FIG. 9 is a flow chart for creating an inverted index according to the second embodiment of this invention.

  Only the differences from FIG. 6 will be described in detail below.

  Step 302) The delimiter character position information aggregating unit 230 sets delimiter characters. For example, "." Or "." Can be set. It is also conceivable to give the delimiter as a pattern such as a regular expression.

  Step 304) The delimiter character position information aggregating unit 230 determines whether word (i) is the delimiter described above. If it is a delimiter, the process proceeds to step 306, and if it is not a delimiter, the process proceeds to step 305.

  Step 305) If it is not a delimiter, the position is advanced by one, and the process proceeds to Step 307.

  Step 306) If it is a delimiter, the position is set to 0 and the process proceeds to Step 307.

  Step 307) The transposed list creating unit 120 adds position to the transposed list of word (i) on the memory (not shown).

  Processing other than the above is the same as the operation of FIG.

  Through such a procedure, a transposed list using a delimiter can be created.

  In addition, each operation | movement of the component of said information processing apparatus can be constructed | assembled as a program, and it can install and run in the computer utilized as an information processing apparatus, or can distribute | distribute it via a network.

  Further, the constructed program can be stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM, and can be installed or distributed in a computer.

  The present invention is not limited to the above-described embodiment, and various modifications and applications can be made within the scope of the claims.

30 Document database (DB)
100 Index creation means, index creation section 110 Word segmentation means, word segmentation section 120 Transposition list creation section 130 Location information aggregation means, location information aggregation section 140 Location information mapping means, location information mapping section 150 Transposition index addition means, transposition index addition Section 200 search result set specifying means, search result set specifying section 230 delimiter character position information aggregation section 300 transposed index storage means, transposed index storage section

Claims (4)

A search result set for creating an index from a document group stored in a document database and storing it in a search index storage means for storing a transposed index, and a search result set to be returned as a search result from the created index An information retrieval device comprising:
The index creation means includes:
Word dividing means for reading a document from the document database and dividing the character string of the document into words;
Position information aggregating means for aggregating the number of pieces of position information indicating how many positions each divided word is counted from the head with a numerical value not more than a preset fixed length and storing the number in a first storage means; ,
Position information mapping means for acquiring a column of position information obtained in the position information aggregation step from the first storage means and mapping it to one transposed list of the second storage means;
An inverted index adding means for acquiring the inverted list mapped by the positional information mapping means from the second storage means and adding the inverted list to the inverted index storage means;
An information retrieval apparatus comprising: The position information aggregation means includes
Wherein when aggregating location information, instead of using the fixed length, the information retrieval apparatus according to claim 1 further comprising a means for aggregating using arbitrarily specified delimiter number of said position information. Information retrieval program for causing a computer to function as each means constituting the information retrieval apparatus according to claim 1 or 2 wherein. A computer-readable recording medium storing the information search program according to claim 3 .

Images