JP5207721B2 - Inverted index creation device and forward index creation device - Google Patents

Description

  The present invention relates to a search index creation method for performing a full-text search of a document for a large document set, and more particularly to an apparatus for creating a transposed index and a forward index for a large document set.

  In today's society, an enormous amount of electronic documents are created every day, and the amount continues to increase. In offices, electronic documents are indispensable for document creation and presentation, and the expansion of the Internet is a factor in generating an explosive number of electronic documents. Along with the increase in the amount of electronic documents, a document retrieval technique capable of retrieving and outputting a document in which necessary information is recorded from a large number of enormous documents in a short time is indispensable, and technological development is progressing.

  A typical style of document retrieval is to output a document including a specified word from a given document set in as short a time as possible. For this purpose, a data structure called an inverted index is used. FIG. 1 is a schematic diagram of a document set 101 to be searched and a transposed index 102 constructed based on the set. A list including document identification numbers 105 of all documents in which a certain word 103 appears is called a transposed list 106.

  Unlike languages in which words such as English, French and Spanish are separated by spaces, it is difficult to accurately divide a document into words in Japanese, Korean and Chinese. Therefore, there are cases where an inverted index is constructed using an arbitrary partial character string in a document consisting of n consecutive characters called n-gram instead of a word, and it is known that it is practically useful ( Information retrieval algorithm, Kenji Kita et al., Kyoritsu Publishing). n is an integer of 1 to 10 mainly. In this specification, a word or a partial character string of length n used for creating an inverted index is referred to as an index word.

  In document retrieval, a data structure called a forward index 201 shown in FIG. 2 may be used in addition to the inverted index. The forward index 201 stores, for each document 104 in the search target document set 101, a list of index word identification numbers 202 of index words 103 included in the document. The index word identification number 202 here is the same number for the same index word, and is a number given differently for different index words. The forward index 201 is used as intermediate data for creating the transposed index 102, and a technique called associative search for searching similar documents (Yasuda, Imaichi, Iwayama, Niwa, Information Processing Society of Japan 69th National Convention, 3D- 1, 2007).

  While the amount of document data to be searched increases explosively, computer resources for constructing a search system are limited. In particular, the computer's memory (main storage device) is capable of high-speed random access, and is essential as a work area for holding a list of known index words and an expandable list of each index word when building an index. Capacity memory is expensive. Therefore, a technique for building a huge index with a small amount of memory is required.

  As a technique for constructing a huge inverted index exceeding the capacity of the memory, there are a method using sorting (Non-Patent Document 1) and a method using a partial inverted index in which an inverted list is recorded in the dictionary order of index words (Non-Patent Document 2). Are known. In the technique of Non-Patent Document 1, a search target document is sequentially read, and a tuple composed of three elements of an index word identification number, a document identification number, and a frequency of the index word in the document is accumulated. A set of these tuples is divided into division units that can be stored in the memory, and sorted by index word identification number for each division unit. Finally, reading each division unit from the top at the same time, collecting tuples with the same index word identification number and creating a transposed list of the index words is repeated for all index words to construct an inverted index. . However, in order to give an index word identification number to the index word by the technique of Non-Patent Document 1, if the character strings of all index words processed so far are not stored in the computer memory, realistic processing performance can be obtained. I can't expect it. Therefore, the method of Non-Patent Document 1 cannot be practically processed when the number of index words is very large. If a pair consisting only of an index word identification number and a document identification number is used in place of the tuple, only the document identification number is recorded in the transposition list 106 as shown in FIG. Can be created. On the other hand, the method of Non-Patent Document 2 builds a transposed index on-memory, and when the limit of the memory capacity is reached, the index word character string 103 and its index word string 103 and all the index words stored in the memory at that time in dictionary order. The index word transposition list 106 is output to the partial transposition index 301 on the auxiliary storage device (FIG. 3). This is repeated until the information of the entire document set 101 is written in the partial transposition index 301 on the auxiliary storage device. After that, each partial transposed index 301 is read simultaneously from the beginning, the transposed list of the index word is read from the partial transposed index where the same index word appears, and is integrated into one transposed list and output to the final transposed index 102 (FIG. 4). In this way, it is possible to construct a huge transposed index that exceeds the memory capacity of the computer.

  On the other hand, regarding the forward index, there is no known technique for creating a huge forward index that reflects the entire large-scale search target document.

A. Moffat & J. Zobel, In situ generation of compressed inverted files, J. American Society of Information Science 46 (7): 537-550, 1995. S. Heinz & J. Zobel, Efficient Single-pass index construction for text databases, J. American Society of Information Science and Technology 54 (8): 713-729, 2003.

  The technology of Non-Patent Document 2 enables the construction of a huge transposed index that far exceeds the capacity of the actual installed memory, but the hash table of index words for search (Algorithm Introduction Volume 1, T. Colmen et al., Tetsuo Asano et al. It is preferable to create a hash table separately. By using a hash table, it is possible to efficiently search for data related to a specific index word from among a set of index words that may be in the number of millions. In order to use the hash table, a function h (s) for converting an arbitrary index word character string s into an integer value is prepared. If the size of the hash table is M, h (s) is prepared with an integer value in the range of 0 ≦ h (s) <M. When data related to the index word s is stored, it is stored in the entry pointed to by h (s) in the hash table. In this way, given the string s, just looking at the entry pointed to by h (s) can tell whether s exists as an index word, and if s is an index word, access the associated data structure. it can.

  In a large document set, even an index word string alone may exceed the main memory, and in such a case, a hash table must be created efficiently. Further, according to the technique of Non-Patent Document 2, when a partial transposed index is output, the index words are sorted in the dictionary order, so that extra calculation time and work memory are required.

  On the other hand, when building a huge forward index, the index word identification number of all index words is not fixed until the last document is processed, so the index word identification number is unknown when creating a partial forward index. There is a problem. If index word identification numbers are given in the order in which the index words appear, the index word identification numbers can be determined at any point in time, but this method does not require that all index word strings be stored in memory. It cannot be processed at a speed sufficient for practical use. Therefore, when creating a partial forward index 501 from a part of a document group, a temporary index word identification number 502 is assigned and converted to a final index word identification number 202 when integrated into the entire forward index 201. (Figure 5). Therefore, a temporary index word that can be calculated from only the document group used when creating the specific partial forward index 501 and can be efficiently converted to the final index word identification number 202 without using a large-scale memory. A method of giving the identification number 502 is required.

  An object of the present invention is to extend the technique of Non-Patent Document 2 and provide a temporary index word identification number assigning method to solve the above problem.

  In the method of Non-Patent Document 2, an inverted list is output in the dictionary order of index words when creating a partially inverted index. In the present invention, an inverted list of index words is output in the following order.

1. For index terms with different hash values, those with smaller hash values are output first.
2. Index words with the same hash value are output first in dictionary order.
Hereinafter, this order is referred to as a hash-lex order.

  By using the hash-lex order, the above-mentioned problems related to the construction of the inverted index can be solved. First, sorting of all index words stored in the memory becomes unnecessary. Instead, it is only necessary to scan the hash table and sort the index terms that conflict in each entry of the table in lexicographic order. Since the number of index words that collide on the hash table is usually much smaller than the number of all index words, the cost of the sort is small. In addition, since the index words are recorded in the partial inverted index in the order of the hash table, if the hash value is stored together with the index word or the hash value is recalculated when integrating the partial inverted index, the hash table is stored in the auxiliary memory. It can be created by sequential addition to the file on the device. In addition, instead of dictionary order, all other types of order defined between index terms, such as reverse order of dictionary order (Algorithm Introduction Volume 1, T. Colmen et al., Tetsuo Asano et al., Modern Science Co., Ltd.) May be used.

  In the present invention, a hash-lex order number is also used as a temporary index word identification number when creating a partial forward index. First, a method for giving a temporary index word identification number in hash-lex order when creating a partial forward index will be described. First, an on-memory transposed index and an on-memory forward index are created while giving an index word identification number in the order of appearance to the index word. After creating the partial inverted index by the partial inverted index writing means, erase the on-memory inverted index to secure free memory, and the index word identification number and hash-lex assigned when creating the on-memory forward index Construct a conversion table with sequential index word identification numbers. Using this conversion table, the on-memory forward index is written into the partial forward index while converting the index word identification number into a temporary index word identification number.

  Next, a method of converting a temporary index word identification number in the hash-lex order into a final index word identification number will be described. The final index word identification number is a number given to all index words in the order of hash-lex. In this way, when integrating the transposed index appearing in the document, the correspondence between the index word identification number in each partial forward index of each index word and the final index word identification number can be calculated sequentially. This is because, when compared with the final index word identification number, the temporary index word identification number is packed with index word numbers that do not appear in the partial forward index. This is because the correspondence between these two types of index word identification numbers can be found by checking the number of index words that have appeared and the total number of index words. This correspondence is output as a correspondence table of temporary index word identification numbers and final index word identification numbers for each partial forward index. If the temporary index word identification number is converted using the correspondence table while sequentially adding the partial forward index to the final forward index in the order of creation, the forward index for the entire given document set can be obtained.

  The hash-lex order of the present invention is a sort-merge join method (P. Mishra and MHEich, Join processing in relational databases, ACM Computing Surveys, 24 (1 ): 63-113, 1992) can be used to sort the two relations before the join. If the number of elements in each relationship is N and M, the normal comparison sort takes an average time proportional to NlogN + MlogM, while the hash-lex order sort using a hash table is a join attribute As long as there is no large-scale collision of hash values with respect to, it is possible in a time proportional to N + M, so the computational complexity order of the join operation is improved.

  According to the present invention, when constructing a huge inverted index that does not fit in the memory (main storage device) of the computer, it is possible to simultaneously create a hash table used for searching. In addition, it is not necessary to sort index words for each partial inverted index, which is necessary in the prior art. In addition, a huge forward index exceeding the memory capacity can be constructed.

  An embodiment of an apparatus for creating an inverted index and a forward index by the method of the present invention will be described. An overview of the entire apparatus is shown in FIG. A central processing unit (CPU) 601 is connected to a memory (main storage device) 602, an auxiliary storage device 603 such as a hard disk, and a network 604 and a user terminal 605 are connected. The apparatus according to the present embodiment includes an on-memory transposed index creating unit S709, an on-memory forward index creating unit S710, an index word segmenting unit S701, an index word identification number assigning unit S702, as programs on the memory 602 executed by the CPU 601. Document identification number assigning means S703, partial inverted index writing means S704, partial forward index writing means S705, partial inverted index integrating means S706, and partial forward index integrating means S707 are provided. The auxiliary storage device 603 stores an input document set 101, a partial inverted index 301, a partial forward index 501, a finally created inverted index 102, a forward index 201, and a hash table 1002 of all index words. The data stored in the auxiliary storage device 603 may be stored in a storage on the network 604. In the following, for the sake of simplicity, it is assumed that these data are stored in the auxiliary storage device 603.

  FIG. 7 shows the flow of data and processing in this apparatus. The flow of processing for constructing the transposed index 102 and the forward index 201 is summarized in FIGS. 8 and 11, respectively.

  First, the CPU 601 acquires the search target documents 104 in the search target document set 101 one by one from the auxiliary storage device 603 as input. The following processing is performed on each search target document 104. First, an index word in the document is cut out by the index word cut-out means S701. As described above, a known morpheme analysis method or n-gram can be used as the extraction means (information search algorithm, Kitakenji et al., Kyoritsu Shuppan). Further, for each index word, an index word number for constructing the on-memory forward index 607 is acquired by the index word identification number assigning means S702. The preferred embodiment of the index word identification number assigning means S702 registers an index word in the hash table, gives 1 to the first index word, and every time an unknown index word that does not exist in the hash table appears, Is assigned a number that is one greater than the largest number assigned to. Further, the document identification number assigning unit S703 assigns a document identification number for each search target document. One preferred embodiment of this means keeps one integer variable initialized to 1, assigning the value of this variable when a new document identification number is needed, and immediately following that variable's value of 1 It is to increase. Through these processes, one search target document 104 is converted into a set 708 of index word identification numbers for the on-memory forward index 607 associated with one document identification number 105.

  Then, the on-memory transposed index creating means S709 adds the document identification number 105 to the transposed list of each index word appearing in the search target document 104 in the on-memory transposed index 606, and makes the search target document 104 Reflected in the on-memory transposed index 606. Similarly, the on-memory forward index creating means S710 adds a list constructed from the index word number set 708 to the on-memory forward index 607 in association with the document identification number 105. At this time, when the memory consumption exceeds a predetermined capacity threshold, the on-memory inverted index 606 is written as the partial inverted index 301 to the auxiliary storage device 603 by the partial inverted index writing means S704, and the on-memory forward index 607 is written. Is also written as the partial forward index 501 by the partial forward index writing means S705.

  As shown in FIGS. 8 and 9, the partial inverted index writing means S704 reads the hash table used to create the on-memory inverted index 606 from the top, and searches for a non-empty unprocessed entry. When such an entry is found, the index word character string, hash value, and transposed list are output to the partial transposed index 301 on the auxiliary storage device in the order of the dictionary for the index word corresponding to the entry. This process is repeated for all index words stored in the on-memory transposed index 606.

  Further, the on-memory forward index 607 is written as the partial forward index 501 by the partial forward index writing means S705 (FIG. 12). After erasing unnecessary on-memory inverted index 606 to secure free memory, the index word identification number used to create on-memory forward index 607 and temporary index word identification in hash-lex order A conversion table with the number 502 is created. For this purpose, a table with a size corresponding to the number of index words is secured in memory, the hash table of on-memory index words is accessed in order from the top, and a temporary index in hash-lex order is found for the found index words. While assigning the word number, the index word identification number in the on-memory forward index of each index word may be written in the entry of the conversion table indicated by the assigned hash-lex order number. Using this conversion table, the on-memory forward index 607 is output to the partial forward index 501 on the auxiliary storage device while converting the index word identification number to the hash-lex order number 502.

  When the information of all the search target documents is converted into the partial inverted index 301 and the partial forward index 501, the inverted index 102 and the forward index 201 corresponding to the entire search target document set 101 are obtained by integrating them by the following method. To construct.

  First, the entire transposed index 102 is constructed from the partial transposed index 301 by the partial transposed index integration means S706. The method will be described with reference to FIGS. First, the partial inverted index integration unit S706 identifies the first index word 1001 in the hash-lex order among the first index words of the unprocessed portions of all the partial inverted indexes 301. This process can be performed by scanning all partial transposed indexes, and can be completed within a time proportional to N, where N is the number of all partial transposed indexes. However, a more preferred embodiment is a priority queue using each partial inverted index as an element and the first index word of the partial inverted index as a key (Algorithm Introduction Vol. 1, T. Colmen et al., Tetsuo Asano et al., Modern Science). To get the first element of the priority queue. By using the priority queue, when processing of one index word is completed, the process of identifying the index word to be processed next can be completed within a time proportional to logN.

  When the earliest index word 1001 in the hash-lex order (“cat” in the example shown in FIG. 10) is identified from the unprocessed index words, the index word 1001 is newly created on the auxiliary storage device 603 first. Add to hash table 1002 for all index words. In this preferred embodiment, as shown in FIG. 15, the contents recorded in the hash table and the hash table are set as separate files, and when a new hash value index word appears, a new entry is added to the hash table file 1501. In addition, the tail position in the hash table contents file 1502 is recorded, and information such as the index word identification number 202 of the index word and the position of the inverted list 106 in the inverted index 102 is recorded in the hash table contents file 1502. It is to be. If the hash value is not continuous with the hash value processed immediately before, the entry corresponding to the hash value for which no corresponding index word exists in the file 1501 is filled with data indicating that the entry is empty. . In the embodiment shown in FIG. 15, the index word character string itself and the index word identification number are written, and the index word identification number can be acquired from the index word character string. Since the index words are stored in the partial transposed index 301 in the hash-lex order, it is guaranteed that a correct hash table can be constructed by sequentially adding index words to the files 1501 and 1502.

  Further, the partial inverted index integration means S706 further reads out and integrates the inverted list corresponding to the index word 1001 from each partial inverted index 301. For example, in FIG. 10, two transposed lists corresponding to “cat” are integrated to create one transposed list. At this time, the document identification numbers 1003 of the transposed lists are compared, and the document identification numbers with the smallest numbers are extracted in order. The priority queue can also be used in the process of selecting the minimum document identification number. The elements of the priority queue may be the transposition list of the partial transposition index 301, and the key may be the unprocessed head document number. However, if the document identification number is assigned so that the document number identification number of the partial inverted index created earlier is smaller, the order of partial inverted index 301 is created without using the priority queue. It is only necessary to concatenate the transposed list in each partial transposed index in the order in which the partial transposed index was created. By this integration process, a transposed list 106 including document identification numbers of all documents in which the index word 1001 appears is obtained. This transposed list 106 is added to the end of the transposed index 102 being created. For all index words, a desired inverted index is obtained by sequentially adding the inverted list 106 to the inverted index 102 being created.

  The partial inverted index integration means S706 also creates a correspondence table 1303 from the temporary index word identification number 502 to the final index word identification number 202, which is used to integrate the partial forward index 501 into the final forward index. . As shown in FIG. 13, when the index word 1001 to be processed is selected from the partial inverted index, the total number 1301 of index words including the index word 1001 that has been processed so far, and the partial inverted indexes. The number of index words 1302 including the processed index word 1001 is recorded. This is possible with a small amount of memory that only records a number of integers approximately equal to the number of partially inverted indexes. If the final index word identification number is given in the hash-lex order, the total number 1301 of processed index words is equal to the final index word identification number 202 of the index word 1001, and each partial transposed index 301 including this index word is assigned to each partial inverted index 301. The number of index words processed is equal to the temporary index word identification number 502 of the index word 1001. Therefore, by outputting a pair of the total index word number 1301 and the index word number 1302 of the partial inverted index, the temporary index word identification number 502 of the partial forward index created together with the partial inverted index is obtained as the final index word identification number. A correspondence table 1303 used for conversion to 202 can be constructed.

  Finally, the partial forward indexes are integrated and converted into a final forward index. As shown in FIGS. 11 and 14, the partial forward index integration unit S707 sequentially adds the partial forward index 501 to the final forward index 201 in the order of creation. At the time of additional writing, the temporary index word identification number 502 is converted into the final index word identification number 202 using the correspondence table 1303 constructed by the partial transposed index integration means S706.

  There may be various variations in the huge inverted index and forward index construction method of the present invention. For example, although the temporary index word number in the hash-lex order is recorded in the partial forward index, the following method is also possible. In other words, the numbers in the order of appearance used in the on-memory forward index 607 are recorded as they are, and the numbers in the order of appearance of each index word are added when the partial transposed index writing means S704 creates the partial transposed index 301. Then, when creating the conversion table 1303, instead of the number of processed index words 1302 in each partial inverted index, the numbers in the order of appearance recorded in the partial inverted index are processed including the index word 1001 being processed. Output together with the total number of index words 1301. Thus, a correspondence table for converting the index word number written in the partial forward index into the final index word number is obtained. On the other hand, if only the transposed index 102 is necessary and the forward index 201 is not necessary, the execution of the on-memory forward index creating means S710, the partial forward index writing means S705, and the partial forward index integrating means S707 can be omitted. Further, in this specification, the transposed index 102 composed of a transposed list composed of a list of only document identification numbers and the forward index 201 composed of a list of only index word identification numbers have been described. The number of times it appears in the document 104 and the position at which each index word 103 appears in the search target document 104 may be added to the index.

  An experiment was implemented in which the method of the present invention was implemented and a huge transposed index was created with a small amount of memory. The subject of processing was text data of about 1.07 million published patent gazettes from 2003 to 2005, and the total amount was 28.2 GB. As index words, morphemes obtained with free software chasen were used. The computer used is a PC with Intel Core2 Duo E6600 CPU with 4GB of memory, 250GB of HDD and Linux for the OS. Each time the memory usage exceeds 60 MB, the on-memory transposed index 606 is output to the partial transposed index 301. As a result, 74 partial inverted indexes were created, and by combining them, a 1.30 GB inverted index was finally created. Since the peak memory usage was 63.1MB, we were able to build an inverted index with a hash table about 21 times larger than the memory usage.

  Moreover, the processing time of this technique and the technique of a nonpatent literature 2 was measured and compared. As a result of measuring 10 times and taking the average, this technology averaged 1154 seconds, and the technology of Non-Patent Document 2 averaged 1183 seconds. From this result, it was found that this technology can not only create a hash table in addition to the inverted index but also improve the processing time slightly.

  On the other hand, a transposed index and a forward index were created simultaneously using the same data under the same computer conditions. While creating an on-memory index, every time the memory usage exceeds 60 MB, the on-memory inverted index and forward index are written as partial inverted indexes and partial forward indexes to the auxiliary storage device as appropriate, for a total of 159 partial indexes. Was generated. The total size of the index created by integrating them was 3.24 GB in total for the inverted index and the forward index. Since the memory usage at the peak time was 61.1MB, it was confirmed that a search index with a size more than 50 times the memory usage could be created.

  The present invention is a technique for constructing a huge inverted index and forward index exceeding the memory capacity of a computer for a large document set. When outputting a partial inverted index, not only can a hash table used for searching be generated, but the processing speed is equal to or better than that of the prior art.

FIG. 3 is a schematic diagram of a document set to be searched and a transposed index constructed based on the set. Schematic diagram of a set of documents to be searched and a forward index constructed based on the set. Explanatory drawing of the step which produces the partial transposition index in the conventional method. Explanatory drawing of the step which integrates a partial transposition index and produces a final transposition index in the conventional method. Explanatory drawing of the subject at the time of making a huge forward index from a large-scale document collection. Schematic which shows one form of the apparatus which implements this invention. 1 is a schematic diagram of a data and processing flow in an embodiment of an apparatus implementing the present invention. The flowchart showing one form of the transposition index construction process by this invention. Explanatory drawing of the partial transposition index writing means in the method of this invention. Explanatory drawing of the partial transposition index integration means in the method of this invention. The flowchart showing one form of the forward index construction process by this invention. Explanatory drawing of a partial forward index writing means. Explanatory drawing of the step which produces a corresponding table in a partial transposed index integration means, in order to convert the temporary index word identification number stored in the partial forward index into a final index word identification number. Explanatory drawing of a partial forward index integration means. Explanatory drawing of the hash table construction process in the method of this invention.

Explanation of symbols

101: Set of search target documents
102: Inverted index
103: Index terms
104: Search target document
105: Document identification number
106: Transpose list
201: Forward index
202: Index word identification number in the forward index corresponding to the set of all documents
301: Partially inverted index
501: Partial forward index
502: Temporary index word identification number in partial forward index
601: Central processing unit (CPU)
602: Memory (main storage device)
603: Auxiliary storage device
604: Network
605: User terminal
606: On-memory transposed index
607: On-memory forward index
708: Set of index word numbers for on-memory forward index of index words contained in a search target document
1001: Examples of index terms that are processed in the partial inverted index integration means
1002: Hash table containing all index words of search target document set
1003: Document identification number in the inverted list to be processed in the partial inverted index integration means
1301: Number of all index words processed so far, including index words currently being processed in partial inverted index integration means
1302: Number of index words in the corresponding partially inverted index that have been processed so far, including index words being processed in the partial inverted index integration means
1303: Correspondence table for converting temporary index word identification number in partial forward index to final index word identification number in partial forward index integration means

Claims (6)

Main storage,
An auxiliary storage device;
Index word cutout means for cutting out, as an index word, either a word or a character string consisting of a plurality of consecutive characters from individual documents in a document set including a plurality of documents;
Document identification number assigning means for assigning a different document identification number to each document in the document set;
A hash table for index words appearing in the document group is created for a part of the document group in the sentence set, and a document including each index word is stored on the main storage device using the hash table. Means for constructing an on-memory inverted index consisting of an inverted list that is a list of document identification numbers;
A partial transposed index writing means for writing the on-memory transposed index into the auxiliary storage device as a partial transposed index;
Partial inverted index integration means for integrating a plurality of partial inverted indexes stored in the auxiliary storage device into one inverted index;
The partial inverted index writing means writes a partial inverted index storing the inverted list of each index word in the order of the hash value of the index word to the auxiliary storage device, and when there are a plurality of index words having the same hash value, Storing the transposed list of index words in the partial transposed index according to the total order between the index words given in advance,
The partial inverted index integration means integrates the inverted list of each index word in the plurality of partial inverted indexes in the order of hash values of index words, and creates an inverted index for all index words. Indexing device. 2. The inverted index creating apparatus according to claim 1 , wherein the dictionary order of index words is used as the entire order.   The hash table of all index words according to claim 1, wherein when the partial inverted index is integrated into the inverted index for all index words, the index words that appear are sequentially added in the order of hash values. Generating an inverted index generating apparatus. Main storage,
An auxiliary storage device;
Index word cutout means for cutting out, as an index word, either a word or a character string consisting of a plurality of consecutive characters from individual documents in a document set including a plurality of documents;
Document identification number assigning means for assigning a different document identification number to each document in the document set;
For some document groups in the sentence set, a hash table for index words appearing in the document group is created, and an index word identification number is assigned to each index word in the order of appearance, on the main storage device. Means for constructing an on-memory forward index comprising a list of document identification numbers of the document group and index word identification numbers appearing in the document of the document identification number;
A partial forward index writing means for writing the on-memory forward index to the auxiliary storage device as a partial forward index;
Partial forward index integration means for integrating a plurality of partial forward indexes stored in the auxiliary storage device into one forward index;
The partial forward index writing means converts the index word identification number in the partial forward index into a temporary index word identification number in the order of hash values stored in the hash table and writes it to the auxiliary storage device,
The partial forward index integration means is a conversion table for converting individual temporary index word identification numbers used in a plurality of partial forward indexes into index word identification numbers in the order of hash values in the forward index of all document sets. And converting the index word identification number in the partial forward index into the index word identification number in the forward index of the whole document set using the conversion table. 5. The forward index creation device according to claim 4, wherein when there are a plurality of index words having the same hash value, the index word identification numbers of those index words are assigned to a total order between index words given in advance (total order). The forward index creation device is characterized in that it is determined according to 6. The forward index creation device according to claim 5 , wherein the dictionary order of index words is used as the total order.

Images