JP5314493B2 - Information search method, information search device, and information search program - Google Patents

Description

  The present invention relates to an information search technique for searching an electronic document in which a character string of a search condition appears and ranking based on the appearance frequency of the character string.

  As is well known, a general information search apparatus creates an index (word index) from a previously stored electronic document group in order to search for an electronic document having an arbitrary character string. A set of search results is obtained with reference to this word index, and the order in which the search results are displayed is determined (ranking).

  Referring to FIG. 6, the information search device 1 includes a word index 2, an index reference unit 3 (including proximity search means 6), a search condition input unit 4, and a search result output unit 5, and the word For the data structure of index 2, a transposed index, “suffix array”, or the like is used. Here, the data structure of the transposed index will be described as an example.

  When the search condition input unit 4 receives a search condition, that is, a search word, a character string (query) of the search word is transferred to the index reference unit 3. In the index reference unit 3, for example, a query such as “Tokyo” or “Tokyo Governor” is morphologically analyzed and divided into words. In addition, the word index 2 is referred to in order to search a document having divided words at high speed.

  For the word index 2, for example, the transposed index of Non-Patent Document 1 is used. Here, word position information is introduced by the method shown in FIG. 7 as the simplest method of holding an inverted index. This structure is called an inverted index, and a list of each word (a list for each “word_x” in FIG. 7) is called an inverted list. In this transposition list, document ID (id in FIG. 7), appearance frequency, and position information are stored.

  The document ID indicates a number assigned to each electronic document, the appearance frequency indicates the number of times “word_x” appears in the electronic document with the ID, and the position information indicates the position of “word_x” in the electronic document with the ID. Is shown. According to the example of FIG. 7, the transposed list corresponding to “Tokyo” appears four times in the document ID “1”, and the position information is indicated as “1, 5, 65, 69”.

This position information is used when the search word is a compound word or a phrase (phrase, idiom, etc.). For example, when searching for a compound word composed of a plurality of words “Tokyo”, the fifth word is “Tokyo” and the sixth word is “Tokyo” in the electronic document with the document ID “1”. It can be seen that the compound word “Tokyo” appears in the electronic document. On the other hand, in the electronic document with the document ID “144”, “Tokyo” and “Tokyo” do not appear next to each other, so that it is understood that the compound word “Tokyo” does not appear. The process of checking whether or not it appears as a compound word or phrase is called a concatenation process. This connection process is mainly executed by the index reference unit 3 and used for the following purposes.
1: Specifying an electronic document having a phrase or compound word 2: Counting the frequency of occurrence of a phrase or compound word In detail, “identifying an electronic document having a phrase or compound word” means that a compound word appears. This means that it is determined whether or not the electronic document is to be output as a search result. For example, when the search term is a compound word “Tokyo”, only electronic documents in which “Tokyo” appears can be used as a set of search results.

  Further, “counting the appearance frequency” means counting the appearance frequency in the electronic document of the compound word serving as the search condition. Referring to the transposed list of “Tokyo” and “Miyako” in the transposed list of FIG. 7, the compound word “Tokyo” is included three times in the electronic document with the document ID “1” (position information “5,65” of “Tokyo”). , 69 ”and“ city ”position information“ 6, 66, 70 ”). This appearance frequency is used as an index for ranking when ranking is finally output from the search result output unit 5 as a search result. For example, the search results may be displayed in the order of appearance frequency of the character string that becomes the search condition. Hereinafter, the processing steps (S001 to S0013) of the index reference unit 3 will be described with reference to FIG.

  S001: First, the character string of the search condition transferred from the search condition input unit 4 is divided for each word. For example, when a character string “Tokyo” is a search condition, it is divided into words “Tokyo” and “Tokyo”. This can be realized by a morphological element analysis technique such as Mecab (see Non-Patent Document 2).

  S002: As a result of the morphological element analysis in S001, it is determined whether or not the search condition can be composed of a plurality of words. For example, when the search condition is “Tokyo”, since it is composed of one word, the process proceeds to S003, the transposed list of the search word is acquired from the word index 2, the search result is created, and the process is terminated. To do. On the other hand, if it is composed of a plurality of morphemes such as “Tokyo”, the process proceeds to S004.

  S004. S005: Here, a transposed list corresponding to each word constituting the search condition is acquired from the word index 2 (S004). With reference to the acquired transposed list, the document ID having the smallest number among the document IDs appearing in all the transposed lists is acquired (S005). For example, in the transposed list of FIG. 7, the document ID “1” corresponds to the smallest number in which the words “Tokyo” and “Tokyo” appear.

  S006: It is checked whether there is a document ID that matches the process of S005. Since the document ID “1” exists in the search example of “Tokyo”, the process proceeds to S007. Conversely, if there is no document ID that matches the process of S005, the process ends.

  S007. S008: An initial value “1” of the appearance frequency i is set (S007). Further, the top position information is acquired in the document ID whose existence is confirmed in S006 (S008). For example, in the electronic document with the document ID “1”, the head position information for “Tokyo” is indicated as “1”.

  S009. S010: It is checked whether or not the position information acquired in S008 through the proximity search means 6 appears next to another transposition list (S009). Here, it is only necessary that position information adjacent to the acquired position information appears in another transposition list.

  In the example of FIG. 7, the transposed list in which the word “city” appears in the position information “2” in the document ID “1” is checked. Here, since it does not appear in the position information “2”, the process proceeds to S010 and it is checked whether or not the next position information exists. In this case, since the position information “5” exists after the position information “1” for the word “Tokyo”, the position information “5” is acquired, and the process of S009 is resumed. At this time, in the example of FIG. 7, since the location information “6” of “Miyako” exists in the other transposition list with respect to the location information 5 of “Tokyo”, the process proceeds to S010.

  S011 to S013: “1” is added to the appearance frequency i (S011), and the next position information is acquired (S012). The processing after S009 is repeated for the position information acquired here, and finally the appearance frequency “i” and its document ID are added to the search result (S013).

Witten et. al. "Managing Gigabytes", Morgan Kaufmann publishers, 1999. “MeCab: Yet Another Part-of-Speech and Morphological Analyzer”, [online], “May 7, 2009 search”, Internet <http: // mecab. sourceforge. net />

  However, in order to obtain the appearance frequency “i”, the position information must be checked (the processing of S008 to S012) for all the position information. Therefore, in the case of the existing index format, it becomes necessary to search the position information of all the words appearing in the electronic document, and the processing speed may be slow and the processing cost may increase.

  The present invention has been made in order to solve the above-described problems, and it is an object of the present invention to quickly calculate the appearance frequency of the character strings constituting the search condition and improve the processing efficiency.

  Therefore, the present invention makes it possible to create a search result without referring to all position information by predicting the number of proximities between words constituting the search condition, that is, the appearance frequency. At this time, information on a process of specifying an electronic document having a phrase or a compound word is used among the purposes of the concatenation process.

  One aspect of the present invention is an information search method for searching for an electronic document including a character string of a search condition and obtaining an appearance frequency of the character string to add to the search result. A first step for obtaining the search result with reference to a word index created from the electronic document, and a proximity number predicting unit predicting the proximity number of each word constituting the character string, and calculating the appearance frequency A second step to obtain.

  Another aspect of the present invention is an information search apparatus for searching for an electronic document including a character string of a search condition and obtaining an appearance frequency of the character string to add to the search result, the electronic document stored in advance And the index reference means for creating the search result with reference to the word index, the index reference means predicting the proximity number of each word constituting the character string, Proximity number predicting means for determining the appearance frequency is provided.

  The present invention may be in the form of a program for causing a computer to function as the information retrieval apparatus, or may be provided in the form of a recording medium on which the program is recorded.

  According to the present invention, since the appearance frequency is calculated without referring to all position information in the electronic document, the processing efficiency is improved and the processing cost is also suppressed.

The block diagram of the information search device which concerns on embodiment of this invention. The flowchart of the basic processing. The figure which shows the number of references of other processing examples (1). The figure which shows the number of references of other processing examples (2). The flowchart of the other process example (2). The block diagram of a prior art example. Structure diagram of transposed index. The processing flow figure of a prior art example.

≪Example of device configuration≫
As shown in FIG. 1, an information processing apparatus 10 according to an embodiment of the present invention is configured in substantially the same manner as the information processing apparatus 1, and is different in that a proximity number prediction unit 11 is incorporated in an index reference unit 7. doing.

  Specifically, the information processing apparatus 10 functions as a so-called search engine, and includes hardware resources of a normal computer such as a CPU, a memory (RAM), a hard disk drive device, a communication device, and the like. As a result of the cooperation between the hardware resource and the software resource (OS, application, etc.), the information processing apparatus 10 uses the word index 2 created from the electronic document group stored in advance as in the conventional example, and the search condition. A search condition input 4 for receiving (search term), an index reference unit 7 for creating a search result by referring to the word index 2 with a character string (query) of the search condition, and a search result output unit 5 for outputting the search result have.

  Here, the index reference unit 7 includes a proximity search means 6 for checking whether or not each word constituting the search condition is adjacent between the transposed lists of the word index 2, and the proximity number of each word, that is, a compound word. And the proximity frequency predicting means 11 for predicting the appearance frequency of the search condition composed of

  If the proximity search means 6 can check the proximity state, that is, the connection of position information at least once by checking from the appearance position of an arbitrary word, the proximity frequency predicting means 11 can check the number of checks for the number of occurrences of the word. Assuming that compound words exist at a rate, the number of adjacent words is predicted.

  It is assumed that the word index 2 is constructed in the hard disk drive device, and the hard disk drive device stores an accumulated document for creating the word index. The input / output unit 4.5 is realized through the communication device, and is connected to a user terminal (not shown) such as a personal computer or a mobile phone so as to be communicable via the Internet.

<< Basic Processing of Index Reference Unit 7 >>
Hereinafter, the processing of the index reference unit 7 incorporating the proximity frequency predicting means 11 will be described with reference to FIG. Here, the search condition input unit 4 accepts a search condition (search term) transmitted from the user terminal, and the index reference unit 7 has the search condition character string (query) transferred from the search condition input unit 4 as described above. Assume that a search result of an electronic document including the character string is created with reference to the word index 2. At this time, search results are ranked using the appearance frequency of the character string as an index, and are returned to the user terminal through the search result output unit 5. The search condition is a compound word or a phrase, and the structure of the word index 2 will be described using the example of the transposed list in FIG.

  S101 to S106: Here, the index reference unit 7 basically performs the same processing as S001 to S006 of the conventional example. In brief, first, the character string of the search condition transferred from the search condition input unit 4 is divided into words (S101). For example, when a character string “Tokyo” is a search condition, it is divided into words “Tokyo” and “Tokyo”. For this division, morphological analysis such as “Mecab” of Non-Patent Document 1 is used.

  Next, as a result of the morphological analysis, it is determined whether or not the character string of the search condition is composed of a plurality of words (S102). For example, if the search condition is “Tokyo”, the search condition is made up of a single word, so that the search is performed using the conventional technique (S103). Specifically, the transposed list of the search condition “Tokyo” is acquired from the word index 2, a search result is created, and the search process is terminated.

  On the other hand, when the search condition is composed of a plurality of morphemes as in “Tokyo”, the transposed list corresponding to each word is acquired from the word index 2 (S104). Thereafter, the obtained transposition list is referred to, and the document ID having the smallest number among the document IDs of the electronic documents appearing in all the transposition lists is obtained (S105). According to the transposed list example of FIG. 7, the document ID “1” corresponds to the smallest number among the electronic documents in which the words “Tokyo” and “City” appear.

  At this time, it is checked whether or not there is a document ID that matches the process of S105 (S106). If there is no document ID, the process ends. On the other hand, in the previous search example of “Tokyo”, the document ID “1” matches the process of S105, so the process proceeds to S107. The intermediate data such as the word arrangement list and the document ID is stored in the memory and processed.

  S107 to S109: The index reference unit 7 sets an initial value “1” to the reference number i for predicting the appearance frequency (S107). After this setting, S008. Processing similar to S009 is performed. That is, the top position information is acquired in the document ID whose existence has been confirmed in S106 (S108). According to the transposed list example of FIG. 7, in the document ID “1”, the head position information for “Tokyo” is indicated as “1”.

  Next, the proximity search means 6 checks whether or not the position information acquired in S108 appears next to another transposition list, that is, whether or not there is a connection (S109). To explain based on the transposed list of FIG. 7, the transposed list in which the word “city” appears in the position information “2” of the document ID “1” is checked (confirmed).

  Since the position information “2” does not appear here, the process proceeds to S110 and subsequent steps. If, as a result of the check, it appears in another transposed list, the process proceeds to S112 and subsequent steps. Note that the position information and the reference number i are also stored in the memory and processed.

  S110: If the appearance of desired position information is not confirmed as a result of the check in S109, the index reference unit 7 adds “1” to the reference number i, and updates the stored information in the memory to obtain the next position information. To get. According to the transposition list of FIG. 7, since the position information “5” for “Tokyo” exists after the position information “1”, the position information “5” is acquired. The position information “5” acquired here is stored in the memory, and the process proceeds to S111.

  S111: The index reference unit 7 checks whether or not the position information acquired and stored in S110 is the end of the electronic document. If the position information is the end, the process returns to S105. Repeat the process.

  In the transposed list of FIG. 7, since the position information “5” stored (set) in the memory is not the end of the electronic document with the document ID “1”, the process proceeds to S109. At this time, in the process of S109, it is checked (confirmed) whether or not the position information “6” appears in the transposition list of “Miyako”. Here, since the position information “6” exists in the document ID “1” of “Me”, the connection of the position information can be confirmed, and the process proceeds to S112.

  S112: The proximity predicting means 11 predicts the number of proximity of each word constituting the search condition, that is, the appearance frequency of the compound word. At this time, the proximity prediction unit 11 calculates a predicted value of the appearance frequency using the storage information of the memory, that is, the reference number “i” and the information of the transposed list (appearance frequency of each word). For this calculation, for example, the following equation (1) is used. This expression (1) is defined in the program.

Here, “tf (q)” indicates the appearance frequency of the word “q _min ” having the smallest “tf” among the words constituting the compound word. In the example of the transposition list of FIG. 7, since the appearance frequencies of “Tokyo” and “Miyako” are equal, the appearance frequency (q _min ) is calculated as “4”. The reference number indicates the reference number i in the flow of FIG. In the example of the transposed list in FIG. 7, since “1” is added to the initial value in S110, the reference number i = “2” is established, and “tf (Tokyo) _estimate = _4/2 = 2 (predicted value) ) ".

  S113: The proximity prediction unit 11 adds the document ID “1” and the predicted value (“2” in the transposition example in FIG. 7) with the document ID to the search result. Thereafter, returning to the process of S105, the same process is performed for all the transposed lists. That is, the processing after S105 is sequentially performed after the document ID “2”, and the processing is terminated when there is no corresponding document ID in S105 (S106).

  Thus, in general, in the case of a search condition composed of a plurality of words (compound words, phrases, etc.), the number of appearances must refer to all position information, but the index incorporating the proximity predicting means 11 According to the reference unit 7, since the appearance frequency is predicted using the number of references and transposition list information (such as the appearance frequency of each word) in S112, a search result is created without referring to all position information. it can.

  Referring to FIG. 7 in detail, in the case of the information processing apparatus 1, the appearance frequency for the transposed list of “Tokyo” must be obtained by referring to all the position information (1, 5, 65, 69). On the other hand, the information processing apparatus 10 has only to refer to the position information (1, 5) because the proximity predicting means 11 is incorporated in the index reference unit 7, thereby reducing the amount of calculation. . In this respect, the processing efficiency is improved, which contributes to speeding up of the search process. Further, since the calculation amount is reduced, the calculation cost is also suppressed.

<< Other processing example (1) >>
The basic processing example (S101~S113), the reference number i although counts only the first word q _1, as shown in FIG. 3, the actual reference number i is present in each word. In the processing based on the transposed list example of FIG. 7, the number of references in formula (1) considers the number of references i only for the word “Tokyo”, but the number of references for all words constituting a compound word or phrase is calculated. It may be used to predict the appearance frequency. In this case, in S112, the predicted value is calculated using the following equation (2). This equation (2) is also defined in the program.

  Here, | Q | indicates the number of words constituting the character string Q, and the reference number (q) indicates the reference number of each word. Thus, the appearance frequency of a compound word or a phrase can be predicted for each word, and the average value can be used as a predicted value.

<< Other processing example (2) >>
In the basic processing example (S101 to S113), the appearance frequency is predicted at the position where each word constituting the compound word is first adjacent (S109.S112), but the frequency is predicted from a plurality of appearances. May be. In this case, as shown in FIG. 4, it is confirmed that the position information of the document ID “1” is connected once at the stage of “5”, but the cursor is moved to the next connection position “65”. To proceed with the process.

  FIG. 5 shows a processing flow that uses a plurality of connection numbers, that is, K connection numbers. S201 to S206 perform the same processes as S101 to S106. In S207, the proximity predicting means 11 is different from the basic processing example in that the connection number “k = 0 (initial value)” is set and the threshold value K is set. The threshold value K set here may be an integer and set in the program.

  In subsequent S208 to S211, the same processing as in S108 to S111 is performed. In S212, if the connection of position information can be confirmed in S209, if the connection number k is smaller than the threshold value K, the connection of the next position information is performed. Let me check. That is, “1” is added to the concatenation number k in S213, and the processing from S209 onward is repeated. At this time, if the connection number k exceeds the threshold value K in S212, S214. The process of S215, that is, S112. Processing similar to S113 is performed. It is assumed that the connection number k is stored in the memory and the processing from S207 is executed.

  Since the threshold value K is set in this way, a search result can be created without referring to all position information. At this time, since the appearance frequency is predicted using the number of consecutive connections, the certainty of prediction is also improved.

≪Programs≫
The present invention can also be configured as a program that causes a computer to function as a part or all of the means 2.4 to 7.11 of the information search apparatus 10. According to this program, S101 to S113. Cause the computer to execute all or some of steps S201 to S213.

  The program can be provided through a network such as a website or e-mail. The program is recorded on a recording medium such as a CD-ROM, DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, MO, HDD, Blu-ray Disk (registered trademark). It is also possible to save and distribute. This recording medium is read using a recording medium driving device, and the program code itself realizes the processing of the above embodiment, so that the recording medium also constitutes the present invention.

2 ... Word index 4 ... Search condition input part 5 ... Search result output part 6 ... Proximity search means 7 ... Index reference part (index reference means)
DESCRIPTION OF SYMBOLS 10 ... Information retrieval apparatus 11 ... Proximity number prediction means

Claims (7)

An information search method for searching an electronic document including a character string of a search condition and obtaining an appearance frequency of the character string to add to the search result,
A first step in which an index reference means obtains the search result by referring to a word index created from an electronic document stored in advance;
A proximity number predicting means predicting the proximity number of each word constituting the character string and obtaining the appearance frequency;
A method for retrieving information, comprising: The first step includes obtaining a list of document ID, appearance frequency, and appearance position group from the word index according to each word constituting the character string;
Sequentially referring to position information groups of other words until position information of arbitrary words constituting the character string is connected to position information of other words,
2. The information search method according to claim 1, wherein the second step predicts the proximity number from the appearance frequency of the arbitrary word and the number of times of reference if the connection of the two pieces of position information is confirmed. . The first step includes obtaining a list of document ID, appearance frequency, and appearance position group from the word index according to each word constituting the character string;
Sequentially referencing the position information group of other words until the number of concatenations with the position information of other words in the position information of any word constituting the character string reaches a threshold number of times,
The second step predicts the proximity number from the appearance frequency of the arbitrary word and the reference frequency when the number of concatenations of the position information reaches the threshold number of times <BR>
The information search method according to claim 1, wherein: An information search device that searches an electronic document including a character string of a search condition and obtains an appearance frequency of the character string to add to the search result,
A word index created from an electronic document stored in advance, and an index reference means for creating the search result by referring to the word index,
The information search apparatus according to claim 1, wherein the index reference means is provided with a proximity number predicting means for predicting the proximity number of each word constituting the character string and determining the appearance frequency. The index reference means acquires a list of document ID, appearance frequency, appearance position from the word index according to each word constituting the character string,
Sequentially refer to the position information group of the other word until the position information of the arbitrary word constituting the character string is connected to the position information of the other word,
The information search according to claim 4, wherein the proximity number predicting unit predicts the proximity number from the appearance frequency of the arbitrary word and the number of times of reference when the connection of the both pieces of position information is confirmed. apparatus. The index reference means acquires a list of document ID, appearance frequency, appearance position from the word index according to each word constituting the character string,
Sequentially refer to the position information group of the other word until the number of concatenations with the position information of the other word in the position information of an arbitrary word constituting the character string reaches a threshold number of times,
5. The proximity number predicting unit predicts the proximity number from the appearance frequency of the arbitrary word and the number of times of reference when the number of concatenations of the both pieces of position information reaches the threshold number of times. The information retrieval device described.   The program for functioning a computer as an information search device of any one of Claims 4-6.

Images