JPH06208582A - Method and device for retrieving adaptive surrogate type information - Google Patents

Abstract

PURPOSE:To shorten a processing time and to reduce the number of disks to be used by efficiently executing full text search for data whose text capacity of documents are sharply different from each other. CONSTITUTION:Text data are divided or unified in accordance with a determined condition to prepare surrogate data (condensed texts 1 to 7, character components 1 to 7 and tables), a corresponding table between the divided or unified surrogate data and the original text data is prepared, surrogate data candidates having possibility of satisfying a conditional formula is extracted by referring to the surrogate data, the text data concerned are searched from the obtained candidates while referring to the corresponding table, and finally the text data matched with the conditional formula are outputted. Since the quantity of text data to be retrieved can be reduced, high speed full text search can be consequently attained.

Description

Detailed Description of the Invention

[0001]

This invention relates to a document database,
It is related to the document search to search for a desired document by searching the entire text of the document by designating a specified character string, that is, a search word, and in particular, the text capacity of the document registered in the document database greatly varies from document to document. The present invention relates to an information search method and apparatus suitable for cases.

[0002]

2. Description of the Related Art Heretofore, Japanese Patent Laid-Open No. 03-174652 has proposed a full-text search method that does not require adding a keyword when registering a document. This method
The purpose is to perform a full-text search at a high speed at a practical level by using a condensed text obtained by compressing a document in word units and a character component table in which characters used in the document are registered in character units. The condensed text and character component table used in this method will be referred to as surrogate data here. In this publicly known example, the surrogate data is examined before scanning the actual text data to narrow down the candidate documents to be scanned, and the text data is scanned only for the obtained candidate documents, thereby reducing the search processing amount, and as a result, It is characterized by realizing an equivalently high-speed full-text search. This prior narrowing down is called pre-search in a known example. This pre-search method was proposed in detail in "Japanese Patent Application No. 03-058311".

An outline of the surrogate data proposed in the above-mentioned known example will be described below. First, in condensed text, which is one of the surrogate data, the text data of the document to be registered is divided at the change points of the character type, and then the duplicated existing character strings are excluded from the divided character strings. Is the original text data compressed. That is, since the condensed text has a smaller capacity as the same word appears in the text data of the original document than the original text data amount, it is possible to create a small amount of surrogate data. As described above, the smaller the data amount is, the more the total condensed text scanning amount can be reduced, and the condensed text search can be performed at high speed. This was the purpose of creating surrogate data.
However, in this method, a simple document in which the same word is rarely used duplicates the data amount between the text data and the surrogate data.
In an extreme case, when one sentence is registered as one document, the data amount may be exactly the same. In such a case, the total search amount including the pre-search can be reduced by directly searching the text data rather than extracting the scan candidate document from the surrogate data and searching the text data. That is, it is useless to search the surrogate data, and if omitted, full-text search can be performed faster.

On the other hand, another surrogate data character component table describes the characters appearing in the text data of a document by bit information. That is, by providing a bit string of a certain length as surrogate data and describing appearance information at the corresponding bit position corresponding to the character appearing in the text data, that is, by setting bit "1", the character level of the text data is set. Represents surrogate information of. In this method, a constant surrogate data amount is always required regardless of the document data amount. Therefore, when the amount of data in the document is large, the surrogate data has a very small capacity compared to that amount, whereas when the amount of data in the document is small, the surrogate data is larger than the original data amount. There is a possibility that it will become. That is, if the amount of document data is small, there will be a lot of unnecessary data. In addition, when the data amount of the document is very large, many kinds of characters inevitably appear, so many bits of the character component table are set. As a result, many documents are listed as candidates as a search result of the character component table, and narrowing down becomes insufficient. In addition, if the volume of document data given as a candidate is large, a large amount of text data will be searched, and the search time will be lengthened. In other words, the effect of narrowing down by surrogate data does not increase, and it becomes necessary to refer to a large amount of condensed text or a large amount of text data. As a result, the search time cannot be shortened.

To summarize the above description, according to the conventional methods, in the case of a document in which the data amount of one document is small, the character component table and the condensed text, that is, surrogate data, becomes larger than the document data amount, and as a result, Search processing time increases. On the contrary, when the data amount of one document is large, many documents are hit by the preliminary candidate document selection, that is, the pre-search using the surrogate data, and as a result, it is necessary to scan many text data. There was a problem that it would occur.

In addition to such a surrogate data capacity, there is a problem in the method of reading text data. "UNIX device driver" (ASCII Publishing) P.P. As described in 51, "2.3 Block Buffering System", when data is read from a storage medium such as a magnetic disk to a memory or the like, the data is collectively read into the memory with a fixed buffer size. It is processing. Therefore,
When such a reading method is used, there is almost no difference in the reading time regardless of whether the reading is performed in the unit of data amount smaller than the buffer size or in the unit of data amount close to the buffer size. for that reason,
When reading text data having a small data capacity from a medium, there is a problem that the reading speed does not increase even though the data capacity is small.

Further, as a method for shortening the seek of a magnetic head such as a magnetic disk or the waiting for rotation to read from a storage medium, Japanese Patent Application No. 4-46685 is available.
Is already known. This is a technique for connecting a plurality of storage media, operating the media in parallel, and reading the data stored separately in order to multiplex the overhead time of each storage media to improve the read efficiency. Is.

[0008]

SUMMARY OF THE INVENTION An object of the present invention is to realize a system search speed which is always stable in full-text search by appropriately adjusting the surrogate data amount even when the data amount of a document varies. Especially. Another object of the present invention is to increase the system search speed in full-text search.

[0009]

In order to achieve the above object, the present invention integrates text data of a plurality of documents under a predetermined condition and creates the surrogate data for the integrated text data. , And create a correspondence table between the text data and the created surrogate data. And
At the time of search, a surrogate data candidate is referred to by referring to the surrogate data, text data corresponding to the candidate is obtained based on the correspondence table, and a document matching the condition is searched by referring to only the corresponding text data. To do. In addition, a predetermined data capacity Qt is set in advance,
When creating surrogate data, the text data capacity is Q
When the capacity of one text data is equal to or more than Qt, the text data is divided within a range not exceeding Qt, and the divided text data is divided for each divided text data. The above-mentioned surrogate data is separately created, and a correspondence table of the text data and the created surrogate data is created. Then, at the time of search, the surrogate data is referred to, a candidate for the surrogate data is given, the text data corresponding to the candidate is obtained based on the correspondence table, and only the corresponding text data is referred to, thereby satisfying the condition. To search. Also, as a search condition expression, AND between search terms
When a condition is given, surrogate data created by integrating multiple documents is searched by AND condition between words, and one document is divided into multiple text data and created separately for each divided text data. The surrogate data is searched by an OR condition between words. Further, in this case, a file for storing each of the surrogate data created by the integration and each of the surrogate data created separately for each of the text data obtained by dividing the one document into a plurality of text data are stored. The files to be created are separate files. Further, a plurality of external storage devices are provided to store the text data of the document as a file, the text data of each document is sequentially stored in the plurality of external storage devices, and the text data of the document exceeding a predetermined capacity is stored in the plurality of external storage devices. By dividing and storing in the device, referring to the surrogate data at the time of retrieval, providing a document candidate, and collectively reading the text data corresponding to the document candidate from a plurality of external storage devices and referring to the condition, Documents that match the above are searched.

[0010]

By combining a plurality of text data of a document or dividing one document into a plurality of data having an appropriate capacity and then creating surrogate data,
Surrogate data with high compression rate and high narrowing rate can be created. As a result, equivalently high-speed full-text search can be realized. Also, by creating a correspondence table of text data and surrogate data at the time of document registration, even if candidate documents are extracted by surrogate data created by integrating or dividing text data,
It is possible to identify which text data it corresponds to. Therefore, even in the case of surrogate data in which a plurality of documents are collected in one case, the corresponding original text data can be referred to, and an accurate search can be realized. Further, the search time can be shortened even if the AND condition is given. Also, the search time can be shortened by providing a plurality of external storage devices.

[0011]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS First, an outline of the search processing according to the present invention will be described. For surrogate data, the text data is divided into character strings at the change points of the character types, Hiragana character strings are removed from these, and duplicates are removed from each divided character string, and the original data is compressed and condensed. We will use a character component table in which the characters appearing in the text and text data are described as bit strings. here,
The data corresponding to one document in the character component table will be called a character component. In addition, it is assumed that a plurality of documents are registered at once for data registration.

First, the surrogate data registration process will be described, and then the search process will be described. When creating surrogate data, the amount of data of the document to be registered is first checked and compared with a preset threshold value Qt. If the data amount is smaller than the threshold value Qt, this document is integrated with the next document. Then, this integration process is repeated until the data amount exceeds the threshold value Qt, and one surrogate data is created from a plurality of documents. Also, the data amount of one document is the threshold value Q.
If t is exceeded, the document is divided to create a plurality of surrogate data. The state at this time is shown in FIG. In FIG. 1, the surrogate data of the condensed body 1 and the surrogate data of the character component 1 are output one by one from the text data of two cases of the document 1 and the document 2. Document 3 as well
The surrogate data of the condensed body 2 and the character component 2 is created from the text data of the three documents 5 to 5. On the contrary, the document 6 is divided into three surrogate data of condensed text 3, 4, and 5.

When the surrogate data is created from the text data divided or integrated as described above, the text data and the surrogate data do not have a one-to-one correspondence. Therefore, in order to know which document the result originally corresponds to after extracting the candidate document by searching the surrogate data, a correspondence table as shown in FIG. 2 is created. Here, the text data number is registered in correspondence with the surrogate data number. For example, since the surrogate data 1 is created by combining the document 1 and the document 2, the text data 1 and 2 are registered on the correspondence table.

At the time of a search, for the search word in a given conditional expression, a candidate document is first extracted from the surrogate data, and the text data of the candidate document obtained here is scanned to match the conditional expression correctly. Search for documents. That is, in the character component table, a document including all characters appearing in the search word is extracted as a candidate document. In the condensed text, the search word is divided into partial character strings by character type, and a document including all of these partial character strings is extracted as a candidate document. With respect to the candidate documents thus obtained, the text data is scanned, and only the documents that really include the search word and satisfy the logical conditions specified between the search words are extracted, and these are output as the final result. .

A specific search process will be described by taking the following conditional expression as an example. search: document DB (1) This conditional expression (1) is "search for a document that includes a search word (character string)" document DB "in one document". "Means." First, the candidate document is extracted with reference to the surrogate data. In the character composition table, ('sentence', 'writing', 'D',
Documents containing all characters of'B ') are listed as candidate documents. For example, if the character components 2, 4, 6, and 7 include the above-mentioned four characters, then the condensed text of these 2, 4, 6, and 7 is scanned, and (“document”, “DB”) Documents containing all substrings of are extracted as candidates. In this way, it is assumed that 2, 4, and 7 are obtained as candidate documents by the two-step pre-search using the surrogate data of the character component table and the condensed text. Since the surrogate data may be made up of a plurality of text data as described above, it is not possible to search the text data with the search result of the surrogate data as a candidate document. This is because the surrogate data and the text data do not have a one-to-one correspondence. Therefore, before searching the text data, it is necessary to refer to the correspondence table shown in FIG. 2 once and select the text data corresponding to the candidate document extracted by the surrogate data. In the above example,
By referring to the correspondence table of FIG. 2 from the search result of the surrogate data of (2, 4, 7), the corresponding text data are (3, 4, 5), 6, and (9, 1), respectively.
Know that it is 0). Thus, finally, the text data 3, 4, 5, 6, 9, 10 are searched, a document including the search word (character string) of (“document DB”) is searched, and the document number is searched. Output as the final result.

Next, a search process based on a slightly more complicated search condition will be described using the following conditional expression (2) as an example.

Search: AND (document DB, search system) (2) This conditional expression means to search for a document that includes both “document DB” and “search system” in one document. . Since the surrogate data may be created by dividing one document into multiple cases, the specified search term may not necessarily be included in the same surrogate data. This problem can occur not only when two search words are specified but also when one search word is specified.
For example, if the search term "document DB" is specified,
If the text data is divided immediately after the'sentence 'in the middle of a word, the surrogate data cannot be searched for with the partial character string "document". That is, even though there is a specified search word in the text data, it will not be hit, resulting in omission of search. However, if the division method is performed by using breaks of sentences, that is, paragraphs, chapters, sections, etc., it is possible to avoid division into different surrogate data in the middle of a word. That is, when a single search word is specified, the problem of dividing the text data into a plurality of surrogate data can be solved. However, since the AND condition of the above equation (2) is satisfied regardless of how far apart the search terms are in the document,
The problem cannot be solved by simply adjusting the dividing points.

In order to solve this problem, the AND condition is replaced with the OR condition for the divided surrogate data, and the surrogate data including any of the specified search terms is first extracted, and the obtained candidate document is used. Scan the corresponding text data and search for documents that include all search terms. The following is an example of that search. First, candidate documents are extracted from the surrogate data. In the character composition table, all four characters of ('sentence', 'writing', 'D', 'B') are included, or ('check', 'search', 'shi'
Documents containing all six characters ('s', 'te', 'mu') are listed as candidate documents. For example, character components 2, 4,
6 and 7 satisfy the above condition, in the next condensed text search, the condensed texts of 2, 4, 6, and 7 are scanned,
A document including both partial character strings of (“document” and “DB”) or a document including both partial character strings of (“search” and “system”) is extracted as a candidate. In this way, if the surrogate data 2, 4, and 7 are obtained as candidate documents by the OR condition search between the specified search terms,
Similar to the previous example, referring to the surrogate data-text data correspondence table shown in FIG. 2, the text data corresponding to the candidate document extracted by the surrogate data is selected, and finally the text data 3, 4, 5, 6, 9, 10 is searched, and this time under the AND condition between the specified search terms (“Document D
B ”,“ search system ”) are both included in the document, and the document number is output as the final search result.

As described above, when the document is registered in the database, its capacity is checked, and if the capacity is not reached,
Create multiple surrogate data by combining multiple documents. When the document size is too large, the surrogate data can be created smaller than the original document size by creating the surrogate data by dividing the document into a plurality of documents that fit in a predetermined size. In addition, a high narrowing rate can be obtained in the pre-search by using the surrogate data. Also, for the problem that the original text data and surrogate data do not correspond one-to-one,
Create a correspondence table for both when registering a document, and refer to this table when searching to select and search the relevant text data from the candidate documents obtained by searching surrogate data so that the correct result can be obtained. .. At the time of data division, division is performed by using a break such as a sentence as a guide so that it is not divided in the middle of a word. By doing so, in the case of a search by a single search term, it is possible to output the final search result with only the surrogate data. In addition, when an AND condition is specified in order to correctly search a document in which the surrogate data is divided, the search for surrogate data is set to O between search terms.
The text data is searched for under the AND condition after narrowing down by performing the R condition. When the OR condition is specified, the surrogate data is searched under the condition as it is. By doing so, even if the divided surrogate data is used, it is possible to realize highly reproducible search without omission of search.

By using the method according to each of the above processing steps, a plurality of text data of a document are put together or one document is divided into a plurality of pieces to obtain data having an appropriate capacity, and then surrogate data is created. Thus, surrogate data having a high compression rate and a high narrowing rate can be created. As a result, equivalently high-speed full-text search can be realized. In addition, by creating a correspondence table of text data and surrogate data at the time of document registration, even if candidate documents are extracted by surrogate data created by integrating or dividing text data, it corresponds to any text data. Can be identified. Therefore, even in the case of surrogate data in which a plurality of documents are collected in one case, the corresponding original text data can be referred to, and an accurate search can be realized.

The above description is about the integration and division of the document text data by the threshold value Qt of the predetermined data amount, but the method of integrating the data by the number of documents without depending on the threshold value Qt. Can also be considered. This provides a simple integration processing method when the data amount per case is uniform but one document consists of a very small data amount. For example, this corresponds to the case where one sentence is treated as one document. It is also possible to use the data amount Qt as a threshold value only as an index for data integration and create a document with a capacity equal to or greater than the threshold value Qt in one surrogate file. In this case, only documents with a small amount of data are combined into surrogate data, which is effective for a document database in which a document with a large amount of data is occasionally included in a set of documents with a very small amount of data. In this way, when there is no long document data, by creating the surrogate data only by unifying the document data without dividing the document data, even if the AND condition between the search terms is given, it is placed in the OR condition. There is no need to repair and search surrogate data. Therefore, there is an advantage that a high narrowing rate can be obtained by searching the surrogate data, the search amount of the text data is reduced, and the search speed of the system is improved.

Further, the data amount threshold value Qt is set to an appropriate length as a general document. That is, it can be said that the threshold value Qt is an amount sufficient to explain it according to one argument. Newspaper articles are examples of the simplest documents, and papers are examples of longer documents. These documents are typical documents that explain the content according to one point of view. The data volume of newspaper articles is about 1 KB (500 characters), and the data volume of longer articles is about 30 KB (15,000 characters). The threshold value Qt is suitably an amount between 1 KB and 30 KB.

Furthermore, as described in the conventional example, when reading data from a storage medium for text data, the data is collectively read from the medium according to a fixed buffer size. In other words, if the text data is smaller than the buffer size, the data can be efficiently read from the medium by continuously reading the text data. Specifically, when the buffer size is 8 KB, if one case is text data of about 500 bytes, the amount does not exceed 8 KB,
That is, about 16 cases will fit in the buffer in one read process. In other words, reading about 16 items at once is the same as the reading time for one item. Therefore, it is also an effective method to specify the read buffer size from this medium as the threshold value Qt for collecting the text data.

In the full-text search using the surrogate data in the above description, which document should be referred to by narrowing down candidate documents from the surrogate data before referring to the text data. Since it can be specified, another effect can be obtained. As described in the conventional example, there is known a technique for improving the reading efficiency by connecting a plurality of storage media and reading the divided data. For example, in the case of a magnetic disk device, the seek time and rotation waiting time of the magnetic head can be reduced by operating a plurality of disk devices in parallel. That is,
Issuing a large number of read commands is highly effective because many disks operate in parallel. Therefore, since a plurality of storage media operate in parallel by collectively executing the read command of the candidate document obtained from the surrogate data,
The overhead of reading data from the disk can be reduced. That is, performing the batch reading of the candidate documents obtained from the sallog data has a great advantage of improving the search throughput as compared with the method of issuing the reading command one by one.

The embodiments of the present invention will be described in detail below. FIG. 3 is a diagram showing the configuration of this embodiment. In this embodiment, a keyboard 301 for inputting a conditional expression, a display 302 for outputting a result, a magnetic disk 303 for storing a database, a memory 304 for storing a database, a memory 306 for storing various programs, and various programs The memory 307 includes a CPU 305 for execution control, a data capacity threshold value Qt and a correspondence table of surrogate data / text data, and a work memory.

First, the procedure for creating surrogate data will be described according to the data registration process, and then the candidate document extraction process using the surrogate data will be described according to the search process.
First, the text data used in this embodiment and the storage form thereof will be described with reference to FIG. As shown in the figure, the text data is composed of a data file in which a plurality of text bodies are collected, and a directory file indicating the start and length of the document in the data file. In addition, t is used for document identification.
The document ID number indicated by id is used. In this embodiment, this t
The id is called a text ID. Directory file o
ffset indicates the number of bytes from the beginning of the data file of the relevant document, and length indicates the length of the data. For example, the document having the text ID 5 indicates that the document starts at the 29,987th byte from the beginning of the data file and has a length of 4,376 bytes.

Next, a correspondence table between text data and surrogate data will be described with reference to FIGS. 5 and 6. This figure shows a specific method of realizing the correspondence table of surrogate data and text data shown in FIGS. 1 and 2.
The sid shown in FIG. 5 is I for identifying surrogate data.
D is called a surrogate ID to distinguish it from a text ID. c
When the chain is not 0, it indicates that the next surrogate data follows, and the value indicates the record number of the chain table. That is, when one text data is divided into a plurality of surrogate data, those surrogate IDs are stored. This surrogate ID table is a conversion table from a text ID to a surrogate ID. The record number of the surrogate ID table corresponds to the text ID (tid). For example, to obtain the surrogate ID corresponding to the text ID2, the second record in the surrogate ID table may be referred to, and sid is 1 in the example of FIG. In addition, when one text is divided to create multiple surrogate data, one text ID contains multiple surrogate IDs.
Corresponds. For this reason, the surrogate ID table has an item called chain. When chain is 0, it indicates that there is no connected data, that is, there is no divided surrogate data. When it is other than 0, the connected surrogate ID can be obtained by referring to the corresponding record in the surrogate ID chain table. You can For example, if the tid is 6, first the surrogate I
3 is obtained as sid from the D table,
Is 1, the first record of the chain table is referred to, and 4 is obtained as sid. Next, since the chain of that record is 2, the second record of the surrogate ID chain table is referred to and the sid is 5
Is obtained. Since the chain of this record is 0, it can be seen that there is no other data to be chained, and the sid corresponding to the text data with tid of 6 is 3,
It can be seen that there are 3 of 4, 5.

The text ID table shown in FIG. 6 is a conversion table from surrogate ID to text ID. The record number of the text ID table corresponds to sid. Similar to the surrogate ID table, when text data is integrated and one surrogate data is created from multiple text data, one text ID corresponds to multiple surrogate IDs, so other texts can be added to the text ID chain table. Register the ID. For example, si
When d is 2, by referring to the second record of the text ID table, 3 is first obtained as tid, and since the chain at that time is 2, refer to the second record of the text ID chain table. , Tid is 4, and since chain is 3, 5 is obtained as tid. From this, it can be seen that the text IDs corresponding to the surrogate data whose sid is 2 are 3, 4, and 5. Further, in the text ID table, the ID of the head surrogate data corresponding to the corresponding text data is registered as top for the surrogate data created by division. Thereby, for example, t corresponding to sid of 5
Although the id is 6, it can be seen that the surrogate data is divided into 3, 4, and 5 as the sid. The above surrogate ID table and text ID table are
As an initial state before registering a document in the DB, the values of sid and tid are all set to -1.

Below, the processing at the time of data registration is shown in FIG.
The PAD diagram of FIG. The registration data has a form as shown in FIG. 4, and a plurality of pieces of data are collectively registered. First, data for one case is read, and the tid registered in the directory file of FIG. 4 is registered in the empty record of the text ID table of FIG. The record number sid at this time becomes the surrogate ID of the surrogate data to be registered. Next, sid is registered in the tid-th record of the surrogate ID table of FIG. Then, the data amount of the text and the threshold value Qt are compared, and if the data amount is equal to or less than the threshold value Qt, the next data is integrated until the data amount exceeds the threshold value Qt. At this time, the same sid as the previous document is registered in the tid-th record of the integrated document in the surrogate ID table, and the tid is chained and registered in the text ID chain table. Then, one surrogate data is created by the integrated text data within the range not exceeding the threshold value Qt, and the s
Register by id.

The registration of the text data shown in FIG. 4 will be specifically described as an example. Here, as the threshold value Qt, 20,0
00 bytes are used. First, the text data whose tid is 1 is read, and 1 is registered as tid, 0 is registered as chain, and 0 is registered as top in the first record, which is an empty record in the text ID table. In the first record corresponding to the tid of 1 in the surrogate ID table, as the sid which is the surrogate ID currently being created, 1 and cha
Register 0 as in. Since the length 6,232 bytes of the text data having the tid of 1 does not exceed the threshold value Qt, the text data having the tid of 2 is continuously read and 2 is registered as the tid in the text ID table. At this time, the text ID table is registered so as to be linked to 1 of tid already registered. That is, since 1 is already registered as the tid in the first record corresponding to the sid that is the surrogate ID currently being created in the text ID table, the chain of the first record is already registered.
Item is changed to 1 which is an empty record in the text ID chain table. Then, 2 is set as tid in the first record of the text ID chain table, and chain
0 is registered as. The surrogate ID table contains t
1 as sid in the second record corresponding to id 2
Register 0 as chain. T read so far
The total capacity of the text data of id 1 and 2 is 19,79
Since the total capacity exceeds the threshold value Qt when the text data of 2 bytes and the tid of 3 (length 3,470) is read, the integration processing of the data ends here and the tid
Creates surrogate data with the integrated text data of 1 and 2. This makes it possible to create surrogate data in which documents with tid of 1 and 2 are integrated.

When the data amount of the read text is equal to or larger than the threshold value Qt, the text data is divided to create a plurality of surrogate data. The procedure of division is the threshold value Q
The text breaks, that is, ', within a range not exceeding t. '
Immediately after. Surrogate data is created for the data thus divided, and the surrogate ID is used as the surrogate ID.
Register in the table and surrogate ID chain table. The target tid is also registered in the corresponding sid-th record in the text ID table.

A specific explanation will be given again using the example of the text data shown in FIG. Now, it is assumed that the registration process is completed up to the document whose tid is 5, and the document whose tid is 6 is registered. ti
Since the text data length of d = 6 is 57,432 bytes, which is larger than the threshold value Qt (20,000), tid
Performs division processing of the text data of 6. First, surrogate data is created by dividing the text at the breaks of sentences that do not exceed the first Qt (20,000 bytes). s
id is set to 3, which is an empty record in the text ID table. Therefore, in the third record of the text ID table, 6 is set as tid, 0 is set as chain, and top is set.
Register 3 as. The top 3 indicates that the surrogate data corresponding to this record whose sid is 3 is created by dividing the text data, and is formed by chaining the surrogate data whose sid is 3 at the head. It means that. Also, surrogate ID
Sid in the 6th record corresponding to 6 in the table tid
Is registered as 3, and 0 is registered as chain. In this way, when the surrogate data whose sid is 3 is registered,
Subsequently, the text data having a tid of 6 is read within a range not exceeding the threshold value Qt. This time a new surrogate ID
That is, the empty record 4 in the text ID table is si
The registration process is continued as d. Therefore, the text ID
In the fourth record of the table, set 6 as tid to chai
Register 0 as n and 3 as top, and enter surrogate I
Register 4 as the sid in the record corresponding to the tid of 6 in the D table. At this time, since the 6th record of the surrogate ID table has the data with the sid of 3 previously registered, the term of chain is changed to the empty record 1 of the surrogate ID chain record, and is changed to the first record of the surrogate ID chain record. Is 4 as sid, c
Register 0 as the chain. Next, the third divided data having the tid of 6 is read, the sid is set to 5, and the 6th is set as the tid in the fifth record of the text ID table.
Register 0 as ain and 3 as top. In the surrogate ID table, the sid whose tid is 6 has been linked to 3 and 4 so far, and the chain is 0 at the first record of the surrogate ID chain table, and the chain has stopped. Perform additional processing. That is, the chain of the first record is changed to 2 which is an empty record in the surrogate ID chain table, and 5 is registered as sid and 0 is registered as chain in the second record. In this way, the text data having the tid of 6 can be divided into three pieces and associated with the respective surrogate data.

Examples of surrogate data created by integrating or dividing in this way are shown in FIGS. 8 and 9. Both are based on the text data shown in FIG. FIG. 8 is an example of a character component table. For example, in the data having the surrogate ID 7, since the documents having the text IDs 9 and 10 are integrated and the character components are registered, the character used in either of the both texts is registered as 1. Explaining in a specific example, the character component whose sid is 7 is
The component values of both the characters “article” used in tid 9 and “cure” used in tid 10 are 1. Also, for the character component with sid of 3, the document with tid of 6 is registered separately, so the character component of "inspection" is 1, but it is used in the middle part of the document with tid of 6. The character component of the character "de" is 0.

FIG. 9 shows an example of creating a condensed text. Since one item of this condensed text is variable length data like the original text data, the offset position from the beginning of the data file and the data length are registered and managed in the directory file. For example, the surrogate data whose sid is 3 indicates that the length of 4,768 bytes from the beginning 8,588 bytes of the data file is stored. This directory file is created at the same time when the surrogate data is created. Also, the symbols ',' in the data file
Represents the delimiter of the substring. For example, since the condensed text with sid 1 is made by integrating the text data with tid 1 and 2, the "correspondence table" that appears in the document with tid 1 and the "plurality" that appears in the document with tid 2 Both "" substrings are registered. Also, sid is 3
In the condensed text of, the partial character strings of "search" and "condition" in the first half of the text data whose tid is 6 are registered, and the "stable" and "search speed" in the second half are s.
The id is registered in the surrogate data of 5. Thus, in the character component table, the record number of the bit string of the character component corresponds to the surrogate ID in the condensed text, and the record number in the directory file corresponds to the surrogate ID.
Data can be referred to by the surrogate ID (sid).

Next, a process of searching based on the surrogate data thus created will be described with reference to the PAD diagram of FIG. At the time of search, a search word, a character used in the search word, and a logical condition are extracted from the given conditional expression. Of these, the characters used in the search words are used to search the character component table, and the search words are used to search the condensed text. Also,
The logical condition between the search words is extracted, and if there is an AND condition, it is replaced with an OR condition to search the surrogate data.
Of the surrogate data, especially the condensed text is made by deleting all the hiragana character strings in the text data.
Search only when the search word is a character type other than hiragana. Thus, by searching the character component table and the surrogate data of the condensed text, a surrogate ID that is a candidate is obtained as a result. If the resulting surrogate ID is 0, the result is always 0 even if you search the text.
Since it is a case, the result is output here, and the search process is ended. When the number of surrogate IDs (sid) as a result is not 0, the text ID table is referenced using sid and converted to tid. Then, using the obtained tid, the directory file in FIG.
ffset and length are obtained, the data file is accessed from this value, the text data is searched, and the search result is output. When there is no need to search for text data, the text ID (tid) obtained from the text ID table according to sid is directly output.

The following are the conditions under which the text data must be searched. (1) When Hiragana characters are used in the search term In this case, the Hiragana character string is deleted from the condensed text,
Because it is not described, it is necessary to search the text data instead. (2) When a compound character type is used in the search term In this case, noise may appear only by searching the condensed text because the condensed text is registered as a partial character string for each character type. is there. For example, in the case of the search term "document data", "document" and "data" in the condensed text
Since the two partial character strings of are registered, the condensed text search will search for data that contains both partial strings of "document" and "data", but the obtained candidate document is really "document data". This is because it is not known whether the character string "" was included. To confirm that, we need to search the text data. (3) When there is an AND condition In this case, one document may be divided into a plurality of surrogate data.
Although it is necessary to search under the R condition, noise may appear under this condition alone, so it is necessary to search the text data under the AND condition. Specifically, when searching for a document that includes both "document" and "data", the surrogate data may be divided, so the surrogate data may be either "document" or "data". This is because it is necessary to search for a document that includes the search word, and then search the text data for a document that includes both "document" and "data" to confirm the document. (4) When tid is chained when obtaining tid from sid In this case, it is not possible to determine which text really matches the conditional expression because the surrogate data is created by integrating multiple texts. This is because it is necessary to directly search the original text data for determination.

FIG. 11 and FIG. 12 show an example of a procedure for searching with this search algorithm. FIG. 11 shows an example when a search is performed using the conditional expression search: data. First, in the first search for surrogate data, the character component table of FIG.
The data including three characters "-" and "Ta") is searched for, and the condensed text in FIG. 9 is searched for by the text including the character string "(data)". It is assumed that, by searching the surrogate data in two steps, sids 2 and 4 are obtained from the character component table, and sids 2 and 4 are obtained in the condensed text. When the tid is obtained by referring to the text ID table shown in FIG. 6, the text IDs of 2 to 3, 4, and 5 as the sid and the text IDs of 4 to 6 as the sid are obtained. Since the surrogate data whose sid is 2 is chained and multiple text data are integrated to create one surrogate data,
From the above condition (4), text data is searched, and as a result, tids of 3, 4, 5, and 6 are finally obtained.

FIG. 12 shows an example of search by another conditional expression. This figure shows an example of searching for a document in which both search words (“document”, “data”) appear in the document based on the conditional expression of search: AND (document, data).
In this case, since there is an AND condition between the search words, the surrogate data is searched for a document including any of the terms (“document”, “data”). First, in the search of the character component table, a document including two characters ('sentence', 'writing') or three characters ('de', '-', 'ta') is extracted. In the character component table of FIG. 8, the sid is 1,
2, 4, 6, and 7 correspond to this. Next, the condensed text is searched on the condition that it contains any of the character strings ("document", "data"). In the example of FIG. 9, sid is 1,
2, 4, 6, and 7 correspond to this. In the example of this conditional expression, text data is searched for from the conditions (3) and (4) above, and a document including both ('document'and'data') is actually found. At this time, the surrogate IDs of the candidates obtained by searching the surrogate data are set as tid by the tid table shown in FIG. 6 as 1, 2, 3, 4, 5, 6,
It is converted into 7, 8, 9, and 10, and only the corresponding tid is searched for. Thus, in the example of the text data of FIG. 4, the documents with tid of 3 and 4 are output as the final result.

The data registration and retrieval processing has been described above. The procedure for deleting and updating the data thus created will be described below. This process
This is done by executing the data update program. FIG. 13 is a PAD showing a procedure of processing when deleting data.
It is a figure. First, the text ID (ti
Enter d). As this text ID, the tid set in the directory file at the time of registration is specified. After that, referring to the surrogate ID table, the surrogate ID (si) corresponding to the specified text ID (tid)
Extract d). At this time, it is checked whether or not the surrogate ID is chained, and if there is a chain, that is, if the text data amount is larger than the threshold value Qt and the surrogate data is divided, the surrogate data of all the corresponding surrogate IDs are delete. Then, the corresponding records in the surrogate ID table and the text ID table are changed to -1, and the chain table reorganization processing is performed so as to fill the deleted chain table, and then the text data is deleted and the processing ends.

A specific description will be given again with reference to FIGS. To delete a document with a tid of 6, surrogate I
Text I that refers to the D table and has a tid of 6
Extract D. In the example of FIG. 5, the surrogate ID corresponding to tid of 6 is chained, and the sid of 3, 4, and 5 is chained.
Corresponds to this. Therefore, all surrogate data whose sid is 3, 4, 5 are deleted. The data in the character component table is deleted by setting all the character components of the corresponding sid to 0. The data of the condensed text can be deleted by setting the length of the corresponding surrogate ID of the directory file to 0. After that, the sixth record of the surrogate ID table whose tid is 6 is changed to -1 as sid and 0 as chain, and the first and second records of the chained surrogate ID chain table are set to -1 as sid. Is changed to 0 as chain. Similarly, delete the text ID table.
The third, fourth and fifth records corresponding to sid of 3,4,5 are changed to -1 as tid, 0 as chain, and 0 as top. Finally, the deletion of text data can be performed by setting the corresponding sixth record of the directory file to 0 as the length, like the deletion of the condensed text.

When the surrogate data is not chained, the obtained sid is used to refer to the text ID table to obtain the text ID corresponding to the surrogate data. This process is performed to determine whether the surrogate data is integrated or made from a single text data. Multiple t for one sid
When there is an id, that is, when the surrogate data is created by integrating a plurality of text data, the surrogate data is recreated and registered with data other than the tid to be deleted. That is, the data created from the portion of the text data to be deleted is deleted from the integrated surrogate data. Then, the corresponding record in the text ID table is changed to -1, the actual text data is deleted, and the processing is ended. In the example of FIGS. 4, 5 and 6, the tid is 2.
When deleting the document, first, the surrogate ID table is referred to, and 1 is obtained as sid. Next text ID
By referring to the table, it can be seen that tid is chained from 1 to 2. Therefore, surrogate data is recreated only with text data having a tid other than 2, that is, text data having a tid of 1, and re-registered with sid being 1. Then, the second record of the text ID table is s
The id is changed to -1 and the chain is changed to 0, and the corresponding text data is deleted at the end. When the surrogate data and the text data have a one-to-one correspondence, that is, when one tid corresponds to one sid, that is, the surrogate data that has not been divided or integrated is:
The sid and tid of the surrogate ID table and the text ID table are initialized to -1, the surrogate data and the text data are deleted, and the processing is ended.

FIG. 14 is a PAD diagram showing a procedure of processing when data is updated. The update data is also given in the same format as the text shown in FIG. First, as in the case of deleting, the text ID (tid) of the text to be updated is fetched, and the corresponding surrogate ID (sid) is extracted by referring to the surrogate ID table. If there are a plurality of sids for one tid, that is, in the case of surrogate data created by data division,
Updates the surrogate data that is created separately.
That is, the data amount of the text data to be updated is compared with the threshold value Qt, and if it is larger, the surrogate data is registered while dividing the text data within the threshold value Qt with the sid already registered in the surrogate ID table. To go. At this time, if the number of divided surrogate data is larger than the number of sid chains registered in the surrogate ID chain table, new sid is added and registered. On the contrary, when the number of divisions becomes small, the surplus sid is changed to -1, and the chain table is reorganized. If the text data to be updated does not exceed Qt, delete the chained surrogate data and change the chained sid to -1.
The chain table is reorganized to update the surrogate data with the first sid of the chain registered in the surrogate ID table.

A detailed description will be given again with reference to FIGS. When updating a document whose tid is 6, surrogate I
From the D table, since sid 3, 4, and 5 correspond to tid 6, it can be seen that they are surrogate data created by data division. Therefore, the newly updated tid is 6
Of the text data is compared with the threshold value Qt, and if the capacity is large, sid is 3, 4 ,. ． ． Create surrogate data while dividing the text data and replace it with the original data. At this time, if the amount of new text data is large enough to divide the text data into three or more, a new sid (for example, 11) is added and the surrogate data is registered. New si
When adding d, an empty record (for example, the 11th record) in the text ID table is set as a new sid, and tid (6 in this case) is registered in the record. Also, the new sid is registered in the surrogate ID chain table. In this case, the sid of the surrogate ID chain table is 5
Of the second record (record number 2) in which is registered
It is sufficient to change the chain to the empty record 3, and register 11 as the sid and 0 as the chain in the third record. In this way, when the amount of text data is large and the number of divisions is large, a new sid is added and the surrogate I
Register surrogate data while changing the D chain table.

On the contrary, when the number of divisions becomes small, the record corresponding to the unregistered sid in the text ID table is set to -1 as tid and 0 as chain.
The top is changed to 0 and the sid is also deleted from the surrogate ID chain table. For example, when the creation of surrogate data is completed with sid of 3 and 4 by changing the text data with tid of 6, the fifth record of the text ID table is set to tid, and -1 is set to chain.
Changed to 0 and top changed to 0, and surrogate ID
-1 as the second record in the chain table
Is changed to 0 as chain. At this time sid 4
Change the chain of the first record of the surrogate ID chain table to 0 so that the chain stops at. If the amount of text data whose tid to be updated is 6 does not exceed the threshold value Qt, surrogate data is created with sid set to 3, and the sixth record of the surrogate ID table is set to si.
Change 3 as d, change 0 as chain, change -1 as sid for the first and second records of the surrogate ID chain table, and change 0 as chain. At the same time, the fourth and fifth text ID tables
-1 for the record tid and 0 for the chain
Is changed to 0 as top. Furthermore, the surrogate data whose sid is 4 and 5 are deleted.

Further, for one tid, one sid
, The text ID table is referred to by the obtained sid, and it is determined whether or not the surrogate data is integrated depending on whether or not there are a plurality of tids. 1 sid
If a plurality of tids correspond to each other, that is, if the integration processing has been performed, the text data integration processing and the surrogate data creation processing are performed again based on the updated text and other integrated text data. Need to do. First, recalculate the total capacity of the integrated text data including the text data to be updated, and if the threshold value Qt is not exceeded, re-integrate all the corresponding text data and re-create the surrogate data. register. If the text data to be updated is larger than the registered text data, and if all the relevant text data is integrated and becomes larger than the threshold value Qt, remove the text ID of the document to be updated from the chain. , Integrate other text data and re-register surrogate data. For the update data, surrogate data is newly created and registered with another sid. Specifically, using the examples of FIGS.
Since the sid of 1 corresponds to the update of the document whose d is 1, and the integration process has been performed, the text data whose tid to be updated is 1 and the text data whose tid is 2 already registered are surrogate data again. To recreate
Re-register with id = 1. At this time, if the text data with tid of 1 and 2 are integrated and the threshold Qt is exceeded, surrogate data with sid of 1 is created only with tid2, and the surrogate data of the document with tid of 1 is the new sid. And register. In this case, in order to remove the chains of 1 and 2 of tid, the sid of the first record corresponding to tid of 1 in the surrogate ID table is changed to a new sid, and the sid of the text ID table is set to 1.
Corresponding to the first record tid 2 and chain 0
And register 1 as the tid in the record of the new sid corresponding to the document with the tid of 1. Furthermore, the tid of the first record in the text ID chain table is set to -1.
When one sid corresponds to one tid, that is, for surrogate data that has not been divided or integrated, it is sufficient to re-register the surrogate data with the sid obtained. In this case, it is not necessary to change the correspondence table of the surrogate ID table and the text ID table. All you have to do is update the body of the surrogate data, such as the character component table and condensed text. After the above surrogate data update processing, if the text data is updated with the specified tid, all data update processing is completed.

The processing of registering, searching, deleting and updating data using surrogate data by division and integration has been described above. The present embodiment has an effect that there is a large variation in the text capacity of the document to be registered, and the data amount of the surrogate data is prevented from becoming uneven compared to the text data amount, and as a result, the surrogate data amount is reduced.

Next, the second embodiment will be described. In the present embodiment, when the AND condition between the search terms is given in the first embodiment, the surrogate data is replaced with the OR condition for the search, so that the narrowing-down ratio in the surrogate data is lowered, and as a result, finally. This eliminates the disadvantage that the amount of text data to be scanned increases. In this embodiment,
As shown in FIG. 15, the surrogate data created by integrating the text data and the surrogate data created by dividing the text data are set as separate files. By dividing the files in this way, it is possible to search the integratedly created surrogate data, that is, the integrated surrogate data under an AND condition, and search the dividedly created surrogate data, that is, the divided surrogate data under an OR condition. . When the AND condition between terms is given, it is only the divided surrogate data created by dividing the text data that needs to be searched by the OR condition. Therefore, by searching the integrated surrogate data under the AND condition and only the divided surrogate data under the OR condition, it is possible to reduce the number of search candidate documents by searching the surrogate data.

Hereinafter, a method of managing surrogate data in a separate file, a data registration process, and a search process will be described. First, the form of the one-character component table of surrogate data is shown in FIG. In this embodiment, the integrated surrogate data and the divided surrogate data are separately managed in this way, and the surrogate ID is also separately managed. For example, information of integrated surrogate data sid1 and si of divided surrogate data si
Information in which d is 1 represents completely different data. FIG. 17
Shows another example of creating a condensed text which is another surrogate data. Also in this case, the integrated surrogate data and the surrogate ID of the divided surrogate data are separately managed.

FIG. 18 and FIG. 19 are correspondence tables of surrogate ID (sid) and text ID (tid) that correlate the surrogate data and text data created in this way. First, FIG. 18 shows an example of a surrogate ID table for converting from tid to sid. The record number corresponds to tid, as in the first embodiment. However, there are documents having the same sid, such as documents with tid of 1 and 6, but this shows different surrogate data. The distinction is made by chain. That is, the one with chain of 0 means the sid of the integrated surrogate file, and the other than 0 means the sid of the divided surrogate data. For example, tid
Documents with 1 and 2 correspond to the integrated surrogate data with the same sid of 1, but the document with tid of 6 has sid of 1.
Two or three divided surrogate data correspond.

On the contrary, FIG. 19 shows an example of a conversion table from sid to tid. Again, the record number of the tid table corresponds to sid, but the table is divided into two because the integrated surrogate data and the divided surrogate data separately manage the sid. The text ID table 1 is a table for converting sid of integrated surrogate data to tid, and the text ID table 2 is a table for converting sid of divided surrogate data to tid. The text ID table 1 has a chain table because one tid corresponds to a plurality of sids for integration. The format is the same as in the first embodiment. However, the text ID table 2 has sid to chain.
There is no need for a chain table because there is no. Instead, it has the information from which part of the text data is divided to create the surrogate data. As I will explain later,
By doing so, it is possible to scan only a part of the long text data and shorten the search time. For example, it is indicated that the data with the sid of 2 of the divided surrogate data is created by cutting out the portion of the text data with the tid of 6 from the beginning of the 230th byte to the length of 19,107 bytes. There is. Also, the text ID
The item top in Table 2 indicates the first surrogate ID in the chain, because one text ID is linked to a plurality of surrogate IDs. These text ID table, surrogate ID table, and chain table, when no data is initially registered,
All tid and sid are initialized to -1. That is, as in the first embodiment, an ID of -1 means an empty record.

FIG. 20 shows how to create such surrogate data and conversion table, and how to register the data.
The PAD diagram of FIG. First, one piece of data is first read, and the data length is compared with the threshold value Qt. If the data length is less than or equal to the threshold value Qt, data integration processing is performed and registered as integrated surrogate data. First, each ID is registered in the text ID table 1 and the surrogate ID table in which the sid and tid of the integrated surrogate data are associated with each other. Then, the text data is integrated in a range in which the data amount does not exceed the threshold value Qt, and the tid of the integrated text data is registered in the chain table of the text ID table 1 for integrated surrogate. Also, sid is registered in the tid-th record of the surrogate ID table. Finally, the surrogate data is created and registered with the integrated text data, the text data is registered, and the processing is ended.

When the threshold value Qt is 20,000 bytes, the registration of the text data shown in FIG. 4 will be described as a specific example. First, the text data whose tid is 1 is read, and it is checked whether the data amount exceeds the threshold value Qt. When the threshold value Qt is not exceeded, 1 is set as tid in the first record, which is an empty record in the text ID table 1, and ch
Register 0 as ain. In the surrogate ID table, 1 is registered as the sid and 0 is registered as the chain in the first record corresponding to the tid of 1. Then tid is 2
Read the text data of and check the amount of data. In this case, the sum of the text data amounts of tid of 1 and 2 is less than the threshold value Qt, so the data is integrated to create surrogate data. That is, the chain of the first record in the text ID table 1 is set to 1 and the text ID
2 as the sid in the first record of the chain table,
0 is registered as chain, 1 is registered as sid, and 0 is registered as chain in the second record of the surrogate ID table.

The read text length is the threshold value Q.
If it is larger than t, it is processed as divided surrogate data. That is, the text I for the divided surrogate data
Tid in D table 2 and s in surrogate ID table
The id is registered, and the surrogate data is registered while dividing the text data within a range not exceeding the threshold value Qt. At this time, the position and length in the text data of the divided data are registered in the text ID table 2 together with tid, and sid is registered in the surrogate ID table.
Finally, the text data is registered and the process ends. For example, when the text data having the tid of 6 in FIG. 4 is registered, the text length is larger than the threshold value Qt, so 6 is set as the tid and 1 is set as the top in the first record, which is an empty record of the text ID table 2. , Offset
Is registered as 0, the length is registered as 19,230, and 1 is registered as the sid and 0 is registered as the chain in the sixth record corresponding to the tid of 6 in the surrogate ID table. Where the length of 19,23
The value 0 indicates that the data length is 19,230 bytes as a result of dividing the text with the data amount equal to or less than the threshold value Qt. Then, surrogate data is created for the divided data within the next threshold value Qt. If the length of the divided data is 19,107 bytes, the text ID
6 as the tid in the second record of table 2
As 1 and offset as 19,230, le
Register 19,107 as ngth. Surrogate I
In the D table, the chain of the sixth record is changed to an empty record of 1 in the surrogate ID chain table, and 2 is registered as sid and 0 is registered as chain in the first record of the surrogate ID chain table. Three
For the second divided data, the text ID table 2
6 as tid, 1 as top, offset
As 38,333 and the length as 19,095
And the chain of the first record of the surrogate ID chain table is changed to the next empty record 2, and 3 is set as the sid of the second record.
Register 0 as ain.

Next, a search process using the surrogate data thus created will be described with reference to the PAD diagram of FIG. First, a search word, a character in the search word, and a logical condition are extracted from the given conditional expression. Then, the surrogate data is searched. At this time, when the logical condition of the conditional expression has an AND condition, only the divided surrogate data is replaced with the OR condition to be searched. The search result of the integrated surrogate data is the integrated surrogate ID, and the search result of the divided surrogate data is the divided surrogate ID.

Integrated surrogate ID and split surrogate ID
If both of the results are 0, it is determined that there is no relevant document and 0 results are output. In other cases, the text data is searched as needed and the resulting tid is output.
First, a search process for divided surrogate data will be described. When the logical condition of the conditional expression includes an AND condition and the divided surrogate ID is not 0, it is necessary to search the text data before the division for the corresponding document. That is, the divided surrogate ID is converted into tid using the text ID table 2, all text data of the corresponding tid are searched,
Store the resulting tid in the buffer tidout. After that, the buffer tidout is used to convert the integrated surrogate ID into tid by using the text ID table 1 according to the search result of the integrated surrogate data, and store the tid which is the search result of the text data by the tid,
Output both results together.

If there is no AND condition in the logical conditions of the conditional expression, the conditional expression has not been corrected, so the result of the divided surrogate data will be correct if the search word is composed of a single character type. If the search term is not a compound character type,
That is, in the case of a single character type, the result of converting the divided surrogate ID to tid using the text ID table 2 is held in the buffer tidout as it is. If the search word is a complex character type, it is necessary to search the text data. However, in this case, it is not necessary to search all the corresponding text data, and only the text portion corresponding to the obtained divided surrogate ID may be searched. For example,
In the example of FIG. 19, when 3 is obtained as the search result of the surrogate data as the divided surrogate ID, the text data whose tid is 6 is 1 from the 38,333th byte from the beginning.
The search range may be 9,095 bytes. The tid that matches the conditional expression thus obtained is stored in the buffer tidout
Hold on.

Next, the processing of the integrated surrogate data search result and integrated surrogate ID will be described. The integrated surrogate ID uses the text ID table 1 and the corresponding ti
can be converted to d. And when there is no chain, that is, when the surrogate data is not created by integrating other text data, and the search term consists of a single character type, it is not necessary to search the text data and the integrated surrogate ID is used. The converted tid is added as it is to the previously created buffer tidout and output. Also, if the search term is composed of compound character types or if there is a chain of tid, the text data of the obtained tid is searched and the result is buffered in the tidou.
Output in addition to t.

The state of candidate document extraction by the above search processing will be described with reference to FIGS. 22 and 23. 22 shows AN
This is an example of searching with a conditional expression search: AND (document, data) having a D condition. Since there is an AND condition, the integrated surrogate data is searched under the AND condition and the divided surrogate data is searched under the OR condition. First, regarding the character component table search, in the character component table of FIG. 16, the integrated surrogate data is a condition that includes both “document” and “data”, that is, ('sentence', 'writing', 'de', ' Search with a condition that includes all the characters', 'ta'). On the other hand, the divided surrogate data is searched under the condition that it contains either "document" or "data". That is, a document containing two characters ('sentence', 'call') or ('de', '-',
Search for documents that contain the three characters'ta '). As a result of searching the character component table, sid2 is obtained as the result of the integrated surrogate data and sid2 is obtained as the result of the divided surrogate data in the example of FIG. Similarly, the result of the condensed text search is that the integrated surrogate ID is 2 and the divided surrogate ID is 2. First, if the result of the divided surrogate data is processed, for example, the divided surrogate ID 2 is converted into the tid 6 by the text ID table 2 shown in FIG. Divided surrogate data is ANDed with OR
Since the search is performed by replacing with the condition, it is necessary to search the text data, and the text data with tid of 6 is searched and the result is stored in the result storage buffer tidout. According to the data example shown in FIG. 4, the document whose tid is 6 does not satisfy the condition, so the buffer tidout becomes null. Here, the symbol null represents a state with no data.
Next, as a result of integrated surrogate data, integrated surrogate ID
Process. Text ID table 1 shown in FIG.
And convert to tid, the tid is 3, 4,
5 is obtained. Since tid is chained, the corresponding text data is searched for. For example, in the case of the data of FIG. 4, 3 and 4 are obtained as tid. This is the buffer t which is the processing result of the previous divided surrogate ID.
Add to idout and buffer tido as final result
ut has tid stored as 3 and 4, and outputs this as a search result.

Another search example will be described with reference to FIG. This example is a search example using a complex character type, and the conditional expression is search: data amount. In this case, since there is no AND condition between the search terms, the integrated surrogate data and the divided surrogate data can be searched with the same conditional expression. In the character composition table, ('de',
"-", "Ta", "quantity") is searched for under the condition that all characters are included, and the condensed text is a character string of both subcharacter strings ("data", "quantity") divided at character type change points. Search on the condition that includes. As a result, in the surrogate data of FIGS. 16 and 17, the integrated surrogate ID is 2 and the divided surrogate ID is 2. Next, the divided surrogate data is converted using the text ID table 2. If the text ID table shown in FIG. 19 is used, the divided surrogate ID 2
Has a tid converted to 6. If the search word is a single character type, the obtained tid is used as it is in the buffer tidou
Although it can be stored in t, since it is a complex character type, the text data is searched and it is confirmed whether or not "data" and "quantity" actually appear consecutively. However, at this time, it is not necessary to set all the text data of the document whose tid is 6 as the search range. Only the portion containing both "data" and "quantity" confirmed in the surrogate data search need be searched. According to the text ID table 2 of FIG. 19, the text data corresponding to the result sid of 2 based on the surrogate data is
Tid is 6, offset is 19,230, length
Since h is the portion of 19,107, only this is searched and the result is stored in the buffer tidout. In the data example of FIG. 4, the word “data amount” certainly appears, so
Store 6 in the buffer tidout.

Next, the integrated surrogate ID is converted into tid using the text ID table 1. According to the example of FIG. 19, sid 2 to tid 3, 4, and 5 are obtained. ti
Since d is chained, these text data are searched, and as a result, the text whose tid is 5 matches the condition. This result is added to the buffer tidout and the final result is 6
And 5 are stored.

In the above, as the second embodiment, the data registration and retrieval processing in the case of being divided into integrated surrogate data and divided surrogate data has been described. According to this embodiment, the surrogate data that needs to be OR-searched can be limited even under the AND condition between search terms, so that a high narrowing down rate can be obtained and a high-speed full-text search can be realized. Further, when the surrogate data is created by dividing the long text data, since the division point of the original text data is recorded, there is an advantage that the search time can be shortened by searching only the necessary text data.

Next, a third embodiment will be described. In the present embodiment, surrogate data is created by integrating registered documents based on the number of registered documents. For example, if the text data integration unit is set to 10 documents, the text data is collected 10 by 10 to create a surrogate file. Registration of surrogate data by summarizing the number of cases and search processing using the registration will be described in detail. First, registration is performed according to the procedure for registering integrated surrogate data described above. That is, the text data of a predetermined number is read, and the data is integrated to create surrogate data. However, at this time, the text ID table and the surrogate ID table used in the first embodiment are not necessary. This is because the number of documents to be integrated is fixed, and the corresponding surrogate ID can be obtained by calculation from the text ID. For example, when surrogate data is created collectively for 10 cases, the sid is 1 for the surrogate data corresponding to the texts 1 to 10 of tid. Conversely, sid
The text data corresponding to No. 2 is from tid 11 to 20
Is. In this way, the corresponding tid can be obtained by simply multiplying by 10. The surrogate data registered in this way can be represented in the same formats as in FIGS. 8 and 9 as in the first embodiment. However, in this embodiment, sid 1 is tid 1 to 10, and sid 2 is tid.
As in 11 to 20, 10 documents are used as a unit. Similar to the above-described embodiments, the search can be performed by first searching the surrogate data, extracting the candidate document, and searching the text data corresponding to the candidate document. A specific example will be described with the following conditional expression. search: data As before, the character component table is ('de', '-',
'Ta') is searched with a condition that includes all characters, and the condensed text searches for documents with the character string "data". The surrogate data satisfying this condition is s in the character component table of FIG.
The ids are 2 and 4. Therefore, in the next search for the condensed text, the condensed texts whose sid are 2 and 4 are searched to extract the candidate documents including the character string of "data". In the example of FIG. 9, si
d corresponds to 2 and 4. In the next text data search, the text data of the text ID corresponding to the obtained surrogate ID is targeted. The surrogate data created collectively by 10 cases has the text IDs whose sid is 2 from 11 to 20 and the text IDs whose sid is 4 from 31 to 40. Therefore, the text data of 20 documents with the tid of 11 to 20 and 31 to 40 may be searched, and the document matching the conditional expression may be output as the search result.

An example of creating surrogate data using the number of cases as a guideline for integration has been described above. In this example,
This is effective when the amount of data per case is relatively uniform and small. Further, there is an effect that a table is not particularly required to associate the surrogate data with the text data.

Now, the fourth embodiment will be described. Figure 2
FIG. 4 is a diagram showing the configuration of this embodiment. The present embodiment is different from the first embodiment in that the plural document batch reading program is stored in the memory 2406 and the directory table is stored in the memory 240.
8 is different in that the text data of the document is provided in each of the four magnetic disk devices 2403-A to D.
Each of the four magnetic disk devices 2403-A to 2D-D has a magnetic disk device controller inside and a buffer memory for holding the temporary data after reading the data in the disk. With a SCSI adapter 2409
Connected to the main bus via. Document data is distributed and stored on four magnetic disks. In this embodiment, 8 KB, which is the unit of data access to the disk
Text data for one case is divided by the data length of and is stored in each disk. The directory table 2408 stores the same information as the directory file shown in FIG. That is, by referring to the directory table 2408, regarding the text data of the candidate document obtained by the surrogate data,
The offset position and length from the beginning of the file can be known. The multiple document batch read program receives the read command composed of the offset position and the length from the head of the file, reads and integrates the text data distributed and stored in each disk, and stores it in the work memory 2407. To do.

Hereinafter, the search process will be described by focusing on the parts peculiar to the present embodiment. First, regarding the characters used after the search of the given conditional expression, a document including all the characters in the search word is extracted as a candidate using the character component table 2404 of the surrogate data. Although a condensed text as surrogate data, a surrogate ID table, a surrogate ID table, etc. are not shown in FIG. 24, a condensed text, a surrogate ID table, a surrogate ID table, etc. may be used to obtain a candidate document. Needless to say. Next, the text data of the candidate document is referred to search for a document that matches the conditional expression. In the present embodiment, at this time, the text data is read from the magnetic disk to the work memory 2 by using the multiple document batch reading program.
The data is read out to 407 and search processing is performed.

Details of reading out the text data are shown in FIG.
This will be described using 5. In this embodiment, as shown in FIG. 25, the text data is divided in units of a data length of 8 KB and stored in the disk device. According to the text data length of the example shown in FIG. 4, in the case of the document 1, since the data length is 6232 bytes, it is stored in one disk device of the disk device A. On the other hand, since the data length of the document 2 is 13560 bytes, which is larger than 8 KB, the text data is stored in the two disk devices B and C.

At the time of retrieval, for the candidate document obtained from the surrogate data, first, a directory table is used to generate a sequence of read instructions composed of offset positions and lengths from the file head of each text data. In the example of FIG. 25, documents 1, 3 and the like are obtained from the surrogate data as candidates, the offset and length which are directory data are respectively extracted from the directory table, and the read command is received by the multiple document batch reading program, and the text data file is read. Based on the offset position and the length from the head, it is divided into read commands for data stored in each disk in a distributed manner, and read commands are sequentially issued to the disk device. In this case, the directory table may also be referred to. For example, document 1 is o
Since ffset is 0, it is stored from the head of the data, that is, from the disk device A, and the length is 6232 bytes, which is less than 8 KB, so it can be seen that the data is stored only in the disk device A. In this way, the disk device and the storage position of the text data are calculated from the offset and the length of the read command, and the read command is issued to each disk device. In the example of FIG. 25, a read command for document 1 is issued to the disk device A, and a read command for document 3 is issued to the disk device D.

At the time of issuing this read command, if the disk device is busy processing other commands and is in a busy state, no command is issued to the disk device and the command is queued. Later, the commands queued when the disk device becomes ready are collectively sent to the disk device. For example, in the example of FIG. 25, when the candidate documents obtained from the surrogate data are documents 1, 3 and 4 and the disk device A is in a busy state and a read command cannot be sent, the document 1 is returned to the ready state. The read commands of 4 and 4 will be sent together.

Each disk device reads data from the magnetic disk in accordance with the sent instruction, stores the data in the buffer memory inside the disk device, and reports the completion of the read command to the multiple document batch reading program. To do. The multiple document batch read program that has received the report integrates the data from the respective disk devices as shown in FIG. 26 and transfers the data to the work memory 2407. The example in the figure shows that the text data of the document 1 stored in the disk device A and the text data of the document 3 stored in the disk device D are respectively transferred to the work memory. That is, in the read example of FIG. 25, two disk devices, the disk device A and the disk device D, operate in parallel. In reality, since many candidate documents are obtained by searching surrogate data, all connected disk devices operate in parallel. In this way, the text data on the work memory read from each disk is referenced to search for a document that matches the conditions, and the search result is displayed on the display 2402.

The fourth embodiment has been described above. According to the present embodiment, the magnetic disks operate in parallel to collectively process a plurality of read commands and the reading speed from the file is improved, so that the deterioration of the search response when reading the text data file is small. effective. Further, if the buffer of the magnetic disk device is also used as a read-ahead buffer that always reads a specified amount from the point where the read command was issued, there is a possibility that there is already data in the buffer even when the read command comes, and Since there is no seek or overhead of waiting for rotation, there is an effect of further improving performance.

[0071]

According to the present invention, since surrogate data can be created with text data having a substantially constant capacity, the surrogate data has a proper capacity as compared with the original document capacity, and the narrowing rate by the surrogate data is also suitable. You can get something. As a result, high-speed full-text search can be realized. Further, by creating a correspondence table of text data and surrogate data at the time of registering a document, it is possible to accurately search the corresponding text data after hierarchical pre-search by surrogate data. Similarly, when deleting and updating data, it is possible to make the database consistent while associating the text data with the surrogate data. In addition, by distinguishing the integrated surrogate data from the divided surrogate data, the integrated surrogate data is AN even if an AND condition between terms is given.
Since the search can be performed under the D condition, the narrowing rate can be improved. At the same time, in the search by the term of the complex character type for which the result cannot be specified with the surrogate data, even the long text data that requires more data scan can search only the necessary part of the text data from the divided surrogate data. The amount of search is reduced, and the search time can be shortened. Furthermore, since a plurality of external storage devices can be operated in parallel to retrieve text data, the retrieval speed can be increased.

[Brief description of drawings]

FIG. 1 is a conceptual diagram of division and integration of surrogate data according to document capacity.

FIG. 2 is a conceptual diagram showing a correspondence table of surrogate data and text data.

FIG. 3 is a configuration diagram of a first embodiment.

FIG. 4 is a diagram showing a format of registration data in the first embodiment.

FIG. 5 is a conceptual diagram showing a conversion table from a text ID to a surrogate ID in the first embodiment.

FIG. 6 is a conceptual diagram showing a conversion table from surrogate ID to text ID in the first embodiment.

FIG. 7 is a PAD showing a processing procedure at the time of data registration in the first embodiment.

FIG. 8 is a diagram showing an example of creating surrogate data (character component table) in the first embodiment.

FIG. 9 is a diagram showing an example of creating surrogate data (condensed text) in the first embodiment.

FIG. 10 is a PAD diagram showing a processing procedure at the time of data search in the first embodiment.

FIG. 11 is a diagram illustrating a procedure of extracting candidate documents at the time of searching in the first embodiment.

FIG. 12 is a diagram illustrating a procedure of candidate document extraction at the time of search in the first embodiment.

FIG. 13 is a PAD diagram showing a processing procedure at the time of deleting data in the first embodiment.

FIG. 14 is a PAD diagram showing a processing procedure at the time of updating data in the first embodiment.

FIG. 15 is an explanatory diagram showing a method of creating surrogate data in the second embodiment.

FIG. 16 is a diagram showing an example of creating surrogate data (character component table) in the second embodiment.

FIG. 17 is a diagram showing an example of creating surrogate data (condensed text) in the second embodiment.

FIG. 18 is a conceptual diagram showing a conversion table from a text ID to a surrogate ID in the second embodiment.

FIG. 19 is a conceptual diagram showing a conversion table from a surrogate ID to a text ID in the second embodiment.

FIG. 20 is a PAD diagram showing a processing procedure at the time of data registration in the second embodiment.

FIG. 21 is a PAD diagram showing a processing procedure at the time of data search in the second embodiment.

FIG. 22 is a diagram illustrating a procedure of candidate document extraction at the time of search in the second embodiment.

FIG. 23 is a diagram illustrating a procedure of candidate document extraction at the time of search in the second embodiment.

FIG. 24 is a diagram showing a configuration of a fourth exemplary embodiment.

FIG. 25 is a diagram for explaining details of reading text data.

FIG. 26 is a diagram for explaining data transfer from each disk device to a work memory.

[Explanation of symbols]

 301, 2401 Keyboard 302, 2402 Display 303, 2403 Magnetic disk 304, 306, 307 Memory 305, 2405 CPU 2404, 2406, 2407, 2408 Memory 2409 SCSI bus adapter

Claims (20)

[Claims] 1. Surrogate data in which document information is compressed by separately storing text data of a document as a file and storing characters or words in the text data or both of them separately in the file without duplication , When searching for information, first refer to the surrogate data as a document that contains the characters or words included in the search term in the specified search condition expression, and then give a candidate, then match the candidate with the search condition expression. In the information retrieval method for retrieving a document by referring to the text data, the text data of a plurality of documents are integrated under a predetermined condition, and the surrogate data is created for the integrated text data. Create a correspondence table of data and surrogate data, and search at the time of the surrogate data. Refer to the list of surrogate data candidates that may satisfy the search condition expression, find the text data corresponding to the candidate based on the correspondence table, and refer to only the corresponding text data to create the search condition expression. An adaptive surrogate type information retrieval method characterized by retrieving matched documents. 2. The adaptive surrogate-type information search method according to claim 1, wherein a plurality of text data are integrated with a predetermined number of documents as the predetermined condition. 3. The adaptive surrogate type information retrieval method according to claim 1, wherein the predetermined condition is based on a predetermined text data capacity, and a plurality of text data are integrated within a range not exceeding the capacity. An adaptive surrogate type information retrieval method characterized by the above. 4. Surrogate data in which text information of a document is compressed is stored as a file, and characters or words in the text data, or both are separately stored in the file without duplication to create separate surrogate data corresponding to the document. , When searching for information, first refer to the surrogate data as a document that contains the characters or words included in the search term in the specified search condition expression, and then give a candidate, then match the candidate with the search condition expression. In the information retrieval method for retrieving the document by referring to the text data, a predetermined data capacity Qt is set in advance, and when the text data capacity is less than Qt when the surrogate data is created, the text data is integrated and Create surrogate data, and if the capacity of one text data is more than Qt In that case, the text data is divided within a range not exceeding Qt, the surrogate data is created separately for each of the divided text data, and a correspondence table of the text data and the surrogate data is created. Search for the surrogate data that may satisfy the search condition expression by referring to the data, find the text data corresponding to the candidate based on the above correspondence table, and refer to only the corresponding text data to find the search condition expression. An adaptive surrogate type information retrieval method characterized by retrieving documents that match the above. 5. The adaptive surrogate information retrieval method according to claim 4, wherein when dividing text data exceeding Qt, the surrogate data is divided at any break of a sentence, paragraph, chapter, or section. An adaptive surrogate type information retrieval method characterized by creating. 6. The adaptive surrogate type information retrieval method according to claim 4, wherein the value of Qt is from 1 KB to 30 KB. 7. The adaptive surrogate type information retrieval method according to claim 4, wherein the value of Qt is 1 in the text storage medium.
An adaptive surrogate-type information retrieval method characterized by taking a read unit, that is, a read buffer size. 8. The adaptive surrogate-type information search method according to claim 4, wherein the search condition is AND between search words.
When given a condition, that is, a condition for searching for a document that includes all specified search terms, surrogate data created by integrating a plurality of documents is searched by an AND condition between words, and one document is An adaptive surrogate-type information retrieval method characterized in that surrogate data created by dividing each piece of text data into separate pieces of text data is searched for by OR conditions between words and candidates for surrogate data are given. 9. The adaptive surrogate type information retrieval method according to claim 8, wherein a file storing each of the surrogate data created by integrating the plurality of documents and the one document is divided into a plurality of text data. An adaptive surrogate-type information retrieval method characterized in that a file for storing each of the surrogate data created separately for each of the divided text data is a separate file. 10. The text data of the document is stored as a file, and the characters or words in the text data, or both are separately stored in the file without duplication so that surrogate data in which the document information is compressed is separately created for the document. , When searching for information, first refer to the surrogate data as a document that contains the characters or words included in the search term in the specified search condition expression, and then give a candidate, then match the candidate with the search condition expression. In the information retrieval method for retrieving a document by referring to text data, a plurality of external storage devices are provided to store the text data of the document as a file, and the text data of each document is stored in the plurality of external storage devices. Text data of a document which is sequentially stored and exceeds a predetermined capacity is stored in the plurality of external storages. By dividing and storing the data in a storage unit, referring to the surrogate data at the time of retrieval, providing a document candidate, and collectively reading and referring to text data corresponding to the document candidate from the plurality of external storage devices. An adaptive surrogate type information retrieval method characterized by retrieving documents that match the conditions. 11. An input device for inputting a conditional expression, an output device for outputting a result, a storage device, and a processing device, wherein text data of a document is stored as a file, and characters or words in the text data, or By separately storing both in a file without duplication, surrogate data that compresses the document information is created separately for the document, and when searching for information, include the characters or words included in the search word in the specified search condition expression. As an existing document, first, by referring to surrogate data, a candidate is given, and then a document that actually matches the search condition expression for the candidate is searched by referring to text data. The text data of a plurality of documents are integrated under a condition, and the surrogate data is added to the integrated text data. A means for creating, a means for creating a correspondence table of the text data and the created surrogate data, and a means for referring to the surrogate data at the time of searching to provide candidates for surrogate data that may satisfy the search condition expression, , An adaptive surrogate type information search characterized by comprising means for searching for text data corresponding to the candidate based on the correspondence table, and searching for a document matching the search condition expression by referring to only the corresponding text data. apparatus. 12. The adaptive surrogate-type information search device according to claim 11, wherein a plurality of text data are integrated under the predetermined condition by a predetermined number of documents. 13. The adaptive surrogate-type information retrieval device according to claim 11, wherein the predetermined condition is based on a predetermined text data capacity and a plurality of text data are integrated within a range not exceeding the capacity. An adaptive surrogate type information retrieval device characterized by the above. 14. An input device for inputting a conditional expression, an output device for outputting a result, a storage device, and a processing device. Text data of a document is stored as a file, and characters or words in the text data, or By separately storing both in a file without duplication, surrogate data that compresses the document information is created separately for the document, and when searching for information, include the characters or words included in the search word in the specified search condition expression. In the information retrieving apparatus for retrieving a document that actually matches the retrieval condition expression for the candidate by referring to the surrogate data and then retrieving the document by referring to the text data, a predetermined data capacity Qt is set in advance. The processing device says that the capacity of the text data is less than Qt when the surrogate data is created. Is a means for integrating the text data to create the surrogate data, and, if the capacity of one text data is Qt or more, divides the text data within a range not exceeding Qt, and separates the divided text data separately. Means for creating the surrogate data, means for creating a correspondence table of the text data and the created surrogate data, and a candidate for surrogate data that may satisfy the search condition expression by referring to the surrogate data at the time of search And a means for searching for a document that matches the search condition expression by obtaining text data corresponding to the candidate based on the correspondence table and referring to only the corresponding text data. Surrogate type information retrieval device. 15. The adaptive surrogate-type information search device according to claim 14, wherein when the processing device divides text data exceeding Qt, the processing device divides the text data at any break of a sentence, paragraph, chapter, or section. An adaptive surrogate-type information retrieval device characterized by creating surrogate data. 16. The adaptive surrogate-type information search device according to claim 14, wherein the value of Qt is 1 KB to 30 K.
An adaptive surrogate type information retrieval device characterized by taking a value of B. 17. The adaptive surrogate type information retrieval device according to claim 14, wherein the value of Qt is one read unit of the text storage medium, that is, the read buffer size. 18. The adaptive surrogate-type information search device according to claim 14, wherein the search condition expression is A between search words.
When an ND condition, that is, a condition for searching a document including all specified search terms is given, the processing device
For surrogate data created by integrating multiple documents, search for AND conditions between words, and divide one document into multiple text data, and for surrogate data created separately for each divided text data, interword O
An adaptive surrogate-type information retrieval device characterized in that a surrogate data candidate is searched for under an R condition. 19. The adaptive surrogate-type information search device according to claim 18, wherein a file for storing each of the surrogate data created by integrating the plurality of documents,
An adaptive surrogate-type information retrieval device characterized in that the one document is divided into a plurality of text data, and a file for storing each of the surrogate data created separately for each of the divided text data is a separate file. . 20. An input device for inputting a conditional expression, an output device for outputting a result, a storage device, and a processing device, wherein text data of a document is stored as a file, and characters or words in the text data, or By separately storing both in a file without duplication, surrogate data that compresses the document information is created separately for the document, and when searching for information, include the characters or words included in the search word in the specified search condition expression. In the information search device that first refers to surrogate data as a document to list candidates and then refers to the text data for a document that actually matches the search condition expression, searches the text data of the document into a file. A plurality of external storage devices are provided to store the text data of each document as the plurality of external storage devices. A unit for sequentially storing text data of a document exceeding a predetermined capacity in the device and storing the divided text data in the plurality of external storage devices, and the processing device refers to the surrogate data at the time of search to extract a document candidate. Means for designating an external storage device to be accessed and a storage position based on the extracted directory data of one or more document candidates, and collectively reading text data corresponding to the document candidates from the plurality of external storage devices. An adaptive surrogate type information retrieving apparatus comprising means for retrieving a document that matches a condition by referring to read text data.