JP4011595B2 - Electronic document retrieval system and recording medium - Google Patents

Description

The present invention relates to an electronic document search system and a recording medium that search for a document including a search term of a designated character string by registering an electronic document group as an index.

  As an electronic document retrieval system, in addition to the conventional keyword retrieval system, a full-text retrieval system is also used due to the recent increase in the speed of electronic computers and the increase in capacity of storage devices. This full-text search method basically scans all the documents registered at the time of search, so that it takes a lot of search processing time for a large number of documents. Attempts have also been made to speed up processing by devising search processing techniques.

  As the index structure, a method of storing only the identifier of the document in association with the index word has been conventionally performed. Generally, however, the index string is divided by dividing the character string constituting the search word into a plurality of index words. Therefore, search noise (excess hit) is unavoidable, and post-processing by scanning all documents is necessary to remove this noise, and there is a limit to speeding up the processing.

  Therefore, a method has been proposed in which statistical information such as the appearance position of each index word in each document is also provided in the index. For example, Non-Patent Document 1 discloses a technique in which one character or two consecutive characters are used as an index word according to the character type (hereinafter referred to as Conventional Technology 1). Patent Document 1 discloses a technique that uses n connected characters (n ≧ 2) as an index word regardless of the character type (hereinafter referred to as Conventional Technique 2).

"A Method for High-Speed Full-Text Search for Japanese Papers" (The IEICE Transactions D-1 Vol. J75-D-1 No. 9 pages 836-846, September 1992) JP 7-56944 A

  However, the prior arts 1 and 2 have a problem that if the index word is short, frequent index words increase and the time required for the search process becomes long. On the other hand, if the index word is long, the index becomes very large.

  An object of the present invention is to enable digitized document search that improves the processing speed of the entire search process.

According to the first aspect of the present invention, there is provided a document dividing unit that divides a plurality of digitized registered documents into consecutive n-character (n is an integer of 2 or more) index words, and the index divided by the document dividing unit. A document frequency that is the number of registered documents including the word and the index word, a document identifier of the registered document that includes the index word, and an intra-document frequency that is the number of occurrences of the index word in each registered document And an index storage means for storing an index in which the index word is associated with the transposed list including the appearance position of each of the index words in each of the registered documents, and a given search word larger than n characters can be arbitrarily repeated n The index word that matches the divided n characters is acquired from the index, and among the acquired combinations of the index words, all the characters in the search word are any of the index words in the combination And the combination Search word dividing means for selecting the combination with the smallest number of index words and the sum of the document frequencies of the index words in the combination, and the index in the selected combination. The first search condition for searching for the document identifier corresponding to the word is a lower node, and the positional relationship between the two index words used in the two first search conditions is the same as the positional relationship in the search word. Search condition analysis means for generating a search condition tree having a second search condition as a higher node for searching the document identifier of the registered document from among the document identifiers as search results of the two first search conditions; And a search condition evaluation unit that executes a search of each node of the search condition tree and obtains the document identifier obtained by the search of the highest node as a search result .

Therefore, since the index word is uniformly a chain of n characters, it is possible to save time and labor for managing the word dictionary as compared with a method using morphological analysis that requires a huge word dictionary. Further, it is possible to speed up the search process by eliminating useless index words. In addition, the document frequency can be reduced to speed up the search process.

According to a second aspect of the present invention, in the first aspect of the invention, the search condition analysis unit further searches for the document identifier corresponding to the index word acquired by the search word division unit. Generating a candidate decision condition tree with the fourth search condition as an upper node for obtaining a product set of the document identifiers as a search result of a plurality of the third search conditions as a lower node, The search condition evaluation means executes a search for each node of the candidate determination condition tree, and executes a search for each node of the search condition tree for the document identifier acquired in the search for the highest node. And obtaining the search result .

  Therefore, prior to the detailed decision condition tree search result synthesis process, the candidate decision condition tree search result synthesis process is executed to narrow down the target document, thereby reducing the character position matching process. Thus, the search process can be speeded up.

The invention according to claim 3 is the invention according to claim 1, wherein the index storage means is a hard disk device, and the index is a unit for reading / writing a file which is a fixed-length block of the hard disk device. When the size of a plurality of transposed lists is smaller than the size of the page, the plurality of transposed lists are stored in one page, and when the size of the transposed list is larger than the page, one transposed list is stored. Is stored in a plurality of pages .

  Therefore, since the inverted list is managed in units of pages in the index according to the size, the search process can be speeded up.

According to a fourth aspect of the present invention, there is recorded a program for causing a computer to search for a registered document including a desired search word from a plurality of registered documents that are digitized and registered in a predetermined storage device. A recording medium, a document dividing procedure for dividing the registered document into index words of continuous n characters (n is an integer of 2 or more), the index word divided by the document dividing procedure, and the index word A document frequency that is the number of the registered documents, a document identifier of the registered document that includes the index word, a document frequency that is the number of occurrences of the index word in each registered document, and each registration of the index word An index storage procedure for storing an index in which a transposed list including an appearance position in a document is associated with the storage means, and a given search term larger than n characters is divided into arbitrary consecutive n characters and divided. n letters and one The index word to be acquired from the index, and among the acquired combinations of index words, all the characters in the search word are included in any of the index words in the combination, and in the combination A search word dividing procedure for selecting the combination in which the number of the index words is the minimum and the sum of the document frequencies of the index words in the combination is the minimum, and the index words in the selected combination The first search condition for searching for the document identifier corresponding to is a lower node, and the positional relationship between the two index words used in the two first search conditions is the same as the positional relationship in the search word A search condition analysis procedure for generating a search condition tree having a second search condition as a higher node for searching the document identifier of a registered document from among the document identifiers that are search results of the two first search conditions; in front A computer readable recording of a program that causes the computer to execute a search condition evaluation procedure unit that executes a search of each node of the search condition tree and obtains the document identifier obtained by the search of the highest node as a search result Storage medium.

Therefore, since the index word is uniformly a chain of n characters, it is possible to save time and labor for managing the word dictionary as compared with a method using morphological analysis that requires a huge word dictionary. Further, it is possible to speed up the search process by eliminating useless index words. In addition, the document frequency can be reduced to speed up the search process.

According to the first aspect of the present invention, since the index word is uniformly a chain of n characters, it is possible to save time and labor for managing the word dictionary as compared with a method using morphological analysis that requires an enormous word dictionary. Further, it is possible to speed up the search process by eliminating useless index words. In addition, the document frequency can be reduced to speed up the search process.

According to the second aspect of the present invention, prior to the detailed determination condition tree search result synthesis process, the candidate determination condition tree search result synthesis process is executed to narrow down the target document, thereby reducing the character position. The matching process can be reduced to speed up the search process.

According to the third aspect of the present invention, since the inverted list is managed in the index according to the size in the index, the search process can be speeded up.

In the invention according to claim 4 , since the index word is uniformly made up of a chain of n characters, it is possible to save time and labor for managing the word dictionary as compared with a method using morphological analysis that requires a huge word dictionary. Further, it is possible to speed up the search process by eliminating useless index words. In addition, the document frequency can be reduced to speed up the search process.

Embodiment 1 of the Invention
FIG. 1 is a block diagram showing an outline of the system configuration of an electronic document retrieval system 1 according to the first embodiment of the present invention. As shown in FIG. 1, the electronic document search system 1 can be implemented as a client / server system in which a client 2 and a server 3 are connected by a communication line 4, for example.

  The server 3 stores an electronic document search program in its external storage. In addition, a large number of digitized documents are registered as a database, and an index table serving as an index for searching for documents including a desired search word from the documents is registered. Document registration means and index storage means are realized). The computerized document search program, the database format, the index table, and the like are stored in a recording medium such as a floppy (registered trademark) disk, an optical disk, or a magneto-optical disk (which realizes the recording medium of the present invention). What has been read is read by the server 3 and stored in the external storage. Various processes described below are realized by the computerized document search program, database, and index table stored in the external storage.

  The client 2 functions as an input device for inputting search conditions for document search, and an output device for displaying the search results on a display or printing them out to a printer.

  FIG. 2 is a table showing an example of the data structure of the index table. The index table 11 includes an address 12, an index word 13, an identifier 14 of a document in which the index word 13 appears, an appearance position 15 of the index word 13 in a document in which the index word 13 appears, and an index registration. In this case, the number of documents 16 in which the index word 13 that can be understood from the number of identifiers 14 appears is stored in association with each other.

  The server 3 receives a document search request from the client 2, analyzes the received search condition, and performs various index collations on the index table 11 according to the contents. That is, one or a plurality of processes are performed individually or at a time among the collation of the search word and the index word 13, the inquiry of the identifier 14 corresponding to the index word 13, and the inquiry of the appearance position 15 corresponding to the index word 13. (Accordingly, the index matching means of the present invention is realized).

  Then, one or a plurality of index words 13 covering the search word received from the client 2 are acquired by this index collation. When the search word can be covered by one index word 13, the identifier 14 corresponding to the index word 13 is inquired, and the display of the document of the identifier 14 is returned to the client 2 as the document search result. For example, the search term received by the server 3 is “nuclear power”, and this “nuclear power” is registered in the index table 11 as the index word 13 as it is.

  Even when a search word can only be covered by a plurality of index words 13, each of the plurality of index words 13 is used as a new search word, and the number 16 of documents of documents in which each search word appears is obtained by index matching. Thus, the number of documents 16, that is, the document frequency is estimated (which realizes the document frequency estimation unit of the present invention).

  In this case, as shown in FIG. 3, the search condition received by the server 3 is set to search the lower node 21 by the index matching for each of the two new search words, and the search results of both the lower nodes 21 3 is converted into a composite search of the tree structure 23 of the binary tree with the combination processing condition 24 of both lower nodes 21 limited by the position conditions of both new search words as the upper node 22 (FIG. 3A). ). When there are three or more new search terms, the binary trees are arranged in a hierarchy and converted to the tree structure 23 of the binary tree (FIG. 3 (b)) (the first search condition conversion of the present invention is thereby performed). Means). FIG. 3A is an example when the index word 13 covering the search word is “nuclear power” and “power generation” when the accepted search word is “nuclear power generation”. ) Is an example when the received search word is “nuclear power generation” and the index word 13 covering the search word is “nuclear power”, “power generation”, and “equipment”.

  Then, the upper node 22 is processed according to the converted search condition. In other words, when the identifier 14 and the information on the appearance position 15 are acquired and compared by index matching, and the same identifier 14 exists between the new search terms, the information corresponding to the identifier 14 is included in the document. Compare the appearance position 15 of the new search word to determine whether or not the position condition of the upper node 22 is met, and output the display of the documents that match in all the upper nodes 22 to the client 2 as the search result. . The comparison of the appearance position 15 is performed in order from the lowest search frequency among new search words (this realizes the composite search means of the present invention). That is, in the example of FIG. 3B, when the document frequency is small in the order of “nuclear power”, “power generation”, and “equipment”, first, documents in which “power generation” also appears in documents in which “nuclear power” appears In this document, it is determined whether or not the appearance positions of “nuclear power” and “power generation” in the document match the position condition of the upper node 22 in the lower layer. Then, among documents that match, the “facility” is limited to documents that appear, and it is determined whether or not the document matches the position condition of the upper node 22 in the upper layer, and the final search is performed. Get the result.

  In this way, if the intermediate results of the search condition evaluation can be obtained by estimating the document frequency of each of the lower nodes 21, the intermediate results can be narrowed down earlier by performing the evaluation in ascending order of the document frequency. The search process can be made faster than before.

  Further, in this case, when a binary tree having a tree structure 23 as shown in FIG. 3 is created, the subordinate nodes of the binary tree in the order of the index word 13 covering the given search word in the search word. 21 is not combined, but is converted into a binary tree in the order of the lower node 21 with the lowest document frequency, and by this conversion, the lower node 21 with the lower document frequency becomes a lower layer of the tree structure 23 (thereby The first search condition conversion means of the invention is realized). As a result, the closer to the end node in the lower layer, the lower the node 21 becomes, so that the intermediate result can be narrowed earlier and the document search process can be further speeded up.

  When a given search word cannot be covered with the index word 13 registered in the index, the search result is always empty. In such a case, instead of converting to a binary tree, in the evaluation of the search condition, it is immediately converted to a terminal node that returns an empty search result (the first search condition conversion means of the present invention is thereby converted). Realized).

  Therefore, an empty search result is immediately returned when the search condition is evaluated, and the search process can be speeded up.

  Hereinafter, specific contents of the composition processing condition 24, correspondence to various search conditions, and the like will be described.

1. Regarding the case where the distance between new search terms is set as the synthesis processing condition 24 In the following, the structure of the binary tree of the tree structure 23 is referred to as “synthesis processing condition (synthesized condition 1, synthesized condition 2,... The condition m) ”is described.

In the first example, the position condition of both new search terms is “the two index words (new two search terms) covering the search terms in the search conditions q1 and q2 are shifted by n characters and appear. It is assumed that the order is constant, that is, it is a normal order and not a reverse order (this realizes the first search condition converting means of the present invention), and this position condition is referred to as “# distance below”. [N] (q1, q2) ". In the example of FIG. 3B, it is as shown in FIG. The document frequency after composition under the composition processing condition 24 is unknown unless it is actually composed, but approximation can be attempted. If the document frequency of the search condition q is “DF (q)” and taking the smaller one of q1 and q2 is expressed as “min {q1, q2}”, “#distance [n] (q1, q2) ”document frequency is
“0 ≦ DF (# distance [n] (q1, q2))
≦ min {DF (q1), DF (q2)} ”(1)
It becomes.

  Therefore, the value of “DF (#distance [n] (q1, q2))” may be approximated to an appropriate value within the range of the expression (1). For example, it can be approximated to “min {DF (q1), DF (q2)}” which is the upper limit value.

  In this way, the distance between the appearance positions of two new search terms is used as the position condition of the upper node, and this position condition is evaluated from the one with the lowest document frequency, thereby eliminating unnecessary index matching and increasing the document search speed. Can be improved.

2. When the search condition includes a logical operation of a plurality of search terms A set operation (logical operation) meaning a product set or union of a plurality of search terms is also generally used for document search. Therefore, hereinafter, processing when such a logical operation is included will be described.

  In such a case, based on the document frequency estimated using each index word covering each search word as a search word, the search of each search word is performed in the lower node 21 and the logical operation of this lower node is combined with the synthesis processing condition. 24 is converted into the tree structure 23 of the composite search to be the upper node 22 (this implements the second search condition conversion means of the present invention).

(1) When a plurality of search terms are connected by a product set When a product set of a plurality of search terms q1, q2,... Is expressed by “#and (q1, q2,...)”, The analysis of the search condition including “#and (q1, q2,...)” Is as in the example shown in FIG.

  Also in the case of composition by intersection, as in the case of “# distance [n] (q1, q2)”, it is possible to squeeze faster by evaluating from the document with the lower document frequency. Processing can be speeded up.

However, “#distance [n] (q1, q2)” is a binary tree, whereas “#and (q1, q2,...)” Is a multi-ary tree. Comparing estimated document frequencies is inefficient. Therefore, the estimated document frequencies are rearranged in ascending order, that is, the lower nodes 21 having the lowest document frequencies are converted into the tree structure 23. By this conversion, the lower nodes 21 having the lower document frequencies become lower layers of the tree structure 23. (Thus, the second search condition conversion means of the present invention is realized). As a result, the results can be narrowed down early, and the document search speed can be increased. For example, if the search condition is “#and (color, image, printer)” and “DF (image) <DF (color) <DF (printer)”, then “#and (image, color, printer) ) ”.

  If the condition synthesized by “#and (q1, q2,...)” Has a nested structure including “#and (q1, q2,...)”, Solve the nested structure. There is no change in the meaning of the logical operation even if it is flattened. If sorting is performed based on the estimated document frequency with the nested structure, the sorting range becomes unnecessarily narrow and efficiency may deteriorate. For example, if “DF (q2) <DF (q3) <DF (q4) <DF (q1)”, “#and (#and (q1, q2), q3, q4)” remains a nested structure. When rearrangement is performed, “#and (#and (q2, q1), q3, q4)” is obtained. However, when rearrangement is performed and rearrangement is performed, “#and (q2, q3, q4, q1)” is obtained. In this case, it is possible to expect early reduction, and it is possible to speed up the document search (the second search condition conversion means of the present invention is thereby realized). For example, when “#and (#and (color, image), printer)” is “DF (image) <DF (color) <DF (printer)”, the nested structure is solved and “#and ( Color, image, printer) ", and rearrangement is performed to convert it into" #and (image, color, printer) ". Further, since the document frequency of the end node is accurate while the document frequency of the intermediate node is an approximate value, there is an advantage that the estimation error is reduced when the hierarchy of the composition processing operation is smaller.

  Also, in the case of a product set, if even one of the subordinate nodes 21 to be synthesized returns an empty search result, the result of the synthesis is also empty. In the case of condition 24, it is immediately converted to a terminal node that returns an empty search result. As a result, the document search process can be speeded up (the second search condition conversion means of the present invention is thereby realized).

Note that the document frequency of the product set is N, where N is the total number of registered documents.
min {DF (q1) + DF (q2) -N, 0}
≦ DF (#and (q1, q2))
≦ min {DF (q1), DF (q2)} (2)
It becomes.

  If this range is approximated by an appropriate value, the document frequency can be estimated. For example, it can be approximated by “min {DF (q1), DF (q2)}” which is the upper limit of displacement.

(2) Case where a plurality of search words are connected by a union If a union of a plurality of search words q1, q2,... Is expressed by “#or (q1, q2,...)”, In the case of composition by union, contrary to the case of “#and (q1, q2,...)”, Evaluation from the document with the highest document frequency can be performed faster, and the document search processing can be performed. The speed can be increased (the second search condition conversion means of the present invention is thereby realized).

  Since “#and (q1, q2,...)” Is also a multi-ary tree, it is inefficient to compare the estimated document frequencies during the search condition evaluation. Therefore, the estimated document frequencies are rearranged in advance in descending order, that is, the lower node 21 having the highest document frequency is converted into the tree structure 23. By this conversion, the lower node 21 having the highest document frequency becomes a lower layer of the tree structure 23. (Thus, the second search condition conversion means of the present invention is realized). As a result, the results can be narrowed down early, and the document search speed can be increased. For example, when the search condition is “#or (pulse modulation, position modulation, PPM)” and “DF (PPM) <DF (pulse) <DF (position modulation)”, “#or (position modulation) , Pulse, PPM) ”.

  Similarly to the product set, when the unset also has a nested structure, the processing based on the estimated document frequency is more effective after the nested structure is solved. 2 search condition conversion means is realized). For example, when the search condition includes “#or (#or (pulse modulation, position modulation), PPM)” and “DF (PPM) <DF (pulse modulation) <DF (position modulation)”. Then, after nesting the structure, “#or (pulse modulation, position modulation, PPM)” is arranged, and then “#or (position modulation, pulse modulation, PPM)” is rearranged.

Note that the document frequency of “#or (q1, q2,...)” Is N as the total number of registered documents.
max {DF (q1), DF (q2) -N, 0}
≦ DF (#or (q1, q2))
≦ min {DF (q1) + DF (q2), N} (3)
It becomes.

  If this range is approximated by an appropriate value, the document frequency can be estimated. For example, it can be approximated by a limit sum “min {DF (q1) + DF (q2), N}” which is the upper limit of the range. Searches where the arithmetic sum "DF (q1) + DF (q2)" exceeds N is considered to be rare in practice as it tries to find the necessary documents from a large number of documents, so the arithmetic sum is used. But there is not much difference in practical use.

(3) Case where a plurality of search terms are connected by a difference set There are a plurality of search terms q1, q2,..., Qm, which includes the search term q1, but the search terms q2,. If a combination using a difference set that searches for items that do not contain any of the above is expressed as “# and-not (q1, q2,..., Qm)”, this is expressed as “#or (q1, q2,. This is synonymous with a logical operation that takes a product set of a complementary set of search results of “)” and a search result of q1. Therefore, if the second term and the subsequent terms are arranged in descending order of the estimated document frequency, the document search process can be speeded up by narrowing down earlier (thus realizing the second search condition conversion means of the present invention). For example, if “# and-not (depletion layer, compound, GaAs, InP)” is included in the search condition and “DF (GaAs) <DF (InP) <DF (compound)”, then “# and-not (depletion layer, compound, InP, GaAs) ".

  Also, when there is a union below the second term, the processing based on the estimated document frequency is more effective after solving the union (this realizes the second search condition conversion means of the present invention). is doing). For example, when “# and-not (depletion layer, compound, #or (GaAs, InP))” is included in the search condition and “DF (GaAs) <DF (InP) <DF (compound)”. Solves the union of the three terms and makes it “# and-not (depletion layer, compound, InP, GaAs)”, and then rearranges it as “# and-not (depletion layer, compound, InP, GaAs)”. .

  Furthermore, when the first term of the difference set returns an empty search result, the difference set also becomes empty. Therefore, by converting the difference set to a node that immediately returns an empty search result, the document search processing is speeded up. (Thus, the second search condition conversion means of the present invention is realized).

Note that the document frequency of “# and-not (q1, q2,..., Qm)” is
0 ≦ DF (# and-not (q1, q2,..., Qm))
≦ DF (q1) (4)
It becomes.

  If an approximate value is approximated within this range, the document frequency can be estimated. For example, it can be approximated by “DF (q1)” which is the upper limit of the range.

(4) When the upper limit of the distance between the appearance positions of two search terms is specified According to the user's desire to search not only for documents in which a plurality of search terms appear in common, but also for documents that appear in association with each other. Document retrieval systems that support proximity computation are also used.

  As an example of the proximity calculation, there is one that specifies the upper limit of the distance between the appearance positions, but the upper limit of the distance between the appearance positions of the two search terms q1 and q2 is n characters, and the appearance order does not matter. Is expressed as “#window [n] (q1, q2)”. In such a case, since the information on the appearance position 15 is included in the index 11, it can be easily dealt with by performing examination based on the position condition after the evaluation that is regarded as a product set. That is, the search of each search word q1, q2 is converted to a lower node 21, and the product set of the lower nodes 21 is converted to a tree structure 23 of a complex search having an upper node 22. The binary tree is converted in order, and the lower node 21 with the lower document frequency is placed below the tree structure 23 (this realizes the second search condition converting means of the present invention).

  In the case of “#window [n] (q1, q2)”, as in the case of the product set, the processing can be speeded up by the rearrangement based on the estimated document frequency. Only when the appearance order of the words q1 and q2 is not considered. Also, even when a nested structure is adopted, the meaning is different if the nested structure is removed.

3. Preliminary evaluation Since the evaluation of “# distance [n] (q1, q2)” and “#window [n] (q1, q2)” described above requires examination based on position conditions, examination based on position conditions It takes time compared to the evaluation that does not involve. Therefore, if unnecessary position condition examination can be reduced, the document search process can be speeded up. Taking "#and (#distance [3] (nuclear power, power generation), accident)" as an example, the evaluation will start from "#distance [3] (nuclear power, power generation)". For documents that do not include "accident", examine the location conditions of "nuclear power" and "power generation" (in the example of the present invention, "nuclear power" and "power generation" appear in this order, and the first three characters are shifted, To examine whether or not they are adjacent to each other.

  Therefore, a rough evaluation in which “# distance [n] (q1, q2)” or “#window [n] (q1, q2)” is replaced with “#and (q1, q2)” is performed as a preliminary evaluation. Thus, it is possible to narrow down in advance, reduce unnecessary position condition examination, and speed up the document search process.

  That is, the search of each search word q1, q2 is performed on the lower node 21, and the position condition of “#distance [n] (q1, q2)” or “#window [n] (q1, q2)” of the lower node 21 is set. It is converted into a tree structure 23 of the complex search for the upper node 22. Then, this conversion is performed so that the lower nodes 21 having the lowest document frequency are converted into binary trees, and the lower nodes 21 having the lower document frequency are arranged in the lower layer of the tree structure 23 (thus, the first and the first of the present invention). 2 Preliminary conversion means are realized). Then, the processing of the upper node 22 in the tree structure 23 after conversion is sequentially executed from the lowest layer to the upper layer in the tree structure 23 to create a composite search result. Comparison of the appearance positions between the search terms q1 and q2 is performed in order from the document having the lowest frequency (this realizes the first and second preliminary search means of the present invention). After that, accurate evaluation is performed only for the document limited by this rough evaluation (this realizes the compound search means of the present invention).

4). When using identifiers 14 having a total order relationship More specifically, the evaluation of search conditions is a process for obtaining a list of identifiers 14 of documents satisfying the conditions (this is expressed as “retrieve ()”. ). Since it is common to use an identifier having a total order relationship such as an integer or a character string, the identifier 14 is given a lower limit d0 of the identifier 14 and is d0 or more among the identifiers 14 of documents that satisfy the search condition. To obtain the smallest one (hereinafter referred to as “lower_bound (d0)”). Thereby, the process of obtaining “retrieve ()” can be realized using “lower_bound (d0)”.

  The index 11 is usually compressed in order to save time for transferring the data of the index 11 between the storage devices of the electronic document search system 1 and resources of the storage device for storing the index 11. However, in many cases, scanning in the order of identifiers 14 is often much faster in index matching than scanning with random changes in identifiers 14 ignoring the order. For such an index 11 (which implements the index storage means of the present invention), if an index word 13 and a lower limit d0 of the identifier 14 are designated, an identifier 14 including ω Among them, a comparatively high-speed index collation capable of obtaining a minimum one at d0 or more becomes possible (thus realizing the first preliminary collation means of the present invention). Thus, the search condition “lower_bound (d0)” corresponding to the index matching of the index word ω can be easily obtained.

  Furthermore, the lower limit d0 of the identifier 14 given to “lower_bound (d0)”, the obtained identifier 14, the address 32, and the index word ω are associated and recorded as a history table 31 as shown in FIG. (By this, the first preliminary collation storage means of the present invention is realized), and by referring to this, the number of index collations can be reduced.

  For example, if “lower_bound (10)” is 20, “lower_bound (11)” and “lower_bound (15)” are both 20, so the lower limit d0 of 10 or more and 20 or less is not index-checked. By referring to the history table 31, a value of 20 can be returned (this implements the first collation range specifying means of the present invention). What is obtained only by referring to the history table 31 is not added to the history table 31.

  Also in the synthesis process of the upper node 22, the identifier 14 satisfying the synthesis process condition 24 is obtained with the minimum value equal to or higher than the lower limit value d 0, and the index word 13, the lower limit value d 0 of the identifier 14, and the obtained identifier 14 are associated. In addition, the number of evaluations of the lower node 21 can be reduced by referring to the history table 31 (the second preliminary collating means, the second preliminary collating memory according to the present invention). Means and second collation range designation means).

  However, if all the history of “lower_bound (d0)” is stored, the history may become enormous. Therefore, it is desirable to limit to only the latest constant number (this implements the first and second preliminary collation storage means of the present invention). In this case, since the old history is erased from the record, useless index collation or evaluation of the lower node 21 may occur. However, most of the evaluation of the search condition is processing for obtaining “retrieve ()”. In the process of “retrieve ()”, the identifier 14 is only scanned once, so it is sufficient to leave only the latest one in the history.

[Embodiment 2 of the Invention]
FIG. 7 is a functional block diagram showing an outline of the digitized document search system 40 according to the second embodiment of the present invention.

  As shown in FIG. 7, the computerized document search system 40 includes index storage means 41 for storing an index for searching for a document including a desired search word from a plurality of digitized registered documents. . For each index word registered as the index heading, the document frequency, which is the number of registered documents containing this index word, the document identifier of the document containing the index word, and the number of occurrences of the index word in each registered document Are stored in association with each other in the document frequency and the appearance position of each index word in each registered document (hereinafter, a series of data for each index word is referred to as a “transposition list”).

  The document dividing unit 42 divides the registered document into index words. The search word dividing means 43 divides a search word in a given search condition into index words, and when there is no index word in the search word, an empty document set indicating that there is no corresponding document Create

  The search condition analysis unit 44 analyzes the search condition and generates a search condition tree by combining at least one of the index word acquired by the search word dividing unit 43 and the empty document set with an operator from the search condition. To do.

  Based on the search condition tree, the search condition evaluation unit 45 obtains information related to the index word from the index and executes search result synthesis processing to obtain a search result.

  (1) When n is an integer of 1 or more, the document dividing unit 42 uniformly divides a registered document into index words that are a chain of n characters. Thereby, compared with the method using the morphological analysis that requires a huge word dictionary, it is possible to save the trouble of managing the word dictionary.

  That is, for example, if document 1 = “Ah”, document 2 = “Aiueo”, document 3 = “Ae”, and document 4 = “say” are registered, if n = 1, the index is as shown in FIG. Information will be recorded. Here, in the appearance information for each document, the range surrounded by {,} corresponds to one document, the first field in {,} is the document identifier, and the second field is the in-document frequency. The third field (enclosed by “(,)”) is the appearance position.

  When the search condition is given as a single search word or in a form in which a plurality of search words are combined by operators such as AND and OR, the search word dividing means 43 is first recorded in the index by n-character chain. Divide into index words. The search condition analysis means 44 consists of only the index word when the search word becomes one index word. When the search word is divided into two or more index words, the search condition analysis unit 44 determines between the appearance positions of those index words. A combined search condition tree is created using position operators that specify distances. When the search word cannot be divided into index words covering the search word, the search word dividing unit 43 outputs an empty document set, and the search condition analyzing unit 44 creates a search condition tree including only the empty document set.

  Now, “# distance [x] (A, B)” designates that a document in which the index word A and the index word B are at a distance x characters is to be searched. For example, if n = 1 and the search term is “Yes”, the search term dividing unit 43 divides the search term into three index words “A”, “I”, “U”, and the search condition analyzing unit 44 , #Distance [2] (#distance [1] (a, i), u) is created.

  Then, the search condition evaluation unit 45 reads the transposed list regarding “a”, “i”, and “u”, and these three index words appear simultaneously, and the distance between “a” and “i” is 1. A search result synthesis process is performed to search for a position where the distance between “A” and “U” is 2 in some cases. In this case, only the document 2 corresponds to this, and this is a search result.

  In the above case, the following processing is performed to enable a correct search even when n is 2 or more and the search word is less than n characters. That is, the search word dividing unit 43 extracts all index words that match the search word from the m-th character (m is an integer that is 1 or more and (n−m + 1) or less) from the index, and the search condition analysis unit 44 performs the search. A plurality of index words taken out by the word dividing means 43 are synthesized by a union operator that takes a union of a plurality of search results.

  For example, in the above example, the index when n = 2 is as shown in FIG. When m = 1, if the search word is “A”, the search word dividing unit 43 outputs “Ah” “Ai”, and the search condition analysis unit 44 is “#or (Ah, Ai)”. Create a search condition tree. Here, “#or (A, B)” specifies that a union of a document set including the index word A and a document set including the index word B is searched. In this case, the documents 1, 2, and 3 are search results in the above example.

  When n is 2 or more and the search word is n characters or more, the following process is performed to speed up the search process by eliminating unnecessary index word processing.

  For example, if the search term is “Aiue”, “#distance [2] (#distance [1] (Ai)”) is created as a search condition tree in the above example. However, a document that satisfies the search condition tree “#distance [2] (ai, u)” always satisfies “#distance [1] (ai, u)”, and therefore a wasteful position matching process is performed. It will be done. Therefore, in such a case, the search word dividing unit 43 divides the search word into the minimum number of index words covering the search word, thereby improving the search efficiency. That is, in this example, the search term is divided into only two index words “Ai” and “Ue”, and a search condition tree “# distance [2] (Ai, Ue)” is created.

  In this case, when the search term is longer, there may be a plurality of cases where the search term can be divided into the minimum number of index terms. For example, if the search term is “Aiueo”, it can be divided into “Ai”, “Ue”, “Eo”, or “Ai”, “Nou”, “Eo”. In this case, the search word dividing unit 43 divides the search word into index words so that the sum of the document frequencies of the minimum number of index words covering the search word is minimized. Thus, the document frequency can be reduced and the search process can be speeded up. In the index of FIG. 9, the document frequency of “say” is 2, whereas “up” is 1. Therefore, the search word segmenting means 43 searches the search terms like “ai”, “up”, “eo”. Will be divided.

  (2) In the above example, both the document dividing unit 42 and the search word dividing unit 43 uniformly divide the registered document and the search word into a chain of n characters, but the character string dividing unit is extracted according to the character type. It is also conceivable to change n to be combined or to combine the division results for different n. As an example, when combining the division results of n = 1 and n = 2, the search terms “Aiueo” are “A” “I” “U” “E” “O” “Ai” “ "Ue" "Eo" is obtained.

  In such a case, the search word dividing unit 43 excludes the index words included in the other index words covering the search word from the plurality of index words obtained by dividing the search word. The search process can be speeded up by dividing the word into index words suitable for search. That is, in the above example, for the search term “aiueo”, “ai”, “say”, “up”, and “eo” are obtained by excluding n = 1, which are included in n = 2. .

  In this case, the search word dividing means 43 divides the search word into the minimum number of index words covering the search word, thereby speeding up the search process by omitting use of useless index words. When there are a plurality of cases where the index word can be divided into the minimum number of index words, the search word dividing unit 43 sets the search words as index words so that the sum of the document frequencies of the minimum number of index words covering the search words is minimized. By dividing, the document frequency is reduced to speed up the search process.

  (3) In the methods (1) and (2), when the search word is divided into two or more index words, the search is performed using only the search condition synthesized by the position operator. However, this method may cause useless character position matching processing. For example, in the example of (1), when the search word “Aieo” is processed, “Ai” and “Eo” are obtained as index words. For example, both index words appear for document 2 = “Aiueo”. However, a search result that there is no corresponding document is obtained because the distance condition is not satisfied. However, considering the index word “No” included in the search term, there is no document that contains “Ai”, “No”, and “Eo” at the same time. It can be determined that there is no document.

  Therefore, when the search word dividing unit 43 divides the search word into two or more index words, the following processing may be performed. That is, the search condition analysis unit 44 includes a candidate decision condition tree that is a condition tree obtained by combining a plurality of index words obtained by dividing a search word with a product set operator that takes a product set of a plurality of search results, A detailed determination condition tree, which is a condition tree obtained by selecting the smallest number covering the search word from the index words and synthesizing it with a position operator specifying the distance between the appearance positions, is created. Then, the search condition evaluation means 45 first executes a search result synthesis process for the candidate decision condition tree to search for a corresponding document from a plurality of registered documents, and then performs a detailed determination for the registered documents after the search. A search result synthesis process is executed to obtain a search result.

  Thus, prior to the detailed decision condition tree search result synthesis process, the candidate determination condition tree search result synthesis process is executed to narrow down the target document, thereby performing the character position matching process. This can reduce the speed of search processing.

  In this case, instead of creating a detailed decision condition tree by selecting the minimum number of search terms covering a search term from a plurality of index terms and combining them with a position operator that specifies the distance between the appearance positions. And selecting the one that covers the search word from the plurality of index words and that minimizes the total document frequency for each index word, and synthesizes it using a position operator that specifies the distance between the appearance positions. It may be.

  (4) Data such as a document identifier, in-document frequency, and appearance position is usually expressed in a fixed length (2 or 4 bytes). For example, if expressed in 4 bytes, the data of the index word “A” in FIG. 8 requires 11 * 4 = 44 bytes = 1408 bits. On the other hand, if each document identifier is expressed by taking the difference from the value of the previously appearing document identifier, the value will generally be a small value, so if the variable length code is used, the index will be downsized. it can. Similarly, the frequency in the document is directly expressed as a variable-length code, and the position of each occurrence is expressed in a variable-length code as the difference from the previous value of each occurrence position for each document. can do.

  For example, if a γ code (see “Managing Gigabytes” by IHwitten, Van Nostrand Reinhold, 1994, p. 84) is used as a variable length code, the document identifier is an example of the index word “A” in FIG. 1, 2-1 = 1, 3-2 = 1 respectively, and these three 1s can be expressed by “0”. In the document frequency, 3, 1, and 1 can be expressed as “101”, “0”, and “0”. Further, the appearance positions are 1, 2 = 1 = 1, 3-2 = 1 in the document 1, and these three 1s can be expressed by “0”, respectively, and appear in the documents 2 and 3. Can be represented by “0”. After all, the data of the transposed list in this case is {“0”, “101”, (“0”, “0”, “0”)}, {“0”, “0”, (“0”)} , {“0”, “0”, (“0”)}, 3 * 1 + (3 + 1 + 1) + (3 * 1 + 1 + 1) = 13 bits of data is sufficient.

  However, an index compressed in this way requires a decompression process in order to process a certain transposed list, which may slow down the search process. Moreover, if the search term is “A”, the appearance position is not required in the search process, but if the index is compressed, the second and subsequent document identifiers are obtained unless the appearance position is expanded. I can't.

  Therefore, the index speeds up the search process by dividing the area for storing each document identifier, the frequency in each document, and the appearance position for each index word, and decompressing only the document identifier. be able to.

  For example, in the above example, the data for recording the document identifier is {“0”}, {“0”}, {“0”}, and the frequency and appearance position data in the document are {“101”, ( “0”, “0”, “0”)}, {“0”, (“0”)}, {“0”, (“0”)} are recorded separately.

  However, in this case, when position matching is performed for a document with a specific document identifier, all the in-document frequencies and appearance positions up to that document must be decompressed.

  Therefore, in correspondence with each document for each index word, data in which the frequency in the document frequency appearance position representing the number of bits necessary for expressing the document frequency and the appearance position is represented by a variable length code is retained. To. As a result, by referring to the number of occurrence frequency representation bits in the document, it is possible to know where the document frequency of the required document and the data of the appearance position are located. There is no need for decompression, and the amount of data to be decompressed when referring to the document frequency and appearance position can be reduced to speed up the search process.

  For example, in the example shown in FIG. 8 described above, the document frequency appearance position number of bits in document 1 for the index word “A” is 6 (γ code “11010”), and in the case of documents 2 and 3, both are 2 (Gamma codes are both “100”), so the frequency in the document and the data of the appearance position are {“11010”, “101”, (“0”, “0”, “0”)}, {“ 100 "," 0 ", (" 0 ")}, {" 100 "," 0 ", (" 0 ")}. In this example, when it is desired to refer to the in-document frequency and appearance position regarding the third document 3, the first two documents are expanded by the number of in-document frequency appearance position expression bits and shifted by the number of bits. As a result, the position for obtaining the frequency and the appearance position in the document regarding the third document can be obtained.

  On the other hand, in such a process, the index is enlarged to record the frequency in the document frequency appearance position expression bit, and the frequency in the document frequency appearance position expression bit is set for a document that requires the frequency in the document and the appearance position. Expansion occurs as an extra process. Therefore, only when the in-document frequency is equal to or higher than the specified threshold, the number of appearance position expression bits, which is the number of bits necessary for expressing the appearance position, is recorded with a variable length code. For example, in the above example of FIG. 8, if the threshold value is 2, the appearance position expression bit number 3 (“101” in the γ code) is recorded only in the document 1 whose document frequency is 3, and the document frequency, The data of the appearance positions are {“101”, “101”, (“0”, “0”, “0”)}, {“0”, (“0”)}, {“0”, (“0 ")}. Here, the second “101” in {,} of the first document 1 is the number of appearance position expression bits. As described above, the second reason is that at the time of retrieval, it is not possible to determine whether or not the number of appearance position bits is recorded unless the in-document frequency is first expanded.

  Note that the document frequency appearance position expression bit number and the appearance position expression bit number are stored in an area for storing the document frequency and the appearance position, as is apparent from the above description.

  (5) In the case of (1) above, if m = 1, the index words combined by the union operator are sorted in the order of the character codes. If the permutation list corresponding to these is stored in an adjacent area of the index file, the data can be read at a high speed, so that the search process is also speeded up. Therefore, in the index, the transposed list for each index word is sorted in the character code order and stored in a file.

  (6) When considering a large-scale document database for one year of newspaper articles, it is important to improve the efficiency of reading and writing data from index files. Since reading and writing of data from the hard disk device is performed in units of fixed-length blocks of an appropriate size, index reading is also performed in units of pages that are fixed-length blocks that are integral multiples of this block. In this case, since the appearance frequency of the index word in the actual document varies, the size of the transposed list of each index word also varies.

  Therefore, when the size of the transposed list is smaller than the page by a predetermined amount, one or more transposed lists are simultaneously stored in one page, and when the size of the transposed list is larger than the page, it is stored using a plurality of pages. . By doing so, a small transposed list can be efficiently stored, and the upper limit of the size of the transposed list can be removed.

  (7) Next, a method for combining the cases (4) and (6) will be described. When processing a search condition consisting only of index terms with a large transposed list, data on the frequency in the document and the appearance position are not required. Therefore, reading them from the file is a wasteful process and slows down the search process. Therefore, the pages constituting the large arrangement list are divided into a document frequency, a header page for storing the document identifier and page management information, a document identifier page for storing the document identifier if necessary, an in-document frequency, an appearance position, and a document. If there is an internal frequency appearance position expression bit number or an appearance position expression bit number, it is stored separately in an in-document frequency appearance position page for storing the in-document frequency appearance position expression bit number or the appearance position expression bit number. As a result, when the in-document frequency and the appearance position are unnecessary, the reading process of the in-document frequency and the appearance position becomes unnecessary, and the search process can be speeded up.

  FIG. 10 shows a configuration example of the transposition list in this case. As shown in the figure, the transposed list is divided into a document identifier page (id page), an in-document frequency appearance position page (loc page), and a header page (header page).

  The header page includes a header part for storing the document frequency, a document identifier page index for recording the position of the document identifier page (id page index), and an in-document frequency appearance position page for recording the position of the in-document frequency appearance position page. It consists of an index (loc page index), a part of the compressed data of the document identifier (last id block), and an unused part (wastage).

  Further, the document identifier is stored across a plurality of document identifier pages, and the page number of the document identifier and the document identifier recorded at the head of each page are recorded in the document identifier page index which is management information of the document identifier page. You may do it. Thus, only the document identifier page storing the necessary document identifier data needs to be accessed, so that the search process can be speeded up. FIG. 11 is an example of a document identifier page index. In this example, in order to check whether or not the document with the document identifier 1010 exists, it is only necessary to read the document identifier page with the page number 200 as the second page by referring to the document identifier page index. Can be avoided.

  Furthermore, as shown in FIG. 12, the document identifier page index may record the document identifier recorded at the end of each page of the document identifier page. In this way, by recording the last document identifier, it is necessary to access the document identifier page by confirming that there is no document with the document identifier 1900 in the example of FIG. 12, for example, only by referring to the document identifier page index. This speeds up the search process.

  Also, the document identifier is divided and stored in document identifier blocks that are fixed-length blocks smaller than the page size, and the document identifier of the first document is stored for each document identifier block without taking the difference from the previous document identifier. If the document frequency, the appearance position, and the document frequency appearance position expression bit number or the appearance position expression bit number are present, the document frequency appearance position expression bit number or the appearance position expression bit number is the same document as the document identifier block. Are divided into document frequency appearance position blocks, which are blocks for storing the information.

  FIG. 13 shows an example of the transposition list in this case. This transposed list differs from that of FIG. 10 in the following points. That is, the document identifier page (id page) is composed of a fixed-length document identifier block (id block). The in-document frequency appearance position page (loc page) is composed of in-document frequency appearance position blocks (loc block). Each document identifier block points to a corresponding intra-document frequency appearance position block. The in-document frequency appearance position block does not necessarily fit on one page. For example, the third intra-document frequency appearance position block from the left in FIG. 13 corresponds to this.

  By configuring a large transposed list in this way, when examining the existence of a specific document within a page, it is not necessary to expand all document identifiers from the top of the page, but first record them at the beginning of each document identifier block. If the desired document identifier exists, it is possible to check in which block the document identifier is stored. In order to check which block a desired document identifier exists in, it is sufficient to search for a block immediately before a block in which the document identifier recorded at the head of the block is larger than the desired document identifier. If the first document identifier of the block that started the comparison is already larger than the desired document identifier, the desired document identifier does not exist in the current document identifier page, and no such block is found. It is assumed that the desired document identifier is in the final block itself when the comparison with the block is completed. In addition, when position information is needed for position matching, the in-document frequency appearance position block is accessed using the position information of the corresponding in-document frequency appearance position block recorded in the document identifier block. What is necessary is just to acquire desired position information. Since the desired document identifier and position information can be obtained easily as described above, the search process can be speeded up.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing an overall system configuration of an electronic document retrieval system that is Embodiment 1 of the present invention. It is a table | surface which shows the index table 11 of the said electronic document search system. It is a block diagram which shows the example of the tree structure created by converting from search conditions with the said electronic document search system. It is a block diagram which shows the example of the said tree structure. It is a block diagram which shows the example of the said tree structure. It is a table | surface which shows the history table of the said electronic document search system. It is a functional block diagram which shows the whole structure of the digitized document search system concerning Embodiment 2 of this invention. It is a table | surface which shows the example of the index used with the said electronic document search system. It is a table | surface which shows the example of the index used with the said electronic document search system. It is a block diagram which shows the example of the transposition list | wrist of the said index. It is a table | surface which shows the example of the document identifier page index of the said transposition list. It is a table | surface which shows the example of the document identifier page index of the said transposition list. It is a block diagram which shows the example of the transposition list | wrist of the said index.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Electronic document search system 11 Index 13 Index word 14 Identifier 15 Appearance position 16 Number of documents 31 1st, 2nd preliminary collation memory means 40 Electronic document search system 41 Index storage means 42 Document division means 43 Search word division means 44 Search Condition analysis means 45 Search condition evaluation means

Claims (4)

Document dividing means for dividing a plurality of digitized registered documents into index words of consecutive n characters (n is an integer of 2 or more);
Said index word to the document divider means is divided, the document frequency is the number of the registered document containing this index words, the document identifier of the registered document including the index word, the index terms of the respective registration document Index storage means for storing an index that associates the frequency in the document that is the number of occurrences in and a transposed list that includes the appearance position of the index word in each registered document;
A given search word larger than n characters is divided into arbitrary consecutive n characters, the index word that matches the divided n characters is obtained from the index, and the search word among the obtained combinations of the index words Are included in any of the index words in the combination, the number of index words in the combination is minimal, and the document frequency of each index word in the combination Search word dividing means for selecting the combination having the smallest sum ;
A first search condition for searching for the document identifier corresponding to the index word in the selected combination is a lower node, and a positional relationship between the two index words used in the two first search conditions is A search condition in which the second search condition for searching the document identifier of the registered document that is the same as the positional relationship in the search word from the document identifiers that are the search results of the two first search conditions is an upper node . A search condition analysis means for generating a tree;
An electronic document search system comprising: search condition evaluation means for executing a search of each node of the search condition tree and obtaining the document identifier acquired by searching the highest node as a search result . The search condition analysis means further uses a third search condition for searching for the document identifier corresponding to the index word acquired by the search word dividing means as a lower node, and searches for a plurality of the third search conditions. Generating a candidate decision condition tree with the fourth search condition for obtaining a product set of the document identifiers as a result as an upper node;
The search condition evaluation unit executes a search for each node of the candidate determination condition tree, and executes a search for each node of the search condition tree with respect to the document identifier acquired in the search for the highest node. The electronic document retrieval system according to claim 1, wherein the retrieval result is obtained. The index storage means is a hard disk device, and the index uses a page, which is a fixed-length block of the hard disk device, as a file read / write unit, and the size of a plurality of transposed lists is smaller than the size of the page stores a plurality of inverted list on one page, according to claim 1 size of the inverted list is characterized by storing one of the inverted list into a plurality of pages is greater than the page Electronic document search system. A recording medium that records a program for causing a computer to search for a registered document including a desired search word from among a plurality of registered documents that are digitized and registered in a predetermined storage device,
A document dividing procedure for dividing the registered document into consecutive n-letter (n is an integer of 2 or more) index terms;
Said index word divided by the document splitting procedure, document frequency is the number of the registered document containing this index words, the document identifier of the registered document including the index word, the index terms of the respective registration document An index storage procedure for storing in the storage means an index that associates the frequency in the document that is the number of appearances in the document and the transposed list that includes the appearance position of the index word in each registered document ;
A given search word larger than n characters is divided into arbitrary consecutive n characters, the index word that matches the divided n characters is obtained from the index, and the search word among the obtained combinations of the index words Are included in any of the index words in the combination, the number of index words in the combination is minimal, and the document frequency of each index word in the combination A search term splitting procedure for selecting the combination having the smallest sum;
A first search condition for searching for the document identifier corresponding to the index word in the selected combination is a lower node, and a positional relationship between the two index words used in the two first search conditions is A search condition in which the second search condition for searching the document identifier of the registered document that is the same as the positional relationship in the search word from the document identifiers that are the search results of the two first search conditions is an upper node. A search condition analysis procedure for generating a tree;
Search condition evaluation procedure means for executing a search for each node in the search condition tree and obtaining the document identifier acquired in the search for the highest node as a search result;
A computer-readable storage medium having recorded thereon a program for causing the computer to execute.

Images