Document retrieval system and retrieval method

A document retrieval system includes a storage device and a retrieval server. The storage device stores document data including documents compressed so as to correspond to a plurality of divided document groups, indexes indicating correspondence relations between partial character strings for retrieving the documents and first identifiers indicating the documents, and a first correspondence table in which the document groups are divided into document small groups, and second identifiers which indicate the document small groups correspond to the partial character strings. The retrieval server retrieves, in response to an input of a retrieval character string, a second identifier corresponding to a partial character string included in the retrieval character string, from the first correspondence table, decompresses document data in a document group, retrieves a first identifier corresponding to the partial character string, obtains document data corresponding to the retrieved first identifier, and outputs the retrieved first identifier.

TECHNICAL FIELD

The present invention relates to a document retrieval system and a retrieval method for large-capacity document data.

BACKGROUND ART

As the capacity of document data increases, a demand for a document retrieval system for large-capacity document data increases. In order to respond to the increase in the capacity of document data, a retrieval device that divides document data into units suitable for a character string retrieval, sets a character string retrieval index in each unit, narrows down a retrieval target in divided document data units based on a retrieval condition, and retrieves an index in the narrowed document data using a character string included in the retrieval condition is disclosed in PTL 1.

CITATION LIST

Patent Literature

SUMMARY OF INVENTION

Technical Problem

The increase in the capacity of the document data which the document retrieval system regards as a retrieval target reaches a capacity on the order of petabyte (PByte), and it is requested to compress document data of a retrieval target and minimize an increase in a storage capacity for storing document data. In other words, there is a demand for a document retrieval system in which compressed document data is a retrieval target.

Compressed document data may be decompressed, and decompressed document data may be a retrieval target, but since the capacity of the decompressed document data comes back to the original, the compression is meaningless, and a retrieval period of time also increases depending on the capacity of document data.

Solution to Problem

A document retrieval system according to the disclosure includes a storage device that stores an index indicating a correspondence relation among document data including a document which is divided into a plurality of document groups and compressed in association with the document groups, a partial character string used for retrieving the document, and a first identifier indicating the document and a first correspondence table in which the document group is divided into small document groups including at least one document, and a second identifier indicating the small document group is associated with the partial character string and a retrieval server that retrieves, in response to an input of a retrieval character string, the second identifier corresponding to the partial character string included in the retrieval character string from the first correspondence table, decompresses the document data of the document group including the small document group indicated by the second identifier, retrieves the first identifier corresponding to the partial character string in which the second identifier is retrieved with reference to the index, acquires the document data corresponding to the retrieved first identifier from the decompressed document data, retrieves the first identifier of the document data including the retrieval character string in the acquired document data, and output the retrieved first identifier.

Advantageous Effects of Invention

According to the document retrieval system of the disclosure, the retrieval period of time can be reduced using compressed document data as the retrieval target.

DESCRIPTION OF EMBODIMENTS

An overview of a document retrieval system will be described. The document retrieval system is a system that specifies a document including a retrieval character string serving as a retrieval condition based on document data including a plurality of documents. When it is possible to specify a document, it is possible to output a specified document in a form convenient to a user of the document retrieval system using a known technique.

The document retrieval system prepares the following (1) to (4) and stores them in a storage device in advance when document data is registered in a document database.

(1) The document retrieval system divides large-capacity document data including a document of a record unit into a plurality of document groups, compresses each document group, and stores the compressed document groups in the document database.

(2) The document retrieval system further divides the document group into small document groups, and generates a correspondence table of the small document group and the document group. The correspondence table indicates that the small document groups are included in the document group.

(3) The document retrieval system generates a correspondence table (an n-gram hit list) of a partial character string (n-gram) for document retrieval and a small document group including the partial character string. The correspondence table (n-gram hit list) indicates that the partial character string is included in any one of the documents included in the small document group.

(4) The document retrieval system generates a correspondence table (index) of the partial character string (n-gram) and a document in units of small document groups. The correspondence table (index) indicates that the partial character string is included in the document.

Practically, it is desirable that the document retrieval system perform the preparation at the time of registration in an opposite order (an in order of (4) to (1)) to the above-described order. In other words, the document retrieval system generates the correspondence table (index) in association with a document to be registered in the document database, generates the small document group by adding several documents, generates a correspondence table (n-gram hit list) by performing a logical sum (OR) of the partial character strings of the correspondence table (index), generates the document group by adding several small document groups, generates the correspondence table of the small document group and the document group, compresses the documents included in the document group collectively, and stores the compressed documents in the document database.

At the time of retrieval, in response to an input of the retrieval character string, the document retrieval system retrieves the small document group corresponding to the partial character string included in the retrieval character string with reference to the n-gram hit list, retrieves the document group corresponding to the retrieved small document group with reference to the correspondence table of the small document group and the document group, retrieves a document corresponding to the partial character string in which the small document group is retrieved with reference to the index, and outputs the document group retrieved as the document group of the decompression target and the document retrieved as a retrieval result document.

The document data of the document group depends on a compression technique but has a capacity in which a compression rate of document data is high (a compression ratio is high). Further, the document data of the small document group has a capacity in which retrieval efficiency of the document retrieval using the partial character string (n-gram) for the document retrieval is good (the retrieval period of time is short). Generally, the compression rate of the document data is as high as several MBytes, and the retrieval efficiency is as high as several Kbytes, and they are incomparable capacities. In this regard, the document retrieval system uses the document group and the small document group corresponding to a data capacity which is desirable for each of the compression and the retrieval of the document data.

In the following description, in order to facilitate understanding of description made with reference to the drawings, each correspondence table is given a name, and an identifier (ID) is further allocated to a document or the like. The correspondence table (index) of the partial character string and the document ID is referred to as an index, the correspondence table (the n-gram hit list) of the partial character string and the small document group ID (hereinafter, a small group ID) is referred to as an n-gram hit list, and the correspondence table of the small group ID and the document group ID (hereinafter, a group ID) is referred to as a group list.

The retrieval server10includes a small group retrieving unit12, a group retrieving unit14, and a document retrieving unit16. The processing units are described as being installed independently in order to facilitate understanding but are preferably installed as a series of processing units executed by the retrieval server10. Each processing unit is described after a description related to the storage device20.

The storage device20includes an n-gram hit list30, an index40, a group list50, and a document database60that stores compressed document data.

FIG. 2is an exemplary configuration illustrating the n-gram hit list30. The n-gram hit list30is a correspondence table of a partial character string n-gram31for retrieval and a small group ID32and indicates that the n-gram31of the n-gram hit list30is included in the document included in the small document group of the small group ID32. In an example ofFIG. 2, the n-gram31of “Hig” is included in the documents included in the small document groups of the small group ID32of “1,” “3,” “14,” “68,” “89,” and “104.”

FIG. 3is an exemplary configuration illustrating the index40. The index40is a correspondence table of an n-gram41and a document ID42and indicates that the n-gram41of the index40is included in the document of the document ID42. In an example ofFIG. 3, the n-gram41of “Hig” is included in the documents of the document IDs42of “1-1,” “1-5,” “2-3,” and the like.

One index40may be installed in the document retrieval system1, but it is desirable that the index40be installed for a document included in the document group or the small document group for each document group or each small document group from a point of view of a process of the document retrieval system1which will be described later.

FIG. 4is an exemplary configuration illustrating the group list50. The group list50is a correspondence table of a small group ID51and a group ID52and indicates that the small document group of the small group ID51is included in the document group of the group ID52. In an example ofFIG. 4, the small document group of the small group ID51of “5469” is included in the document group of the group ID52of “68.”FIG. 4illustrates an example of a one-to-one correspondence of the small group ID51and the group ID52of the group list50, but the small group ID51and the group ID52of the group list50may have an m-to-one correspondence, where m indicates the number of small document groups included in the document group.

FIG. 6is a flowchart illustrating a process of the small group retrieving unit12. The small group retrieving unit12extracts the partial character string (n-gram) from the retrieval character string (S120). In the n-gram retrieval, the partial character string (n-gram) of n consecutive characters in the retrieval character string is extracted from the retrieval character string. When the retrieval character string includes p (p=n or more) characters, (p−n+1) partial character strings are extracted. The small group retrieving unit12determines whether or not the following process (S122to S124) ends in connection with the (p−n+1) extracted partial character strings (S121), and when the process ends, the small group retrieving unit12ends the process.

The small group retrieving unit12sequentially selects one of the (p−n+1) extracted partial character strings (S122). The small group retrieving unit12determines whether or not the selected partial character string is included in the n-gram of the n-gram hit list30(S123), and when no selected partial character string is included, the small group retrieving unit12causes the process to return to S121. When the selected partial character string is included, the small group retrieving unit12adds the selected partial character string and the small group ID to the small group hit list with association with each other (S124), and causes the process to return to S121.

FIG. 7is an exemplary configuration illustrating a small group hit list70. The small group retrieving unit12generates the small group hit list70in the memory of the retrieval server10. A configuration including a correspondence relation of a partial character string (n-gram)71and a small group ID of the small group hit list70is the same as the configuration of the n-gram hit list30. They have the same configuration because when the selected partial character string is included in the n-gram of the n-gram hit list30, the small group retrieving unit12copies a corresponding row from the n-gram hit list30and adds the row to the small group hit list70. Thus, the list has a capacity in which the number of rows of the small group hit list70does not exceed p−n+1.

FIG. 8is a flowchart illustrating a process of the group retrieving unit14. The group retrieving unit14determines whether or not the following process (S141to S146) ends in connection with the small group ID72included in the small group hit list70(S140), and when the process ends, the group retrieving unit14ends the process.

When the process does not end, the group retrieving unit14sequentially selects one of the small group IDs72included in the small group hit list70(S141). It is determined whether or not the selected small group ID72is included in the group hit list (S142).

FIG. 9is an exemplary configuration illustrating a group hit list80. The group retrieving unit14generates the group hit list80in the memory of the retrieval server10. The group hit list80is a correspondence table of a small group ID81and a group ID82. A configuration including a correspondence relation of the small group ID81and the group ID82of the group hit list80is the same as the group list50. They have the same configuration because the group ID52corresponding to the small group ID51equivalent to the selected small group ID is acquired with reference to the group list50, and the acquired group ID52is stored as the group ID82using the selected small group ID72as the small group ID81.

Referring back toFIG. 8, the description is continued. When the selected small group ID72is included in the group hit list80, the group retrieving unit14causes the process to return to S140. The selected small group ID72is included in the group hit list80when the same small group ID72corresponds to the different partial character strings (n-grams) of the small group hit list70. In this case, since the correspondence relation between the small group ID81and the group ID82is included in the group hit list80, the group retrieving unit14ends the process related to the selected small group ID72, and causes the process to return to S140.

The group retrieving unit14acquires the group ID52corresponding to the small group ID51equivalent to the selected small group ID72with reference to the group list50(S143). The group retrieving unit14determines whether or not the acquired group ID52is stored in the group hit list80as the group ID82(S144). When the acquired group ID52is not stored in the group hit list80as the group ID82, the group retrieving unit14additionally stores the correspondence relation between the selected small group ID72and the acquired group ID52as the correspondence relation between the small group ID81and the group ID82(S145), and causes the process to return to S140.

On the other hand, when the acquired group ID52is stored in the group hit list80as the group ID82, the group retrieving unit14associates the group ID52with the group ID82which is already stored, and stores the selected small group ID72in the group hit list80as the small group ID81(S146), and causes the process to return to S140. The acquired group ID52is stored in the group hit list80as the group ID82when small document groups62of a plurality of different small group ID72of the small group hit list70are included in a document group61of a certain group ID82.

Through the above process, the group retrieving unit14can generate the group hit list80in which the group IDs52corresponding to the small group IDs72of the small group hit list70are included not to overlap. The group ID82included in the group hit list80indicates the document group61in a compression unit of document data and indicates the document group61of document data to be decompressed.

FIG. 10is a flowchart illustrating a process of the document retrieving unit16. Here, the index40is installed for a document63included in the small document group62for each the small document group62.

The document retrieving unit16determines whether or not the following process (S161to S170) ends in connection with the partial character string71of the small group hit list70(S160), and when the process ends, the document retrieving unit16causes the process to end. When the process does not end, the document retrieving unit16sequentially selects one of the partial character strings71of the small group hit list70(S161). The document retrieving unit16determines whether or not the following process (S163to S170) ends in connection with the small group ID72corresponding to the selected partial character string71of the small group hit list70(S162), and when the process ends, the document retrieving unit16causes the process to return to S160.

When the process does not end, the document retrieving unit sequentially selects one of the small group IDs72corresponding to the selected partial character string71from the small group hit list70(S163). The document retrieving unit16acquires the group ID82corresponding to the selected small group ID72from the group hit list80(S164). The document data corresponding to the acquired group ID82is decompressed (S165). The document retrieving unit16acquires the index40corresponding to the selected small group ID72from the small group hit list70(S166), and acquires the document ID42corresponding to the selected partial character string71of the small group hit list70with reference to the acquired index40(S167). The document retrieving unit16acquires the document data of the document ID42corresponding to the selected partial character string71from the decompressed document data (S168). The document retrieving unit16acquires the document ID42of the document data including the retrieval character string among the document data of the document ID42corresponding to the selected partial character string71(S169). The document retrieving unit16adds the retrieval character string and the acquired document ID42to the document ID list (S170), and causes the process to return to S162.

The above-described document retrieval system outputs the document ID list90which is generated in association with the small document group62. The document retrieval system causes the document63specified by the document ID92of the document ID list90to be output on a display device of the retrieval server10as a subsequent process. Further, the document retrieval system displays the retrieval character string included in the document which is a combination of one or more of the partial character strings (n-grams) in a different form (display in a color, a character size, or a font which is different, reversed display, underline display, bright display, or the like) in the document output on the display device. Further, when a storage position of a decompressed document corresponding to a document group is included in the index40, the document retrieval system can output the document ID and the storage position of the document63indicated by the retrieved document ID in the document group60as the retrieval result document with reference to the index40. Such a subsequent process can be performed by a known technique, and thus a detailed description is omitted.

According to the above-described document retrieval system1, it is possible to reduce the retrieval period of time using the compressed document data as the retrieval target. Specifically, the document retrieval system1specifies the small document group62including the partial character string (n-gram) extracted from the retrieval character string, and specifies the document63by performing index retrieval within the range of the specified small document group62(specifying the document ID42corresponding to the partial character string (n-gram) with reference to the index40), and thus the index retrieval range is narrowed down to be smaller than when index retrieval is performed on all document data, whereby the retrieval period of time is reduced. Further, even when the index40is installed in association with the decompressed document group61, the retrieval period of time is reduced to be shorter than when index retrieval is performed on all document data.

Further, since the document retrieval system1specifies the document group61to be decompressed through the group hit list80, the document retrieval system1uses the compressed document data as the retrieval target and thus can save a decompression period of time of document data of the document group61that need not be decompressed and implement the high-speed process as a whole.

REFERENCE SIGNS LIST