JP3081093B2 - Index creation method and apparatus and document search apparatus - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for creating an index for retrieving a character string or the like from a document in a document retrieval system or a document editing system using an electronic computer. .

[0002]

2. Description of the Related Art In recent years, with the spread of word processors and personal computers, an increase in the capacity of computer storage devices, and the practical use of character recognition by computers, etc.,
The number of full-text databases storing all character information in documents has increased. Therefore, a large amount of character information is accumulated,
Interest in a full-text database retrieval system that retrieves document information as needed has been growing.

[0003] In a conventional document database system, a keyword search system using a keyword manually assigned to each document as a key for searching for a document is generally used. However, keyword addition work cannot keep up with the increase of stored documents, keywords become obsolete over time, and search omissions occur due to differences in keyword interpretation between the keyword assigner and the searcher. There was a problem. From such a background, in recent years, a document search method called full-text search (full-text search) has attracted attention.

[0004] The full-text search includes a "full-text scan" method in which the document data is scanned every text without any auxiliary information other than the document data, and a character that appears in the document data prior to the search. Alternatively, index information is automatically created so that character string information can be extracted at a high speed, and the index is searched at the time of search.

[0005] Among them, the full text scanning method is
Since information other than the original document is not used, the storage capacity is small and the search can be performed immediately after the document data is updated. In the case of complex search conditions including character string patterns such as regular expressions and logical conditions, and search Even if there are many results,
The advantage is that the search time is substantially constant, but it has been pointed out that the search speed is slower than that of the indexing method because all the document data is scanned.

On the other hand, the index system generally has a higher search speed than the full-text scan system, and has the advantage that the search speed hardly depends on the amount of documents depending on the method of creating the index, but the index information has a large capacity. It has been pointed out that the time required to create an index is long and that the search speed is reduced when the search conditions are complicated or the search results are large.

[0007] Such a conventional document search method and index creation method for full-text search and its features are described in "Access M."
methods for Text] (Ohristos
Falloutsos, Computing Surv
eys, Vol. 17, No. 1, March 198
Detailed descriptions are given in papers such as 5) and textbooks such as "Text Search Processor" (by Kosuke Takahashi, published by the Institute of Electronics, Information and Communication Engineers).

[0008]

However, in the conventional methods introduced in the above-mentioned papers and compendiums, the search speed cannot be increased without using an index, while the index creation / update time can be reduced by using the index. In addition to this, there is a problem that the capacity of the index data becomes large and it takes time to search for a complicated character string pattern such as a regular expression.

SUMMARY OF THE INVENTION The present invention solves the above-mentioned problems of the prior art, in which the creation / update time is short, the capacity is small, and an approximate search using 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 creation method and an apparatus therefor, and a document search apparatus having a high search speed by combining created index data and full text scan.

[0010]

In order to achieve the above object, an index creation method according to the present invention provides a method for generating index data by statistically examining the appearance of characters and character strings in sample document data. Creating index type data as information; and creating index data on the search target document data according to the type of the index type data. In the index type data creating step, the appearance of the character string is statistically determined. As a check operation, it is determined that an index is created with one character for a character having a certain frequency or less (low-frequency character), and for a character having a certain frequency or more (high-frequency character), two consecutive characters of the high-frequency character are determined. Then, for two consecutive characters having a certain frequency or less (low-frequency two consecutive characters), it is decided to create an index using two characters, and two characters having a certain frequency or more (two consecutive characters) are determined. The frequency 2 character sequence), high by frequency 2 that the characters perform successive characters sequentially three characters examine the continuous operation among high enough frequency strings, long as a character sequence of content determined to create an index Index Model data is created.

Further, according to the present invention, the index creation apparatus is characterized in that a character appearance frequency calculating means for statistically examining the degree of appearance of a certain character in the sample document data, and the degree of appearance of the character examined last time is predetermined. , N characters including all of the characters examined last time (N is 2, 3, 4,...)
A natural number), a plurality of N-character continuous appearance frequency calculating means for statistically examining the degree of appearance of the character string, a character appearance frequency calculating means according to the degree of appearance of the character or the character string in the sample document data, and And index type output means for generating index type data serving as common information when index data relating to the search target document data is generated from the output of the N character continuous appearance frequency calculating means.

Further, the index creating apparatus according to the present invention comprises a plurality of grouping means for grouping characters or character strings in the sample document data according to the degree of appearance thereof, and the index type output means comprises a grouping means. Based on the grouping information output from the means, a correspondence table between the serial number of each group and the character or character string to which it belongs is output.

Further, the index creation device according to the present invention is a character continuation number calculating means for determining the number of search characters to be used when creating index data relating to search target document data in accordance with the index type data output from the index creation device having the above configuration. And a group number calculating means for calculating a corresponding group number from the number of characters determined by the character continuation number calculating means and the index type data output from the index creating apparatus having the above configuration; and a group output from the group number calculating means. Index information storing and outputting means for generating index data of each document record from the number.

[0014] 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 a character or a character string for collating the index data output from the index creating apparatus with the above configuration based on the search condition
An index matching condition creating means for creating an OR tree; an index matching means for matching index data with an AND / OR tree created by the index matching condition creating means;
A full-text scanning character string matching unit that matches a corresponding part of the search target document data with a search condition including a character string pattern input from the search condition input unit, and outputs a successfully matched part as a final search result. It is provided.

[0015]

According to the present invention, a small-capacity index data in which the type of an index relating to the retrieval target document data is statistically adapted to the retrieval target document data by the above-mentioned structure is obtained without examining the statistical properties of the retrieval target document data. Create fast
For low-frequency characters whose degree of appearance in the sample document is equal to or less than a predetermined value, that is, equal to or less than the narrowing-down rate, index data for recording the appearance of one character in the search target document data by the index type output unit. For high-frequency characters whose degree of appearance in the sample document is higher than the narrowing-down ratio, N characters belonging to the high-frequency characters, that is, 2 characters consisting of two characters first
The frequency of occurrence of two consecutive characters in the sample document data of character continuity is statistically checked by the two character continuous appearance frequency calculating means. Means for indicating the type of index data for recording the appearance of two consecutive characters in the search target document data, and the frequency of appearance in the sample document data is higher than the narrowing rate.
Regarding the character continuation, the frequency of appearance of three consecutive characters having two consecutive two characters belonging to the high frequency two consecutive characters as the first two characters and the last two characters in the sample document data is calculated as a three-character consecutive 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 degrees of appearance of characters and character strings are different. Also, it is possible to create index data that enables the search target document data to be narrowed to a narrowing rate or less regardless of the search conditions.

The character string appearance frequency calculating means statistically examines the degree of appearance of a character or a character string in the sample document data, and thereafter, the grouping means sets a group consisting of one or more characters or character strings. 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 equal to or less than a predetermined narrowing-down ratio. If any character or character string belonging to the group appears, the type of index data for recording information that "any of the characters or character string belonging to the group has appeared" is determined by an index type determining means. Determines and creates indexed format data, so that even if there are many types of It is possible to create.

Further, in the document retrieval apparatus, the index collation condition creating means uses the character or character string AND for collating the index data based on the retrieval condition including the character string pattern inputted by the user from the retrieval condition input means. / OR tree is created, and the index collating means collates the index data with the AND / OR tree created by the index collating condition creating means, and if the collation is successful, the full-text scanning character string collating means Conventionally, 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 complex search conditions that could only be handled by the full-text scan method, it is possible to increase the search speed by the index.

[0018]

【Example】

(Embodiment 1) Hereinafter, an apparatus for implementing an index creation method of the present invention will be described with reference to the drawings. FIG.
FIG. 1 is a block diagram illustrating a configuration of an index creation device according to a first embodiment of the present invention. In FIG. 1, reference numeral 101 denotes sample document data storing a plurality of document records constituting the document data. The sample document data may be all or 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 sample document punctuation data in which the position of each document record in the sample document data 101 is recorded, and 103 is a specified document record cut out from the sample document data 101 in accordance with the position information of the sample document punctuation data 102, and the beginning of the record is extracted. A document delimiter that outputs a character string in which a special character <START> representing the end of the document record is added to the head of the document record and a special character <END> indicating the end of the record is added to the end of the document record.
3, the degree of appearance of each character appearing in the sample document data 101 after receiving the document record character string is determined by dividing the sum of the number of characters of the document record in which the character appears by the sum of the number of characters of all the document records. The character appearance frequency calculating means 105 which calculates the value as a “value” is received by the document record character string output from the document separating means 103 and the calculation result of the character appearance frequency calculating means 104, A two-character continuation frequency calculating means for calculating a degree of occurrence of two consecutive characters appearing as “a value obtained by dividing the total number of characters of the document records in which the two consecutive characters appear by the total number of characters of all the document records”; 1
Reference numeral 06 denotes a document record character string output from the document delimiter 103 and a calculation result of the two-character continuous appearance frequency calculator 105, and the degree of occurrence of three consecutive characters appearing frequently in the sample document data 101. Is calculated as “the value obtained by dividing the sum of the number of characters of the document record in which the three consecutive characters appear by the sum of the number of characters of all the document records”, and 107 is the calculation of the character appearance frequency calculation means 104. Receiving the result, a plurality of characters whose degree of appearance is equal to or less than 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 to be close to each other receives the calculation result of the two-character continuous appearance frequency calculating means 105 and narrows the degree of appearance. Grouping a plurality of two-character continuations that are equal to or less than the narrowing-down ratio, and adjusting the degree of occurrence of any two-character continuation belonging to the group to be the closest to the narrowing-down ratio within a range that does not exceed the narrowing-down ratio. Means 109, three character continuous appearance frequency calculating means 106
If there is a plurality of consecutive three characters whose degree of appearance is equal to or less than the narrowing rate after receiving the calculation result of, the degree of occurrence of any three consecutive characters belonging to the group exceeds the narrowing rate. Make adjustments so as to be the closest to the narrowing-down ratio within a range that does not exist, and make a group of three consecutive characters whose appearance is higher than the narrowing-down ratio.
The character continuation grouping means 110 receives the grouping information output from the character grouping means 107, the two-character continuation grouping means 108, and the three-character continuation grouping means 109, and assigns a serial number to each group. Serial number and the assigned character or two consecutive characters or 3
Index type output means for outputting a correspondence table with character continuity, 11
Reference numeral 1 denotes index type data output from the index type output unit 110.

As shown in FIG. 4, 553,966 ISBN numbers of books are recorded in the sample document data 101 as one-by-one document record, and the sample document delimiter data 102 shown in FIG. It is assumed that the distance of the head character of each document record of the document data from the head of the sample document data 101 in character units is recorded, and 0.05 is specified as a narrowing-down ratio.

The operation of the index creating apparatus configured as described above will be described. First, each document record in the sample document data 101 is cut out by the document separating means 103 and sent to the character appearance frequency calculating means 104,
The degree of appearance of each character is calculated by the sum of the number of characters of the document record in which the character appears / the sum of the number of characters of all the document records. FIG. 5 to FIG. 23 show the report output of this index creation device, and refer to the “character frequency table (Chara) in FIG.
cter histgram & Monogram-
index), “High-frequency two-character continuous table” in FIGS. 6 to 7 (Frequency Digram), and “2 in FIG.
Character grouping result "(Digram part
9) to FIG. 9 to FIG. 18 (trigger table), FIG. 19 to FIG.
Of "Grouping results of three consecutive characters" (Trigram
Information of “Partitioning Table” and “index size” of FIG. 23 are sequentially recorded.

In FIG. 5, which is the calculation result of the character appearance frequency calculation means 104, the item “Occurrence” indicates the total number of characters of the document record in which the character of interest 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 record in which the character of interest appears by the total number of characters of all the document records.
The “k” item indicates the order of appearance of the character of interest,
The “Char” item indicates a character of interest, and “Monogr”
The “am-index” item indicates character group numbers grouped according to 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 the character types are as small as 16 types, there is no character group including two or more characters.

As described above, 1 of the sample document data 101
When the second scanning is completed, the document delimiter 103 starts the second scanning of the sample document data 101 and converts the cut document record into a two-character continuous appearance frequency calculating unit 10.
Send to 5. The two-character continuation frequency calculation means 105 extracts only continuation of high-frequency characters (in this example, all character types correspond to high-frequency characters) from two-character continuation in the document record. The appearance of two consecutive characters is
It is calculated by “the sum of the number of characters of the document record 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 refinement rate,
The "high-frequency two-character continuation table" shown in FIGS.

In FIG. 6, the “No.” item indicates a serial number of two consecutive high-frequency characters, and “Digram-Cod”.
The item “e” represents a set in which the first character and the second character constituting two consecutive characters are represented by a character group number, and “Digra”
The “m-Character” item represents a character string forming two consecutive characters, and the “Occ” item represents the total number of characters of a document record in which two consecutive characters of interest appear, and “(Per
The “cent)” item represents a value obtained by multiplying the value obtained by dividing the total number of characters of the document records in which two consecutive characters of interest appear by the total number of characters of all the document records by 100. For example, it can be seen that the appearance degree of two consecutive characters “-4” having the serial number 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 Are grouped by the two-character continuation grouping means 108. When grouping, the method of calculating the degree to which any two consecutive characters of a group appear is based on the assumption that the appearance of each two consecutive characters in the group is statistically independent.
It is calculated from the following equation.

[0024]

(Equation 1) Here, P is the degree of appearance of any of n consecutive two characters in the group, and P _j (j = 1, 2,... N) is the degree of appearance of the jth two consecutive characters in the group. is there.

The result is the “grouping result of two consecutive characters” in FIG. In FIG. 8, the "No."
Represents a group number consisting of two consecutive characters, "Digram-C
The “mode” item is the first character of a two-character continuation having the largest character string order among the groups located at the boundary between the groups.
Represents the character group number of the character and the second character, "Digr
The “am-Character” item indicates a character string that forms the two-character continuation. For example, two-character continuous group number 7 includes two-character continuous “22” and “23”, and two-character continuous group number 8 includes two-character continuous “2”.
5 "," 26 "," 27 ", and" 29 ".

Thus, the sample document data 101-2
When the first scanning is completed, the document separating unit 103 starts the third scanning of the sample document data 101, and converts the extracted document record into the three-character continuous appearance frequency calculating unit 10.
Send to 6. The three-character consecutive appearance frequency calculation unit 106 determines that (first character, second character) and (second character, third character) are both high-frequency two out of three consecutive 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 determined as “the total number of characters of the document records in which the consecutive three characters appear / the total number of characters of all the document records”.
Is calculated, and the result is sent to the three-character continuous grouping means 109, and is grouped based on the narrowing-down ratio according to the same criterion as in the equation (1). The results are displayed in the “high-frequency three-character continuation table” in FIGS. 9 to 18 and the “three-character continuation grouping result” in 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 indicates a character group number of a first character, a second character, and a third character of three consecutive characters, and “Trigram-Ch”
The “aractor” item represents a character string that forms the three consecutive characters, and the “Occ” item represents the total number of characters of a document record in which the three consecutive characters of interest appear, and “(Perc
ent) "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 three consecutive characters of interest appear by the total number of characters of all the document records.

In FIG. 19, the item “No.” represents a group number of three consecutive characters, and “Trigraph”.
The “m-Code” item indicates the first and second character group numbers of two consecutive characters in 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 constituting the three consecutive characters. For example, a group number 138 having three consecutive characters has 3
Character continuation "202", "203", "205", "20"
6 "," 207 "," 209 ", and" 204 ".

The obtained grouping information is sent to the index type output means 110, and the low-frequency 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. FIG. 2 shows the size of the created index per document record.
No. 3 “index size”.

In FIG. 23, "1) Monogram
The “-index:” item indicates the size of the low-frequency character index, “2) Digram-index:” indicates the size of the index of two consecutive characters, and “3) Trigram-
The “index:” item indicates the size of an index of three consecutive characters, and the “Total Index size:” item is
1) represents the size of the index per document record obtained by summing up 2) and 3). In this example, an index of a total of 32 bytes is created for one document record.

As described above, according to the present embodiment, from the degree of appearance of characters and character strings in sample document data, for characters that frequently appear, two-character continuation information is used.
By creating more detailed index information and creating more detailed two-character continuation information using the three-letter continuity information, more frequently occurring characters and character strings can be created. High-precision index type data can be created,
Conversely, for characters and strings that do not appear often,
By grouping, index type data in which the capacity of index information is reduced can be created.

(Embodiment 2) 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 creation device according to the second embodiment of the present invention. In FIG. 2, reference numeral 201 denotes search target document data storing a plurality of document records, 202 denotes search target document punctuation data in which the position of each document record in the search target document data 201 is recorded, and 203 denotes search target document punctuation 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 head of the record is added to the head of the document record, and a special character <EN indicating the end of the record is added.
D> a document delimiter for outputting a character string with the document record added to the end of the document record; 204, index type data created by the index creation device shown in FIG. Receiving
A character continuation number calculating means for determining, based on the index type data 204, whether the number of search characters to be used at the time of creating an index of a character string starting from each character appearing in the search target document data 201 is 1, 2 or 3. , 206 are group number calculating means for receiving the number of characters as the calculation result of the character continuation number calculating means 205 and the definition of the group of character strings and index type data, and calculating the corresponding group number;
Reference numeral 207 denotes an index information storage and output unit that receives the group number output from the group number calculation unit 206 and creates and outputs index information of one document record. Reference numeral 208 denotes search target data 201 output by the index information storage and output unit 207.
Is index data for

The operation of the index creating apparatus configured as described above will be described with reference to an example of a report output output when the index creating apparatus shown in FIG. 24 operates.
In FIG. 24, “<STA” of Record No. 2
RT> 4-587-5151-X <END> ”is a result of extracting the second record of the search target data. When this character string is sent to the character continuation number calculating means 205, first, each character is converted into a character group number, and then the character continuation number is calculated according to the index type data 204. The character string in this example can be expressed as “0,
2, 3, 9, 6, 11, 3, 7, 7, 10, 5, 4,
3, 10, 1 ". Then, at the beginning "<START
>, 4 ”is cut out as a two-character continuation 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 accumulation and output means 207 Receiving this, the 0th bit string inside is changed from hexadecimal “0000” to 16
Change to hexadecimal "0001". "4," the second character from the beginning
In the case of three characters “−, 5”, the characters are cut out as a group of three characters consecutively by a set 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 internal bit string to hexadecimal "00".
"00" to hexadecimal "0100". In this way, the index information of the second record is accumulated in the bit string inside the index information accumulation and output means 207 in the form of a bit string while moving the character of interest one after another. When the processing of the last character is completed, the accumulated bit string is stored in the index data 20.
8 is output. By sequentially performing the above processing for each document record, finally, the search target data 101
Index information about all document records in the index data 2
08, and the index creation processing ends.

As described above, according to the index creating apparatus of this embodiment, if the index type data 204 is similar in the appearance of characters and character strings to the search target document data, the index type data 204 Without examining the search target document data using the statistical information in, for more characters, create more detailed index information using the two-character continuous information, and use the two-character continuous In
By creating more detailed index information using three-character continuous information, characters and character strings that appear frequently
High-precision index data can be created. Conversely, for characters and character strings that do not appear often,
Index data in which the capacity of index information is reduced can be created.

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 one embodiment of a document search device using the document search method of the present invention. 3, reference numeral 301 denotes search target document data storing a plurality of document records; 302, search condition input means for a user to input search conditions; 303, an index shown in FIG. Index data created using the creation device, 304
Is a full-text scanning character string matching 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 denotes 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. An index collation condition creating unit 306 collates the index data 303 with the index collation condition created by the index collation condition creating unit 305, and obtains information of the collated document record. Is sent to the full-text scanning character string matching means 304, and 307 is a search result output by the full-text scanning character string matching means 304.

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

As described above, according to the document search apparatus of the present embodiment, the 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. , It is possible to execute a high-speed document search even in the case of a complicated search condition which can be conventionally handled only by the full text scan method.

[0038]

As is apparent from the above embodiments, the present invention statistically examines the appearance of characters and character strings in sample document data when creating index data relating to search target document data and performs the index search. In addition to creating index type data as common information when creating data, creating index data relating to the search target document data in accordance with the type of the index type data, in the index type data creating step, the appearance of the character string is statistically determined. As an operation to check the characteristics, it is determined that an index is created with one character for a character having a certain frequency or less (low-frequency character), and for a character having a certain frequency or more (high-frequency character), two characters between the high-frequency characters are determined. Check character continuity,
Next, it is determined that an index should be created with two characters for two consecutive characters having a certain frequency or less (low-frequency two consecutive characters), and for two characters having a certain frequency or more (two consecutive high-frequency characters), By sequentially performing an operation of checking for three consecutive characters between two consecutive high-frequency characters, it was determined that an index was created as a longer character sequence for a higher-frequency character string .
An index creation method and device that creates index type data of the contents, so that the creation / update time is short, the capacity is small, and an approximate search with a complex character string pattern such as a regular expression can be performed at high speed. Further, it is possible to realize a high-speed document search apparatus that combines created index data and full-text scan.

In particular, when there are a large number of documents to be searched in which the degree of appearance of characters and character strings does not change much, or when the documents to be searched are frequently updated, the index format data may be created once. You can create very small amounts of index data very quickly,
The speed of full-text scanning can be increased, and the effect is great. By the way, if the index data according to the present invention is used, when one year's worth of newspapers of the national newspaper is searched with one keyword, the search speed can be improved by about 20 times compared with the related art.

[Brief description of the drawings]

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

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

FIG. 3 is a block diagram illustrating 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 showing a report output relating to an index type creation process in the first embodiment.

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

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

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

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

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

FIG. 11 is a list showing a report output relating to an index type creation process in the first embodiment.

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

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

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

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

FIG. 16 is a list showing a report output relating to an index type creation process in the first embodiment.

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

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

FIG. 19 is a view showing a list of reports output regarding the index type creation processing in the first embodiment.

FIG. 20 is a list showing a report output relating to the index type creation processing in the first embodiment.

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

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

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

FIG. 24 is a list 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 in the third embodiment.

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

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

[Explanation of symbols]

 101 sample document data 102 sample document separation data 103 document separation means 104 character appearance frequency calculation means 105 two-character continuous appearance frequency calculation means 106 three-character continuous appearance frequency calculation means 107 character grouping means 108 two-character continuous grouping means 109 three 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 continuation 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

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-5-174064 (JP, A) Kikuchi, "A technique for high-speed full-text search for Japanese documents," Informatics Basics, No. 25-2, May 12, 1992, p. 9-16 Ando, Sugano, Ito, Tamura, Tsurubayashi, Hayakawa, "Full-text database system" Kenzo-kun "", Advanced Data System System Symposium '90, December 5, 1990, p. 17-25 (58) Field surveyed (Int. Cl. ⁷ , DB name) G06F 17/30 G06F 17/21 JICST file (JOIS)

Claims (5)

(57) [Claims] A step of statistically examining the appearance of characters and character strings in sample document data to create index type data serving as common information when creating the index data; and searching according to the type of the index type data. Creating index data relating to the target document data. In the index type data creating step, as an operation of statistically examining the appearance of the character string, one character is used for characters having a certain frequency or less (low-frequency characters). It is determined that an index is to be created, and for characters having a certain frequency or higher (high-frequency characters), two consecutive characters between high-frequency characters are checked. For ()), it is decided to create an index with two characters, and for two consecutive characters of a certain frequency or more (high-frequency consecutive two characters), three consecutive characters of high-frequency consecutive two characters By sequentially performing an operation to investigate, it decides to create more frequent string, the index as long character sequence
An index creation method characterized by creating index type data of contents . 2. A character appearance frequency calculating means for statistically examining a degree of appearance of a certain character in sample document data, and a character appearance frequency calculating means for determining whether the degree of appearance of a character examined last time is higher than a predetermined value. A plurality of N-character consecutive appearance frequency calculating means for statistically examining the degree of appearance of N character strings (N is a natural number of 2, 3, 4,...) Including all of the checked characters; It becomes common information when creating index data on search target document data 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 a character or a character string in data. An index creation device comprising: index type output means for creating index type data. A plurality of grouping means for grouping characters or character strings in the sample document data in accordance with the degree of appearance thereof, wherein the index type output means outputs the grouping output from each of the grouping means. 3. The index creation device according to claim 2, wherein a correspondence table between a serial number of each group and a character or character string belonging to the group is output based on the information. 4. A character continuation number calculating means for determining the number of search characters to be used when generating index data relating to search target document data according to index type data output from the index creation device according to claim 3, and said character continuation number A group number calculating means for calculating a corresponding group number from the number of characters determined by the calculating means and the index type data output from the index creating device according to claim 3, and a group number output from the group number calculating means. An index creation device comprising: index information accumulation output means for creating index data for each document record. 5. A search input means for inputting a search condition including a character string pattern, and a character or character string for collating index data output from the index creation device according to 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 a full-text scanning character string matching unit that matches a corresponding part of the search condition with a search condition including a character string pattern input from the search condition input unit, and outputs a part that has been successfully matched as a final search result. Search device.