JPH06149882A - Full-text database search device - Google Patents

Abstract

(57) [Summary] [Purpose] To provide a full-text database search device capable of accessing a full-text database at high speed and reducing the storage area for the index. [Structure] Full-text text 1a stored in full-text storage unit 1
For each character, the direct array 4-1, ..., 4-n in which the character appearance position is recorded at the position corresponding to the next character code based on the pair information of the character that appears next and the character appearance position.
To create. Then, the direct array is shifted to the right and left by an appropriate amount to overlap the data so that the data does not overlap, and the compressed array 2a is obtained and stored in the index area section 3. At the time of retrieval, the retrieval unit 3 retrieves information corresponding to the requested key from the compressed array stored in the index area unit 2 and uses this information to retrieve the requested content from the full-text storage unit 1. Since the full-text text is searched using the compressed array, high-speed search is possible, and the sparse array is compressed by directly overlaying the arrays.

Description

Detailed Description of the Invention

[0001]

[Industrial field] Due to the recent advances in computer technology,
As a large number of documents have been digitized, the demand for searching these documents is also increasing. In the database search, there is a method of adding a keyword in advance, but it is troublesome to add a keyword to a large amount of full-text data.

On the other hand, there is also a full-text search system in which the search is performed by directly referring to the text based on the keyword freely specified by the searcher without preparing the secondary information in advance. However, this causes a problem in the execution time for searching the full text. As an intermediate between the two, there is an attempt to treat all characters in the whole sentence as if they were keywords, give an index to all characters in the whole sentence, and perform a fast search without keywords. .

The present invention relates to a full-text database search device that holds address information of each character as described above and performs a full-text search using this address information as an index, and in particular, the present invention relates to a technique for creating the index. Is.

[0004]

2. Description of the Related Art In a full-text database search device that holds address information of each character as described above and performs a full-text search based on this address information, conventionally, the address information of each character is stored in each character. On the other hand, it held the next character information appearing in the text and its position as a pair.

However, in the above-mentioned conventional holding method, it is necessary to hold the following character information and position information for the characters in the whole sentence, and the storage capacity required for this index is 2 in the text. It was necessary more than twice. Further, it is difficult to increase the search speed because it is necessary to sequentially look at the character that appears next to each character in the search.

[0006]

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned problems of the prior art, in which a full-text database can be accessed at a high speed, and a storage area for the index thereof is a conventional one. It is an object of the present invention to provide a full-text database search device that can be reduced in number compared to the above.

[0007]

FIG. 1 is a block diagram showing the principle of the present invention. In the figure, 1 is a full-text storage unit that stores the full-text text 1a, 2 is an index area unit that stores the position of each character of the full-text text 1a in the full-text storage unit 1, and 3 is an index area for a given key. The search units 4-1 to 4-n that search the full-text storage unit 1 by using the index information of the unit 2 directly record the information about the character appearance position at the position corresponding to the code of the character next to each character code. Arrangement (circles indicate areas with data) 2a is a direct arrangement of each character code 4-1 to 4-
It is a compressed array in which n is shifted to the right or left by an appropriate amount and overlapped.

According to the first aspect of the present invention, as shown in FIG. 1, in order to search the contents of an electronic document, the full-text storage unit 1 holding the full-text 1a and the full-text 1a. An index area part 2 for holding each character and its appearance position for one character, and a search part 3 for performing a full-text search by referring to the index of the index area part 2 are provided. In the full-text database search device that also holds the next character information in the full-text database, based on the list of pairs of the next character information given to each character code and information on the character appearance position, the character of the next character information Direct array 4-1, ..., 4-n in which character appearance position information is recorded at the position corresponding to the code is generated, and the elements whose values are defined do not overlap. As described above, the direct arrays 4-1, ..., 4-n obtained from the respective character codes are shifted to the right or left by an appropriate amount and overlapped with each other to obtain one compressed array 2a from a set of a plurality of direct arrays to obtain the index. Area 2
The full text database is searched for the requested character string by using the compressed array 2a stored in the index area unit 2.

According to a second aspect of the present invention, in the first aspect of the invention, the compressed array 2a does not explicitly have information about each character positioned before the next character information, but the compressed array 2a
Full text 1a based on the character appearance position information in a
Each of the above characters is searched, and the compressed array 2 is obtained from the search result.
The information of the character appearance position extracted from a is confirmed to be correct information.

According to a third aspect of the present invention, in the first aspect of the invention, two character strings of the same combination appear a plurality of times in the full-text text 1a, and position information of a specific character code in the compressed array 2a. When there are a plurality of items, the plurality of pieces of information are held in an area different from the compressed array 2a. In the invention of claim 4 of the present invention, in the invention of claim 1, two character strings of the same combination appear multiple times in the full-text text 1a, and a plurality of position information of a specific character code exists in the compressed array 2a. When the plurality of information is compressed array 2
It is designed to be held in the continuous region of a.

According to a fifth aspect of the present invention, in the fourth aspect of the invention, a plurality of position information are held in the divided continuous areas of the compressed array 2a by holding a pointer flag in the compressed array 2a. It was done like this.

[0012]

With respect to each character of the full-text text 1a stored in the full-text storage unit 1, the character appearance position is set at the position corresponding to the code of the next character based on the pair information of the character that appears next and the character appearance position. , Direct array 4-1, ..., 4-n
To create. Then, the compressed array 2a is obtained by shifting the direct array by an appropriate amount to the left and right so that the data does not overlap, and is stored in the index area unit 3.

At the time of retrieval, the retrieval unit 3 retrieves information corresponding to the requested key from the compressed array stored in the index area unit 2 and uses this information to access the full-text storage unit 1 to request it. Take out the contents. In the invention of claim 1 of the present invention, as described above, the direct arrangement 4-
Since the compressed array 2a is obtained from 1, ..., 4-n and the full-text text 1a is searched using this compressed array 2a, high-speed search is possible and direct array 4-
By superimposing 1, ..., 4-n, the sparse array is compressed.

According to a second aspect of the present invention, in the first aspect of the invention, each element in the compression array 2a is
The index area 2 can be made compact because it is obtained which character has the information by referring to the full text 1a. In the invention of claim 3 of the present invention, in the invention of claim 1, when there are a plurality of pieces of position information of a specific character code in the compressed array 2a, the plurality of pieces of information are held in an area different from that of the compressed array 2a. Since this is done, it is possible to deal with the case where two character strings of the same combination appear multiple times in the full text 1a.

According to the fourth and fifth aspects of the present invention,
In the invention of claim 1, when two character strings of the same combination appear a plurality of times in the full-text text 1a and there is a plurality of position information of a specific character code in the compression array 2a, the plurality of pieces of information are compressed. The index area 2 can be made compact because it is held in a continuous area of, or is divided and held in a continuous area of the compressed area 2a.

[0016]

FIG. 2 is a diagram showing the basic configuration of a full-text database search device according to the present invention. In FIG. 2, 11 is a full-text storage section for storing the entire text to be searched, and 12
Is an index area portion, and stores the position of each character in the full-text storage portion, as will be described later. An index creating unit 13 is activated when creating or updating a part or all of the text in the full-text storage unit 11 and creates a text index. A search unit 14 searches the full-text storage unit 11 using the index information stored in the index area unit 12 for a given key. Reference numeral 15 denotes a user interface unit that takes in a search request from a user and outputs a search result.

In the figure, when the text in the full-text storage unit 11 is created or updated, the index creation unit 1
3 is activated. The index creation unit 13 determines, for each character in the full-text text stored in the full-text storage unit 11,
An index is created as described later, and this index is stored in the index area unit 12. When the user issues a search request from the user interface unit 15,
The search unit 14 retrieves the information corresponding to the requested key from the index area unit 12, and uses this information to access the full-text storage unit 11 to retrieve the requested content.

Then, the result of the retrieval, or if the retrieval fails, the user interface section 1
5 is output to the user. Next, an embodiment of index creation and search processing in the full-text database search device shown in FIG. 2 will be described. (1) Creation of Index FIG. 3 is a diagram showing a flowchart of index creation processing in the index creation unit 13. Using the actual example of FIG. 4 without reference to FIG. Creation will be described.

In step S1 of FIG. 3, the full-text file stored in the full-text storage unit 11 is opened. In step S2, it is determined whether or not the file has ended. If the file has not ended, step In S3, one character is read from the full text storage unit 11, and in step S4
go to. In step S4, a pair of the position in the full-text file and the next character for the read character is output to the work file. Then, the above process is repeated until the file ends, and the above process is performed for all characters of the full text, and when the process ends, step S
Go to 5.

FIG. 4 is a diagram showing an example of the full text to be indexed and the work file created in step S4. In FIG. 4, FIG. 4A shows an example of the full-text text, and FIG. 4B shows the created work file. In FIG.
The numbers attached to the vertical and horizontal axes are addresses indicating the position of each character.

Further, in (b), the column on the left end side is a heading character, the next column is an address indicating the character next to the heading character and its position in the full text, as shown in FIG. For characters that appear multiple times inside,
Only one character is recorded in the column of the index character, and a plurality of characters following the index character are recorded in the column in which the character next to the index character is recorded. For example, the word "day" is used as "Japan", "daily", and "daily" in the full text, but "day" appears only once in the column of heading characters,
In the column indicating the next character, "book", "person", "circle" and the address indicating the position in the full text are recorded.

When the work file is created for the whole text as described above, the process goes to step S5 in FIG. 3 to directly create an array for each character code. Figure 5
Is a diagram showing an example of a direct array, and in FIG.
Indicates a heading character, and 52 indicates a direct arrangement corresponding to the heading character. In the figure, as an example, the character "day" is a heading character, and the characters following "day" are "book", "people",
"Koro" is the address 4,8,2 in the full text respectively
The array when it appears at position 4 is shown.

In the figure, the array 52 has areas corresponding to the number of character codes (character sets) that can be used in the full-text, each area is arranged in the order of the character code, and each position of the area is different. Corresponds to the character code. That is, the character code can be specified by specifying the position of the array 52. For example, when the character "book" appears at address 4 in the full-text, "4" is recorded at the character code position "book" in the array 52, as shown in FIG. Similarly, when the character "s" appears at address 8 in the full text, array 5
“8” is recorded at the position of the character code “2” of 2.

Further, "nil" (meaning no data) is recorded in the area other than the area in which the address is recorded. Therefore, the caption characters are “s”, “shi”,
In the case of “o” and “day”, an array as shown in FIG. 6 is created and its address (for example, “9”, “2”,
From the position where "7" etc. is recorded, the character (for example,
"No", "I", "Sun", etc.)

That is, for each character code i in the full text, an array Ai of elements of the number of character sets is prepared, and when the character of code j exists as the next character of the character of code i, Ai [ In j], a pointer (address) to a list that stores information indicating the position of the character in the full-text database is stored. When the character of code j does not exist as the next character of the character of code i, "n
il ”is stored.

In the above example, a pointer (address) to a list that stores information indicating the position of the code j on the full-text database is stored for convenience of description. You may store the pointer (address) to the list which stored the information to show. After directly creating the array for each character in the full text as described above, the process goes to step S6 of the flowchart of FIG. 3 while appropriately shifting the compressed array to the right or left so that non- "nil" information does not overlap. , Create a compressed array by directly overlaying the array.

FIG. 7 is a diagram showing the arrangement superposition processing in step S6. In the figure, 71, 72,
Reference numeral 73 represents an array corresponding to the first to third character codes, and 74 represents a compressed array in which arrays 71, 72 and 73 are superposed. “Nil” is shown, and the position marked with a circle shows non-nil (the above-mentioned address is recorded).

In order to create the compressed array 74, FIG.
When the arrays 71, 72, 73 shown in are given, for example, the arrays 71 are shifted to the left by 2 and the arrays 72, 73 are moved to the right so that the positions of the circles do not overlap as shown in FIG. Shift 1 Then, as shown in FIG.
1, 72, 73 are overlapped to create a compression array 74. Further, in order to show which character code each position of the compressed array corresponds to, as shown in FIG. 6C, which character code the position corresponds to the area corresponding to each position of the compressed array. Is recorded. For example, as shown in FIG. 7C, the leftmost column of the compression array 74 corresponds to the first character code of the array 71 of FIG. “1” is recorded in the area corresponding to the column, and similarly, in order to indicate that the rightmost column of the compression array 74 corresponds to the third character code of the array 73, the leftmost column of the compression array 74 is indicated. “3” is recorded in the corresponding area.

Further, the shift amount of each array 71, 72.73, etc. is stored as a shift amount table. 8 is a diagram showing a schematic diagram of the displacement amount table and the compression array of the index,
The figure (a) shows an example of the shift amount table, and the figure (b) has shown an example of the compression arrangement | sequence of an index.

The shift amount table records headline characters and the shift amounts corresponding to the respective headline characters, and is shown in FIG.
As shown in, for example, the shift amount of “s” is “+1
The shift amount of "2" or "o" is recorded as "-29". Further, the compressed array of indexes has a structure as shown in FIG. 7B, and as shown in FIG.
The address 24 of the character "circa" in the character string "Hishiko" is
In the compressed array, "-125" (the shift amount of the character "day" is "-" from the original position of "koro" in the character set.
It is recorded at the position of "125"). (2) Search When the user issues a search request from the user interface section 15, the search section 14 retrieves information corresponding to the requested key from the compressed array of the indexes stored in the index area section 12, and The information is used to access the full-text storage unit 11 to retrieve the requested content.

In order to search for a character string in which the codes i and j are continuous, first, the shift amount Ti corresponding to the character code i is obtained by referring to the "shift table" shown in FIG. Next, the address L in the full-text text in the full-text storage unit 11 is extracted from the Ti + jth element of the index area shown in FIG. 8 (b). Also, Ti + j in the index area
Information indicating which character code the area corresponding to the th element corresponds corresponds to (see FIG. 7C). When the character code of the extracted information is the character code i, the address L is correct. It is information. If the character code of the extracted information is not the character code i, it means that there is no character string in which the character codes i and j are continuous.

For example, when searching for a character string in which "day" and "book" are continuous in FIG. 8, first, in FIG.
Refer to the "shifting table" shown in, and shift amount of "day""-1"
"25" is taken out, and "j-125" is obtained from the character code j of "book" and the "shift amount". Then, Fig. 8
The address 4 recorded at the position "j-125" is taken out from the index area of (b). In addition, "j-12
Find out which character code the 5 ”area corresponds to,
When the character code is a character code corresponding to "day", it is assumed that the character string in which "day" and "book" are continuous is at the position of address 4 in the full-text.

It should be noted that, in the above embodiment, to show which character code each position of the compressed array corresponds to, FIG.
As shown in (c), information indicating which character code the position corresponds to is recorded in a region corresponding to each position of the compressed array, and when searching, the above information is referred to for the above-mentioned. As described above, an example of confirming the existence of a character string in which the character codes i and j are continuous is shown, but as described above, the character strings are continuous without having information indicating which character code the position corresponds to. You can also check that the string exists.

That is, since each character and its address are stored in the full-text text in the full-text storage unit 11,
When the address L in the full text is extracted from the Ti + jth element of the index area, the full text storage unit 11
When the position of the address L is searched from the full text of, the character code before the position (the character code of the position when the address L indicates the position of the previous character) is the character code i, the character It can be confirmed that the codes i and j are continuous. (3) Creating an index when two character strings of the same combination appear multiple times in the full text.

In the above (1), the case where the two character strings appear only once in the full text has been described, but the two character strings of the same combination may appear in the full text multiple times. In this case, it is necessary to hold a plurality of position information in the index. Figure 9
(A) is a diagram showing a work file in the case where two character strings of the same combination described above appear multiple times in a full-text text, and the figure shows a continuous character string composed of a heading character β and a character code E. Shows four times at addresses 8, 59, 64, and 96.

FIG. 9B is a diagram showing an embodiment in the case where it is necessary to hold a plurality of position information in the index as described above. In the present embodiment, a plurality of position information is not included in the compressed array of indexes, and the plurality of position information is stored in a place different from the compressed array. As a method of storing in another location, for example, the head address of a list storing a plurality of position information is stored in the compressed array, and a plurality of position information is read using the head address of the list.

Alternatively, an array H different from the compressed array is prepared, the above-mentioned position information is stored in a continuous area of the array H, and the number of data or end mark of data is marked so that the number or end of data can be known. Set up. Then, the index of the first data of the array H in which the data is stored is stored in the compressed array, and a plurality of position information is read by referring to the index.

FIG. 9 (c) is a diagram showing another embodiment in the case where it is necessary to hold a plurality of position information in the index. This figure stores the plurality of position information in an area different from the compression array. Instead of doing so, an example is shown where it is stored directly in the compressed array. If there is at most one position information for a certain two consecutive characters, the actual position information is simply stored in the compressed array. The area mark / bit area is introduced, and as shown in FIG. 7C, the continuous area mark / bit is turned on while the data continues.
Position information is stored on the compressed array area.

FIG. 9D shows a method of storing a plurality of position information when a long continuous area cannot be secured when directly storing in the compressed array. In this embodiment, When a long continuous area cannot be secured, the area is divided and stored. That is, as shown in FIG. 9D, pointer bits are prepared in addition to the mark bits described above, and when the pointer bits are turned on,
The data is not the actual data, but the index on the compression area in which the next data is stored.

[0040]

As is apparent from the above description,
In the present invention, for each character of the full-text text, a direct array in which the character appearance position is recorded at the position corresponding to the code of the next character is created based on the pair information of the character that appears next and the character appearance position. However, the direct array is shifted to the right and left by an appropriate amount so that the data does not overlap and the compressed array is obtained, and the compressed array is used as an index to access the full-text text. The position information in the full text of the searched character can be immediately obtained from the character code of the character, and the access speed can be increased. Further, the storage area for the index can be reduced as compared with the conventional one.

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is a diagram showing a basic configuration of a full-text database search device of the present invention.

FIG. 3 is a diagram showing a flowchart of index creation.

FIG. 4 is a diagram showing an example of a full text and a work file.

FIG. 5 is a diagram illustrating a configuration of a direct array.

FIG. 6 is a diagram showing a state of an index array before compression.

FIG. 7 is a diagram illustrating superposition of arrays.

FIG. 8 is a diagram showing an example of a shift amount table and an index array after compression.

FIG. 9 is a diagram showing a storage state of position information in a compressed array.

[Explanation of symbols]

 1,11 Full-text storage section 1a Full-text text 2,12 Index area section 2a Compressed array 3,14 Search section 4-1, ..., 4-n Direct array 13 Index creation section 15 User interface section

Claims (5)

[Claims] 1. A full-text storage unit (1) holding a full-text (1a) for searching the contents of a computerized document.
And an index area part (2) that holds the appearance position for each character of the full text (1a), and a search part (3) that performs a full text search by referring to the index of the above index area part (2) In a full-text database search device that has the following character information in the full-text database in addition to the appearance position of each character as an index, a pair of the next character information and character appearance position information given for each character code Based on the list of, the direct array (4-1, ... 4-n) in which the character appearance position information is recorded at the position corresponding to the character code of the following character information is generated, and the element whose value is defined is To avoid overlapping, the direct arrays (4-1, ... 4-n) obtained from each character code are shifted to the right or left by an appropriate amount and overlapped, so that one compressed array (2a ) Got on Stored in the index area portion (2), the full text database using stored compressed sequence in the index area portion (2) and (2a), full-text database retrieval apparatus characterized by retrieving the requested string. 2. The compressed array (2a) is not explicitly provided with information regarding each character positioned before the next character information,
Full text (1a) based on character appearance position information in a)
Search for each of the above characters, and use the compressed array (2
The full-text database searching device according to claim 1, wherein the character appearance position information extracted from a) is confirmed to be correct information. 3. When two character strings of the same combination appear multiple times in the full-text text (1a) and there are a plurality of position information of a specific character code in the compression array (2a), the plurality of pieces of information are compressed. The full-text database search device according to claim 1, wherein the full-text database search device is held in a region other than the array (2a). 4. When two character strings of the same combination appear multiple times in the full-text text (1a) and there are a plurality of position information of a specific character code in the compression array (2a), the plurality of pieces of information are compressed. The full-text database searching device according to claim 1, wherein the full-text database is held in a continuous area of the array (2a). 5. The full-text database according to claim 4, wherein a plurality of pieces of position information are held in divided continuous areas of the compressed array (2a) by holding a pointer flag in the compressed array (2a). Search device.