JPH03125263A - Retrieving method using phrase index for information retrieving system - Google Patents

Abstract

PURPOSE:To shorten the scanning time of the real data and to improve the character retrieving speed by selecting the candidate real data via a character index and a phrase index. CONSTITUTION:When the information is retrieved, a phrase produced from combination of characters included in a character string is extracted. Then the key value corresponding to the phrase is obtained, and an AND is obtained between the same position bits of a bit train corresponding to plural key values of a phrase index. Thus a data number shown by an on-bit is obtained and the data including a phrase of a character string is retrieved as the retrieving conditions. That is, the combination of the prescribed characters in expressed in an AND of several keys. Thus the total number of keys can be cut down to several thousands even though the permutations and combinations of optional two characters, for example, among several thousands of characters used in the Japanese sentences reach a large number, i.e., several ten millions. As a result, the retrieving time can be shortened in terms of combinations of characters.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to an information retrieval system for searching data matching search conditions from a database consisting of a large amount of character information in Japanese or the like.

(Prior art) As a free word-based information retrieval system,
No. 1-055683 "Japanese Information Retrieval System" has been proposed. This is - for each character, the character type,
It has only a character index consisting of the data number specification bit of the actual data that contains that character, and the logic between bit strings that indicates the data number of that index for all character types in the character string specified as a search condition. Performs an operation, uses the result to find out the data number of the actual data that includes all character types in the specified string, then reads and scans the actual data to see if it matches the string specified as the search condition. The target actual data is then searched for.

The above method does not have an index specifically for characters and character combinations. Therefore, for example, when trying to search for the character string "information search" as a combination of characters, the four characters "information", "information", "search", and "search" are searched.
After searching for data containing characters, it is necessary to search for the character string "information search" in the data.

(Problem to be Solved by the Invention) In such a conventional method, the necessary condition of data containing at least all the characters in a specified character string can be satisfied by logical operations using a character index. , characters and character combinations are not considered, so the actual data must be scanned,
Therefore, when there is a large number of actual data candidates, there is a problem in that an extremely long search time is required.

(Means and effects for solving the problem) The present invention, as a means for solving the above-mentioned problems, provides an information retrieval system that: When registering information, adds a data number to registered data;
Extracting a collocation consisting of a combination of characters appearing in the registered data, and expressing the collocation using a combination of a plurality of key values.In a collocation index having the key value and a data number specification bit string corresponding to the key value, The collocation is registered by turning on the corresponding bits of the plurality of key values and data numbers, and when searching for information, the collocation is extracted by the combination of characters included in the character string as the search condition, and the collocation is registered. The key value corresponding to the collocation is determined, the logical AND is performed on the bits at the same position in the bit string corresponding to the plurality of key values of the collocation index, and from the data number indicated by the resulting ON bit, the search condition is determined. The present invention provides a search method using a collocation index in an information retrieval system, which is characterized by searching for data containing collocations of character strings.

Also, set a compound number according to the kanji code table for the compound word, calculate the compound number by the modulus of several integers (MOD) in which multiple prime numbers are set as integers, and add a type mark to the calculation result. By doing so, the above-mentioned problem is attempted to be solved by a search method using a collocation index in an information retrieval system, which is characterized in that the character numbers of single kanji are converted into the plurality of key values.

The method of the present invention expresses a predetermined combination of characters by the logical product of several keys. Despite the large number of permuted combinations, in the tens of millions, the total number of keys can be reduced to a few dozen, and indexes on characters and combinations of characters can be treated just like traditional character indexes. This is what made it possible.

(Example) Next, an example of the present invention will be described with reference to the drawings.

Figure 3 shows how kanji are defined in the JIS code. Kanji are divided into level 1 and level 2 depending on their frequency of use, and one kanji character is represented by two code numbers.

Now let's say that the first code number is "Ban" and the second code number is "Rou", then the first level kanji is expressed in hexadecimal notation as 32 Bang characters from (30) to (4F). Similarly, the second level kanji are (50) to (7).
It has a code number indicating 36 flats up to 3). Each of these 68 planes is (21) to (7
Combined with the 94 labor code numbers up to E), the total number of Kanji characters is the product of 6,392 characters (including the last 43 undefined characters of the first level).

Although the method of the present invention can be applied to any number of character combinations, in order to avoid complicating the explanation, we will apply the method described in the third method to the case of a combination of two kanji characters.
This will be explained with reference to the figures.

There are various methods of assigning numbers to combinations of characters, but here we will explain the case of using a serial numbering method.

Furthermore, there are various ways to determine the key when expressing the above-mentioned 0-complex by the logical product of several numbers (keys), but here we will use the modulus (MOD) of several integers. I will explain about it.

First, according to the table in Figure 3, the first character ``A'' is number 1, the next character ``唖'' is number 2, and so on (and the last character ``Tori'' is number 6). .It will be number 392.Also,
Based on this, if we number the combinations of two kanji characters in order, ``aya'' is number 1, ``aya'' is number 2, etc.
..."Menu" is 6°392, "Scene" is 6.393
Number...The last "bird" can be number 40,857.664.

The general formula for this is P for the first character number and S for the second character number.
Then, collocation number N= (P-1) +6.392 +5-(
1), from which a key can be determined by a modulus (MOD) of several predetermined integers, and a collocation can be defined thereby.

A more detailed explanation of the above will now be given using the operations of this embodiment when storing data and when retrieving data.

FIG. 1 is for explaining the operation of collocation index registration at the time of data storage in this embodiment, taking data "information storage and retrieval" as an example.

Now, suppose that the data "Information storage and retrieval" is input, a data number (123 in this example) is assigned, and it is stored in the actual data section (Processing 1) At this time, the data "Information storage and retrieval" is input. All characters included in are extracted (Process 2... Hiragana is omitted here).

Next, the bit corresponding to the data number of each extracted character index bit string is set to logic "1" (copy 0) and registered in the character index (processing 3).

Next, all adjacent characters and combinations of characters included in the data "information accumulation and analysis" are extracted as collocations. In other words, there are seven pairs of "information/report/storage/storage/product and/to inspection/search", but in Figure 1, combinations that are not kanji characters are omitted (processing 4).
).

Next, key values are determined so that each of these seven sets is expressed by the logical product of several keys (numeric values), but here we will focus on "information" and explain it.

First, the letter numbers for “information” and “information” are shown in Figure 3.
From the S code, ``jo'' is number 1,396, and ``information'' is number 1,396.
is number 2.527, so the collocation number N of "information" is, from equation (1) above, N = (1,396-1) + 6,392 + 2,52
7 = 8,919,367.

Next, a key is determined by a modulus (MOD) of several predetermined integers. The number of keys and the value of the integer can vary, but here the number of keys is 4, and the integers are, for example, 4 prime numbers (751743739733), MOD (751) = (8919367 ÷ 751) Remainder = 491MOD (743) = (8919367÷74
Remainder of 3) = 395 MOD (739) = (891936
Remainder of 7÷739)=376MOD(733)=(89
The remainder of 19367÷733) = 223, so (4913
95376223) can be obtained.

If we use these as the four keys, we will also add a type mark (
(required to distinguish between the four keys), the 3008 first-level kanji are divided into 752 for each type.
Perform the following calculations so that each range falls within the following four ranges.

1st key MOD (751) + 752 pass = 491
mr turtle” 2nd key MOD (743) + 752*l=1
, 147 -r axis" 3rd key MOD (739) + 75
2 Umbrellas 2 = 1,880 0 r 4th key MOD (
73:3) +752㎟3=2,479 0r.The key value (491114718802479) obtained from this is further regarded as a character number, and the JI of the third tooth is
Translated using the S code, it becomes "tortoise/axis/love/hei".

The reason for converting to kanji at the end in this way is to treat it in the same way as a conventional character index, and is not an essential problem. (For example, express the type in 1000 digits,
(1491239533764223) is the simplest method. ) In any case, the collocation word "information" can be expressed using four keys (for example, a combination of four kanji characters) (processing 4).

Therefore, the bits corresponding to the data numbers of the bit strings of the collocation index of the four keys (kanji) of the collocation "information" mentioned above are set to logic "1" and registered in the collocation index, and similarly "storage" and "search" are performed. '' are also calculated and registered in the collocation index (processing 5).

Next, the search of the collocation index will be described below.

Figure 2 shows the character string "information search" as an example of a search condition.
The operation at the time of search in this embodiment will be explained by taking up the following.

In addition, the actual data section includes data number 123 "Information storage and retrieval" as shown in the actual data section of process 1 in Figure 1, as well as data number 456 "Tokai TV information search system" and many other data. Assume that has already been stored.

When the character string "information search J" is input as a search condition (process 1), first "information", "information", and "ken" are input.

The bit strings of the four character indexes "prime" are ANDed with the same bit positions. By this operation, the 12th
Assuming that a bit string in which only the 3rd bit and the 456th bit are “1” is obtained, from this result, “information/information/
Data containing the four characters "Search/Search" are number 123 and 45.
It turns out that there are only two numbers, number 6, and the other data is "
Since it is unlikely that the character string ``Information Search'' is included, it can be removed from the search candidates (Processing 2).

Next, we extract the three combinations of "information,""investigation," and "search" contained in the string "information search," and calculate the four keys for each using the calculation method used during registration as described above. do. As a result, the key for "Information j" is "Turtle/Axis/Kei/Hei", and by the same calculation, the key for "Information J" is "Kan/Ato/Kei".
Freeze/NJ, and the key for “search” is “Ku/Sho/Toro/He”
(Process 3).

Therefore, a logical AND operation is performed between the bit string obtained as a result of the logical AND operation of the character index and the same bit position of the bit string of the conjunctive index of these 12 keys. Assuming that this operation yields a bit string in which only the 456th bit is "1", the only data that may contain the character string "Information Search" is the 456th bit (Process 4).
.

Therefore, read data number 456 from the actual data section,
If it is confirmed that the character string "information search" is actually included, this data is found to match the search conditions (processing 5).

In this way, in the present invention, by searching the collocation index together with the character index, the number of actual data candidates can be narrowed down to a much smaller number than when searching only with the character index.

Next, we will explain why it is possible to handle an extremely large number of combinations using a small number of collocation indexes. A collocation consisting of two kanji characters from the first and second levels is
As mentioned above, there are about 40,000,000 possible numbers, but for example, 35003 is already over 40,000,000, so 3 on a scale of about 350
It is possible to locate all collocations at unique coordinates by the values (keys) of these coordinate axes.

However, conversely, if a certain coordinate is "1", it does not necessarily mean that a corresponding collocation exists. This is because multiple collocations may interfere with each other and indicate the coordinates by chance. This acts as search noise and reduces the accuracy of search results. In such a case, by approximately doubling the scale and increasing the number of coordinate axes by one to have approximately 300 billion coordinates, it is possible to prevent the generation of such search noise to a considerable extent.

The reason why the data No. 123 on the upper side was eliminated as a result of the logical operation is because the data No. 123 was "information storage and retrieval", so it is a combination of eight keys corresponding to "information" and "retrieval". Naturally, the 123rd bit of the index bit string is ``1'', but it is very possible that all 4 123rd bits of the conjunctive index bit strings of the four keys corresponding to ``Hoken'' are 1''. This is because it is small.

In addition, although the case where the search condition is one character string "information search" is explained above, it is not limited to "information search".
and complex search conditions such as "search" that includes all multiple character strings, "information" or "search" that includes any of multiple character strings, and mixed types. Correspondence can also be easily achieved by changing the contents of logical operations between the same bit positions in the bit strings of the character index and compound word index.

In addition, although we explained above about collocations that are combinations of kanji, it is easy to create collocation indexes using the same method for combinations that are not kanji, such as combinations of kanji and hiragana, or combinations of katakana. can.

Moreover, although the combination of two characters has been described above, it is also possible to apply the combination to three or more characters.

Furthermore, on the upper side, the number of collocation indexes between kanji is 2,966, which is the sum of four prime numbers (751,743739733).
, and when converted to characters, it falls within the range of the first level. In other words, combinations of kanji with over four characters are expressed within the range of first-level characters.
The precision of logical operations is determined by the number of coordinate axes (keys) and the possible range of values (key values), so it is easy to increase the precision if necessary.

Note that although the above explanation has been made regarding information retrieval in Japanese, the present invention is even more suitable for information retrieval in Chinese, which has a kanji structure.

(Effects of the Invention) According to the present invention, compared to narrowing down candidate real data using only a character index as in the conventional method, by using a character index and a collocation index, candidate real data is narrowed down. can be narrowed down to less. Therefore, the time required to scan actual data can be shortened, and the search speed can be improved.

In addition, since the accuracy of this logical operation is extremely high, there is a possibility that search noise may occasionally enter and add unnecessary data to the candidate data, but data that matches the search conditions will never be missed. By utilizing this property, it is practically possible to omit scanning of the actual data. In that case, search results can be presented using only logical operations, which has the effect of significantly shortening the search time.

[Brief explanation of the drawing]

FIG. 1 is a diagram for explaining the operation at the time of registering a character index and a compound word index according to an embodiment of the present invention. FIG. 2 is a diagram for explaining the operation at the time of search in this embodiment. Figure 3 shows that the kanji are JIS as a premise for explaining the present invention.
Diagram showing how it is defined in code.

Claims (2)

[Claims] (1) In the information retrieval system, when registering information, a data number is added to the registered data,
A collocation index that extracts a collocation consisting of a combination of characters appearing in the registered data, expresses the collocation using a combination of a plurality of key values, and has the key value and a data number designation bit string corresponding to the key value. , the collocation is registered by turning on the corresponding bits of the plurality of key values and data numbers, and when searching for information, the collocation is extracted by the combination of characters included in the string as the search condition. , find the plurality of key values corresponding to the collocation, calculate the logical product of bits at the same position in the bit string corresponding to the key value of the collocation index, and perform the search from the data number indicated by the resulting ON bit. A search method using a collocation index in an information retrieval system, characterized by searching for data containing a collocation of character strings as a condition. (2) Set a compound number according to the kanji code table for the compound word, calculate the compound number by a modulus of several integers (MOD) in which multiple prime numbers are set as integers, and mark the result of the calculation with a type mark. 2. The search method using a collocation index in an information search system according to claim 1, wherein the key values are converted into single kanji character numbers by adding .