Retrieval apparatus, retrieval method and retrieval program

A retrieval apparatus 100 for searching document data comprises a document storage area 141 for storing documents to be searched and a document management table 142 for storing a data size of a document such that the data size is associated with a document ID for identifying the document. The retrieval apparatus 100 reads out from the document management table data sizes of documents to be searched, and calculates a retrieval document size by adding up the read out data sizes, and calculates an estimated time t1 taken for a retrieval process by the index scan method and an estimated time t2 taken for the retrieval process by the text scan method, based on the retrieval document size. The retrieval apparatus 100 compares the estimated times t1 and t2, and decides which method to use for a retrieval process, the index scan method or the text scan method.

This application relates to and claims priority from Japanese Patent Application No. 2006-344819 filed on Dec. 21, 2006, the entire disclosure of which is incorporated herein by reference.

BACKGROUND

Recently, owing to widespread use of computers in various works, it has been getting easier to create electronic documents, and the number and volume of documents stored in storage devices such as memories or hard disk drives have been significantly increasing.

Under such circumstances, a user cannot access his/her desired document if he/she does not know the name of the document or has forgotten it. It is hard and difficult for a user to examine all of a great number of documents to find which the desired one is.

Therefore, searching throughout a storage device for a document including a search key, i.e., full text search is conveniently utilized. Examples of searching methods used in full text search include the text scan method, which means scanning sequentially target documents to check whether each of them contains a search key (as described in, for example, page 219 to page 240 in “Information Retrieval” edited by William B. Frakes and Ricardo Baeza-Yates, published by Prentice Hall PTR, Inc. in 1992), and the index scan method using an index in which, for each search key, a document containing the search key is registered (as disclosed in, for example, Japanese Patent Application Laid-open Publication No. Hei 08-194718).

Meanwhile, as a technique for selecting a search engine, for example, there is the disclosure of Japanese Patent Application Laid-open Publication No. 2003-308335.

SUMMARY

When a full text search is performed, it is desirable to estimate the time taken for the search in the case of using the text scan method and the time in the case of using the index scan method, and carry out the search by the method whose estimated time is less.

However, the total of the data sizes of documents to be searched is required for calculating an estimated time taken for a search, and it would take a long time to retrieve the data sizes of the documents from the storage device, especially when a large number of documents are stored therein.

In order to provide a solution to the foregoing and other problems, one aspect of the present disclosure is a retrieval apparatus for searching document data to retrieve desired data, comprising a document storage unit for storing document data to be searched, a document size storage unit for storing a data size of the document data such that the data size is associated with a document ID for identifying the document data, a retrieval document size calculation unit for reading out from the document size storage unit the data size associated with the document ID indicating the document data to be searched, and calculating a retrieval document size by adding up the read out data sizes, a prospect time calculation unit for calculating a first estimated time taken for a retrieval process by a first retrieval method and a second estimated time taken for the retrieval process by a second retrieval method, based on the retrieval document size, and a retrieval method decision unit for comparing the first and second estimated times and deciding which retrieval method to use for performing the retrieval process, the first method or the second method.

DESCRIPTION OF EMBODIMENTS

In an illustrative embodiment of the present disclosure, a retrieval apparatus100performs a retrieval of a document containing a keyword provided by a user, a so-called full text search. Documents to be searched are placed under the management of the apparatus100as, for example, a file stored in a file system or a record stored in a database.

When the text scan method is adopted as a document retrieval method used in a full text search of documents, all of the documents are checked sequentially to find whether they contain a word or the like matching a keyword. Therefore, a search time taken for a search of documents by the text scan method (this search is hereinafter referred to as “text search”) is proportional to the total of the data sizes of all of documents to be searched (hereinafter referred to as “target documents”). That means, when the number of target documents or the data size thereof is large, a long time is required for retrieving a desired document.

For example, let's assume that there are 400 thousands target documents with an average data size of 200 kilobytes per document, making the total data size 80 gigabytes (80,000 megabytes), and they are stored in a storage device from which data of 100 megabytes can be read out per second. In this case, when retrieving the document(s) containing a keyword of one character, the time required for checking the contents of the target documents against the character by the text scan method is calculated as 80,000 [megabytes]÷100 [MB/sec]=800 [seconds]. However, the acceptable range of a time taken for a retrieval process is usually around from several seconds to several tens seconds, thus it is impractical to take as much as 800 seconds as a retrieval time.

On the other hand, in the present embodiment, indices are generated in advance by the so-called N-gram method (1-gram method) so that, for each of characters contained in documents, information indicating the document containing that character and the position where that character occurs within the document (offset) are stored such that these items are associated with each other. Utilizing thus generated indices, the apparatus100performs a search of documents by the index scan method (this search is hereinafter referred to as “index search”).

However, the number of indices tends to be enormous when the indices are generated by the N-gram method as in the case of the retrieval apparatus100in the present embodiment, and there are some instances when the time taken for reading out all documents may be shorter than the time for reading out indices, depending on the number of target documents.

Therefore, the retrieval apparatus100in the present embodiment, each time it finishes an index search regarding one of characters constituting a keyword specified by a user (such a character corresponds to a retrieval key), compares the estimated time that it will take to perform the text search of the current target documents, which are narrowed down by the previous index search, with the estimated time that it will take to perform the further index search regarding the remaining characters. If the time for the text search of the narrowed-down target documents is shorter, the apparatus100switches the retrieval method to the text search for the rest of the retrieval process.

FIG. 1is a hardware block diagram of the retrieval apparatus100with regards to the present embodiment. As shown inFIG. 1, the retrieval apparatus100in the present embodiment comprises a CPU101, a CD-ROM drive102, a display device103, a keyboard104, a communication interface105, a main memory106, a magnetic disc device107, and a bus108connecting them.

A CD-ROM109stores programs and data. In some embodiments, the CD-ROM109maybe replaced with another type of portable storage media, such as a DVD-ROM, a MO disk, a floppy disk, a flash memory, a hard disk, or the like.

The CD-ROM drive102reads out the programs and the data stored in the CD-ROM109. After being read out from the CD-ROM drive102,the programs and the data are stored in the main memory106, and maybe transferred to the magnetic disc device107through the bus108. In some embodiments, the CD-ROM drive102may be replaced with a DVD drive, a MO drive, a floppy disk drive (FDD) or the like, depending on a storage media storing the programs and the data.

The communication interface105is an interface for connecting to a communication network200. The communication network200may be in the form of, for example, the Internet, a LAN (Local Area Network), or a SAN (Storage Area Network). The communication interface105may be in the form of, for example, an adapter for connecting to an Ethernet (registered trademark), an adapter for connecting to a fiber channel, or a modem for connecting to a public telephone network.

The main memory106stores a system control program110. The system control program110is launched in response to a command inputted through the keyboard104. In some embodiments, as a command to launch the system control program110, a command sent from another computer (not shown) connected to the network200through the communication interface105may be also received.

The system control program110comprises a document registration control program111and a retrieval control program112. The document registration control program111, in turn, comprises a document storage program120and a character string index making program121.

The retrieval control program112comprises a query analysis program122, a retrieval action program123, a retrieval document size calculation program125, a prospect time calculation program126, and a result output program127.

The above-mentioned programs are stored in the CD-ROM109, and are read out to the main memory106by the CD-ROM drive102. In some embodiments, these programs may be stored in the magnetic disk device107, or may be received through the communication interface105from another computer (not shown) connected to the communication network200. In other embodiments, these programs may be entered through the keyboard104.

In the present embodiment, the functions of the retrieval apparatus100are realized by the CPU101executing the programs110to127shown inFIG. 1. However, it should be appreciated that they may be realized by means of hardware, for example, by employing integrated circuit components configured to carry out the functions, such as a system control component, a document registration control component, a document storage component, an index making component, a retrieval control component, a query analysis component, an index scan component, a text scan component, an index scan search time estimation component, a text scan search time estimation component, and a retrieval result output component.

In the following description, for the sake of brevity, the functional units realized by the CPU101executing the programs110to127are treated as actors of processing. In the embodiments where the functional units are realized in hardware, these functional units serve as actors of processing.

In addition, in the main memory106, there are reserved storage areas of a keyword storage area140, a document storage area141, a document management table142, a query storage area143, a retrieval method storage area144, a retrieval result storage area145, a matching target index storage area146, and a setting information storage area147. In some embodiments, these storage areas may be reserved in the magnetic disk device107.

The magnetic disk device107is a secondary storage device to store data. The magnetic disk device107may be, for example, a hard disk drive. In the magnetic disk device107, storage areas of an index storage area150and an index management table151are reserved. In some embodiments, the magnetic disk device107may be in the form of a NAS (Network Attached Storage) connected to the communication network200, and be connected to the retrieval apparatus100through the communication interface105. In other embodiments, the magnetic disk device107maybe built into another computer (not shown) connected to the communication network200through its communication interface.

The magnetic disk device107stores the index management table151, as will be described later. In some embodiments, the index storage area150may be reserved in the main memory106. Likewise, the index management table151may be stored in the main memory106.

FIG. 2is a software block diagram of the retrieval apparatus100. As shown inFIG. 2, the retrieval apparatus100includes a command input unit211, a document storage unit212, an index making unit213, a query analysis unit215, a retrieval method decision unit216, a retrieval document size calculation unit217, a prospect time calculation unit218, a retrieval action unit219, and a retrieval result output unit221.

The command input unit211receives an input of a command for instructing to register a document (hereinafter referred to as “registration command”) or a command for instructing to retrieve a document (hereinafter referred to as “retrieval command”). The command input unit211receives a command input through the keyboard104. The command input unit211is realized by the CPU101executing the system control program110.

In the present embodiment, a registration command is assumed to include data indicating the content of a document to be registered. For example, the content of the document may be stored as a file in the magnetic disk device107in advance, and the name of that file may be included in the registration command.

In the present embodiment, a retrieval command is assumed to include a retrieval criterion. A retrieval criterion included in a retrieval command comprises one or more keywords. In the present embodiment, for brevity of description, it is assumed that a document retrieval is performed so as to retrieve a document containing all of such keywords, that is, a so-called “AND” operator search is performed.

The document storage unit212stores in the document storage area141a document indicated in a registration command.FIG. 3shows an illustrative structure of the document storage area141. As shown inFIG. 3, documents are stored in the document storage area141, and each of them is given individual identification information of document (hereinafter referred to as “document ID”).

Moreover, the document storage unit212registers in the document management table142(corresponding to “a document size storage unit”) the data size of the document stored in the document storage area141and the address where the document is stored.FIG. 4shows an illustrative structure of the document management table142. As shown inFIG. 4, the document management table142stores a size1412and an offset1413such that these items are associated with a document ID1411therein. The size1412is a data size of a document, and the offset1413is an offset from the first address of the document storage area141indicating the address where the document is stored.

The retrieval document size calculation unit217calculates a total data amount of documents to be searched for a document retrieval (such a total data amount is hereinafter referred to as “retrieval document size”). The retrieval document size calculation unit217calculates a retrieval document size by reading out from the document management table142the sizes1412associated with the document IDs indicating target documents and adding up them. The process of calculating a retrieval document size will be described later on.

Indices are set to a document stored in the document storage area141. The indices of a document are stored in the index storage area150.FIG. 5shows an illustrative structure of the indices stored in the index storage area150. As shown inFIG. 5, the index storage area150stores information including a document ID1502, which indicates the document containing a character1501, and an occurrence position1503, which indicates where the character1501occurs within the document indicated by the document ID1502(this information is hereinafter referred to as “index information”) such that this information is associated with the character1501therein. In the present embodiment, the indices are generated by the so-called 1-gram method. Thus, for each of all characters1501occurring in a document, the above-mentioned index information is stored in the index storage area150.

The index management table151stores, for each character, a total data size of all of index information associated with the character stored in the index storage area150.FIG. 6shows an illustrative structure of the index management table151. As shown inFIG. 6, the index management table151stores a size1512which is a total data size of all of index information related to a character1511such that the size1512is associated with the character1511therein.

The index making unit213updates the indices based on a document which the document storage unit212registers in the document storage area141. The index making unit213is realized by the CPU101executing the character string index making program121. The process of updating the indices will be described in detail later on.

The query analysis unit215analyzes a retrieval criterion included in a retrieval command. The query analysis unit215extracts all of keywords included in a retrieval criterion, and stores the extracted keywords in the keyword storage area140.FIG. 7shows the keyword storage area140with keywords stored therein. In the example shown inFIG. 7, four keywords1401to1404(reference numerals1401,1402,1403and1404respectively represent “”, “”, “” and “” ) are stored in the keyword storage area140. As will be described later, when the retrieval criterion “andandand” is specified in a retrieval command, the four keywords coupled by the “and” operator, “”, “”, “” and “” are registered in the keyword storage area140.

Moreover, the query analysis unit215generates a character string by concatenating all keywords extracted, and obtains from the index management table151the index information size1512associated with each of the characters included in the generated character string, and stores the character and the obtained size into the query storage area143such that the character and the size are associated with each other therein.FIG. 8shows an illustrative structure of the query storage area143. As shown inFIG. 8, the query storage area143stores an index size1432and a continuous character check flag1433such that these items are associated with each of characters1431constituting a character string generated by concatenating keywords. The index size1432is a total data size of all index information associated with a character. The continuous character check flag1433is a flag value indicating whether a character is the first character of any keyword, or the second or larger. For the first character of each keyword, “0” is set in this flag. Otherwise, “1” is set therein. Furthermore, a pointer1434pointing to the character1431is stored in the query storage area143. For example, the address in the main memory106where the character1431is stored may be set to the pointer1434.

The prospect time calculation unit218calculates estimated times taken for searching documents, that is, a t1which is an estimated time for an index search and a t2which is an estimated time for a text search. Data required to calculate such an estimated time t1, for example, an amount of data which can be read out from the main memory106per unit time (hereinafter referred to as “memory access speed”) and an amount of data which can be read out from the magnetic disk device107per unit time (hereinafter referred to as “disk access speed”), are assumed to be stored in advance in the setting information storage area147as shown inFIG. 9. The prospect time calculation unit218is realized by the CPU101executing a prospect time calculation program126stored in the main memory106.

The retrieval method decision unit216decides a retrieval method based on estimated times t1and t2. As will be described later, when the t1becomes longer than the t2in progress of a document retrieval process by the index scan method, the retrieval method decision unit216decides to perform the rest of the retrieval process by the text scan method. The retrieval method decision unit216is realized by the CPU101executing the retrieval control program112stored in the main memory106.

The retrieval action unit219performs a document retrieval by the index scan method or the text scan method. The result of a retrieval process performed by the retrieval action unit219is stored in the retrieval result storage area145(corresponding to “retrieved document ID storage unit”).FIG. 10shows an illustrative structure of the retrieval result storage area145. As shown inFIG. 10, the retrieval result storage area145stores a document ID1451which is the ID of a document retrieved as a retrieval result. In addition, the retrieval result storage area145stores an occurrence position1452such that the position1452is associated with the document ID1451therein. The occurrence position1452is a value indicating the position where a character in a keyword occurs within the document, and is used in an index search, as will be described later. It should be noted that, similarly to the retrieval result storage area145, the matching target index storage area146stores a document ID1461and an occurrence position1462such that these items are associated with each other, as shown inFIG. 11. A combination of the document ID1461and the occurrence position1462stored in the matching target index storage area146are used in an index search, as will be described later.

The retrieval result output unit221outputs a result of a document retrieval, outputting on the display device103a list of the document IDs stored in the retrieval result storage area145.

In the following, procedures in a document retrieval system in the present embodiment will be described.

FIG. 12is a PAD diagram illustrating a flow of a process performed by the retrieval apparatus100. The retrieval apparatus100receives an input of a command from a user (S302), and if the received command is a registration command (S303: Registration Command), then performs a document registration process (S304), or if the received command is a retrieval command (S303: Retrieval Command), then performs a document retrieval process (S305).

A flow of a document registration process is illustrated in the PAD diagram ofFIG. 13. Upon receiving an input of a registration command, the retrieval apparatus100assigns a new document ID to the document indicated in the registration command (hereinafter referred to as registration document)(S321), and attaches the assigned document ID to the registration document, and stores it in the document storage area141(S322). The retrieval apparatus100calculates the location where the document is registered in the document storage area141as the offset from the first address of the document storage area141(S323). The retrieval apparatus100registers in the document management table142the document ID assigned to the registration document, the calculated offset, and the data size of the registration document (S324).

Then, the retrieval apparatus100performs the following process for each of all characters contained in the registration document, starting from the first character thereof (S325). The retrieval apparatus100decides what number character the character to be processed (hereinafter referred to as “indexing target character”) is from the beginning of the document, as its occurrence position (S326). The retrieval apparatus100creates index information in which the indexing target character, the document ID, and the occurrence position are associated with each other, and registers the created index information in the index storage area150(S327), and adds the data length of the created index information to the size1512associated with the indexing target character in the index management table151(S328).

FIG. 14specifically illustrates how a document is registered by the document registration process. In the example shown inFIG. 14, the document1400with a data size of “30720” bytes (hereinafter referred as registration document) is being registered. The registration document is assigned a document ID of “322”, and is stored in the document storage area141. “30720”, which is the data size of the registration document, and “6545000”, which is the value resulting from adding the data size of the document ID “321” to the offset of the document ID “321”, are registered in the document management table142. Then, for each of the characters written in the registration document, index information including the character, the document ID “322” and the offset from the beginning of the registration document (occurrence position) is stored in the index storage area150, and the data size of the registered index information is added to the size1512associated with that character in the index management table151.

FIG. 15is a PAD diagram illustrating a flow of a document retrieval process.

Upon receiving an input of a retrieval command, the retrieval apparatus100extracts keywords from the retrieval criterion contained in the retrieval command (S341), and stores the extracted keywords in the keyword storage area140(S342).

The retrieval apparatus100performs the following process for each of the keywords (S343), and performs the following process for each of the characters contained in each keyword (S344). The retrieval apparatus100, if the currently processed character is the first character of the keyword (S345: True), then sets “0” to the continuous character check flag (S346), or if not (S345: False), then sets “1” to the flag (S347). The retrieval apparatus100reads out the size1512associated with that character from the index management table151(S348), and adds the read-out size1512, that character, and the continuous character check flag to the query storage area143such that these items are associated with each other therein (S349).

Repeating the above process, the retrieval apparatus100stores the character string, which is used as a criterion for the retrieval, in the query storage area143. After that, the apparatus100sets the pointer1434of the query storage area143to the first character of the string (S350).

FIG. 16specifically illustrates how a retrieval criterion is stored in the keyword storage area140and the query storage area143. In the example shown inFIG. 16,andandand” is provided as a retrieval criterion. The four keywords(1401)”, “(1402)”, “(1403)” and “(1404)”are extracted from this retrieval criterion, and are stored in the keyword storage area140. Then, for each of the characters constituting the character string1405” generated by concatenating the four keywords, the data amount of the index information, and the continuous character check flag, which indicates whether or not the character is the first character of any keyword, are stored in the query storage area143. In addition, the pointer1434which is supposed to point to the current search target character is set so as to point to the first character of the character string.

After registering a retrieval criterion by the above-mentioned process, the retrieval apparatus100sets “Index Scan” in the retrieval method storage area144(S351). This setting causes the document retrieval to be performed initially by the index scan method, as will be described below.

The retrieval apparatus100reads out from the index storage area150the document IDs1502and the occurrence positions1503associated with the character pointed by the pointer1434, and stores the combinations of the read-out document ID and occurrence position in the retrieval result storage area145(S352). The retrieval apparatus100repeats the following process until the pointer1434goes over the last character or “End” is set in the retrieval method storage area144(S353).

If “Index Scan” is set in the retrieval method storage area144(S354: True), then the retrieval apparatus100performs an index search as described below (S355). If “Index Scan” is not set in the retrieval method storage area144(S354: False), then the retrieval apparatus100performs a text search (S356) as will be described later on, and sets “End” in the retrieval method storage area144(S357).

After repeating the above process, the retrieval apparatus100extracts the document IDs stored in the retrieval result storage area145without duplication, and for each of the extracted document IDs (S358), outputs the document associated with the document ID (S359).

FIG. 17is a PAD diagram illustrating a flow of an index search.

The retrieval apparatus100increments the pointer1434of the query storage area143(S361), and sets the character pointed by the pointer1434as the search target character (S362). The retrieval apparatus100reads out from the index storage area150the document IDs1502and the occurrence positions1503associated with the current search target character, and stores the combinations of the read-out document ID1502and occurrence position1503in the matching target index storage area146(S363). In the following description, a combination of a document ID and an occurrence position stored in the matching target index storage area146is referred to as “matching target record”.

The retrieval apparatus100performs the following process for each of the combinations of document ID and occurrence position stored in the retrieval result storage area145(hereinafter referred to as “result record”) (S364). If the continuous character check flag of the current search target character is “1” (S365: True), then the retrieval apparatus100decides whether any matching target record with the document ID of the current result record and the occurrence position thereof +1 is registered in the matching target index storage area146, based on the matching target index storage area146(S366). If there is registered such a matching target record (S366: True), then “1” is added to the occurrence position of the current result record (S367). If there is not registered such a matching target record (S366: False), then the current result record is deleted from the retrieval result storage area145(S368).

On the other hand, if the continuous character check flag of the current search target character is “0” (S365: False), then the retrieval apparatus100decides whether any matching target record with the document ID of the current result record is registered in the matching target index storage area146(S369). If there is registered such a matching target record (S369: True), then the occurrence position of that matching target record is set to the occurrence position of the result record (S370). If there is not registered such a matching target record (S369: False), then the current result record is deleted from the retrieval result storage area145(S371). By repeating this process, the retrieval apparatus100checks whether each of the documents stored in the retrieval result storage area145contains the search target character.

Next, the retrieval apparatus100performs a process of calculating a t1, which is the estimated time it will take to perform the index search for the rest of the characters, the characters after the one pointed by the pointer1434(S372).FIG. 18is a PAD diagram illustrating a flow of the t1calculation process.

The retrieval apparatus100sets “0” to a remaining index size (S381), and for each of the characters from the character following the one pointed by the pointer1434to the last one in the query storage area143(S382), adds the index size of the current character to the remaining index size (S383). Then, the retrieval apparatus100obtains the read-out time by dividing the remaining index size by the disk access speed (S384), and the matching time by dividing the remaining index size by the memory access speed (S385). The retrieval apparatus100calculates the t1by adding the obtained read-out time and matching time (S386).

After calculating the t1in this way, the retrieval apparatus100performs a process of calculating a t2, which is the estimated time it will take to perform the text search from then using character strings of keywords (S373).FIG. 19is a PAD diagram illustrating a flow of the t2calculation process.

The retrieval apparatus100sets “0” to a retrieval document size (S401). The retrieval apparatus100reads out the document IDs without duplication from the retrieval result storage area145, and performs the following process for each of the read out document IDs (S402). The retrieval apparatus100obtains the size1412associated with the current document ID from the document management table142(S403), and then adds the obtained size1412to the retrieval document size (S404). By repeating this process, the retrieval apparatus100calculates the retrieval document size. Then, the apparatus100calculates the t2by dividing the calculated retrieval document size by the memory access speed (S405).

After calculating the t1and the t2in this way, the retrieval apparatus100decides whether the t1exceeds the t2(S374). If the t1is greater than the t2(S374: True), then the apparatus100sets “Text Scan” in the retrieval method storage area144(S375).

An index search is performed in the above-mentioned way.

It should be noted that the retrieval apparatus100in the present embodiment utilizes the document management table142in order to calculate the data amount of documents to be searched. Therefore, the apparatus100does not need to, for each of target documents, read out the data size from the document storage area141. This allows a process of obtaining the data sizes of target documents to be sped up.

In some embodiments, the above-mentioned steps S372to S375may be performed concurrently during the process of checking result records against matching target records (S364to S371).

FIG. 20is a PAD diagram illustrating a flow of a text search.

The retrieval apparatus100performs the following process for each of the keywords stored in the keyword storage area140(S421). The retrieval apparatus100reads out the document IDs stored in the retrieval result storage area145without duplication, and for each of the read out document IDs (S422), reads out the document associated with the document ID from the document storage area141(S423). Then, the apparatus100decides whether the read out document contains the keyword (S424), and if the document does not contain it (S424: False), then deletes the record corresponding to the document ID from the retrieval result storage area145(S425).

In the above manner, the retrieval apparatus100performs a document retrieval according to a retrieval criterion included in a retrieval command.FIG. 21specifically illustrates the document retrieval process. In the example shown inFIG. 21,andandand” has been provided as a retrieval criterion. By the process similar to the before-mentioned example shown inFIG. 16, the keywords and the character string have been registered in the keyword storage area140and the query storage area143, respectively.

In the example inFIG. 21, the document retrieval process has been already performed with regards to the characters14311“Kyou” and14312“Iku” by taking the steps S361to S368inFIG. 17, and therefore the pointer1434points to the character14312“Iku”. Now, three result records, which are the result of the retrieval process until then, are stored in the retrieval result storage area145. That means, in the example inFIG. 21, the target documents are narrowed down to the documents respectively having the document IDs “100” and “322”.

The t1, the estimated time in the case of performing the index search from then, is obtained by the process illustrated inFIG. 18as follows. First, for reading out to the matching target index storage area146the index information of the characters14313“Su” to14315“Gu”, if the total of the index sizes of the characters14313“Su” to14315“Gu” is “30 (MB)”, then, the read-out time taken will be “30 (MB)÷30 (MB/sec)=1000 (ms)”. Meanwhile, as to the matching time taken for checking the index information stored in the retrieval result storage area145against the index information stored in the matching target index storage area146, its approximate value is obtained by dividing “30 (MB)”, which is the data amount of the index information stored in the matching target index storage area146, by the memory access speed “100 (MB/second)”. Thus, the matching time will be approximately “30 (MB)÷100 (MB/sec)=300 (ms)”. Now, the t1is calculated as the sum of the read-out time plus the matching time, “1000 (ms)+300 (ms)=1300 (ms)”.

On the other hand, the t2, the estimated time in the case of performing the text search from then, is calculated by the process shown inFIG. 19. Since the memory access speed, which is the speed to access the above-listed two documents, is “100 (MB/sec)” and the total data amount of the two documents is “40960 (bytes)”, the t2is “40960 (bytes)÷100 (MB/sec)=0.4 (ms)”.

Then, the t1and the t2are compared in the step S374inFIG. 17, and if the t2, the estimated time for the text search, is shorter than the t1, the estimated time for the index search, the document retrieval is continued using the text scan method from then. In other words, the target documents have been narrowed down to the documents respectively having the document IDs “100” and “322” by performing the index search with regards to the characters14311“Kyou” and14312“Iku”, and then the keywords are searched by the text scan method in the thus narrowed-down-to two documents, the documents with the IDs “100” and “322”.

It will be appreciated from the foregoing explanation that, according to the retrieval apparatus100in the present embodiment, a number of advantages can be provided. For example, each time a retrieval process is performed with regards to each character contained in a retrieval criterion, it is possible to compare the estimated time taken in the case of performing the index search with regards to the remaining characters and the estimated time taken in the case of performing the text search against the target documents narrowed down to by the retrieval process until then, and switch the retrieval method accordingly. As a result, the time taken for a document retrieval can be shortened. In particular, when the number of target documents becomes small after a retrieval process is performed with regards to a character in a retrieval criterion, it may take less time to read out all of the narrowed down target documents and perform the text search, than to read out the index information from the index storage area150. In such a case, switching the retrieval method to the text scan method allows the retrieval time to be shortened.

Moreover, according to the retrieval apparatus100in the present embodiment, because data sizes of documents are stored in the document management table142in advance, a calculation of the total data size of all target documents can be performed without requiring a process for obtaining the data size of each of the documents stored in the document storage area141. This provides a faster calculation of the total data size of all target documents. As a result, it is possible to speed up a calculation of an estimated time taken for a text search, since this calculation uses the total data size of the documents. This allows a time taken for a whole document retrieval process in the retrieval apparatus100to be further reduced.

Now, those skilled in the art will appreciate that a number of variations of the retrieval apparatus100and corresponding algorithms are possible. Some non-limitative examples thereof are described below.

==First Variation: for the Case that Target Documents are Written in a Language Other than Japanese==

In the retrieval apparatus100in the illustrative embodiment discussed above, documents to be registered and documents to be searched are assumed to be written in Japanese. However, documents to be registered and documents to be searched may be written in English or other languages in which word boundaries are defined by, for example, white spaces, punctuations or the like.

FIG. 22shows an illustrative structure of indices stored in the index storage area150in this case. As shown inFIG. 22, the index storage area150stores information including the document ID1502which indicates a document containing a word1501, and the occurrence position1503indicating where the word1501occurs within the document indicated by the document ID1502(this information is hereinafter referred to as “index information”) such that this information is associated with the word1501therein. In the embodiment in this case, so-called word indices are created. Thus, for each of all of the words1501occurring within a document, the above-mentioned index information is stored in the index storage area150. Likewise, the index management table151is managed on the word basis rather than the character basis.FIG. 23shows an illustrative structure of the index management table151in this case.

FIG. 24specifically illustrates how a document is registered by the document registration process. In the example shown inFIG. 24, the document “enterprise computer . . . hitachi harmonious computing is . . . information technology . . . database . . . ” with a data size of “30720” bytes (hereinafter referred to as registration document) is being registered. This registration document is assigned the document ID “322” and is stored in the document storage area141. “30720”, which is the data size of the registration document, and “6545000”, which is the value resulting from adding the size of the document ID “321” to the offset of the document ID “321”, are registered in the document management table142. Then, for each of the words written in the registration document such as “enterprise” and “hitachi”, the word and the index information including the document ID “322” and the offset from the beginning of the document (occurrence position) are stored in the index storage area150, and the data size of the registered index information is added to the size1512associated with that word in the index management table151.

FIG. 25specifically illustrates how a retrieval criterion is stored in the keyword storage area140and the query storage area143. In the example shown inFIG. 25, ““harmonious computing” AND enterprise AND information AND hitachi AND database” is provided as a retrieval criterion. The five keywords “harmonious computing”, “enterprise”, “information”, “hitachi” and “database” are extracted from this retrieval criterion, and are stored in the keyword storage area140. Then, for each of the words constituting the five keywords, the data amount of the index information and the continuous word check flag, which indicates whether or not the word is the first word of any keyword, are stored in the query storage area143. Furthermore, the pointer1434which is supposed to point to the current search target word is set so as to point to the first word of the word string.

FIG. 26specifically illustrates how a document retrieval is performed in this case. In the example shown inFIG. 26, the retrieval criterion “‘harmonious computing’ AND enterprise AND information AND hitachi AND database” has been provided, and by performing the process similar to the before-discussed example shown inFIG. 16, the keywords and the word string have been registered in the keyword storage area140and the query storage area143, respectively.

In the example shown inFIG. 26, the document retrieval has been already performed with regards to the words “harmonious” and “computing” by taking the steps S361to S368as shown inFIG. 17, and therefore the pointer1434points to the word “computing”. Now, three result records, which are the result of the retrieval process until then, are stored in the retrieval result storage area145. This means, in the example inFIG. 26, the target documents are narrowed down to the documents respectively having the document IDs “100” and “322”.

The t1, which is the estimated time taken in the case of performing the index search from then is obtained by the process illustrated inFIG. 18as follows. First, for reading out to the matching target index storage area146the index information of the words from “enterprise” to “database”, if the total of the index sizes of the words from “enterprise” to “database” is “30 (MB)”, then, the read-out time taken will be “30 (MB)÷30 (MB/sec)=1000 (ms)”. Meanwhile, as to the matching time taken for checking the index information stored in the retrieval result storage area145against the index information stored in the matching target index storage area146, its approximate value is obtained by dividing “30 (MB)”, which is the data amount of the index information stored in the matching target index storage area146, by the memory access speed “100 (MB/sec)”. Thus, the matching time will be approximately “30 (MB)÷100 (MB/sec)=300 (ms)”. Now, the t1is calculated as the sum of the read-out time plus the matching time, “1000 (ms)+300 (ms)=1300 (ms)”.

On the other hand, the t2, which is the estimated time taken in the case of performing the text search from then, is calculated by the process shown inFIG. 19. Since the memory access speed, which is the speed to access the above-listed two documents, is “100 (MB/sec)” and the total data amount of the two documents is “40960 (bytes)”, the t2is “40960 (bytes)÷100 (MB/sec)=0.4 (ms)”.

Next, the t1and the t2are compared in the step S374shown inFIG. 17, and if the t2, the estimated time for the text search, is shorter than the t1, the estimated time for the index search, the document retrieval process from then is performed by the text scan method. In other words, the target documents have been narrowed down to the documents respectively having the document IDs “100” and “322” by performing the index search using the words “harmonious” and “computing”, and then the keywords are searched by the text scan method in the thus narrowed-down-to two documents, the documents with the IDs “100” and “322”.

==Second Variation: for the Case that Target Documents are Stored in the Magnetic Disk Device107==

In the retrieval apparatus100in the illustrative embodiment discussed above, documents are stored in the document storage area141which is reserved in the main memory106. However, documents may be stored in the magnetic disk device107.FIG. 27shows an illustrative hardware structure of the retrieval apparatus100in this case. In the embodiment shown inFIG. 27, the document storage area141is reserved in the magnetic disk device107, and a storage area of a document buffer161is reserved in the main memory106and a buffer management table162is stored in the main memory106. The document buffer161is a storage area for caching a document stored in the document storage area141in the magnetic disk device107. The buffer management table162manages a document ID indicating a document cached in the document buffer161.FIG. 28illustrates the buffer management table162with document IDs stored therein. The document buffer161and the buffer management table162are, for example, managed by an operating system running on the retrieval apparatus100.

In the case that the document storage area141is provided in the magnetic disk device107as mentioned above, when performing the before-discussed t2calculation process shown inFIG. 19, the time to read out data from the magnetic disk device107to the main memory106should be also taken into consideration.FIG. 29is a PAD diagram illustrating a flow of a t2calculation process in this case. As shown inFIG. 29, the retrieval apparatus100initializes a retrieval document size to “0” (S401), and a disk document amount to “0” (S501). Then, for each of the document IDs1451stored in the retrieval result storage area145(S402), if the document ID1451is not registered in the buffer management table162(S502: False), the apparatus100adds the data size thereof to the disk document amount (S503). Then, the apparatus100calculates the checking time taken for searching documents that are read out to the main memory106by dividing the retrieval document size by the memory access speed, and also calculates the read-out time taken for reading out documents that are not cached in the document buffer161from the magnetic disk device107to the main memory106by dividing the disk document amount by the disk access speed, and then calculates the t2by adding the calculated checking time and read-out time (S504).

In this way, a t2can be calculated taking the time for reading out documents from the magnetic disk device107to the main memory106into consideration, for the case that the document storage area141storing documents to be searched exists in the magnetic disk device107. As a result, an estimated time t2for a text search can be calculated more precisely.

FIG. 30specifically illustrates how a t2is calculated in the case that the document storage area141is provided in the magnetic disk device107. In the example shown inFIG. 30, similarly to the before-discussed example shown inFIG. 21,andandand” has been provided as a retrieval criterion.

As shown inFIG. 30, the retrieval apparatus100, in addition to calculating the retrieval document size, calculates as the disk document amount the total data amount of documents that have to be read out from the magnetic disk device107to the main memory106, that is, the total of the sizes1412of the document management table142associated with the document IDs that are registered in the retrieval result storage area145but not in the buffer management table162.

In the example shown inFIG. 30, the document IDs “100” and “322” are stored in the retrieval result storage area145. Meanwhile, in the buffer management table162, the document ID “322” is stored, but the document ID “100” is not. This means, the document associated with the document ID “100” is not cached in the document buffer161. Therefore, the retrieval apparatus100obtains the size1412associated with the document ID “100” from the document management table142, and then sets the obtained data size “10240” bytes to the disk document amount, which has to be read out from the magnetic disk device107to the main memory106.

Then, as explained above, the retrieval apparatus100calculates the t2by adding the quotient of dividing the retrieval document size by the memory access speed and the quotient of dividing the disk document amount by the disk access speed. In the example shown inFIG. 30, the t2is calculated as “40 (KB)÷100 (MB/sec)+10 (KB)÷30 (MB/sec)=0.7 (ms)”.

In some embodiments, the document storage area141may be provided in, for example, the CD-ROM109, rather than the magnetic disk device107. In this case, the setting information storage area147stores the data amount which can be read out from the CD-ROM109per unit time as a disk access speed.

In the retrieval apparatus100in the illustrative embodiment discussed above, each time a document retrieval is performed with regards to one character by the index scan method, a method switching decision process is performed to decide whether to continue the index search with regards to the rest of the characters or switch the retrieval method to the text scan method. However, the apparatus100may determine to perform or omit this switching decision process, depending on the number of the remaining target documents. In the following, a description is given with regards to the retrieval apparatus100according to the variation in which a process of deciding whether or not to switch a retrieval method is determined to be performed or omitted, depending on the number of the remaining target documents.

FIG. 31shows an illustrative hardware structure of the retrieval apparatus100in this variation. As shown inFIG. 31, the retrieval apparatus100stores a threshold calculation program171in the main memory106.FIG. 32shows an illustrative software structure of the retrieval apparatus100in this variation. As shown inFIG. 32, the retrieval apparatus100includes a threshold calculation unit222for calculating a threshold of the number of target documents. The threshold calculation unit222is realized by the CPU101executing the threshold calculation program171.

FIG. 33is a PAD diagram illustrating a flow of an index search process according to this variation. The process shown inFIG. 33is identical to the before-discussed process shown inFIG. 17, except that the steps S521to S524are additionally included therein. It is assumed that the retrieval apparatus100calculates in advance an average of sizes1412(hereinafter referred to as “average size”) using the document management table142.

After calculating the t1(S372), the retrieval apparatus100calculates the average time for reading out a document by dividing the average size of documents by the memory access speed (S521), and then obtains a threshold by dividing the read-out time calculated in the step S384inFIG. 18by the average document read-out time (S522). The retrieval apparatus100counts the number of the document IDs registered in the retrieval result storage area145without duplication (S523), and then, only if the counted number of the document IDs is less than the threshold (S524: True), goes through the steps S373to S375.

In this way, when the number of the narrowed down target documents is equal to or greater than a given threshold, it is possible to continue the document retrieval by the index scan method without a process of deciding whether or not to switch the retrieval method. The threshold is determined based on an average data size of documents and an amount of remaining indices, so that it is possible to decide based on the threshold which time is longer, the time taken for the index search or the time taken for the text search, without a t2calculation process, provided that target documents have about average data sizes. Thus, the time taken for a t2calculation process can be omitted, and therefore the time taken for an entire document retrieval process can be reduced.

FIG. 34specifically illustrates a process of determining whether or not to perform a t2calculation using a threshold as mentioned above. In the example shown inFIG. 34, similarly to the before-discussed example shown inFIG. 21,andandand” has been provided as a retrieval criterion. In addition, the average document size, which is the average of the sizes1412of the document management table142, has been obtained as “20 (KB)” in this example.

In the example shown inFIG. 34, the remaining index amount or the index amount of the characters14314“Su” to14315“Gu” is “30 (MB)”, and the disk access speed is “30 (MB/sec)”, and the memory access speed is “100 (MB/sec)”, and the average document size is “20 (KB)”. Therefore, the threshold is “30 (MB)÷30 (MB/sec)÷(20 (KB)÷100 (MB/sec))≈5120”. The document IDs registered in the retrieval result storage area145without duplication are two IDs, “100” and “322”. Thus, since “2<5120”, determination is made so as to perform the steps (S373) to (S375), the step for calculating the t2and the following steps.

In this variation, a threshold is obtained from a read-out time calculated based on a remaining index amount and the disk access speed, and an average document read-out time calculated based on an average document size and the memory access speed. However, a threshold may be stored in advance in the setting information storage area147as a fixed value.

The retrieval apparatus100in the illustrative embodiment discussed above may be modified such that a weight is assigned to a t1in a process of deciding whether to switch a retrieval method.FIG. 35shows an illustrative hardware structure of the retrieval apparatus100according to this variation. As shown inFIG. 35, the retrieval apparatus100according to this variation stores a retrieval simulation program172in the main memory106. Also,FIG. 36shows an illustrative software structure of the retrieval apparatus100according to this variation. As shown inFIG. 36, the retrieval apparatus100according to this variation includes a factor calculation unit223for calculating a factor for assigning a weight to a t1. The factor calculation unit223is realized by the CPU101executing the retrieval simulation program172.

FIG. 37shows a flow of a factor calculation process. The retrieval apparatus100receives an input of a plurality of retrieval criteria from a user (S541).FIG. 38shows an illustrative screen for receiving an input of retrieval criteria. As shown inFIG. 38, on a screen700, there are provided five entry fields701for entering retrieval criteria, allowing up to five retrieval criteria to be specified. In the example shown inFIG. 38, the three retrieval criteria,7011andandand”,7012“and”, and7013“and T O E I C and” are entered in the entry fields701. When one or more retrieval criteria are entered in the entry fields701and a Start Simulation button702is pressed, the retrieval apparatus100performs the following process for each of the entered retrieval criteria (S542).

The retrieval apparatus100performs the following process for each of the factors from “0.6” to “1.0” incremented by “0.1” (S543). The retrieval apparatus100sets the current time to a start time (S544), and performs the before-discussed document retrieval process shown inFIG. 15, with regards to the retrieval criterion that is currently processed (S545).

Here it should be noted that, in an index search in this variation, a t1is multiplied by the above-mentioned factor before being compared to a t2.FIG. 39illustrates a flow of an index search in this case. An index search in this case is identical to the before-discussed index search shown inFIG. 17, except that the step S561, in which a t1is multiplied by a factor, is additionally included therein.

Referring back toFIG. 37, upon completing the retrieval process, the retrieval apparatus100sets the current time to an end time (S546), and sets the time elapsed from the start time until the end time to a retrieval time which is the time taken for the retrieval process (S547). The retrieval apparatus100stores the retrieval criterion, the factor, and the retrieval time in the main memory106such that these items are associated with each other (S548).

After completing the above process for each of all combinations of the entered retrieval criteria and the factors from 0.6 to 1.0, the retrieval apparatus100reads out, for each retrieval criterion (S549), the associated factors and retrieval times from the main memory106(S550), and then displays a graph with the factors on the x-axis and the retrieval times on the y-axis (S551).

FIG. 38shows an illustrative screen710displaying the graph with regards to the before-listed three retrieval criteria. Further, below this graph, there is displayed a slider711pointing to one of the factors, and a user can specify one of the factors by moving the slider711. When a Setting button712on the screen710is pressed, the retrieval apparatus100receives the input of the factor pointed by the slider711(S552), and stores the received factor in the setting information storage area147(S553).

When performing an index search thereafter, in the above-mentioned step S561shown inFIG. 39, the retrieval apparatus100uses the factor stored in the setting information storage area147.

In this way, it is possible to assign a weight to a t1, which is used in deciding whether or not to switch a retrieval method. Thus, a user can further speed up a document retrieval process by adjusting a factor according to need, taking execution times for retrieval processes into consideration.

In this variation, a factor is specified by a user. However, not limited to this, a factor may be also decided by the retrieval apparatus100. In this case, the retrieval apparatus100reads out, for each factor, the associated retrieval times from the main memory106, and calculates the average of the read out retrieval times, and stores in the setting information storage area147the factor whose average calculated is the least. This allows an adjustment for optimizing a retrieval process to be automatically made by the retrieval apparatus100

Further, in this variation, retrieval criteria are directly entered on the screen700. However, retrieval criteria may be written in a file or the like in advance, and the retrieval apparatus100may read out the written retrieval criteria from that file.

Further, on the screen710discussed above, changes in factor and retrieval time is diagrammatized with a line graph. However, they may be showed using any type of graph, or may be expressed numerically using, for example, a table format.

Furthermore, in this variation, retrieval processes with regards to a plurality of retrieval criteria are performed using a plurality of factors, and then a graph of retrieval times relative to the combinations of retrieval criterion and factor is displayed. However, a retrieval process may be performed with regards to one retrieval criterion using a factor specified by a user.FIG. 40shows an illustrative screen for use in this case.

In the example shown inFIG. 40, the retrieval criterion “andandand” is entered in a retrieval criterion entry field721on a screen720. When a Start Simulation button722on the screen720is pressed, the retrieval apparatus100performs a document retrieval process including the above-discussed index search shown inFIG. 39using the factor “1.0”, and then displays a screen730for showing the retrieval time.

The screen730includes a display field731for outputting a retrieval time and various statistical information regarding a retrieval process. In the example shown inFIG. 40, the display field731shows that, the searches “JOIN ID 1” and “JOIN ID 2”, two searches in total, are carried out, and one of them, the search indicated as “JOIN ID 1”, is performed by the index search, while the other, the search indicated as “JOIN ID 2”, is performed by the text search.

In addition, regarding the search “JOIN ID 1”, the display field731first shows that the estimated times t2taken for the text search and t1taken for the index search are “1000 (milliseconds)” and “1500 (milliseconds)”, respectively. The display field731then shows that the time actually taken for index checking with regards to the characters7311“Kyou” and “Iku” is “200” milliseconds, and the number of the documents retrieved from this index search is “6000”.

Moreover, the screen730includes a slider732for setting a factor, the slider732situated below the display field731. A user can specify a factor by moving the slider732. When a user presses a Re-simulation button733after specifying a factor by moving the slider732, the retrieval apparatus100performs the above-discussed retrieval process using the factor pointed by the slider732.FIG. 40also shows an example of the screen730displayed after the slider732is moved to point to the factor 0.8 and then the Re-simulation button733is pressed.

Here, the display field731shows that, with the factor “0.8” specified, in the search “JOIN ID 2”, the estimated times t2taken for the text search and t1taken for the index search are “1200 (milliseconds)” and “1300 (milliseconds)”, respectively. In this case, since the t2is greater than “1040 (milliseconds)” which is the t1multiplied by 0.8, the retrieval process is continued still using the index scan method as the retrieval method, as displayed in the field731.

On the other hand, as displayed in the field731, in the search “JOIN ID 3”, the estimated time t2becomes “0.4 (millisecond)” and the estimated time t1becomes “1200 (milliseconds)”. Thus, since “1200*0.8=960 (milliseconds)” and therefore the estimated time t1becomes greater than the estimated time t2, the retrieval method is switched to the text search, as displayed in the field731.

When a user presses a Setting button734after specifying a factor by moving the slider732, the retrieval apparatus100stores the factor pointed by the slider732in the setting information storage area147. When performing an index search thereafter, in the before-discussed step S561shown inFIG. 39, the retrieval apparatus100uses the factor stored in the setting information storage area147.

In this way, a user can repeat a retrieval process with regards to a specified retrieval criterion, changing a factor. This allows a user to tune the retrieval apparatus100, adjusting a factor so as to further reduce a retrieval time.

In this variation, it is a t1that is multiplied by a factor before a t1-t2comparison. However, a t2may be multiplied by a factor, or two factors may be received and a t1and a t2may be respectively multiplied by them.

In the illustrative embodiment discussed above, the index storage area150is reserved in the magnetic disk device107. However, the area150may be reserved in the main memory106in some embodiments. In this case, in the step S384in the before-discussed process of calculating the estimated time t1taken for the index search as shown inFIG. 18, the read-out time is calculated by dividing the remaining index amount by the memory access speed. Index information stored in the main memory106can be read out faster than that stored in the magnetic disk device107, so that it is possible to further speed up the index search.

In the illustrative embodiment discussed above, indices are created by the 1-gram method. Not limited to this, indices may be created by any N-gram method such as 2-gram, 3-gram and so on. Index information may be stored in the order of character codes. Index information may be stored in a hash format, or may be stored in a Balanced tree structure. In some embodiments, rather than using the N-gram method, index information may be created based on a morpheme included in a document. In other embodiments, indices may be created on the word basis.

In the illustrative embodiment discussed above, for brevity of description, an AND operator retrieval is performed with regards to keywords extracted from a retrieval command. However, a criterion including the OR operator may be used as well. In this case, for each of two keyword groups connected by the OR operator, a retrieval process as mentioned above may be performed, and then the document ID lists created by the respective processes may be joined together.

In the illustrative embodiment discussed above, the memory access speed and the disk access speed are stored in the setting information storage area147. In some embodiments, they may be written in the programs, or may be obtained by measuring the times taken for reading out data from the main memory106and from the magnetic disk device107. In other embodiments, they may be provided as arguments of a retrieval command.

In the illustrative embodiment discussed above, in an index search, the retrieval apparatus100first reads out the document IDs and the occurrence positions to the matching target index storage area146, and then determines whether a record with a document ID matching the document ID of the result record is stored in the matching target index storage area146(S366and S369). In some embodiments, the retrieval apparatus100may search the index storage area150for index information with the current search target character and the matching document ID.

In the illustrative embodiment discussed above, when analyzing a retrieval criterion or in the step S348shown in FIG.15, index sizes of characters are stored in the query storage area143. In some embodiments, index sizes thereof may be obtained from the index management table151during an index search, for example, in a t1calculation process (S383) shown inFIG. 18.

In the illustrative embodiment discussed above, the document management table142is created in a document registration process. In some embodiments, the table142may be created during a document retrieval process. For example, immediately before the step S373ofFIG. 17in the case of first performing an index search, the document data sizes of the document IDs stored in the retrieval result storage area145may be obtained from the document storage area141, and the obtained data sizes may be registered in the document management table142such that they are associated with the document IDs. In other embodiments, the process of creating the document management table142may be performed concurrently with an index search.

In some embodiments, the offset1413of the document management table142may be replaced with the address in the main memory106where a document is stored. In this case, the retrieval apparatus100can obtain an address required to access a document from the document management table142, so that it becomes possible to perform an address resolution therefor faster, allowing a time taken for reading out a document to be shortened.