JPH08314964A - Index model creation device - Google Patents

Abstract

(57) [Summary] [Purpose] In a document retrieval system using an electronic computer, the indexing unit of the signature file based on the pre-search method is appropriately selected according to the user's request, the user's search history, and the index capacity. Enables fast search by setting. [Structure] For a character and a character string designated by the user by the special category input means 112, the search speed is improved in response to a search request including them. Further, by providing a search request character string appearance frequency calculating means, the search speed is improved in response to a search request frequently used by the user. Further, the maximum index amount input means is provided to specify the upper limit of the index amount, and the narrowing rate calculation means is provided to automatically create an index type having a narrowing rate within a range not exceeding the maximum index amount.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an index type creating apparatus for searching a character string or the like from a document in a document searching 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, the increase in storage capacity of computers, the practical use of character recognition by computers, and the like, the number of full-text databases that store all character information in documents has increased. There is. Therefore, there is an increasing interest in a full-text database search system that accumulates a large amount of character information and retrieves 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, problems such as keyword addition work not keeping up with the increase of accumulated documents, keywords becoming obsolete over time, and omission of search due to difference in interpretation of keywords between the person who made the keywords and the one to be searched. was there. 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 does not use information other than the original document, so it requires less storage capacity and can be searched immediately immediately after updating the document data, and character string patterns and logical expressions such as regular expressions. The advantage is that the search time is almost constant even when the search conditions are complicated including conditions or there are many search results. However, since the entire document data is scanned, the search time is slower than the index method. A problem has been pointed out.

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.

As a solution to the problems of the index system,
There is a pre-search method using a signature file. Among them, the applicant of the present application has proposed a method of grouping according to the frequency of appearance of characters or character concatenation to create a signature file type (Patent Application 1993, Second Edition).
53032). FIG. 4 is a block diagram showing the configuration of the index type creating apparatus according to the embodiment of this method. Each document record in the sample document data 401 is cut out by the document delimiter 403 based on the position information from the sample document delimiter data 402, and the character appearance frequency calculation unit 404 statistically checks the degree of appearance of each character. The character grouping unit 407 groups a plurality of characters with respect to low-frequency characters whose appearance degree is a predetermined value or less, that is, a narrowing-down rate or less. At this time, the characters are sorted so that the degree of appearance of at least one of the characters belonging to the group does not exceed a predetermined narrowing rate. For high-frequency characters whose degree of appearance in the sample document data 401 exceeds the narrowing-down rate, the two-character consecutive appearance frequency calculation means 405 checks the degree of appearance in two-character consecutive sample document data consisting of two high-frequency characters. As for the low-frequency two-character continuous character whose degree of appearance is less than or equal to the narrowing-down rate, the two-character continuous grouping unit 408 performs grouping as in the case of characters. For high-frequency 2 consecutive characters whose degree of appearance exceeds the screening rate, high-frequency 2
Two consecutive two characters belonging to a consecutive character are the first two
The three-character consecutive appearance frequency calculation unit 406 examines the degree of appearance of characters and the three-character consecutive sample documents of the last two characters, and 3 for low-frequency three-character consecutive cases where the degree of appearance is less than the narrowing rate. Grouping is performed in the same manner as in the case where the character continuous grouping means 409 is for characters or two characters in succession. For high-frequency 3 consecutive characters, each group consists of only 3 high-frequency consecutive characters. After that, the index type output means 410 outputs the index type data 411 which assigns 1-bit index information to each group.

In this way, even if the degree of appearance of characters and character strings is different, it is possible to narrow down the document data to be searched to below the narrowing rate regardless of the search conditions, and many types of low-frequency characters Even if there is, it is possible to create index type data that makes it possible to create a small index.

[0009]

However, in the above-mentioned conventional technique for grouping characters and character strings, how often the characters and character strings having a low frequency of appearance in the sample document are used for the user's search request. Irrelevant, since the degree to which at least one of the characters and character strings belonging to the group appears is grouped so that it does not exceed the predetermined narrowing rate, the search speed is improved by the reciprocal of the narrowing rate. There was a problem that the search speed could not be improved beyond that level.

The parameter that can be set by the user is the narrowing down rate of the documents to be searched, and the index data amount that changes depending on the narrowing down rate cannot be known in advance. Therefore, when the storage capacity is limited, the index type There is a problem that it takes time to create the necessary index type data because it is necessary to repeatedly create the data and obtain an appropriate narrowing rate.

The present invention solves the above-mentioned problems of the prior art. For a specific search request set by the user, or for a search request frequently used by the user checked from past search histories. It is an object of the present invention to provide an index type creating apparatus that enables a high-speed search that exceeds the reciprocal of the narrowing rate without reducing the search speed for other search requests. It is another object of the present invention to provide an index type creating device capable of creating an index type by automatically setting an appropriate narrowing rate by directly giving a limit to the amount of index data.

[0012]

In order to achieve the above-mentioned object, the index type creating apparatus according to the present invention comprises special section input means for designating a character or a character string to be included in a single group consisting of only one element, In addition, a character appearance frequency calculation means that statistically examines the degree of appearance of one character in the sample document data, which is possessed by the index creation device according to the related art, and the degree of appearance of the previously examined character is higher than a certain value. , N characters (N is 2,
A plurality of N character consecutive appearance frequency calculation means for statistically checking the degree of appearance of a character string of 3, ...
The character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means and the plurality of grouping means for grouping characters or character strings from the output of the special classification input means are provided.

Further, the index type creating apparatus according to the present invention is provided with a search request character string appearance frequency calculating means for calculating the appearance frequency of the search request character string in the past search request history. , A character appearance frequency calculation means for statistically checking the degree of appearance of one character in the sample document data, and includes all of the previously examined characters when the degree of appearance of the previously examined character is higher than a certain value A plurality of N-character consecutive appearance frequency calculation means for statistically examining the degree of appearance of a character string of N characters (N is a natural number of 2, 3, ...), a character appearance frequency calculation means, and a plurality of N
It is provided with a plurality of grouping means for grouping characters or character strings from the output of the character continuous appearance frequency calculating means and the output of the search request character string appearance frequency calculating means.

Further, the index type creating apparatus according to the present invention has a character appearance frequency calculating means for statistically checking the degree of appearance of one character in the sample document data, and a character appearance frequency calculating means which is previously examined and is higher than a certain value. And a plurality of N character consecutive appearance frequency calculation means for statistically checking the degree of appearance for an N character string (N is a natural number of 2, 3, ...) Including all of the characters checked last time, if high. A maximum index amount input means for inputting a limit on the amount of index data, an output of the character appearance frequency calculation means and a plurality of N character consecutive appearance frequency calculation means and an output of the maximum index amount input means Of the character appearance frequency calculating means and the character appearance frequency calculating means and the N character consecutive appearance frequency calculating means, and outputs the result to the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means. It is obtained by a plurality of grouping means for grouping a character or character string from the output of the fine plurality of N characters continuous occurrence frequency calculating means.

[0015]

According to the present invention, the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means check the degree of appearance of the character or the character string in the sample document data with respect to the predetermined narrowing down rate. Then, when the grouping means determines the classification of characters and character strings, the low-frequency characters of the constituent characters of the characters and character strings input by the special classification input means are registered as a group consisting of only those characters. By doing so, when searching with a search request character string including them, it is possible to create an index type that enables a higher speed search without reducing the search speed for other search requests.

Further, after the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means examine the degree of appearance of a character or a character string in the sample document data with respect to a predetermined narrowing down ratio, grouping is performed. When the means determines the classification of the character and the character string, the appearance frequency of the search request character string in the past search request history is calculated by the search request character string appearance frequency calculation means, and regarding the search request character string that appears at high frequency, Of the constituent characters, those that are infrequent characters in the sample document are registered as a group consisting of only those characters, so that the index type that enables high-speed search for the search request frequently used by each user is automatically created. Can be created dynamically.

Further, the degree of appearance of a character or a character string in the sample document data is examined by a character appearance frequency calculating means and a plurality of N character consecutive appearance frequency calculating means with respect to a predetermined narrowing rate, and the narrowing rate calculating means is calculated. Calculates the narrowing rate from the appearance frequency of characters and character strings with the index amount input by the maximum index amount input means as the upper limit, and then calculates the appearance frequency of characters or character strings again for this narrowing rate. Even if the storage capacity is limited, the preset maximum index amount is not exceeded by the means and the plurality of N character consecutive appearance frequency calculation means, and then the grouping means determines the division of the character and the character string. It is possible to create an index type that can achieve the highest speed in the range in a short time.

[0018]

【Example】

(First Embodiment) A first embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the configuration of an index type creating device according to the 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 101 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. Reference numeral 102 denotes sample document delimiter data in which the positions of the respective document records in the sample document data 101 are recorded. Reference numeral 103 denotes a designated document record cut out from the sample document data 101 according to the position information of the sample document delimiter data 102.
A special character <START> indicating the beginning of the record is added to the beginning of the document record, and a special character <indicating the end of the record <
END> is a document delimiter for outputting a character string added to the end of the document record. Reference numeral 104 is a document delimiter output from the document delimiter 103. The document delimiter 103 indicates the degree of appearance of each character appearing in the sample document data 101. A character appearance frequency calculation means for calculating as "a value obtained by dividing the total number of characters of the document records in which the character appears by the total number of characters of all document records", 105 is a document record character string output from the document delimiter means 103, Sample document data 1 based on the calculation result of the character appearance frequency calculation means 104
2 consecutive characters appearing in 01 are calculated as the degree of occurrence of 2 consecutive characters "the value obtained by dividing the sum of the number of characters of the document records in which the two consecutive characters appear by the sum of the number of characters of all document records". A frequency calculation means 106 receives the document record character string output from the document delimiter means 103 and the calculation result of the two-character consecutive appearance frequency calculation means 105, and appears frequently in the sample document data 101.
Three-character consecutive appearance frequency calculating means for calculating the degree of appearance of consecutive characters as "value obtained by dividing total sum of the number of characters of the document record in which the consecutive three characters appear by total sum of the number of characters of all document records", 107 is a character appearance frequency A range in which, after receiving the calculation result of the calculation means 104, a plurality of characters whose appearance degree is less than or equal to a predetermined “narrowing rate” are grouped and the degree to which any character belonging to the group appears does not exceed the narrowing rate. The character grouping means 108 for adjusting so as to be closest to the narrowing-down rate, 108 receives the calculation result of the two-character consecutive appearance frequency calculating means 105, and groups a plurality of two-character consecutively whose degree of appearance is less than or equal to the narrowing-down rate. , Adjust so that the degree to which any two consecutive characters belonging to the group appear is closest to the narrowing rate within the range that does not exceed the narrowing rate. 2 character continuous grouping means that, 10
9 receives the calculation result of the three-character consecutive appearance frequency calculation means 106, and a plurality of 3 whose degree of appearance is less than or equal to the narrowing rate
If there are consecutive characters, group them and adjust the degree of occurrence of any three consecutive characters belonging to the group to be the closest to the narrowing rate within the range that does not exceed the narrowing rate. 3 character consecutive grouping means for making 3 groups of consecutive 3 characters higher than the rate into one group by one, 110 is an output of the character grouping means 107, 2 character consecutive grouping means 108 and 3 character consecutive grouping means 109. Index type output means for receiving certain grouping information, assigning serial numbers to each group, and outputting a correspondence table of serial numbers of each group and belonging characters or two consecutive characters or three consecutive characters, 111 is an index type output means 110. Is the index type data output by. And
Reference numeral 112 is a special classification input means for instructing the character grouping means 107 to create a group consisting of only designated elements.

The operation of the index type creating apparatus constructed as described above will be described. First, each document record in the sample document data 101 is a document delimiter 10
It is cut out in 3 and sent to the character appearance frequency calculation means 104, and the degree of appearance of each character is calculated by the sum of the number of characters of the document record in which the corresponding character appears / the sum of the number of characters of all the document records. The user uses the special category input means 11
Input the search request character string whose search speed is to be improved by 2. The character grouping unit 107 receives the calculation result of the character appearance frequency calculating unit 104, groups a plurality of characters whose degree of appearance is equal to or less than a predetermined “narrowing rate”, and determines which of the characters belonging to the group. The degree of appearance should be adjusted to be the closest to the narrowing rate within a range that does not exceed the narrowing rate. At this time, the calculation method of the degree of appearance of any character in the group is calculated from the following formula, assuming that the appearance of each character in the group is statistically independent.

[0020]

[Equation 1] However, P is the degree to which any of the n characters in the group appears, and Pj (j = 1, 2, ..., N) is the degree to which the j-th character in the group appears.

When grouping, the special section input means 1
For the characters input in 12 or for each character string, of the constituent characters, for the characters whose result by the character appearance frequency calculation means 104 is low in frequency, those low frequency characters are registered as a single group consisting of only those characters. .

When the first scan of the sample document data 101 is completed, the document delimiter 103 starts the second scan of the sample document data 101 and sends the clipped document record to the two-character consecutive appearance frequency calculator 105. .
The two-character consecutive appearance frequency calculation unit 105 extracts only the consecutive high-frequency characters from the two-letter consecutive letters in the document record, and the degree of appearance of each two-letter consecutive letters is “the document record in which the two-letter consecutive letters appear. Of the total number of characters / total number of characters in all document records ". The degree of appearance of any two consecutive characters belonging to a group is equal to or less than the narrowing rate based on the same criteria as in the formula (1) for all of the consecutive two characters consisting of high-frequency characters other than the frequent two-character consecutive. The two-character continuous grouping unit 108 groups the characters.

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 grouped based on the narrowing-down rate according to the same criteria as in formula (1).

The grouping information thus obtained is sent to the index type output means 110, and the low frequency character groups, 2
An index type that assigns 1-bit index information to each of the character continuous group and the three character continuous group is output to the index type data 111.

As described above, according to the present embodiment, the characters that do not appear in the sample document very much, but the user wants to search at high speed, should be designated as a special classification and not grouped. Thus, it is possible to create an index type that enables a high-speed search for a search request including the character without increasing the index capacity too much and reducing the search speed for other search requests. .
In particular, when searching with one character specified in the special category, the narrowing rate is c, and the degree of occurrence of the character in the document is c '.
If (c ′ <c <1), the conventional method for grouping requires full-text scanning of documents that are c times the total amount of documents, whereas according to the present embodiment, all documents are scanned. The search speed is increased by c / c 'times, since only full text scans of documents of c'times the quantity are required.

(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 type creating device according to the second embodiment of the present invention. In FIG. 2, 201 is sample document data, 202 is sample document delimiter data, and 203.
Is a document delimiter, 204 is a character appearance frequency calculator, 2
Reference numeral 05 is a two-character continuous appearance frequency calculation means, 206 is a three-character continuous appearance frequency calculation means, 207 is a character grouping means, 2
Reference numeral 08 is a two-character continuous grouping means, 209 is a three-character continuous grouping means, 210 is an index type output means, and 211 is index type data. Further, 212 is the search request history data, 213 is the occurrence frequency of the search request character string from the past search request history data 212, and creates a group consisting of only a single element for the character grouping means 207. It is a means for calculating the frequency of appearance of a search request character string.

The operation of the index type creating apparatus constructed as described above will be described. First, each document record in the sample document data 201 is stored in the document delimiter 20.
It is cut out in 3 and sent to the character appearance frequency calculation means 204, and the degree of appearance of each character is calculated by the sum of the number of characters of the document record in which the corresponding character appears / the sum of the number of characters of all the document records. The character grouping unit 207 receives the calculation result of the character appearance frequency calculating unit 204, groups a plurality of characters whose degree of appearance is less than or equal to a predetermined “narrowing rate”, and determines whether any of the characters belonging to the group The degree of appearance should be adjusted to be the closest to the narrowing rate within a range that does not exceed the narrowing rate. At this time, the calculation method of the degree of appearance of any character in the group is calculated from the equation (1), assuming that the appearance of each character in the group is statistically independent. Further, when grouping, the search request character string appearance frequency calculation unit 213 causes the search request history data 212 to be displayed.
The character appearance frequency calculation means 2 among the constituent characters of the search request character or the character string having a high appearance frequency calculated from
As for the character whose result of 04 is infrequent, each of those infrequent characters is registered as a single group consisting of only that character.

After the first scanning of the sample document data 201 is completed, the document delimiter 203 starts the second scanning of the sample document data 201 and sends the clipped document record to the two-character consecutive appearance frequency calculation unit 205. .
The two-character consecutive appearance frequency calculation unit 205 extracts only the consecutive high-frequency characters from the two-letter consecutive letters in the document record, and the degree of appearance of each two-letter consecutive letters is “the document record in which the two-letter consecutive letters appear. Of the total number of characters / total number of characters in all document records ". The degree of appearance of any two consecutive characters belonging to a group is equal to or less than the narrowing rate based on the same criteria as in the formula (1) for all of the consecutive two characters consisting of high-frequency characters other than the frequent two-character consecutive. The two-character continuous grouping unit 208 groups the characters.

Thus, 2 of the sample document data 201
When the scanning of the third time is completed, the document dividing means 203 starts the third scanning of the sample document data 201, and the cut-out document record is calculated by the three-character consecutive appearance frequency calculating means 20.
Send to 6. The three-character continuous appearance frequency calculation unit 206 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 consecutive grouping means 209 and grouped based on the narrowing-down rate according to the same criteria as in formula (1).

The grouping information thus obtained is sent to the index type output means 210, and the low frequency character groups, 2
An index type that allocates 1-bit index information to each of the character continuous group and the three character continuous group is output to the index type data 211.

As described above, according to the present embodiment, a character that does not appear frequently in the sample document but is frequently used by the user as a search request is automatically selected from the search request history. By not grouping the characters, an index that enables high-speed search according to each user without significantly increasing the index capacity and reducing the search speed for other search requests A model 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 the configuration of the index type creating device according to an embodiment of the present invention. In FIG. 3, 301 is sample document data, 302 is sample document delimiter data, 303 is document delimiter, 304 is character appearance frequency calculator, 305.
Is a two-character consecutive appearance frequency calculation means, 306 is a three-character consecutive appearance frequency calculation means, 307 is a character grouping means, 308
Is a 2-character continuous grouping means, 309 is a 3-character continuous grouping means, 310 is an index type output means, and 311 is index type data. Then, 312 is a maximum index amount input means for inputting the maximum amount of the index to be created, 313 is an input from the maximum index amount input means 312 and the character appearance frequency calculation means 3
The calculation result of 04, the calculation result of the two-character continuous appearance frequency calculation means 305, and the calculation result of the three-character continuous appearance frequency calculation means 306 are received to calculate the narrowing rate, and the result is again calculated with the character appearance frequency calculation means 304 and two characters. It is a narrowing-down rate calculating means for outputting to the consecutive appearance frequency calculating means 305 and the three-character consecutive appearance frequency calculating means 306.

The operation of the index type creating apparatus constructed as above will be described. First, each document record in the sample document data 301 is stored in the document delimiter 30.
It is cut out in 3 and sent to the character appearance frequency calculation means 304, and the degree of appearance of each character is calculated by "total sum of character numbers of document records in which the corresponding character appears / total sum of character numbers of all document records". Let N be the total number of characters that appear in the document, let a character with an appearance frequency higher than a predetermined value c as the initial value of the narrowing rate be a high-frequency character (the number of which is α (c)), and the other characters. Characters are infrequent characters.

When the first scan of the sample document data 301 is completed, the document delimiter 303 starts the second scan of the sample document data 301 and sends the clipped document record to the two-character consecutive appearance frequency calculator 305. .
The two-character consecutive appearance frequency calculation unit 305 extracts only the consecutive high-frequency characters from the two-letter consecutive letters in the document record (the total number of which is W (c)), and the appearance degree of each two-letter consecutive letters. Is calculated by "total sum of the number of characters of the document record in which two consecutive characters appear / total sum of the number of characters of all document records". Two consecutive characters having a higher appearance frequency than c are defined as two consecutive frequently occurring characters (the number of them is β (c)).

Thus, 2 of the sample document data 301
After the scanning of the third time is completed, the document dividing means 303 starts the third scanning of the sample document data 301, and the cut-out document record is calculated by the three-character consecutive appearance frequency calculating means 30.
Send to 6. The three-character continuous appearance frequency calculation unit 306 has a high frequency of (First character, Second character) and (Second character, Third character) of the three consecutive characters in the document record.
Extract only 3 consecutive characters (the total number is T
(C)), the degree of appearance of each three consecutive characters is calculated by "total sum of the number of characters of the document record in which the consecutive three characters appear / total sum of the number of characters of all document records". c
A series of three characters having a higher appearance frequency than the above is defined as a series of high-frequency three characters (the number thereof is γ (c)).

The character appearance frequency distribution with respect to the initial value c of the narrowing down ratio thus obtained, the two character continuous appearance frequency distribution, 3
Based on the character continuous appearance frequency distribution and the upper limit of the index amount input by the maximum index amount input means 312, the narrowing-down rate calculating means 313 determines the narrowing-down rate by the following method without checking the appearance frequency distribution again.

The character appearance frequency distribution depends on the narrowing rate.
It does not change. Therefore, the narrowing rate c₁High frequency
The number of degree characters is directly known from the character appearance frequency distribution examined previously.
It is possible to use α (c₁). Appear in the document
The number of two consecutive high-frequency characters is the same as any high-frequency character.
Assuming that it is proportional to the total number of combinations,
Rate c₁The number of consecutive two characters W (c
₁) Is represented by equation (2). W (c₁) = W (c) × {α (c₁)²/ Α (c)²} (2) Narrowing rate c₁2 characters consecutive appearance frequency distribution (x axis
To (rank, appearance frequency on the y-axis) is the narrowing rate
Expand / shrink the distribution of the appearance frequency of two consecutive characters in c in the x-axis direction
Assuming that it is small, the narrowing rate c₁Against
Number of two consecutive letters β (c₁) Is for the narrowing rate c
The appearance frequency is c in the two-character continuous appearance frequency distribution ₁Get higher
Number of consecutive two letters β '(c₁) Is used as in equation (3)
Can be represented. β (c₁) = Β ′ (c₁) × {W (c₁) / W (c)} = β '(c₁) × {α (c₁)²/ Α (c)²} (3)

In addition, among the three consecutive characters appearing in the document, three consecutive characters such that (first character, second character) and (second character, third character) are high-frequency two consecutive characters. the number of, when assumed to be proportional to the total number of any high frequency second character sequence among the combination, the number of the conditions are satisfied 3 character sequence when the narrowing ratio c ₁ T (c ₁₎ has the formula (4)
Represented by T (c ₁ ) = T (c) × {β (c ₁ ) ² / β (c) ² } (4)

Narrowing rate c₁When 3 characters appear consecutively
The degree distribution is the frequency of occurrence of three consecutive characters at the narrowing rate c.
Assuming that the cloth is scaled in the x-axis direction,
Rate c₁The number of high-frequency three-character continuous γ (c₁) Is
In the three-character continuous appearance frequency distribution for the narrowing rate c
Appearance frequency is c₁Higher number of consecutive three letters γ '
(C ₁) Can be expressed as in equation (5). γ (c₁) = Γ ′ (c₁) × {T (c₁) / T (c)} = γ '(c₁) × {β (c₁)²/ Β (c)²} (5)

The size of the created index is obtained by multiplying the total number of low-frequency character groups, low-frequency 2-character continuous groups, and 3-character continuous groups obtained by each of the subsequent grouping means by the number of document records R (unit: unit). bit). The sum of the frequency of occurrence of low frequency character for narrowing ratio c ₁ S ₁
Then, the number of infrequent character groups can be approximated as S ₁ / c ₁ . The sum S ₂ of the appearance frequencies of two low-frequency consecutive characters with respect to the narrowing-down rate c ₁ is 3 straight lines x = β (c ₁ ), x = W
(C ₁ ), y = 0 and the area surrounded by the curve of the two-character continuous appearance frequency distribution for the narrowing-down rate c ₁ ,
Area surrounded by three straight line x = β '(c ₁ ), x = W (c), y = 0 and the curve of the two-character continuous appearance frequency distribution for the narrowing-down rate c, that is, the two-character continuous appearance frequency for the narrowing-down rate c 2 where the frequency of occurrence is less than or equal to c ₁ in the distribution
It can be expressed as in Expression (6) using the sum S ₂ 'of the appearance frequencies of consecutive characters. S ₂ = S ₂ '× {W (c ₁ ) / W (c)} = S ₂ ' × {α (c ₁ ) ² / α (c) ² } (6)

As for the total number of consecutive 3 character groups, it is assumed that the number of consecutive high frequency 3 characters is negligibly small.
Consider only low frequency 3 consecutive letters. The sum S ₃ of the appearance frequencies of three consecutive low-frequency characters with respect to the narrowing-down rate c ₁ is 3 straight lines x
= Γ (c ₁ ), x = T (c ₁ ), y = 0 and narrowing rate c
Since it is considered to be the area surrounded by the curve of the three-character continuous appearance frequency distribution for ₁ , three straight lines x = γ ′ (c ₁ ), x = T
(C), the area surrounded by the curve of the three-character continuous appearance frequency distribution with respect to y = 0 and the narrowing rate c, that is, the narrowing rate c
In the three-character continuous appearance frequency distribution for
Sum of appearance frequencies of three consecutive characters that are less than or equal to ₁ S ₃ '
Can be expressed as in equation (7). _{S 3 = S 3 '× {} T (c 1) / T (c)} = S 3' × {β (c 1) 2 / β (c) 2} = S 3 '× {β' (c 1) ² / β (c) ² } × {α (c ₁ ) ⁴ / α (c) ⁴ } (7)

That is, the index size I (c ₁ ) (unit is bit) created when the narrowing-down rate c ₁ is calculated by the value calculated from each appearance frequency distribution at the narrowing-down rate c, Can be approximately calculated as follows. I (c ₁ ) = {(S ₁ + S ₂ + S ₃ ) / c ₁ } × R = [[S ₁ + S ₂ ′ × {α (c ₁ ) ² / α (c) ² } + S ₃ ′ × {β '(C ₁ ) ² / β (c) ² } × {α (c ₁ ) ⁴ / α (c) ⁴ }] / c ₁ ] × R ·· (8)

The narrowing-down rate calculating means 313 calculates the narrowing-down rate c ₁ that enables the creation of an index having a size equal to or smaller than the maximum index amount, and again the character appearance frequency calculating means 304, the two-character continuous appearance frequency calculating means 305, It outputs to the three-character consecutive appearance frequency calculation means 306.

The character grouping unit 307 receives the calculation result of the character appearance frequency calculating unit 304, groups a plurality of characters whose degree of appearance is the narrowing rate c ₁ or less, and one of the characters belonging to the group appears. The degree of adjustment is adjusted so that it is closest to the narrowing rate within a range that does not exceed the narrowing rate. At this time, the calculation method of the degree of appearance of any character in the group is calculated from the equation (1), assuming that the appearance of each character in the group is statistically independent.

The two-character continuous appearance frequency calculation means 305 extracts only the continuous high-frequency characters from the two-character continuous characters in the document record, and the appearance degree of each two-character continuous character is "the relevant 2".
It is calculated by the sum of the number of characters of document records in which consecutive characters appear / the sum of the number of characters of all document records. The degree of appearance of any two consecutive characters belonging to a group is equal to or less than the narrowing rate based on the same criteria as in the formula (1) for all of the consecutive two characters consisting of high-frequency characters other than the frequent two-character consecutive. 2 character continuous grouping means 30
8 group.

The three-character consecutive appearance frequency calculating means 306 calculates the (first character, second character) among the three-character consecutive characters in the document record.
Characters) and (2nd character, 3rd character) are both high-frequency 2 consecutive characters. Only 3 consecutive characters are extracted, and the degree of appearance of each 3 consecutive characters is “document record in which the consecutive 3 characters appear. Of the total number of characters / the total number of characters of all document records ", and the result is sent to the three-character continuous grouping means 309, and grouped based on the narrowing-down rate c _{1 according} to the same criteria as in formula (1). To be done.

The grouping information thus obtained is sent to the index type output means 310, and the low-frequency character group, 2
An index type that allocates 1-bit index information to each of the character continuous group and the three character continuous group is output to the index type data 311.

As described above, according to the present embodiment, even when the storage capacity of the computer is limited, an appropriate narrowing down rate is automatically obtained by directly giving the upper limit of the index data amount, and the index can be repeatedly displayed. It is possible to create an index model of a size that meets the requirements without repeating the model creation.

[0049]

As described above, according to the present invention, other than the specific search request set by the user or the search request frequently used by the user checked from the past search history, It is possible to create an index type that realizes an improvement in the search speed that exceeds the reciprocal multiple of the pre-specified narrowing rate without reducing the search speed for the search request.

Further, when the capacity of the storage device is limited, the user can set the upper limit of the index amount to be created, and it is not necessary to repeat trial and error many times to determine the optimum narrowing rate. This saves the user the trouble and shortens the total index model creation time.

[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 type creating device according to a second embodiment of the present invention.

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

FIG. 4 is a block diagram showing a configuration of an index type creating device according to a conventional technique.

[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 112 Special classification input means 201 Sample document data 202 Sample document break data 203 Document break means 204 Character appearance frequency calculation means 205 2 Character continuous appearance frequency calculation means 206 3 Character continuous appearance Frequency calculation means 207 Character grouping means 208 Two-character continuous grouping means 209 Three-character continuous grouping means 210 Index type output means 211 Index type data 212 Search request history data 213 Inspection Search request character string appearance frequency calculation means 301 Sample document data 302 Sample document delimiter data 303 Document delimiter means 304 Character appearance frequency calculation means 305 2 Character continuous appearance frequency calculation means 306 3 Character continuous appearance frequency calculation means 307 Character grouping means 308 2 Character continuous grouping means 309 3 Character continuous grouping means 310 Index type output means 311 Index type data 312 Maximum index amount input means 313 Narrowing rate calculation means 401 Sample document data 402 Sample document break data 403 Document break means 404 Character appearance frequency calculation Means 405 Two-character consecutive appearance frequency calculating means 406 Three-character consecutive appearance frequency calculating means 407 Character grouping means 408 Two-character consecutive grouping means 409 Three-character consecutive grouping means 410 Index type output means 411 Index type data

Claims (3)

[Claims] 1. A character appearance frequency calculation means for statistically checking the appearance degree of a certain character in sample document data, and when the appearance degree of the previously examined character is higher than a certain value,
N characters including all of the characters checked last time (N is 2, 3, ...
A natural number), a plurality of N-character consecutive appearance frequency calculation means for statistically examining the degree of appearance of a character string, and a special classification input means for specifying a character or character string to be included in a single group consisting of only one element , A plurality of grouping means for grouping characters or character strings from the outputs of the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means and the output of the special classification input means. Index model making device. 2. A character appearance frequency calculation means for statistically checking the appearance degree of a certain character in the sample document data, and when the appearance degree of the previously examined character is higher than a certain value,
N characters including all of the characters checked last time (N is 2, 3, ...
A natural number) of a plurality of N character consecutive appearance frequency calculating means for statistically checking the degree of appearance of the character string, and a search request character string appearance frequency for calculating the appearance frequency of the search request character string in the past search request history Calculating means, a plurality of grouping means for grouping characters or character strings from the outputs of the character appearance frequency calculating means and the plurality of N character consecutive appearance frequency calculating means and the output of the search request character string appearance frequency calculating means; An index type creating apparatus comprising: 3. A character appearance frequency calculation means for statistically checking the appearance degree of a certain character in the sample document data, and when the appearance degree of the previously examined character is higher than a certain value,
N characters including all of the characters checked last time (N is 2, 3, ...
A natural number), a plurality of N-character consecutive appearance frequency calculation means for statistically examining the degree of appearance of a character string, a maximum index amount input means for inputting a limit on the amount of index data, and the character appearance frequency calculation Means and the output of the plurality of N-character consecutive appearance frequency calculating means and the output of the maximum index amount input means, a narrowing down rate that enables the creation of an index having a size equal to or less than the maximum index amount is calculated, and the character appearance frequency calculating means is calculated again. And a narrowing-down rate calculating means for outputting a result to the plurality of N-character consecutive appearance frequency calculating means, and a group of characters or character strings from the output of the character appearance frequency calculating means and the plurality of N-character consecutive appearance frequency calculating means. An index type creating apparatus comprising a plurality of grouping means.