JPH07105237A - Method and device for index generation, and document retrieval device - Google Patents

Abstract

PURPOSE:To enable high-speed all sentence retrieval under complicated retrieval conditions. CONSTITUTION:The index generating device has a character appearance frequency extent calculating means 104, a two-character successive appearance extent calculating means 105, and a three-character successive appearance extent calculating means 106 which analyze the extent of appearance of a character or character string of high frequency, and also has means 107-109 which group characters of low frequency, two successive characters, and three successive characters respectively according to the respective extents of appearance frequencies; and an index type for generating small-sized precise index data and index data are generated at a high speed according to the type. The document retrieval device has the index data which are thus generated, an index collation condition generating means, an index collating means, and a whole scanning character string collating means, and can perform high-speed retrieving operation utilizing the index data even under complicated retrieval conditions of a regular expression, etc.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for creating an index for searching a character string or the like from a document in a document search system or a document editing system to which an electronic computer is applied, and an apparatus and a document search apparatus. .

[0002]

2. Description of the Related Art In recent years, with the spread of word processors and personal computers, the increase in storage capacity of computers, and the practical use of character recognition by computers,
There is a growing number of full-text databases that store all textual information in documents. Therefore, a large amount of character information is accumulated,
There is increasing interest in a full-text database search system that searches document information as needed.

In a conventional document database system, a keyword search method is generally used in which a keyword manually assigned to each document is used as a key for searching a document. However, the keyword addition work cannot keep up with the increase in accumulated documents, the keywords become obsolete over time, and the search omission occurs due to the difference in the interpretation of the keyword between the person who added the keyword and the person who searches. There was a problem. From such a background, a document search method called a full-text search (full-text search) has recently been attracting attention.

The full-text search is a "full-text scan" method in which full-text scanning is performed on the document data for each search without any auxiliary information other than the document data, and a character appearing in the document data prior to the search. Alternatively, it is roughly classified into two types, that is, a method of automatically creating index information that can extract character string information at a high speed and searching this index at the time of searching.

Of these, the full text scanning method is
Since information other than the original document is not used, the storage capacity is small and it is possible to search immediately even after updating the document data, and in the case of complicated search conditions including character string patterns such as regular expressions and logical conditions Even if there are many results,
Although the advantage is that the search time is almost constant, it has been pointed out that the search speed is slower than that of the index method because all document data is scanned.

On the other hand, the index method generally has a faster search speed than the full-text scan method, and depending on the method of creating the index, the search speed has little advantage that it depends on the amount of documents, but the index information has a large capacity. It has been pointed out that problems such as a long index creation time and a low search speed when the search conditions are complicated or the number of search results are large.

The conventional document search method and index creation method for full-text search and their characteristics are described in "Access M".
methods for Text] (Ohristos
Faloutos, Computing Surv
eys, Vol. 17, No. 1, March 198
Detailed explanations are given in papers such as 5) and in textbooks such as "Text Search Processor" (written by Tsunesuke Takahashi, published by The Institute of Electronics, Information and Communication Engineers).

[0008]

However, in the conventional methods introduced in the above papers and books, the search speed cannot be improved without using the index. On the other hand, when the index is used, the index creation / update time is increased. In addition to the above, there is a problem that the amount of index data becomes large and it takes time to search for a complicated character string pattern such as a regular expression.

The present invention solves the above-mentioned problems of the prior art, and has a short creation / update time, a small capacity, and an approximate search with a complicated character string pattern such as a regular expression can be performed at high speed. An object of the present invention is to provide an index creating method and its device, and a document searching device which combines the created index data and full-text scanning and has a high search speed.

[0010]

In order to achieve the above object, the index creating method according to the present invention first detects the appearance of characters and character strings in the sample document data when creating the index data related to the search target document data. The index type data, which is common information when statistically checking and creating the index data, is created, and the index data is created according to the type of the index type data.

Further, according to the present invention, the index creating apparatus has a character appearance frequency calculating means for statistically checking the degree of appearance of one character in the sample document data, and the degree of appearance of the previously examined character. If the value is higher than the specified value, N characters (N is 2, 3, 4, ...
Natural number), a plurality of N character consecutive appearance frequency calculation means for statistically checking the appearance degree of a character string, and a character appearance frequency calculation means and a plurality of character appearance frequency calculation means according to the appearance degree of a character or a character string in sample document data. And an index type output unit for creating index type data which is common information when creating index data relating to the search target document data from the output of the N character consecutive appearance frequency calculation unit.

Further, the index creating device according to the present invention comprises a plurality of grouping means for grouping the characters or character strings in the sample document data according to the degree of their appearance, and the index type output means groups each group. Based on the grouping information output from the means, a correspondence table of serial numbers of each group and the characters or character strings to which they belong is output.

Further, the index creating device according to the present invention is a character continuous number calculating means for determining the number of search characters used when creating the index data relating to the document data to be searched according to the index type data output from the index creating device having the above-mentioned configuration. And a group number calculation means for calculating the corresponding group number from the number of characters determined by the character continuation number calculation means and the index type data output from the index creation device having the above configuration, and a group output from the group number calculation means. Index information storage / output means for creating index data of each document record from the number.

Further, the document search device according to the present invention comprises search input means for inputting search conditions including a character string pattern,
AND / of characters or character strings for collating the index data output from the index creating device having the above-mentioned configuration from the search condition
An index matching condition creating means for creating an OR tree, an index matching means for matching the index data with the AND / OR tree created by the index matching condition creating means, and when the matching is successful,
A full-text scanning character string collating unit that collates the corresponding portion of the search target document data with the retrieval condition including the character string pattern input from the retrieval condition input unit and outputs the successfully collated portion as the final retrieval result. Be prepared.

[0015]

According to the present invention, with the above configuration, the index data of the search target document data is statistically adapted to the search target document data, and the index data having a small capacity is not checked for the statistical property of the search target document data. To create fast,
Also, for low-frequency characters whose degree of appearance in the sample document is less than or equal to a predetermined value, that is, the narrowing-down rate or less, the index type output means records the occurrence of one character in the search target document data. For a high-frequency character whose degree of appearance in the sample document is higher than the narrowing-down rate, N characters belonging to the high-frequency character, that is, 2 characters consisting of two characters first
The two-character consecutive appearance frequency calculation means statistically examines the degree of appearance in the sample document data of consecutive letters, and the low-frequency two-letter consecutive in which the degree of appearance in the sample document data is equal to or less than the narrowing rate is output as an index type output. The means indicates the type of index data for recording the appearance of two consecutive characters in the search target document data, and the degree of appearance in the sample document data is higher than the narrowing rate.
Regarding the character continuity, the degree of appearance in the sample document data of two consecutive two characters belonging to the high-frequency two consecutive characters in the first two characters and the last two characters in the sample document data is calculated as the three consecutive character appearance frequency. The means statistically examines, and the index type output means indicates the type of index data for recording the appearance of three consecutive characters in the search target document data, so that the degree of appearance of characters and character strings is different. Also, it is possible to create index data that enables the search target document data to be narrowed down to the narrowing rate or less regardless of the search conditions.

Further, the character string appearance frequency calculation means statistically checks the degree of appearance of the character or character string in the sample document data, and then the grouping means makes a group consisting of one or more characters or character strings. In addition, the characters or character strings in the sample document data are sorted into groups in which the degree of appearance of at least one of the characters or character strings belonging to the group is less than or equal to a predetermined narrowing rate, and If any character or character string belonging to the group appears, the index data type determining unit determines the index data type for recording the information that "any character or character string belonging to the group has appeared". Decides to create indexed type data, so even if you have many types of infrequent characters, It is possible to create.

Further, in the document search device, the index matching condition creating means ANDs the characters or character strings for matching the index data from the search condition including the character string pattern inputted by the user from the search condition inputting means. / OR tree is created, and the index matching means matches the index data with the AND / OR tree created by the index matching condition creating means, and if the data is successfully matched, the full text scanning character string matching means. However, by completely matching the corresponding part of the search target document data with the search condition including the character string pattern input from the search condition input means, and making the part that has been successfully matched the final search result, Even in the case of complicated search conditions that can only be handled by the full-text scan method, the search speed can be increased by using the index.

[0018]

【Example】

(Embodiment 1) An apparatus for carrying out the index creating method of the present invention will be described below with reference to the drawings. Figure 1
FIG. 1 is a block diagram showing a configuration of an index creating device according to a first embodiment of the present invention. In FIG. 1, reference numeral 101 is sample document data in which a plurality of document records forming the document data are stored. The sample document data may be all or a part of the search target document data, or may be other document data having similar statistical properties regarding the appearance of characters and character strings to the search target document data. 102
Is the sample document phrase segmentation data recording the position of each document record in the sample document data 101, and 103 is the segment of the designated document record from the sample document data 101 according to the position information of the sample document segmentation data 102. A document delimiter means 104 is provided with a special character <START> indicating the end of the document record and a special character <END> indicating the end of the record is added at the end of the document record.
The degree of appearance of each character that appears in the sample document data 101 after receiving the document record character string that is the output of No. 3 is "the total number of characters of the document records in which the character appears is divided by the total number of characters of all document records". The character appearance frequency calculation means 105 calculates the document appearance frequency of the document record character string output from the document delimiter means 103 and the calculation result of the character appearance frequency calculation means 104. A two-character continuous appearance frequency calculating means for calculating the degree of appearance of two consecutive characters appearing as "a value obtained by dividing the sum of the number of characters of the document record in which the two consecutive characters appear by the sum of the number of characters of all document records", 1
06 receives the document record character string output from the document delimiter 103 and the calculation result of the two-character consecutive appearance frequency calculator 105, and the degree of appearance of three consecutive characters that frequently appear in the sample document data 101. Is calculated as "a value obtained by dividing the sum of the numbers of characters of the document records in which three consecutive characters appear by the sum of the numbers of characters of all document records", 107 is a calculation of the character appearance frequency calculating unit 104. When the result is received, a plurality of characters whose degree of appearance is less than or equal to a predetermined “narrowing rate” are grouped, and the degree of occurrence of any character belonging to the group does not exceed the narrowing rate. The character grouping means 108 for adjusting so as to be closer to each other receives the calculation result of the two-character consecutive appearance frequency calculating means 105, and narrows down the degree of appearance. A group of two consecutive characters that is less than or equal to the refinement rate, and a two-character consecutive grouping that adjusts so that the degree of appearance of any two consecutive letters belonging to the group is closest to the refinement rate within the range that does not exceed the refinement rate. Means, 109 is a three-character consecutive appearance frequency calculation means 106
When there is a plurality of consecutive 3 characters whose degree of appearance is less than or equal to the narrowing rate, the degree of appearance is grouped, and the degree of appearance of any 3 consecutive characters belonging to the group exceeds the narrowing rate. Adjust it so that it is closest to the narrowing rate within the range that does not exist, and if there are three consecutive characters with a higher degree of appearance than the narrowing rate, group one by one 3
Character consecutive grouping means 110 receives grouping information output from the character grouping means 107, two character consecutive grouping means 108 and three character consecutive grouping means 109, assigns serial numbers to each group, and Serial number and belonging character or 2 consecutive characters or 3
Index type output means for outputting a correspondence table with character continuation, 11
Reference numeral 1 is index type data output by the index type output means 110.

In the sample document data 101, as shown in FIG. 4, the ISBN number of the book is recorded as 1 number 1 document record for 553966 records, and in the sample document delimiter data 102, it is shown in FIG. It is assumed that the character at the beginning of each document record of the document data is recorded in character units from the beginning of the sample document data 101, and 0.05 is specified as the narrowing rate.

The operation of the index creating device configured as described above will be described. First, each document record in the sample document data 101 is cut out by the document delimiter 103 and sent to the character appearance frequency calculator 104,
The degree of appearance of each character is calculated by the sum of the number of characters in the document record in which the character appears / the sum of the number of characters in all the document records. FIG. 5 to FIG. 23 are report outputs of the index creating device, which are shown in FIG.
cter histgram & Monogram-
index) "," high-frequency two-character continuous table "of FIGS. 6 to 7 (Frequent Digram), and" 2 "of FIG.
Grouping result of consecutive characters "(Digram part
19), "High-frequency three-character continuous table" (Trigram Table) in FIGS.
"Results of grouping three consecutive characters" (Trigram
The Partitioning Table) and each information of the “index size” (Index size) of FIG. 23 are recorded in order.

In FIG. 5, which is the calculation result of the character appearance frequency calculating means 104, the item "Occurence" represents the total number of characters in the document record in which the target character appears,
The “(Percent)” item represents a value obtained by multiplying 100 by a value obtained by dividing the total number of characters of the document records in which the target character appears by the total number of characters of all document records, and
The item “k” represents the order of appearance of the target character,
The "Char" item represents the character of interest, and "Monogr"
The “am-index” item represents a character group number grouped by the degree of appearance. For example, "Cha
The character “−” in the “r” item is the fourth most frequent character, and the total number of characters in the appearing document record is 369924.
It is one character and has an appearance frequency of 87.29%. In addition,
In the case of this sample document data, since there are as few as 16 character types, there is no character group consisting of two or more characters.

Thus, 1 of the sample document data 101
After the scanning of the second time is completed, the document dividing means 103 starts the second scanning of the sample document data 101, and the cut-out document record is calculated as the two-character consecutive appearance frequency calculating means 10.
Send to 5. The two-character continuous appearance frequency calculation means 105 extracts only the series of high-frequency characters (in this example, all character types correspond to high-frequency characters) from the two-character series in the document record, and The degree of appearance of two consecutive characters is
It is calculated by "the sum of the number of characters of the document records in which the two consecutive characters appear / the sum of the number of characters of all the document records". Among them, the degree of appearance is higher than the narrowing rate,
The high-frequency two-character continuous table shown in FIGS. 6 to 7 displays the high-frequency two-character continuous.

In FIG. 6, the "No." item represents a serial number of two consecutive high-frequency characters, and is "Digram-Cod".
The “e” item represents a set in which the first character and the second character that form two consecutive characters are represented by a character group number, and “Digra
The “m-Character” item represents a character string that constitutes two consecutive characters, the “Occ” item represents the total number of characters of the document record in which two consecutive consecutive characters of interest appear, and “(Per
The “cent)” item represents a value obtained by multiplying 100 by a value obtained by dividing the total number of characters of the document records in which two consecutive focused characters appear by the total number of characters of all the document records. For example, it can be seen that the degree of appearance of two consecutive characters “-4” having a serial number of 6 is 17.57%. Of the two consecutive characters consisting of high-frequency characters, all but the two consecutive high-frequency characters are arranged in ascending order of the character string when the first character and the second character are represented by the character group number, and then the arrangement order. The two-character continuous grouping means 108 groups together two-character continuous characters that are adjacent to each other. The method of calculating the degree of occurrence of any two consecutive characters in a group when grouping assumes that the occurrence of each two consecutive characters in the group is statistically independent,
Calculate from the following formula.

[0024]

[Equation 1] However, P is the degree to which any one of the n two consecutive letters in the group appears, and P _j (j = 1, 2, ... N) is the degree to which the j-th consecutive two letters in the group appears. is there.

The result is the "grouping result of two consecutive characters" in FIG. In FIG. 8, the “No.” item is
Represents a group number consisting of two consecutive characters, "Digram-C
The "ode" item is the first of two consecutive characters in the largest character string order in the group located at the boundary between the groups.
Represents the character group number of the character, the second character, "Digr
The “am-Character” item represents a character string that constitutes the consecutive two characters. For example, the group number 7 with two consecutive characters includes two consecutive characters “22” and “23”, and the group number 8 with two consecutive characters has two consecutive characters “2”.
5 ”,“ 26 ”,“ 27 ”, and“ 29 ”are included.

Thus, 2 of the sample document data 101
When the scanning of the third time is completed, the document dividing means 103 starts the third scanning of the sample document data 101, and the cut-out document record is calculated by the three-character consecutive appearance frequency calculating means 10.
Send to 6. The three-character continuous appearance frequency calculation means 106 has a high frequency of 2 for the (first character, second character) and (the second character, third character) among the three characters in the document record.
Only three consecutive characters, which are consecutive characters, are extracted, and the degree of appearance of each consecutive three characters is "total sum of character numbers of document records in which the consecutive three characters appear / total sum of character numbers of all document records".
And the result is sent to the three-character continuous grouping means 109, and the results are grouped based on the narrowing-down rate according to the same criteria as in formula (1). The results are displayed in the "high-frequency three-character continuous table" of FIGS. 9 to 18 and the "three-character continuous grouping result" of FIGS. 19 to 22.

In FIG. 9, the "No." item represents a serial number of three consecutive characters, the "Group" item represents a group number of three consecutive characters, and "Trigram-Cod".
The “e” item represents the character group number of the first character, the second character, and the third character of three consecutive characters, and “Trigram-Ch
The “actor” item represents a character string that constitutes the consecutive three characters, the “Occ” item represents the total number of characters in the document record in which the consecutive three characters of interest appear, and “(Perc
The “ent)” item represents a value obtained by multiplying 100 by a value obtained by dividing the total number of characters of document records in which three consecutive focused characters appear by the total number of characters of all document records.

Further, in FIG. 19, the "No." item represents a group number of three consecutive characters, which is "Trigra".
The “m-Code” item represents the character group number of the first character and the second character of two consecutive characters in a large character string order measured by the character group number in the group located at the boundary between the groups. -Charact
The “er” item represents a character string that constitutes the three consecutive characters. For example, a group number 138 of three consecutive characters has 3
Character sequence "202", "203", "205", "20"
6 ”,“ 207 ”,“ 209 ”, and“ 204 ”belong.

The grouping information thus obtained is sent to the index type output means 110, where the infrequent character group,
An index type that assigns 1-bit index information to each of the two-character continuous group and the three-character continuous group is output to the index type data 111. Figure 2 shows the size of each index record created.
3 is the "index size".

In FIG. 23, "1) Monogram
The "-index:" item represents the size of the infrequent character index, the "2) Digim-index:" item represents the size of the index of two consecutive characters, and the "3) Trigram-" item.
The "index:" item represents the size of an index of three consecutive characters, and the "Total Index size:" item is
It represents the size of the index per document record, which is the sum of 1), 2) and 3). In this example, an index of 32 bytes is created for each document record.

As described above, according to the present embodiment, two-character consecutive information is used for a character that appears abundantly based on the degree of appearance of characters and character strings in the sample document data.
By creating more detailed index information, and by using the three-character continuous information to create more detailed index information for the two-character consecutive occurrences that occur more frequently, for characters and character strings that appear frequently You can create highly accurate index type data,
On the other hand, for characters and character strings that rarely appear,
By grouping, index type data with a reduced amount of index information can be created.

(Second Embodiment) Next, a second embodiment of the present invention will be described with reference to the drawings. FIG. 2 is a block diagram showing the configuration of the index creating device according to the second embodiment of the present invention. In FIG. 2, 201 is search target document data that stores a plurality of document records, 202 is search target document phrase cut data that records the position of each document record in the search target document data 201, and 203 is search target document phrase cut data. A specified document record is cut out from the search target document data 201 according to the position information of 202, a special character <START> indicating the beginning of the record is added to the beginning of the document record, and a special character <EN indicating the end of the record is added.
A document delimiter that outputs a character string with D> added to the end of the document record, 204 is index type data created by the index creating device shown in FIG. 1, and 205 is a document record character string that is an output of the document delimiter 203. Received
A character continuous number calculating means for determining, according to the index type data 204, whether the number of search characters used for index creation of the character string starting from each character appearing in the search target document data 201 is 1, 2, or 3 , 206 is a group number calculating means for receiving the number of characters which is the calculation result of the continuous character number calculating means 205 and the definition of the group of the character string and the index type data, and calculating the corresponding group number,
207 is an index information storage / output unit that receives the group number output from the group number calculation unit 206 and creates and outputs index information for one document record, and 208 is search target data 201 output from the index information storage / output unit 207.
It is index data regarding.

The operation of the index creating device configured as described above will be described with reference to the report output output when the index creating device shown in FIG. 24 operates.
In FIG. 24, “<STA of Record No. 2”
“RT> 4-587-51115-X <END>” is the cutout result of the second record of the search target data. When this character string is sent to the character continuous number calculating means 205, first, each character is converted into a character group number, and then the number of continuous characters is calculated according to the index type data 204. The character string in this example is expressed as "0,
2, 3, 9, 6, 11, 3, 7, 7, 10, 5, 4,
It becomes 3, 10, 1 ". And at the beginning, "<START
>, 4 ”as two consecutive characters are cut out by a set of character group numbers [0-2], the group number calculation means 206 calculates the group number 0 from this, and the index information storage output means 207 calculates When this is received, the 0th bit of the internal bit string is changed from hexadecimal "0000" to 16
Change to "0001". The second character from the beginning, "4
In the case of 3 characters "-, 5", it is cut out as a set of 3 groups of character group numbers [2-3-9], and the group number calculation means 206 calculates the group number 72 from this and stores the index information. The output means 207 receives this and outputs the fourth bit of the internal bit string to the hexadecimal "00".
Change from "00" to hexadecimal "0100". In this way, the index information of the second record is accumulated in the bit string inside the index information accumulating / outputting means 207 in the form of the bit string while moving the focused character one after another. When the processing of the last character is completed, the accumulated bit string is used as the index data 20.
Output to 8. By performing the above-described processing on each document record one after another, finally the search target data 101
The index information about all the document records in the index data 2
08, and the index creation process ends.

As described above, according to the index creating apparatus of this embodiment, when the index type data 204 is similar to the document data to be searched in the degree of appearance of characters and character strings, the index type data 204 is used. For the characters that appear frequently without looking up the document data to be searched using the statistical information in, the more detailed index information is created using the 2-character continuation information, and the 2 characters that appear more often in the index information are created. Has
By creating more detailed index information using three-character continuous information,
High-precision index data can be created, and conversely, for characters and character strings that rarely appear, grouping
It is possible to create index data with a reduced amount of index information.

(Embodiment 3) Next, a third embodiment of the present invention will be described with reference to the drawings. FIG. 3 is a block diagram showing an embodiment of a document search device using the document search method of the present invention. In FIG. 3, reference numeral 301 is search target document data storing a plurality of document records, 302 is search condition input means for the user to input search conditions, and 303 is index of FIG. 2 in which index information regarding the search target document data 301 is recorded. Index data created using the creating device, 304
Is a full-text scanning character string collating unit that scans the search target document data 301 and outputs a document record that matches the search condition input from the search condition input unit 302, and 305 is a search condition input from the search condition input unit 302. Is converted into a search condition that can be handled by the index data 303. Reference numeral 306 is a collation between the index data 303 and the index collating condition created by the index collating condition creating unit 305, and information of the collated document record. To the full-text scanning character string collating means 304, and 307 is a search result output by the full-text scanning character string collating means 304.

The operation of the document retrieval apparatus configured as described above will be described with reference to the retrieval example of FIG. In FIG. 25, the character string next to “keyword?” Is the search condition input by the user using the search condition input means 302, and in this example, the regular expression “115 [1-3] -X” is input. Has been done. The interpretation of this search condition is "1151-
X "," 1152-X ", or" 1153-
It means that any of "X" should be obtained for all the document data included in the record. When this search condition is sent to the index matching condition creating means 305, "Matc" in FIG.
"hing Vector", as shown below,
The search matching condition is found by the type of AND / OR tree embedded in the vector. Each element of this vector has information of (position-offset-bit string). The interpretation is shown in FIG.
And it becomes like FIG. In this example, for example, "11
The element corresponding to three consecutive characters of "5" is (5-10-100
0), of these, "10" and hexadecimal "1000",
The bit in the bit string of the index information corresponding to the document record is specified. The search collation condition of this vector type is sent to the index collating means 306 and collated with the index data 303, and as shown in “Index match” in FIG. 25 and thereafter, “Record No. 3 (4-587-5115).
1-X) "or" Record No. 10347 (4-
09-151801-X) ”and the like, and the position information of this record is sent to the full-text scanning character string collating means 304. The full-text scanning character string collating means 304,
Based on the position information of the document record that the index matching unit 306 has successfully matched, and the document information of the search target document data 301, the necessary document record is read, and the search condition input from the search condition input unit 302, In the example, the character string matching with the regular expression “115 [1-3] -X” is performed, a final result such as “Result” in FIG. 25 is obtained, and the final result is stored in the search result 307, and the document search processing is performed. To finish.

As described above, according to the document search apparatus of the present embodiment, index data created with the help of the index creation apparatus of the present invention, which has a small index capacity and can cope with complicated search conditions such as regular expressions. By using, it is possible to execute a document search at high speed even in the case of a complicated search condition that can be conventionally handled only by the full-text scan method.

[0038]

As is apparent from the above-described embodiments, the present invention statistically examines the appearance of characters and character strings in the sample document data when creating index data for the document data to be searched, and the index is created. Since index type data that is common information when creating data is created and index data is created according to the type of this index type data,
Combining an index creation method and its device, and the created index data and full-text scan, which can create and update in a short time, has a small capacity, and can perform approximate search with complex character string patterns such as regular expressions at high speed. It is possible to realize a document search device having a high search speed.

In particular, when there are a large number of search target documents in which the degree of appearance of characters and character strings does not change so much, or when the search target documents are frequently updated, index type data should be created once. In this way, a very small amount of index data can be created at extremely high speed, and there are no restrictions on search conditions.
Full-text scanning can be speeded up, and its effect is great. By the way, by using the index data according to the present invention, when one year worth of newspapers of national newspapers are searched with one keyword, the search speed can be improved by about 20 times compared with the conventional case.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an index type creating device according to a first embodiment of the present invention.

FIG. 2 is a block diagram showing a configuration of an index creating device according to a second embodiment of the present invention.

FIG. 3 is a block diagram showing a configuration of a document search device according to a third embodiment of the present invention.

FIG. 4 is a list diagram showing a part of sample document data in the first embodiment.

FIG. 5 is a list diagram showing report output related to index type creation processing according to the first embodiment.

FIG. 6 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 7 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 8 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 9 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 10 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 11 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 12 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 13 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 14 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 15 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 16 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 17 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 18 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 19 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 20 is a list diagram showing report output related to index type creation processing in the first example.

FIG. 21 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 22 is a list diagram showing report output related to index type creation processing in the first example.

FIG. 23 is a list diagram showing report output related to index type creation processing in the first embodiment.

FIG. 24 is a list diagram showing report output related to index creation processing in the second embodiment.

FIG. 25 is a list diagram showing a search example of the document search device according to the third embodiment.

FIG. 26 is a list diagram for explaining the format and interpretation of index matching conditions in the third embodiment.

FIG. 27 is a list diagram for explaining the format and interpretation of index matching conditions in the third embodiment.

[Explanation of symbols]

 101 sample document data 102 sample document delimiter data 103 document delimiter means 104 character appearance frequency calculation means 105 2 character consecutive appearance frequency calculation means 106 3 character consecutive appearance frequency calculation means 107 character grouping means 108 2 character consecutive grouping means 109 3 characters Continuous grouping means 110 Index type output means 111 Index type data 201 Search target data 202 Search target document delimiter data 203 Document delimiter means 204 Index type data 205 Character continuous number calculation means 206 Group number calculation means 207 Index information accumulation output means 208 Index Data 301 Search target data 302 Search condition input means 303 Index data 304 Full-text scanning character string matching means 305 Index matching condition creating means 306 Index matching means 307 Search results

Claims (5)

[Claims] 1. When creating index data relating to search target document data, index type data which is common information when creating index data by statistically examining the appearance of characters and character strings in sample document data. And creating the index data according to the model of the index model data. 2. A character appearance frequency calculation means for statistically checking the degree of appearance of a certain character in the sample document data, and if the degree of appearance of the previously examined character is higher than a predetermined value, A plurality of N-character consecutive appearance frequency calculating means for statistically checking the degree of appearance of an N-character (N is a natural number of 2, 3, 4, ...) Character string including all the examined characters, and a sample document It becomes common information when the index data relating to the search target document data is created from the output of the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means according to the degree of appearance of the character or the character string in the data. An index creating device having an index model output means for creating index model data. 3. A plurality of grouping means for grouping characters or character strings in the sample document data according to the degree of their appearance, and the index type output means outputs the grouping output from each of the grouping means. 3. The index creating device according to claim 2, wherein a correspondence table of the serial numbers of the respective groups and the characters or character strings to which they belong is output based on the information. 4. A character continuous number calculating means for determining the number of search characters used when creating index data related to document data to be searched according to the index type data output from the index creating device according to claim 3, and the continuous character number. From the group number calculation means for calculating the corresponding group number from the number of characters determined by the calculation means and the index type data output from the index creating device according to claim 3, and the group number output from the group number calculation means. An index creation device having index information storage output means for creating index data of each document record. 5. A search input means for inputting a search condition including a character string pattern and an AND / character combination of a character or a character string for matching the index data output from the index creating device according to claim 4 with the search condition. Index matching condition creating means for creating an OR tree, index matching means for matching the index data with the AND / OR tree created by the index matching condition creating means, and search target document data when the matching is successful A document provided with full text scanning character string collating means for collating the corresponding portion of the above with the retrieval condition including the character string pattern input from the retrieval condition input means and outputting the portion for which the collation succeeds as the final retrieval result. Search device.