JPH1027183A - Data registration method and device - Google Patents

Abstract

(57) [Summary] An object of the present invention is to provide a data registration method and apparatus for performing high-speed full-text search (full-text search). A text (1604) to be searched is registered (1601), a condensed text (1605) in which duplication of words repeatedly appearing in the text is eliminated, and whether a predetermined character is included in the text. Character table (16)
03) (1602, 16)
03), register.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data (document) registration method and apparatus which enable full-text search in a data search system. In addition, a data (document) registration method for a search that enables a search omission due to a difference in a synonym or a notation when a search is performed using a keyword (called a free word) that is not controlled, and Related to the device. The present invention also relates to an information registration method and apparatus for an information search system suitable for collectively determining whether or not a plurality of character string sets exist in a searched character string.

Further, the present invention provides a collective magnetic disk drive having a large storage capacity suitable for an apparatus for implementing the above information retrieval system and capable of writing and reading in a short time.
Also, the present invention relates to a collective magnetic disk device suitable for continuous writing and reading of a plurality of files.

[0003]

2. Description of the Related Art In recent years, the importance of large-scale database services including not only secondary information (bibliographic information) such as document information and patent information but also primary information (text) has been increasing.
In the information search of such a database (sometimes abbreviated as DB), a method using a keyword or a classification code has been conventionally used.

[0004] A keyword is assigned when the information is registered in the database (referred to as indexing).
Experts select and add words from a controlled vocabulary (called a thesaurus). The DB searcher selects a keyword from the thesaurus and performs a search.
However, this keyword assignment operation involves a very complicated operation. That is, it is necessary to read the contents of the data to be registered and select an appropriate vocabulary expressing the contents from the thesaurus. If the indexing is not performed properly, the correct information cannot be obtained from the database. Therefore, there is a problem that this indexing requires an expert who has expertise in data contents and is also familiar with the vocabulary registered in the thesaurus. Similarly, at the time of retrieval, if an appropriate vocabulary according to the thesaurus is not specified as a keyword, there is a problem that requested data cannot be called or unnecessary data is mixed in the called data.

[0005] Further, in this thesaurus, since the classification system itself changes with the years, there arises a problem that keywords and classification codes must be constantly updated.

[0006] Furthermore, since indexing takes time, a large amount of new data is registered collectively by batch processing. Therefore, there is also a problem that information that can be searched always has a certain period of time. For this reason, with the spread of DBs, even non-DB specialists can easily register and search data in free words (also called uncontrolled words) without being bound by a thesaurus or the like. A system has been desired.

[0007] Further, as the size of the database increases, the contents of data cannot be described in sufficient detail only by controlled words described in a thesaurus, so that even if a keyword is searched, only a few dozen to a few hundred are narrowed down. It is getting stuck. The only way to find the desired data from among them is to read them directly, which is a major problem in search efficiency.

To solve the problem of the current retrieval method based on the indexing using thesaurus restricted words, attempts have been made for automatic abstraction and automatic indexing.
In the case of Japanese, linguistic difficulties also necessitate various dictionaries, so that the above-mentioned essential problem has not been solved.

In the search process using such free words,
When the keyword specified by the user, that is, the search character string, and the words used in the DB to be searched often indicate the same content, but the search or omission is inconsistent, resulting in a search omission. There is. For example, the word “piano” may be described as “Pyano”, and the word “interface” may be described as “interface”, “interface”, or “interface”. Due to such subtle variations in syllable notation, it may not be possible to retrieve desired information.

In the following, expanding to a character string having a different notation is referred to as a notation expansion, and expanding to another character string using a dictionary is referred to as synonym expansion. Character strings with different notations are called different notations.

As a fundamental solution to these problems, a full-text search (full-text search) in which a searcher can search the contents by directly referring to the body of data based on free keywords (called free words or uncontrolled words) ) Systems have been proposed.

FIG. 1 shows a typical configuration, and its contents will be described below.

The search system 101 is connected to a host computer, and receives a search request and transmits a search result via a communication line. Search request 1 from host computer
When 07 is sent, the search control means 103 accepts and analyzes this, and sends the corresponding search control information 108 to the character string collation means 105 and the complex condition determination means 104.
Further, the search control means 102 controls the storage device control means 103 to convert the character string data (text data) 111 stored in the character string storage means 106 into the character string matching means 1.
05.

The character string matching means 105 compares the input character string data with a preset search character string (keyword).
10 is output to the complex condition determination means 104. The compound condition determining means 104 adds detection information 110 to compound conditions relating to the positional relationship, co-occurrence relationship, and the like between character strings described in the search request.
Check whether or not matches. If this matches,
The identification information and the data content of the corresponding data are output as a search result 109 and sent back to the host computer.

One of such conventional examples is R.L.
Hanskin and Horror: “Operational Characteristic of a Hardware Beast Pattern Matcher”, AC M Transaction on Database Systems, No. 8
Vol. 1, No. 1983 (RLHaskin and A. Hollaa
r: “Operational Characterstics of a Hardware-Base
d Pattern Matcher ”, ACM Trans. on Database Syste
m, Vol. 8, No. 1, 1983).

As a method of collating a character string by the character string collating means 213 which is a key of the character string retrieval apparatus 200 described above, a method of retrieving a plurality of character strings by one scan using a finite automaton is known. I have. A typical method is A. buoy. Aho and M. Jay. Classic: “Efficient String Matching”, Communications AC M, No. 1
8, No. 6, 1975, AV Aho and MJ Coras
ick: "Efficient String Matching", CACM, Vol 18, N
o.6, 1975 discloses an example.

This document describes in detail two types of automaton creation methods and a character string collation method using the automaton. Hereinafter, each will be described.

First, the first method (hereinafter referred to as conventional method 1) will be described with reference to FIG. FIG. 6 is a state transition diagram of an automaton for detecting a keyword “interface” given by a user from character string data. Here, the circle represents the state of the automaton, and the arrow represents the state transition. The character added to each arrow indicates the input character at which the corresponding state transition occurs. In this figure, when expressing a negation such as a character other than "n" and a character other than "i", a negative sign "" is added and "@"
“I”｝ ”. An arrow 403 indicates a starting point state at which a state transition starts. The numerical value described inside each circle indicates the state number of the same state. The double circle represents the state of the end point indicating that the “interface” has been collated.
The feature of this method is that state transitions for all input characters that may be input are described by an automatic machine. For this reason, the number of state transitions increases, so that there is a problem that the time required to create an automaton, that is, the number of keywords increases, becomes extremely long.

Hereinafter, the character string collating operation of the conventional method 1 will be described with reference to FIG. When a character is input to the automaton, it is clarified by placing in the token in which state the input character should be collated. That is, a token is a mark that indicates the position of a state that transits in the automaton. First, as an initial setting, the token is placed in state 0, which is the starting point state. In this example, if the input character is "i", the token moves to state 1. If a character other than "i" comes in, the token moves to state 0. On the other hand, if the token is in state 1 and the input character is “on”, the token moves to state 2. If “a”, move to state 1. If it is a character other than "A" and "N", it moves to state 0. Next, when the token is in state 2, if the input character is "ta", the token moves to state 3. Here, if "i" is input, the token moves to state 1. Furthermore,
If there is a token in state 3 and "face" is input, the token moves from state 4 to state 5 to state 6 to state 7. State 7 is indicated by a double circle, and here, the character string “interface” has been collated.

In the conventional method 1, state transitions for all input characters that may be input are described in the automaton. Therefore, as the number of keywords increases, the number of state transitions increases and the time required to create the automaton becomes extremely long. There is a problem. Hardware for realizing the present method is disclosed in Japanese Patent Application Laid-Open Nos.
It is disclosed in Japanese Patent Publication No. 0-105040.

Next, the second method (hereinafter referred to as conventional method 2) will be described. The conventional method 2 is devised to shorten the automaton creation time as compared with the conventional method 1. In the conventional method 2, the time required for creating the automaton is greatly improved to one third of that in the conventional method 1. The details are described in JP-A-63-31530. The conventional method 2 will be described with reference to FIGS. FIG. 3 shows a state transition diagram of the automaton in the case where the "interface" is collated as in FIG. By default, the token is placed in state 0, the starting state. Here, if the input character "A" is input, the collation is performed in the state 0 where the token is placed, and the state is moved to the state 1. If a character other than "i" comes in state 0, the token moves to state 0.

On the other hand, if the token is in state 1 and the input character "n" is input, the token moves to state 2. If the token is in state 2 and "ta" is entered, the token moves to state 3. Here, if the token is in state 3 and a character other than "F", such as "I", which is not described in the automaton, is input,
In the second conventional method, it is said that "fail" has occurred, and the fail table in FIG. 4 is referred to. The fail table stores the state number of the fail destination to be rematched with the state number where the token is placed. In this case, the value 0 of the fail destination corresponding to the current state number 3 is obtained, and the token is moved to the state 0. Then, the token is moved to the state 1 by collating the input character "i". Such a function is called a fail function. Further, when the input character string “interface” successively enters one character at a time, the token moves in the order of state 2 → state 3 → state 4 → state 5 → state 6 → state 7. State 7 is indicated by a double circle, and here, the character string “interface” has been collated. For example, if the keyword “interface” is given,
The text may be described in a notation (different notation) different from the search term specified by the user.

In the text, "-" (minus sign) is used instead of "-" (long sign) like "interface".
(This is called a prolonged notation), "-" is added like "interface" (this is called the presence or absence of a prolonged sound), and the difference in pronunciation notation is used like "interface""Fee" is described as "fay" (this is called "pronunciation notation").

In order to retrieve all of them, "interface", "interface", "interface", "interface",
All nine words of "interface", "interface", "interface", "interface", and "interface" need to be keywords.

An example of this case will be described with reference to FIGS. FIG. 5 is a state transition diagram of the automaton in a case where the above nine words including different notations are collated from character string data.

If the transition character is different from the beginning of the keyword, branch to another state.

For example, in the example of the keywords “interface” and “interface”, when compared from the front of the keyword, “inter” is the same, but in the next character, “fu” and “-” indicate transition characters. different. For this reason, a state transition branch occurs such that a transition is made from the state 3 to the state 22 with the transition character “F” and to the state 4 with the transition character “-”.

That is, when the transition character is different in a certain state, a tree-like automaton is formed because different transition destination states are allocated. FIG. 6 is an explanatory diagram of a fail table indicating a transition destination when a character not shown in the automaton is input. As described above, when the collation including the different notation is performed, a problem occurs that the number of states is greatly increased because the number of keywords is increased.

Also, in the character string search, the keyword "don't"
Care characters may be used. Fixed length keywords
An example in which don't care characters are used will be described with reference to FIGS. FIG. 7 shows a state transition diagram of the automaton when a keyword “A? B” including one fixed-length don't care character “?” Is searched. FIG. 8 is an explanatory diagram of a fail table indicating a transition destination when a character not shown in the automaton is input.

In this example, a one-byte character code (JIS
Code is used) to create an automaton. "?" Is a character symbol meaning that matching with any character or symbol is permitted. Therefore, the transition due to the don't care character “?” Is represented as a transition due to all the character codes ○ to FF having the state 1 in FIG.
That is, “A? B” specifies that a character string having an arbitrary character inserted at the beginning with “A” at the beginning and having an end at “B” is searched.

Even with such simple retrieval conditions, a fixed-length do
The problem that the number of states of the automaton greatly increases when an n't care character is included occurs.

As a method for solving the problem of different notations and synonyms, there is JP-A-62-011932. In this gazette, the development of different notations is called occurrence of different notations, and the development of synonyms is called similar word extraction.

FIG. 9 is a block diagram showing the configuration of this reference. In this configuration, all the search character strings input in Roman characters or katakana expressions are temporarily converted into character strings in standardized notation in katakana. In other words, a standardization process of a notation that combines a plurality of notations into one is first performed by the reverse operation of the occurrence of a different notation. Also, the search character string input in the alphabetic expression is unified to the katakana expression by the foreign language kana conversion.

In this way, the once standardized katakana character string is developed into a similar word using a synonym dictionary, and a word having the same meaning as the input katakana character string is output as a katakana character string. The katakana character string after the extraction of similar words is converted to a kanji character string by performing kana-kanji conversion, and a kana-to-foreign word conversion is performed to convert a kana-romaji character to a foreign language of an alphabetic expression, and then converted to a roman character string.

In this way, the katakana character string obtained as a result of the similar word extraction is converted into each expression of kanji, romaji, katakana, and foreign language, and is developed in different notations.

In the conventional character string search apparatus 101 shown in FIG. 1, a magnetic disk device capable of storing large-scale data is required as the character string storage means 106 which is a component of the character string search apparatus 101. . A general magnetic disk device has a problem that data input / output cannot be performed at a high speed, and a multi-head type magnetic disk device capable of data input / output at a high speed has a problem that it is very expensive.

In view of the above, there has been considered a collective magnetic disk drive in which a plurality of inexpensive general small magnetic disks are connected to increase the speed of data input / output. As one of them, there is an "image data division storage device" described in JP-A-60-117326.

This device has a plurality of magnetic disk devices, and is constituted by the same number of magnetic disk controllers as the magnetic disk devices and a master controller for controlling data transfer between the input / output buffer and the external device. In the master controller, the input data is divided into the input / output buffer or less, and the divided data is sequentially transferred to each magnetic disk controller, and the magnetic disk controller writes the data into the corresponding magnetic disk device. The master controller causes the magnetic disk controller of the magnetic disk device to which data is not being written to perform a seek operation, so that the seek time of the second and subsequent magnetic disk devices for storing data becomes apparent, and the data is lost. It is intended to shorten the time for writing and reading data.

Further, there is no method for registering data for performing a full-text search.

[0040]

When a large-capacity text database is to be searched in the conventional search system as shown in FIG. 1, the following problems arise. First, there is the problem of search time. For example, if a full-text search is to be performed on 20,000 documents having a capacity of 20 KB per document, 400M
The data of B must be scanned.
This 400 MB of text data is stored in the character string storage means, and is read out at an effective speed of about 1 MB / s on average,
Even if the matching process is performed at the same speed by the character string matching means, it takes about 7 minutes to complete the search. That is, if a general magnetic disk device is used, there is a problem that reading of text data takes time and is not practical. That is, it is necessary to increase the reading speed of the character string storage means for storing the text data to approximately the same as the processing speed of the character string matching means. This is the first problem to be solved by the present invention.

However, even if the reading speed of the character string storage means is increased to the same level as the character string collating means, that is, even if the reading speed is increased to, for example, 10 MB / s, 400 M
It is still 40 to finish scanning the text data of B.
It takes seconds. It is a second object of the present invention to reduce this to a few seconds that is practically acceptable.

Japanese Patent Application Laid-Open No. Sho 62-241026 entitled "Character String Search Method" has been filed with respect to the technology for speeding up the scanning process. In this "string search method", in order to speed up the process of searching for a specified character string in a text database (called a file), a text (called "data") The contents are checked to see what characters are used and at what frequency, and a "used character frequency distribution table" is created.

At the time of retrieval, the "used character frequency distribution table" is referred to, and the text which is first used is searched by using the least frequently used character among the keywords designated by the user, and the text is searched for. If there is, then a method is proposed in which the characters before and after that are also checked.

Further, in the above-mentioned Japanese Patent Application Laid-Open No. 62-241026,
If the frequency of the character with the lowest frequency in the "used character frequency distribution table" is zero, the search can be completed without searching for the text.

Therefore, according to Japanese Patent Application Laid-Open No. Sho 62-241026, the number of unnecessary character collations can be reduced, and the effect of increasing the search processing speed can be obtained.

However, in this method, a "used character frequency distribution table" is created for the entire database (file), and a text file (data) is searched based on the table. Therefore, when searching for a keyword related to a character that does not appear once in the entire database, the effect can be obtained in terms of the efficiency of the search process. However, in general, when the size of the database increases, the keyword appears once in the entire database. Since there is almost no character indicating that there is no search, there is a problem that the effect of the search processing by this method is almost completely lost.

It is a second object of the present invention to solve such a problem, realize an efficient search process, and enable an equivalently high-speed full-text search.

On the other hand, in a full-text search using free words, there is often a discrepancy in the expression between the keyword specified by the searcher and the word described in the text body even if the same meaning is expressed. There is. In such a case, documents having different expression forms are omitted from the search, and the target document may not be searched. Examples of such words include synonyms and variants (also called variant words or simply variant forms). Examples of synonyms are "electronic computer" and "computer" for "computer"
"Computer" and the like. Examples of the different notation are “computer” and “computer”, “computer”, “computer”, “computer”, “computer”, “computer”, “computer”. "Computer", "Computer", "Computer", "Computer"
, "Consumer", "Converter",
The "Converter" sends "Computer" to "Computer".
uter "and" COMPUTER ". In order to deal with the problem of notation between the keyword specified by the searcher and the words described in the contents of the document, the searcher must specify all of these synonyms and different notations and perform a search. is there. However, since different notations can take hundreds of forms depending on the case, it is practically difficult for the searcher to specify each one. It is a third object of the present invention to solve such a problem.

That is, in the above-described conventional example, when standardizing the notation, the information obtained by the original character string is changed, so that an expected expansion result may not be obtained.

This will be described with reference to an example of the conversion rule ““ HOO ”→“ HO ”” for the partial character string for standardization of the katakana notation. By applying this conversion rule, the character string "joho" is correctly standardized as "joho" (information). However, even if this same conversion rule is used, if "John phone" (constant heat retention) is input, it is standardized to an incorrect character string of "John phone". This affects the synonym expansion process after the standardization process and the subsequent notation expansion process, and the expected expansion result cannot be obtained. One of the objects of the present invention is to always obtain expected expansion results without performing the above-mentioned standardization.

According to the above-mentioned prior art, when keywords are synonymously expanded from “computer” to “computer” using a synonym dictionary, all search keywords input by the user are once converted into katakana expressions and then expanded into synonyms. After that, kana-kanji conversion, kana-romaji conversion, and kana foreign language conversion are performed. For this reason, the synonym dictionary must always expand from katakana character strings to katakana character strings. In other words, the headword: "computer" Synonym 1: "Keisanki" Synonym 2: "Johoshishosochi" and the like, the synonym between words had to be always described in katakana character strings. This is a problem because the kana-kanji conversion dictionary and the kana foreign-language conversion dictionary after synonym expansion must be registered so that the character strings of the expressions corresponding to these must be output. There is. In addition, even if Japanese have the same pronunciation, there are many homonyms with different meanings, which cause a problem when synonyms are developed. For example, the character string “Kensaku” can be interpreted as “search” or “grinding”, so that there is a problem that a synonym dictionary using only katakana expressions cannot distinguish between them. Furthermore, in the conversion of katakana to kanji after synonym expansion, there is a problem that the user must interactively select a homonym.

Further, a foreign language / kana conversion dictionary for converting a search keyword into katakana expression, a kana / kanji conversion dictionary after synonym expansion and a kana foreign language conversion dictionary are required, and various types of large-scale dictionaries are required. There is also a problem that the creation and maintenance of it becomes difficult because of using. That is, a third object of the present invention is to solve the problems of homonyms in the above-described kana-kanji conversion and kana foreign language conversion, and the problems of creating and maintaining a large-scale dictionary used for these conversions. .

Further, if a search is to be performed as a keyword including such hundreds of synonyms and different notations, a character string collating means for collating all these at once is necessary. Otherwise, searching for synonyms and other notations would take hundreds of times longer and would not be practical. It is a fourth object of the present invention to provide a character string matching unit capable of performing a search process without lowering the matching speed even when a keyword having a word number close to one thousand words is designated.

In a conventional search method using an automaton, in the case of a different notation, all keywords including the different notation are enumerated and expanded into keywords. Furthermore, an automaton based on these is created. Since the automaton created here is described in a tree shape, a large number of automaton states are required.

Also, in the case of performing a search for specifying don't care characters, all combinations of character codes permitted by the don't care characters are listed and expanded into keywords. In order to create an automaton based on these, an extremely large number of automaton states are required as in the case of different notations. As described above, the increase in the number of states of the automaton causes a problem that the time required to create the automaton increases and the capacity of the state transition table for storing the automaton increases, that is, the hardware increases.

According to the present invention, in a search method using an automaton, the number of states is reduced as compared with the conventional method by describing the transition of the automaton in a net-like manner even when performing a search in which a different notation or a don't care character is specified. Another object of the present invention is to provide a search method that can be realized with compact hardware because the time required for creating an automaton can be reduced and the capacity of the state transition table can be small.

Further, when the document data is sequentially registered in the text database, the capacity of the magnetic disk device constituting the character string storage means may become full at a certain point in time. Even in such a case, it is necessary to be able to increase the storage capacity of the system without damaging the data stored up to that time. Further, if the size of the text database to be searched is increased to, for example, 100,000, that is, 4 GB, simply increasing the storage capacity of the magnetic disk device increases the processing time. Will not be able to reach. It is necessary to respond to the increase in the storage capacity without reducing the search time. It is a fifth object of the present invention to provide a search device having an architecture that can meet such a demand.

The important factors in the character string storage means of the character string search device are that the storage capacity is large, that a plurality of files can be continuously input / output at a high speed regardless of the file size, and that it is inexpensive. There are three points, and a collective magnetic disk drive that satisfies these factors is needed.

In the prior art, the access time of the seek time is made apparent to reduce the data write / read time, and the number of magnetic disk drives required for the data transfer speed required by the external device is reduced. No consideration has been given to whether or not the configuration should be made using the method, and there was a problem in terms of cost performance.

The conventional technique has an effect of reducing the access time when a file having a large data size spreads over a plurality of magnetic disk devices such as image data, but does not extend over a plurality of magnetic disk devices. When writing and reading a file with a small data size, the seek time cannot be hidden, and there is a problem that the access time becomes the same as that of one magnetic disk device.

Further, the prior art does not take into consideration the point that continuous writing and reading of a plurality of files are performed, and it is possible to process write and read commands from a higher-level device for only one file. When accessing a file, it is necessary to repeat one process, and there is a problem that the overhead time required for the process becomes long.

As one of the overhead times,
There is a process of retrieving storage position information of a magnetic disk device from a file identification code for specifying a file to be accessed from a higher-level device. In a conventional general magnetic disk device, a file identification code is represented by a file name composed of a character code string such as an ASCII code, and the file name is stored in a file management information area of the magnetic disk device. It is necessary to retrieve the file management information to find the physical storage location, and there is a problem in that the processing time required for the location is long.
SUMMARY OF THE INVENTION It is an object of the present invention to provide an inexpensive collective magnetic disk drive having a large storage capacity and capable of continuously inputting / outputting a plurality of files regardless of the file size. On the other hand, the document information is not only composed of text data, but also includes drawings and photographs as its constituent elements. Therefore, it is necessary to respond to a request for reading a retrieved document with a print image. It is a sixth object of the present invention to provide a search device having an architecture capable of responding to this.

Further, the text database is to be shared by a plurality of users.
(Local area network) must be accessible from the search interaction workstation. Therefore, the search device must be connected to the LAN and have a function of responding to search requests from a plurality of other workstations. It is a seventh object of the present invention to provide a full-text search device having such a function. It is a final object of the present invention to provide a full-text search system that can respond to each of the problems described above.
In particular, it is an object to provide data registration suitable for this full-text search system.

[0064]

In order to achieve the above object, the present invention has the following arrangement. Data that can be searched is stored in the data storage unit, and a search file that can exclude data that is unlikely to include the search keyword itself during the search is registered. As the search file, a “character component table” indicating whether or not each predetermined character is included in the registered data, and “condensed body data” that eliminates duplication of words repeatedly appearing in the registered data. is there.

[0065]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, a first embodiment of the present invention will be described.
This will be described with reference to FIG. In this embodiment, the keyboard 11
01, search machine control computer (CPU0) 1
150, a display 1120, an automaton generation computer (CPU1) 1105a, a bit search computer (CPU3) 1107a, a string search engine 1106, a compound condition determination computer (CP
U2) 1145a, a search result storage memory 1146, and a text data file 1110. Also, a search machine control computer (CPU0) 11
At 50, a search expression analysis program 1102, a synonym variant expression expansion program 1103a, a complex condition analysis program 1141a, a search execution control program 1108, and a search result display program 1147 are executed, and an automaton generation computer (CPU1) 1105a generates an automaton. In the bit search computer (CPU3) 1107a, the bit search program 1107 executes the compound condition determination computer (C3).
PU2) 1145a executes the complex condition determination program 114
5 is executed.

First, the search condition expression input from the keyboard 1101 is converted into a search machine control computer (CPU
0) Analyzed by the search expression analysis program 1102 on 1150. That is, the search expression analysis program 1102
Are separated into a composite condition description part which describes the keyword parts constituting the search condition expression and their inclusion conditions and arrangement conditions. The inclusion condition is described as a logical condition, and the arrangement condition is described as a neighborhood condition or a context condition. After the separation and extraction, the keyword portion is also passed to the synonym variant description expansion program 1103a on the CPU 01150, and the complex condition description portion is passed to the complex condition analysis program 1141a.

In the synonym variant notation expansion program 1103a, a synonym of a keyword input with reference to a built-in synonym dictionary is obtained in accordance with a conversion rule. For example, when the keyword "computer" is entered, "computer" and "computer" are generated as synonyms in addition to "computer", and "computer" is generated from "computer" as a different notation Is done.

As synonyms, in addition to the synonyms as in the above example, there are higher terms, lower terms, related words, and the like, and these are expanded as synonyms. In this case, examples of the high-order words include “electronic equipment”, low-order words include “calculator”, and related words include “office automation”.

The different notation expansion includes katakana expansion, kanji hiragana expansion, and alphabet expansion. What is shown is an example of katakana expansion in this. Kanji Hiragana development includes the conversion of new and old fonts and the development of sending characters. Examples of the conversion of new and old fonts include conversion from “Sai” to “Sai” and “Sai”. In addition, examples of the expansion of the feed include expansion from “reading” to “reading” and “reading.” The expansion of the alphabet includes the expansion of the Roman alphabet into Hepburn, the expansion of the Roman alphabet, and the expansion of the uppercase and lowercase alphabet. "CHISHI" from "Chishiki" is an example of Hebon-style development, and "CHISHI" is an example of Romaji-style instruction
There is an expansion to “KI”, and an example of expansion of uppercase and lowercase letters of the alphabet is an expansion from “TISIKI” to “tisiki”.

The expansion types of the synonym expansion and the different notation expansion described above can be combined and selected by the user.

Examples of English synonyms are looking glass → mirror pingpong → table tennis the Lord → God typhoon → cyclone → hurricane WS → work station, and examples of different English notations are center → center liter → litre Examples include brier → briar humor → humour modeler → modeller Chile → Chili orangutan → orangoutan → orangoutang MacDonald → McDonald.

Further, examples of synonyms in German include Brief → Schreiben Mostert → Mostrich Maschine → Motor, and examples of different notations in German are Foto → Photo Coda → Koda Code → Kode Buffet → Buffet Friburg → Fribourg and the like.

The keyword group developed in this way as a synonym and a different notation is then converted to a computer (C
PU1) Automaton generation program 1 on 1105a
Sent to 105.

The automaton generation program 1105 creates an automaton for collectively collating the keyword groups sent from the synonym variant expression expansion program 1103a. By performing synonym and variant notation expansion, several hundreds of expansion results can be obtained depending on the number of initially input keywords.

Since these keywords are searched one by one from the input text data, it is impossible to realize a high-speed search. That is, it is necessary to collect these keywords and perform a search by scanning the text data only once. A collation method using an automaton is known as a method of collating a plurality of keywords at once (also referred to as a large amount collation). Among them, Japanese Patent Application Laid-Open No. 63-31530 proposes a method of executing this automaton by hardware. The search engine 1106 is a high-speed multiplexed character string matching circuit realized by further developing this method. Therefore, the automaton generation program 1105 generates the identification code information of the keyword to be compared with the state transition table set in the search engine 1106, and transfers these to the search engine 1106.

Further, the synonym-notation expansion program 110
The keyword group developed by synonyms and different notations in 3a is a corresponding keyword identification code (also referred to as a keyword identifier).
Together with a bit search computer (CPU 3) 11
It is passed to the bit search program 1107 on 07a.

On the other hand, the composite condition analysis program 1141 on the search machine control computer (CPU0) 1150 which has received the composite condition description portion in the input search condition expression from the search expression analysis program 1102, executes the neighborhood condition, the context condition, and the logical condition. Analysis of conditions, etc., as control information for determining each condition, is converted into the identification code of the specified keyword and the specified distance information, specified context code information, and specified logical condition code information therebetween, and is used as a compound condition determination computer. (CPU2) This is passed to the complex condition determination program 1145 on the 1145a.

Now, the above-described search expression analysis processing, synonymous notation expansion processing, automaton generation processing, and complex condition analysis processing are completed, and the bit search computer (CPU 3)
Bit search program 1107 on 1107a, search engine 1106, and compound condition determination program 1 on computer (CPU2) 1145a for compound condition determination
When the control information has been passed to 145, the search process is started.

The search processing is controlled by a search execution control program 1108 on a search machine control computer (CPU 0) 1150. That is, in the search execution control program 1108, the bit search program 110
7. The search engine 1106 and the complex condition determination program 1145 are activated, the text data to be searched is read from the text data file 1110, and the hierarchical pre-search and the text search are executed. First, a character component table is read from the text data file 1110 to the bit search program 1107, and a character component table search is performed. The character component table search result is written out to the search result storage memory 1146 as a corresponding document identifier. Next, the condensed text of the document specified by the document identifier is extracted from the text data file 1110 by the string search engine 11.
06 and performs a condensed text search. The string search engine 1106 searches for a specified keyword group from the input condensed text data in accordance with preset state transition table information. When any of the keywords is found, the identifier of the text file, the identification code of the keyword, and the detected position information are stored in the compound condition determination computer (CPU 2).
It is sent to the complex condition determination program 1145 on 1145a.

The position information added as the output information of the search engine is information indicating the position in the document where the keyword is found, and specifically, the number of characters counted from the head of the document. Is a value obtained by counting the number of characters. FIG. 11 shows the collation position information in a specific example.
This figure shows that the contents of the document are "Intelligent search technology for fuzzy search."

.. "Is assumed to be a case where this is searched using the keyword" intelligent search ". Here, the part of "intelligent search" in the "intelligent search technology" matches the keyword, so that this part is detected. As the collation position information, the character position from the beginning of the document of the last character “search” of “intelligent search” is used. In this example, 13 is the collation position information.

The output information of the search engine to which the collation position information is added has the configuration shown in FIG. That is, in the present embodiment, a keyword identifier having a length of 32 bits,
Similarly, it is composed of 32-bit keyword collation position information. Further, a document identifier is output for each document prior to the output of the keyword identifier, so that it is possible to know which document the collation output information corresponds to.

The result of the condensed text search is passed to the composite condition determination program 1145 on the composite condition determination computer (CPU 2) 1145a as collation information in which the corresponding document identifier, collation keyword identifier and keyword collation position information are combined. Compound condition judgment program 114
In step 5, a document that matches the specified condition is determined based on the previously set composite condition determination control information, and the document identifier is written to the search result storage memory 1146. The search execution control program 1108 determines whether the neighborhood condition or the context condition is set in the compound condition, and performs the last text search if it is set. That is, the text data corresponding to the corresponding document identifier obtained as a result of the condensed text search is read from the text data file 1110 into the string search engine 1106 and the text search is performed. The collation information output from the string search engine 1106 is a compound condition determination program 114
5 to determine whether the neighborhood condition and the context condition specified here are met. This determination processing result is output to the search result storage memory 1146 as final search result information in the form of a corresponding document identifier.

When the condensed text search or text search has been completed and the search processing is finally completed, the search result display program 1147 on the search machine control computer (CPU 0) 1150 executes the search based on the corresponding document identifier on the search result storage memory 1146. The bibliographic items such as the number of search results or the bibliographic information of the hit document, such as the document name and author, are read from the text data file 1110 and displayed in a list on the display 1120. Text data is read from the text data file 1110 and displayed.

The above is the description of the first embodiment of the full text search apparatus provided by the present invention.

Next, a second embodiment of the present invention will be described with reference to FIG. In this embodiment, the keyboard 250 is used.
1. Search machine control computer (CPU0) 25
20, a display 2520, an automaton generation computer (CPU1) 2505a, a bit search computer (CPU3) 2507a, a string search engine 2506, a compound condition determination computer (CPU
2) 2545a, search result storage memory 2546, semiconductor memory device 2510a, RAM disk device 2510
b, a collective magnetic disk drive 2510c, and an image data file 2530. In the search machine control computer (CPU0) 2550,
Search expression analysis program 2502, synonym expansion program 2503, variant notation expansion program 2504, compound condition analysis program 2541, neighborhood condition analysis program 254
2. context condition analysis program 2543, logical condition analysis program 2544, search execution control program 2508,
And the search result display program 2547 is executed, the automaton generation program 2505 is executed by the automaton generation computer (CPU1) 2505a, the bit search program 2507 is executed by the bit search computer (CPU3) 2507a, and the complex condition determination computer (CPU2) 2545a is executed The composite condition determination program 2545 is executed. The collective magnetic disk device 2510c is different from the collective magnetic disk control device 2510d.
And composed of a magnetic disk apparatus 2510e ₁ ~2510e _12.

In this figure, first, the search condition expression input from the keyboard 2501 is obtained by the search expression analysis program 2 on the search machine control computer (CPU 0) 2550.
Analyzed by 502. In other words, the search expression analysis program 2502 separates the keyword portion that constitutes the search condition expression into a compound condition description portion that describes the inclusion condition and the placement condition thereof. Inclusion conditions are described as logical conditions,
The arrangement condition is described as a neighborhood condition or a context condition. After the separation and extraction, the keyword portion is also CPU0,
Passed to the synonym expansion program 2503 on the 2550,
The complex condition description part is passed to the complex condition analysis program 2541.

In the synonym expansion program 2503, the synonym of the input keyword is obtained by referring to the synonym dictionary stored therein. Then, the keyword group that has undergone synonym expansion is passed to the variant notation expansion program 2504. In the case of the example of this figure, “computer”, “computer”, “COMPUTER”, etc. are generated from “computer”.

In the different notation development program 2504, different notation development processing is performed on the keyword group input here. In the case of the example in this figure, “Computer” is changed to “Computer” and “COMPUTER” is changed to “Computing”.
er "is generated.

The keyword group expanded in this way into a synonym and a different notation is then converted to an automaton generating computer (C
PU1) Automaton generation program 2 on 2505a
505.

The automaton generation program 2505 generates an automaton for collectively collating the keyword groups sent from the variant notation development program 2504, and searches the state transition table as identification code information of keywords to be collated. Set to engine 2506. The search engine 2506 is a high-speed multiple character string matching circuit based on the finite automaton method.

The keyword group developed in the different notation by the different notation developing program 2504 together with the corresponding keyword identification code together with the bit search computer (CPU 3)
It is passed to the bit search program 2507 on 2507a.

On the other hand, the composite condition analysis program 2541 on the search machine control computer (CPU0) 2550, which has received the composite condition description portion in the input search condition expression from the search expression analysis program 2502, analyzes this and executes the neighborhood condition description. Part, a context condition description part, and a logical condition description part. Then, each condition description part is respectively stored in the neighborhood condition analysis program 2542 and the context condition analysis program 254.
3 and passed to the logic condition analysis program 2544.

The neighborhood condition analysis program 2542 extracts a character distance condition and a word distance condition. Each condition extracted here is converted into an identification code of a designated keyword and distance information therebetween, and is passed to a composite condition determination program 2545 on a composite condition determination computer (CPU 2) 2545a.

The context condition analysis program 2543 extracts various co-occurrence conditions such as the same sentence co-occurrence condition, the same paragraph co-occurrence condition, the same section co-occurrence condition, and the same chapter co-occurrence condition. Each condition extracted here is converted into an identification code of a designated keyword and designated context code information, and is passed to a complex condition determination program 2545 on a complex condition determination computer (CPU 2) 2545a.

The logical condition analysis program 2544 extracts the logical condition specified in the search condition expression, converts the logical condition into logical condition code information, and executes the composite condition determination program 245 on the composite condition determination computer (CPU2) 2545a.
545.

Now, the above-described search expression analysis processing, synonym and variant notation expansion processing, automaton generation processing, complex condition analysis processing, neighborhood condition analysis processing, context condition analysis processing, and logical condition analysis processing are completed, and the bit search Bit search program 2 on computer (CPU 3) 2507a
When control information has been passed to the search condition 2507 on the search condition 2507a, the search engine 2506, and the compound condition determination computer (CPU2) 2545a, search processing is started.

The search processing is controlled by a search execution control program 2508 on a search machine control computer (CPU 0) 2550. That is, in the search execution control program 2508, first, the bit search program 2
507 is started, a character component table is read from the semiconductor memory device 2510a, and a character component table search is performed. The character component table search result is written out to the search result storage memory 2546 as a corresponding document identifier.

Next, the string search engine 250
6. Activate the compound condition determination program 2545 and the RAM disk device 2510b and read the condensed text of the document specified by the document identifier written in the search result storage memory 2546 from the RAM disk device 2510b to the string search engine 2506. Perform a condensed text search. The condensed text search result is used as collation information in which the corresponding document identifier, collation keyword identifier, and keyword collation position information are combined, as the composite condition determination program 2 on the composite condition determination computer (CPU 2) 2545a.
545. In the composite condition determination program 2545, based on the composite condition determination control information set earlier,
The document matching the designated condition is determined, and the document identifier is written to the search result storage memory 2546.

The search execution control program 2508
Determines whether the neighborhood condition or the context condition is set in the compound condition, and if the condition is set, performs the last text search. That is, the string search engine 2506, the complex condition determination program 2545, and the set-type magnetic disk drive 2510c are started, and the text data corresponding to the corresponding document identifier in the search result storage memory 2546 obtained as a result of the condensed text search is collected. Search engine 2 from the magnetic disk drive 2510c
The content is read into 506 and a text search is performed.

[0102] collective type magnetic disk unit 2510c is constituted by a plurality magnetic disk apparatus 2510e ₁ ~2510e ₁₂ of character component table, condensed text, text, and a magnetic disk drive various text data of such bibliographic 2510E ₁ distributed and stored in ~2510e _12. Then, these magnetic disk devices 2510e _{1 to} 251
0e ₁₂ is under the control of the set magnetic disk controller 2510D, reads out text data independently in parallel. The read text data are integrated by the collective magnetic disk controller 2510d, that is, are multiplexed and the string search engine 25
06. When the twelve magnetic disk devices are operated at the same time, the reading speed is about ten times faster than when only one magnetic disk device is used.

The set information output from the string search engine 2506 is stored in the complex condition determination program 2545.
To determine whether the neighborhood condition and the context condition specified here are met. The result of this determination processing is output to the search result storage memory 2546 as final search result information in the form of a corresponding document identifier.

When the condensed text search or text search has been completed and the search process is finally completed, the search result display program 2547 on the search machine control computer (CPU 0) 2550 sets the corresponding document identifier on the search result storage memory 2546 to the corresponding document identifier. Based on the search result, the bibliographic items such as the document name and the author, which are the bibliographic information of the hit document or the bibliographic information of the hit document, are read from the collective magnetic disk drive 2510c and displayed in a list on the display 2520, or the hit is specified according to the user's designation The text data of the written document is read out from the collective magnetic disk drive 2510c and displayed. Further, when the user designates viewing of the drawing or image information of the hit document, the image data file 2
The corresponding image data is read from 530 and displayed on the display 2520. The above is the description of the second embodiment of the full text search device provided by the present invention.

In this embodiment, the collective magnetic disk controller 110d (FIG. 20) is used as the text data full 110 (FIG. 1) for storing the text data.
In order to increase the capacity of the text data file 110, it is also possible to use a collective optical disk device. That is, instead of the magnetic disk device 110e ₁ ~110e _12, it is also possible to use an optical disk device. However, compared with the case where a magnetic disk device is used, the access speed is reduced, so that the text search speed is reduced accordingly. Further, in this case, a write-once optical disk device can be used as the optical disk device when the text data is not corrected, and a rewritable optical disk device is used when the text data is corrected.

Next, the RA in the above-described second embodiment will be described.
A specific embodiment of the M disk device 2510b will be described with reference to FIG. In the figure, a RAM disk device 2510b is provided with a semiconductor memory 71 for storing a condensed text.
00 (RAM) and a RAM disk controller 7200 that controls reading of the condensed text on the semiconductor memory 7100.

The RAM disk controller 7200
Direct memory access controller 7210 (DM
AC), an address controller 7220, and an address memory 7230. In the address memory 7230, it is possible to set a plurality of sets of data to be read from the semiconductor memory 7100 as a pair of a start address STARTn and an end address ENDn. The start address 7360 and the end address 7370 are managed in the search execution control program 2508 by the search execution control program 2508 based on the identifier information of the condensed text to be read written in the search result storage memory 2546. It is given by referring to the condensed text storage information to be performed.

The address controller 7220 reads the read area address information in the address memory 7230, that is, the start address START1 and the end address END1 based on the start signal given from the search execution control program 2508, and reads the start address of the area to be read from this. 7310 and the number of words to be read 732
The value 0 is obtained and set in the direct memory access controller 7210, which is activated. The direct memory access controller 7210 reads and outputs data in the corresponding area from the semiconductor memory 7100 based on the designated address 7310 and the number of words 7320.

Direct memory access controller 7
Upon completion of the reading, the 210 sends an end signal 7370 to the address controller 7220. In response to this, the address controller 7220 reads the next transfer address information, that is, the start address START2 and the end address END2, and similarly, the head address 7310 of the area to be read from now and the number of words to be read 7
320 is obtained and set in the direct memory access controller 7210 to start. In response to this, the direct memory access controller 7210 reads and outputs data in the corresponding area from the semiconductor memory 7100 based on the designated address 7310 and the number of words 7320.

Thereafter, the same processing is repeated to read data in the semiconductor memory 7100 corresponding to the transfer information set in the address memory 7230.

The preceding is an explanation of the embodiment of the RAM disk device 2510b.

Next, a more detailed embodiment of the composite condition analysis program 2541 (FIG. 25) in the second embodiment will be described with reference to FIG. In the present embodiment, the complex condition analysis program 1141 is configured in a pipeline by a neighborhood condition determination program 330, a context condition determination program 340, and a logical condition determination program 350.

The search execution control stage exemplifies a case where a text search is performed. That is, as the input text data, the collective magnetic disk device 1110c
In this case, the search engine 1106 searches for and matches a keyword from the input text data.

As a search condition expression, a complex condition expression 301 including a logical condition, a neighborhood condition, and a context condition is input.

Compound conditional expression 301: Q = and (document [4
[C] understanding, document [S] search) In this compound conditional expression 301, "document" and "understanding" appear in this order, are close to a distance of four characters or less, and "document" and "search" are the same. This means searching for co-occurrence in the sentence. That is, “Understand document [4C]”
Indicates a neighborhood condition that “document” and “understanding” appear in this order and are close to a distance of 4 characters or less, and “document [S] search” indicates that “document” and “understanding” are in the same sentence. The context condition that co-occurs is “and (...,...)”, Which indicates a logical condition that both occur simultaneously.

When such a complex condition search expression 301 is designated, first, as described in the second embodiment (FIG. 25), this search condition expression is analyzed by the search expression analysis program 1102 and included in the search condition expression. Keywords, ie, the words "document", "understanding", and "search" are extracted. Then, identifiers T1, T2 and T3 are given to these, respectively, and are passed to the synonym expansion program 1103 and further to the different notation expansion program 1104. Here, for the sake of simplicity, the description will be made on the assumption that there are no synonyms and words developed in different notations. Therefore, the result of synonym and different expression expansion is the same as the input keyword,
That is, three words of “document”, “understanding”, and “search”. These are the automaton generation program 1107
, Where an automaton for collating each character string is created, and its state transition table is stored in the search engine 110.
6 will be set.

On the other hand, for the compound condition in the search condition expression, the compound condition analysis program 1141 uses the neighborhood condition “document [4C] understanding”, the context condition “document [S] search”, and the logical condition “and ( At this time, the keyword in each conditional expression is replaced with a keyword identifier (also referred to as a term identifier) previously assigned at the time of automaton generation. 4C] T2 ”and the context condition is“ T1
[S] T3 ”. Item identifiers I1 and I2 are also assigned to these conditional expressions, respectively.
Therefore, the logical conditional expression is expressed as "and (I1, I2)". The above processing is performed by the neighborhood condition analysis program 2542 (FIG. 25), the context condition analysis program 2543 (FIG. 25), and the logical condition analysis program (FIG. 25) 2544, respectively. Each condition expressed by the term identifier and the item identifier in this way is sent to each condition determination processing program of the complex condition determination program 2545 (FIG. 25).

In this way, the search engine 1106 is set with the automaton state transition table for search term matching and search term identifier information, and the search term identifier is stored in the neighborhood condition determination program 330, the context condition determination program 340, and the logical condition determination program 350, respectively. When the conditional expressions described with the term and the term identifier are set, the collective magnetic disk device 1110c, the search engine 1106, the complex condition analysis program 1145, the neighborhood condition determination program 330,
The context condition determination program 340 and the logical condition determination program 350 are activated.

Then, the collective magnetic disk drive 11
Text data is read from 10c and sent to the search engine 1106. In search engine 1106,
The specified search terms "document", "understanding" and "search"
Are found, the search term identifiers T1, T
2 and T3 are sent to the neighborhood condition determination program 330 together with the location information in the found text. Also, the search engine 1106 detects "." Which is a delimiter between sentences, and sends the corresponding phrase identifier T0 and position information to the neighborhood condition determination program 330 without any particular designation from the user.

The neighborhood condition determination program 330 compares the search term identifier sent from the search engine 1106 with the designated neighborhood condition in consideration of the position information. If there is a designated neighborhood condition "T1 [4C] T2", that is, "document [4C] comprehension",
The item identifier I1 corresponding to the condition as a result of the comparison
Is the period identifier T input from the search engine 1106.
0, in addition to the search term identifiers T1, T2 and T3, are sent to the context condition determination program 340.

The context condition determination program 340 checks the specified context condition based on the punctuation point identifier T0 and the search term identifiers T1 and T3 input from the neighborhood condition determination program 330 and their position information. The context condition "T
1 [S] T3 "is the period identifier T0, T1 and T
3 is determined. That is, if T1 and T3 are sandwiched between two T0 before and after in this order, it is determined that the context condition “T1 [S] T3” is satisfied. If a match with this context condition “document [S] search” is found, a term identifier I2 corresponding to the relevant condition is obtained as a collation result, using a term identifier T0 input from the neighborhood condition determination program 330 and a search term identifier T1. , T3 and the item identifier I1 and send them to the logical condition determination program 350.

In the logical condition determination program 350, the term identifier T0, the search term identifiers T1 and T3, and the term identifier I sent from the context condition determination program 340 are used.
1, I2, the designated logical condition "and (I1, I2
2) Check if there are identifiers I1 and I2 that match ". That is, if both the term identifiers I1 and I2 are found, the original complex condition retrieval formula Q is satisfied, and the text (document) is retrieved. This means that the search has been performed using Expression Q.
As an example of the text, the text 30 shown in FIG.
2 will be searched.

On the other hand, the collective magnetic disk device 111
The collation information flowing from 0c to the search engine 1106, the proximity condition determination program 330, the context condition determination program 340, and the logical condition determination program 350 also includes an identifier of text data not described above. That is, the logical condition determination program 350 sends the document identifier of the text data for which the search formula Q is satisfied to the search result display program at the next stage, where the number of hits is displayed, or based on this document identifier. The bibliographic information of the relevant document is read from the collective magnetic disk device 1110c,
20 will be displayed.

Next, the full-text search method provided by the present invention will be specifically described. In the present invention,
As a method of accelerating the scan type full text search, a two-stage pre-search, that is, a character component table search 402 and a condensed text search 403 shown in FIG. Narrow down. By doing so, it is possible to reduce the amount of text search processing that accounts for a large proportion of the search processing time, and it is possible to shorten the entire search processing time.

These are all controlled by the search execution control program. First, an embodiment of a character component table search which is a first-stage pre-search will be described.

In this character component table search, as shown in the flow of the entire registration process in FIG. 16 and the hash coding procedure shown in detail in FIG. Make a list of documents that contain the code in the text.

That is, the presence / absence of each character code for each document is represented by 1-bit information (referred to as a bit list).

For example, when the keyword “search” is specified, as shown in FIG. 18, the entry address of the character component table 500 via the hash function 510 for each of the characters “search” and “search” Ask for. Then, by taking the logical product between the bits of the bit lists 503 and 506 obtained from the hash values of the respective character codes, the bit list 520 of the document including both the characters "" and "" is obtained.

The processing procedure of the above character component table search is shown in FIG.
As shown in FIG. That is, the character component table search is repeated for the number of keywords included in the specified search condition expression. In the character component table search for each keyword, a bit list indicating the presence of each character for the number of characters constituting this keyword And AND of the two. As a result, for each keyword, a document candidate having a possibility of including the keyword is obtained in the form of a bit list. Finally, the bit list thus obtained is converted into a document identifier. This document identifier is a document number uniquely determined in the system, and is provided in correspondence with the bit position from the head of the bit list.

In the character component table search, if a logical product condition (AND) is set in the designated search condition expression, the logical product condition is also processed in the character component table search process. By narrowing down the number of search processing target documents after this, it is possible to shorten the entire search processing time.

For example, a case where a search condition expression “Q = and (document, search)” is input will be described.
This search condition expression represents a meaning of searching for a document in which both “document” and “search” appear. In this case, first, a character component table search is performed for the keyword “document”, and then a character component table search is performed for the keyword “search”. Thereafter, a logical AND of each bit between the bit lists of the two search results is calculated to obtain the final search result of the character component table search. FIG. 24 shows this processing procedure. In this figure, the keyword included in the search condition expression, that is, the character component table search is repeated for the number of keywords.

In the character component table search for each keyword, the logical product AND of bit lists indicating the presence of each character is obtained for the number of characters constituting the keyword. After this process is performed for all the keywords, the logical product AND between the bit lists of the character component table search result of each keyword is calculated. The final bit list thus obtained represents document candidates that can simultaneously include the keyword specified by the logical product condition in the search condition expression.

As described above, when the logical product condition (AND) is set in the specified search condition expression, the logical product condition is also processed in the character component table search process. By narrowing down the number of subsequent search target documents, the entire search processing time can be reduced.

In the character component table 500, the presence / absence of each character code for each document is represented by 1-bit information, which is further hashed, so that the table capacity becomes tens of tenths of the original text data. Also, the data capacity to be searched becomes extremely small, which greatly contributes to speeding up the search. However, noise is generated only by this character component table search. That is, FIG. 17 showing the search processing procedure
As in Document 3, the text in which the "search" and the "search" appear separately is also searched. The second pre-search, ie, the condensed text search, eliminates this noise.

In the condensed text search which is the second pre-search, a search is performed on the condensed text. The condensed text is a text in which adjuncts such as particles and conjunctions are deleted from the text text in advance and duplicate words that appear repeatedly are eliminated. FIG. 19 shows a method of creating this condensed text.

Here, a text character string “Intelligent search technology for fuzzy search” 601 is taken as an example. First, in a character type dividing process 610, an input character string is divided between different character types. In this example, "fuzzy", "search", "for" and "intelligent search technology"
Into four character strings 602.

Next, in the attached word analysis processing 620, of the character strings 602 divided into character types, those that can be interpreted as attached words by adding an attached word analysis to the hiragana character strings “ambiguity” and “for” Remove words that are not used in search. That is, those that can be regarded as particles or conjunctions are discarded. Even if such a word is used as a search keyword, it appears in almost all documents, so that almost all hits are made, and it does not make sense to search. In this example, the hiragana character string “for” 603 is replaced with the particle “no”.
Since all partial character strings such as the conjunction "me" and the particle "no" can be interpreted as unnecessary words, they are removed as character strings that cannot be used for search. On the other hand, since "ambiguity" cannot be interpreted as an adjunct, it is left as it is as a condensed text. In this case, "ambiguity" is not recognized and left as a noun. Therefore, no matter what new words appear in the document, they will always be registered in the condensed text.

Finally, in the duplicate registration elimination process 630, it is checked whether or not the same word exists in the remaining character string group 602 removed as an unnecessary word. If there is the same thing, throw away the next one so as not to register twice. Even if they are not exactly the same, if either character string is included in the other character string, the included character string is unnecessary and is discarded. In the example of this figure, "Search"
Are included in the "intelligent search technology", and are cut off for eliminating duplicate registration. As a result, "fuzzy", "search", and "technology" are finally left as condensed texts. As described above, since the condensed text means that the original document is information-compressed word by word, by searching this condensed text, for example, only a character string continuous with “search”, that is, a document in which a keyword appears as a word is picked up. It is possible to put out.

The capacity of the condensed text thus created is reduced to about 20 to 25% of that of the original text. Therefore, the full-text search can be equivalently speeded up about five times. Further, by placing the condensed text on a memory that can be accessed at high speed such as a semiconductor memory, it is possible to further increase the equivalent scan speed.

The method of creating the condensed text differs from the method of using a keyword dictionary or the like to cut out the words required for retrieval, and the method of removing only unnecessary words that can be grammatically analyzed without using a dictionary. Is used, there is no danger that necessary words will be cut off, and search omission is less likely to occur. With the conventional search method, search omissions may occur because new words that are not registered in the keyword dictionary cannot be collected.However, in this method, even if new words do not fall from the condensed text, search omissions due to new words Does not occur.

This condensed text search is performed using the search engine 1106 (FIG. 10). Thereafter, for the documents narrowed down as a result of the condensed text search, the relevant text data is searched for and the last composite condition is used. A search will be performed. That is, in the text search, the search is performed while performing the determination process of the neighborhood condition and the context condition that cannot be determined unless the text body is scanned.

Normally, the character component table and the condensed text are stored together with the text data in the collective magnetic disk device 1110c (FIG. 3). When the retrieval system is started, the semiconductor memory device 1110a and the RAM disk device 1
110b is loaded. At the time of retrieval, the semiconductor memory device 1110a and the RAM disk device 11
10b. The text data is stored in the collective magnetic disk device 1110c (FIG. 1).
3) will be read directly and searched.

As described above, a two-stage pre-search of “character component table search” and “condensed text search” is performed in advance, and the number of documents to be subjected to the most time-consuming “text search” is minimized in advance. By narrowing down, equivalently high-speed full-text search can be realized.

In the text search, a search is performed by adding a process of determining a neighborhood condition and a context condition that cannot be determined unless text data is scanned. Normally, the character component table and the condensed text are stored on the collective magnetic disk, but are loaded on the RAM disk when the system starts up, and are read from the RAM disk when searching. The text body is read from the collective magnetic disk drive 2510 (FIG. 25).

As described above, by performing a two-stage pre-search in advance and narrowing down the number of documents to be searched for the text that requires the longest time to a minimum in advance, an equivalently high-speed full-text search can be realized. become.

In this three-step search, if the neighborhood condition search and the context condition search are not specified, the text need not be searched, so that the search can be terminated only by the character component table search and the condensed text search. it can. That is, FIG.
As shown in, if the specified search condition expression does not include the neighborhood condition or the context condition, it is only necessary to search for whether the keyword exists as a word or whether it is apricot.
A document containing characters constituting the designated keyword is extracted by the character component table search, and the condensed text of the document obtained as a result is searched to extract only those containing the keyword as a word, and the search can be completed. As a result, unnecessary text search requiring a long search time can be omitted, so that the search time can be shortened as a whole.

In the three-stage hierarchical search, if the first character component table search result is zero and there is no corresponding document, the search can be terminated here.
That is, as shown in FIG. 22, even if the neighborhood condition or the context condition is set, the next-stage condensed text search and the subsequent text search can be omitted. Similarly, if the number of condensed text search results is zero, the next-stage text search can be omitted even if the neighborhood condition or the context condition is set. As a result, it is possible to complete the search processing in a minimum time according to the input search condition expression.

In the hierarchical pre-search described above, the character component table and the condensed text stored in the semiconductor memory are narrowed down, and finally, the text is read out from the collective magnetic disk device and searched. In the method of placing the condensed text in the semiconductor memory as described above, the cost of the retrieval device using the semiconductor memory increases. Therefore, by performing the search by placing the condensed text on the magnetic disk device, the semiconductor memory can be made unnecessary, and the cost of the device can be reduced.

However, when performing a condensed text search based on the results narrowed down by the character component table search, the condensed text is selectively read from the collective magnetic disk device. In this case, since a large amount of data having a relatively small capacity is accessed, the effective read speed from the collective magnetic disk device, that is, the throughput is largely affected by the seek time rather than the data read time. Will be. Therefore, when the number of results of the character component table search is large, the condensed text search time becomes extremely long as compared with the case where the condensed text is placed on a semiconductor memory having an extremely short access time. In such a case,
Rather than selectively browsing through the condensed text, it is possible to reduce the number of seeks by reading the entire case as one file, so that the reading can be performed in a much shorter time.

Therefore, in order to reduce the cost of the search device, when searching for the condensed text while keeping it on the magnetic disk device instead of the semiconductor memory, the search is performed according to the procedure shown in FIG. Makes it possible to perform a search without greatly reducing. That is,
If the result of the character component table search is larger than the predetermined number, the search result of the character component table search is ignored, and the condensed text is newly read from the all-set magnetic disk drive to search for the presence of the specified keyword. I do. If the number of results of the character component table search is smaller than the predetermined number, the corresponding condensed text on the collective magnetic disk device is selectively read to perform the condensed text search.

In this case, the predetermined number is the number of readouts in which the time for selectively reading the condensed texts by the predetermined number is equal to the time for continuously reading out the condensed texts as a single file. . Also, in this case, if the number of condensed text search results is zero, the search process can be terminated here regardless of whether the neighborhood condition and the context condition are set.

When the volume of the text data is small, since a redundant text is generally small, a large compression ratio of the condensed text cannot be expected. Therefore, considering that the disk seek time and the rotation waiting time are dominant in the file read time, a large difference does not occur between the condensed text read time and the text read time. That is, when the number of results of the character component table search is smaller than the predetermined number, it is more efficient to selectively read out the relevant text data on the collective magnetic disk device and perform the text search as shown in FIG. 22B. Become. In other words, when the number of results of the first character component table search is larger than the predetermined number, the search result of the character component table search is ignored, and a new condensed text is newly read from the all-set magnetic disk device and specified. Search for the presence of a keyword. In this case, if the number of the condensed text search results is zero, the search processing is terminated here regardless of whether the neighborhood condition and the context condition are set. If the number is not zero, it is checked whether a neighborhood condition or a context condition is set in the conditional expression. If the condition is set, a text search is performed.
On the other hand, if the number of results of the character component table search is smaller than the predetermined number, the relevant text on the collective magnetic disk device is selectively read out and the text search is performed including the neighborhood condition and the context condition. By performing such a search procedure, if the average volume of document data is small,
A more efficient search can be performed.

As described above, by changing the method of reading the condensed text according to the number of results of the character component table search, even if the condensed text is placed on the collective magnetic disk drive, the search processing can be performed without significantly increasing the search time. Thus, a low-cost and high-performance full-text search device can be provided.

Next, modified examples of the synonym expansion and the different notation expansion according to the present invention will be described.

FIG. 28 is a block diagram showing the configuration of the embodiment of the present invention. In the present embodiment, the console 2800, the dialogue control unit 2801, the different notation development processing units 2802 and 280
5. Synonym expansion processing unit 2803, synonym dictionary file 2
804, character string integration column unit 2806, character string search processing unit 2
807, and a text database 2808. Search string 4 input from console 2800
0 is a different notation development processing unit 2 via the dialogue control unit 2801
802. The character string group 41 expanded by the different notation expansion processing unit 2802 is sent to the synonym expansion processing unit 2803 and also to the character string integration processing unit 2806. The synonym expansion processing unit 2803 matches each character string of the character string group 41 sent with reference to the synonym dictionary 2804 with the dictionary header, and if there is a matched character string, the synonym expansion mode In accordance with the control signal 2810, a word corresponding to the headline described in the dictionary is output, and the character string group 42 is sent to the different notation development processing unit 2805. The different notation development processing unit 2805 performs the different notation development on the synonym-expanded character string 42 using the same processing method as the different notation development processing unit 2803, and converts the character string group 43 into a character string integration processing unit 280.
Output to 6. The character string integration processing unit 2806 receives the character string group 4 received from the different notation development processing units 2802 and 2805.
1 and the character string group 43 are combined into one character string group 44 and output to the character string search unit 2807. Character string search unit 2807
Searches the text DB for any character string in the received character string group 44, and outputs the identifier information of the hit document to the dialog control unit 2801 as the search result 45. Upon receiving the search result 45, the dialog control unit 2801 outputs the number of search results 46 and the text information 46 to the console 2800 as appropriate.

The different notation development processing units 2802 and 2805 are exactly the same. The character string search unit 2807 can be realized by a known technique, for example, using Japanese Patent Laid-Open No. 63-31530. The text DB 408 may be newspaper article data, data of a document created by a word processor, or bibliographic data of an electronic filing system, as long as it is character code information.

Hereinafter, different notation development processing units 2802 and 280
The configuration and operation of the synonym expansion processing unit 2803 and 5 will be described in detail.

First, the outline of the different notation development process will be described with reference to FIG. Here, first, the input character string 2901 is cut between different character types and divided into partial character strings.

For example, in the case of the input character string 2901 “desktop type”, it is divided into a kanji character string 2902 “desktop type” and a katakana character string 2903 “interphone” according to the character type. Next, different notation expansion is performed for each of the divided character strings, and a kanji different notation character string list 2904,
A katakana variant notation character string list 2905 is obtained. afterwards,
Expand the Kanji different notation character string list 2904 and the Katakana different notation character string list 2905, combine the character strings separately developed for the two character types into one, and obtain the final result 2.
906 is output.

Next, the details of processing for developing different notations will be described in detail with reference to FIG. FIG. 30 is a block diagram showing an embodiment of the variant notation expanding means in the present invention. The configuration of the present embodiment includes a character type division / selection unit 3001, a Roman character discrimination unit 3002, a Roman character / kana conversion unit 3003, a kanji variant notation development unit 3004, a katakana variant notation development unit 3005, an alphabet variant notation development unit 3006, and a kana Roman character conversion unit. 3
007, consisting of a divided character string integration unit 3010.

Different notation development processing unit 2802 or 280
5 is first sent to the character type division / selection unit 3001. The character type division / selection unit 3001 converts the input character string 3020 into the kanji and hiragana character string 3031, the katakana character string 3032, the alphabet character string 3033, and the other character strings 3030 as described above.
Split into substrings of type The divided partial character strings are classified according to the respective character types, and are subjected to separate expansion processing. The outline of the expansion processing is shown in the character type below.

(1) Character strings other than kanji, hiragana, katakana, and alphabets This character type includes numbers, symbols, special characters, and external character codes. In this embodiment, a character string 3030 input without expanding these character types is output to the divided character string integration unit 3010 as it is. However, it is also conceivable to convert alphanumeric characters into kanji numerals with respect to numbers, and to expand the symbol "." Into "-" or "/" with respect to alphanumeric symbols.

(2) Kanji / Hiragana Character Strings Regarding these character types, the character string 3031 is developed in different representations for new and old kanji and kanji in kanji by a kanji variant representation development unit 3004. Kanji different notation development unit 3004
Is transmitted to the divided character string integration unit 3010.

(3) Katakana Character String Regarding this character type, the character string 3032 is subjected to different notation development for the notation of similar syllables by the katakana different notation development unit 3005. The expanded character string 3042 is sent to the divided character string integration unit 3010. At the same time, it is also sent to the kana-romaji conversion unit 3007. Kana-Roman conversion unit 300
The character string 3053 converted into Roman characters in step 7 is subjected to different notation development relating to the case of the alphabet in the different letter notation developing unit 3006, and the character string 3043 is obtained.
Is sent to the divided character string integration unit 3010.

(4) Alphabet Character Strings There are two types of this character type: the case of the Japanese Roman alphabet and the case of the foreign language.

Here, first, the Roman character discriminating unit 3002
Then, it is determined whether the character string 3033 is a Roman character or a foreign language. The criterion uses a Roman alphabet notation. That is, if the arrangement of alphabetic characters matches the Roman alphabet notation, it is determined to be Roman, and if it cannot be interpreted as Roman, it is determined to be a foreign language. This determination can also be performed by the Roman character / kana conversion unit 3003. In other words, if the Roman alphabet / kana conversion can be performed, it is determined that the alphabet is a Roman alphabet, and if not, it is determined that the language is a foreign language. In addition to the method of the present embodiment, a method of using a foreign language dictionary can be used for this determination.

The character string 3051 determined to be a Roman character by the Roman character discriminating unit 3002 is sent to a Roman character / kana conversion unit 3003, where it is converted to a katakana character string 3052. Character string group 3042 is obtained by performing different notation expansion. Subsequent processing of the character string group 3042 is the same as the processing of the katakana character string of (3). That is, the character string group 3042 expanded in katakana different notation is divided into the divided character string
010 and kana-romaji conversion unit 3007
Also sent to. The katakana character string group 3042 is converted into Roman characters by the kana-roman character conversion unit 3007, and is sent to the alphabet variant writing unit 3006 as a Roman character string group 3053. The Roman character string group 3053
Is subjected to different notation development related to the case of the alphabet in the different letter notation developing unit 3006, and then sent to the divided character string integrating unit 3010.

On the other hand, the character string 3034 determined to be a foreign language by the Roman character discriminating unit 3002 is sent to the alphabet different notation developing unit 3006 without performing Roman character kana conversion, and the output character string 3043 is converted into the divided character string integrating unit 3010. Sent to

The flow of the different notation development process has been described above. Subsequently, the details of each processing block in this variant notation development processing will be described.

First, katakana different notation developing unit 3005
Will be described. FIG. 31 is a diagram for explaining the processing in the different notation developing unit by using a katakana character string as an example.
Here, an input character string “interphone” is used as an example. The different notation expansion process is performed with reference to a conversion rule. In the conversion process, if there is a partial character string in the input character string that can be converted, the conversion process refers to the conversion rule and replaces it with another notation. The table format of this conversion rule is also shown in FIG. This conversion rule table includes a heading part and a development part character string list part. If the input character string includes a part corresponding to the heading part of the conversion rule table, the corresponding part is sequentially replaced with a different notation character string group described in the expanded character string list part.

The search for the heading character string is performed by the longest matching method from the head of the input character string. That is, as shown in the figure, when both the partial character string "Fo" and the partial character string "Fo" in the input character string are present in the heading, the conversion of the longer heading "Fo" is performed. Apply rules.

The process of searching for a headline character string and replacing it with an expanded character string list will be described with reference to the example shown in FIG.
In the search for a heading character string, a search pointer is set to match a partial character string in the input character string with the heading character string. At the time of collating the input character string with the heading character string, the position of the search pointer is moved and the character string starting with the search pointer in the input character string is collated with the heading character string. First, the search pointer is set to the first character of the input character string. Therefore, in this example, the search for the heading character string is started from the character "A". Since there is no corresponding heading, move the search pointer one character
Searches for a heading character string again from the character string starting with. Since there is no corresponding heading, another character search pointer is moved to search for a heading character string from the character "TA". In the future, since the heading character string "TA" is found, the "TA" part is replaced with "TA" and "TA" described in the expanded character string list portion. Then, the search pointer is moved by the number of characters of the heading "TA", that is, by one character.
Next, a heading character string is searched from the character "F" to obtain the corresponding headings "Fo" and "Fo". This time, two heading character strings are collated. When there are a plurality of collated heading character strings, a conversion rule with the longest heading character string is adopted according to the longest matching method. In this example, since the heading “Fo” is longer than “Fo”, “Fo” is adopted as the conversion rule for expansion, and the partial character string “Fo” in the input character string is described in the expansion character string list section. "Pho", "Pho", "Ho" and "Ho". Then, the search pointer is moved by the number of characters of the heading "Four", that is, three characters. Finally, a heading search is performed from the last character, "n" in the input character string. However, since there is no corresponding heading, the character "n" is not subjected to the expansion processing and remains as it is. Since the search pointer has reached the final position of the input character string in this way, the process ends.

The character string “in (ta, ter) (for, pho, fo) including the expanded list generated as a result of the above processing
, Ho) n "to obtain the final variant expression expansion string. In this example,
The expansion is performed in two ways in the “ta” part and four ways in the “four” part. Therefore, the expansion result is a character string of 2 × 4, ie, 1) “interphone” 2) “interphone” 3) “ Interphone 4) “Interphone” 5) “Interphone” 6) “Interphone” 7) “Interphone” 8) “Interphone”.

The above-described headline character string search and replacement processing with the expanded character string list will be described with reference to a PAD diagram shown in FIG. First, the search pointer is set at the head of the input character string. Next, a search is performed using a character string starting with the current search pointer to see if there is a heading character string of the conversion rule. If there is no matching heading, the search pointer is moved backward by one character, and then a matching heading character string is searched again using the character string starting with the search pointer.
If there is a matching heading, the longest heading among the matching headings is adopted, and the corresponding part is replaced with the expanded character string list. When the replacement is completed, the search pointer is moved backward by the number of characters of the matched heading character string. Until the search pointer reaches the final position of the input character string, the above-described headline character string search and replacement processing with the expanded list are repeated.

Another embodiment relating to the method of searching for a heading character string in the different notation development described above will be described with reference to FIG. In this embodiment, an automaton is used for searching for a heading character string. Hereinafter, the procedure will be described. First, an automaton as shown in the figure is generated by a conversion rule. In the variant notation expansion processing, an input character string is input to the automaton one character at a time, and a character string including the expansion character string list described with reference to FIG. 31 is obtained from the operation output of the automaton.

Hereinafter, the operation will be specifically described. In this figure, a symbol a indicates an input character, a circle indicates each state constituting the automaton, and a number in the circle indicates the state number. The character on the line indicates that when the character is input, the state changes in the direction of the arrow. Symbol ''
Represents a character other than the character that follows. The symbol “→” indicates that the following character string is output. This automaton includes a state transition table for controlling the operation and an output table describing the output of each state. The state transition table is as shown in FIG.

Here, the input character in each state and the state number of the transition destination when the character is inputted are described as a pair. However, when transitioning to state 0, the description is omitted. That is, when a character that is not described in the state transition table is input in each state,
It is assumed that the state transits to state 0. As shown in FIG. 35, the output table describes a list of character strings to be output in each state of the automaton. When the automaton operates, only when a transition from a state other than state 0 to state 0 is made, the corresponding expansion character string is output with reference to this output table. Then, when the output is completed, the character which caused the transition to the state 0 again is input to the automaton, and the automan is transited again with reference to the state transition table. When returning from state 0 to state 0, the input characters are output as they are.

The control and output of the state transition in the automaton system have been described above. Next, this operation will be described in detail based on a specific example. Hereinafter, the operation of the input example “interphone” of FIG. 33 every time one character is input will be described. Initially, the state of the automaton is in state 0.

(1) When the character "A" is input, the destination of the transition from the state 0 is not registered in the state transition table, so that the state where the "I" is output remains 0 as it is.

(2) When the character "n" is input, since the transition destination from state 0 is not registered in the state transition table, "n" is output as it is and the state remains 0.

(3) When the character "TA" is input, the state transition table is referred to, the state number 6 is read as the transition destination from the current state 0, and the state shifts to 6.

(4) When the character "F" is input, the state transition table does not provide a transition destination that transits from state 6 to "F". Since the current state is not 0, the output table is referred to and the output character strings "ta" and "tar" in state 6 are output. Thereafter, the state moves to zero. Further, in this new state 0, the input character "F" is again input to the automaton. As a result, the state moves from state 0 to state 1 according to the contents of the state transition table.

(5) When the character "o" is input, the state moves from state 1 to state 2 from the contents of the state transition table.

(6) When the character "-" is input, the state moves from the state 2 to the state 3 from the contents of the state transition table.

(7) When the character "n" is input, the state transition table cannot obtain the transition destination state number for transitioning from state 3 to "n". And since the current state is not state 0, the output table is referred to and the output character string in state 3
“Pho”, “Pho”,
"Ho" and "Ho" are output. Thereafter, the state shifts to 0, and the input character "n" is input again to the automaton. Here, since the transition destination cannot be obtained from the state transition table, the input character "n" is output as it is.

(8) Since the last character of the input character string has been reached, the processing is terminated. In this way, a character string "in (ta, ter) (four, pho, ho, ho)" including the expansion list is obtained.

Next, a method of generating the heading character string searching automaton will be described with reference to FIG. This automaton generation need only be created once before the input character string is actually sent. This figure shows a method of generating a search automaton, that is, a method of creating a state transition table and an output table in a PAD diagram. The contents will be described below. First, the state transition table and the output table are initialized. Next, the following processing is repeated until the end of the conversion rule while taking out the rules one by one.

(1) Set the state number to 0. (2) Create a state transition table while extracting characters one by one until the end of the heading character string. That is, the state transition table is referred to, and if the transition destination by the extracted character is registered, the state shifts to the transition destination state. If the transition destination is not registered, a new state number is generated and additionally registered in the state transition table. Then, the current state is moved to the new state. Further, the character string that has transitioned from state 0 to the current state is registered in the output table. (3) After the processing of (2) is completed for all the characters of the heading character string, the current state number of the output table and the expanded character string list of the conversion rule are registered.

The specific processing flow is defined by two conversion rules [“Four” → (“Four”, “Foo”, “Ho”,
“E”) and [“Fo” → (“Four”, “Fo”,
"Ho", "ho")].

First, processing is performed on the heading character string “Four” of the first conversion rule.

(1) Input of Character "F" Since the state transition table is initialized first, no transition destination state number is registered. Therefore, a new state number 1 is generated, and the state is moved to 1. Then, a character string “F” that causes a transition from state 0 to state 1 is registered as an output of state number 1 in the output table.

(2) Input of character "o" The transition destination from the current state 1 is not defined in the state transition table. Therefore, a new state number 2 is generated, and the state is set to 2
Go to Then, the character string “F” from state 0 to state 2 is registered as an output of state number 2 in the output table.

(3) Input of character "-" The transition destination from the current state 2 is not defined in the state transition table. Therefore, a new state number 3 is generated, and the state is set to 3
Go to Then, the character string “four” from state 0 to state 3 is registered as an output of state number 3 in the output table. In addition, since this is the last character of the heading character string, the expansion character string list (“for”,
“Fo”, “ho”, and “ho”) are registered in the output table as the output of state 3 by replacing the previously registered output character string “pho”.

Next, the process is executed for the heading character string “F” of the second conversion rule. Prior to processing, the state returns to 0.

(4) The state number 1 of the transition destination is obtained with reference to the state transition table registered at the input destination of the character "F", and the state is moved to 1.

(5) Input of character "o" Referring to the state transition table, the state number 2 of the transition destination is obtained, and the state is moved to 2. Although the output of state 2 has already been registered in the output table, since it is the end of the heading character string, it is already registered as the output of state 2 in the output table.

“Fo” is rewritten into a conversion character string list (“Foo”, “Foo”, “Ho”, “H”) of the conversion rule.

By the above processing, an automaton for searching for the above two conversion rules can be created. Except for the two conversion rules shown in the specific example, an automaton can be obtained by a completely similar procedure.

FIG. 37 shows the details of the conversion rule table for katakana different notation development described in the above example. In addition, the conversion rule table was created by defining the principle of notation for similar syllable notation of katakana character strings, "Showa 2
9-year National Language Council Report Foreign Language Notation "can be used. . That is, in the above report, different notations of katakana character strings are shown, and a principle for unifying the notations is described, but the conversion rules can be created by using the reverse.

Although the different notation expansion of katakana character strings has been described above by way of example, the different notation expansion of kanji character strings can be realized by exactly the same processing only by using the conversion rule table for kanji character strings. . FIG. 38 shows an example of a conversion rule table for developing different notations for new and old kanji characters.
Figure 3 shows an example of a different notation development rule for sending
9

Further, the different notation development rule tables shown in FIGS. 37 to 39 can be additionally modified as necessary, so that the different notation expansion desired by the user can be performed.

The above is the details of the processing performed by the kanji variant notation developing unit 3004 and the katakana variant notation developing unit 3005.

Next, a description will be given of the development of different representations of Roman characters. In the present embodiment, in order to develop a different representation of Roman characters, a method of once converting a character string input in Roman characters into a katakana character string, then developing this into katakana different notations, and returning to Roman characters again by kana-romaji conversion. Has been adopted. Accordingly, two parts related to the development of different representations of Roman characters are the Roman alphabet-kana conversion unit 3003 and the kana-romaji conversion unit 3007 in FIG.

First, the processing contents of the Roman character / kana conversion unit will be described. When an alphabetic character string is input, first, Roman alphabetic kana conversion is performed. Roman alphabet Kana conversion part 3
In 003, Roman-kana conversion is performed using a Roman-kana correspondence table as shown in FIG. In the figure, for example, in the first record, the Roman character "A"
Corresponds to the katakana "A". Regarding a record in which a plurality of character strings are arranged in a Roman character item, it indicates that all of the plurality of character strings correspond to katakana items. For example, the Roman alphabet “SYA” and “SHA” are replaced by the katakana “sha”.
Corresponding to These correspond to the Roman alphabet notation and Hepburn notation, respectively. Therefore, in the Roman alphabet kana conversion unit 3003, even a character string is converted into katakana in a notation style, a Hepburn style, or a mixed notation such as these. The conversion method is the same as the above-described Kanji different notation expansion and Katakana different notation expansion. That is, the input character string and the Roman character string in the correspondence table are searched for the longest match, and are sequentially replaced with the corresponding katakana character strings. If the corresponding Roman character string is not found in the correspondence table, it is determined that the input character string is not a Roman character, and no Katakana character string is output.

Next, the kana-romaji conversion unit 3007 will be described. Here, the correspondence table of FIG. 40 is used as it is. Conversely, the input character string is successively replaced with the Roman character while matching the longest match between the input character string and the katakana character string in the correspondence table. When there are a plurality of corresponding Roman alphabets as in the example of "sha" described above, the corresponding portion is replaced as a list of partial character strings. That is, the input character string of katakana is expanded into a character string including an expansion list in the same manner as the processing of expansion of different notation, and the result of expansion of the Roman alphabet can be obtained by combining the parts of the expansion list. This will be described by taking as an example a case where a katakana character string “Shishamo” is input. At this time, the input character string “Shishamo” is matched with the Katakana-Roman character correspondence table to obtain “(SI,
A character string including an expansion list of “SHI) (SYA, SHA) MO” is obtained. Therefore, by combining the expansion lists, 1) “SISYAMO” 2) “SISHAMO” 3) “SHISHAMO” 4) “SHISHAMO” 4 As described above, the type of Roman character different notation character string is obtained, and the above is the description of the process of developing different notation.

In the above-described embodiment of the different notation expansion, the kanji hiragana character string, the katakana character string,
Although the expansion processing is performed for all of the Roman character strings and the alphabet character strings, these processings can be selectively performed. In other words, the type of the output character string after the different notation expansion is as follows: 1) Kanji Hiragana character string 2) Katakana character string 3) Roman character string 4) Alphabet character string or a mixed character string of these It can be controlled to output as a result.
By making it possible to select different notation development for each character type, useless development processing can be omitted and search processing according to the user's request can be performed.

Hereinafter, a method of controlling the character type of the result of the development of the different notation will be described.

As shown in FIG. 41, this output character type is controlled by a switch a3008 for controlling the output of the alphabet character string 3034 and a switch b3 for controlling the output of the katakana character string group 3042 in addition to the configuration of the embodiment of FIG.
009 is provided. Also, control signal lines 3061 and 3 for controlling the output of the kanji variant notation developing unit 3004, katakana variant notation developing unit 3005, kana roman character conversion unit 3007, switch a3008, and switch b3009.
062, 3063, 3064, and 3065 are provided, respectively. Then, the control signal is turned ON and OFF in accordance with the designation mode of the different notation development result output character type set by the user, thereby realizing the different notation development according to the mode. For example, in the case where it is not necessary to expand the Roman alphabet different notation, the control signal 3063 of the kana-romaji conversion unit 3007 is turned off to stop the output. FIG. 42 shows a combination of control signals for the conversion units, the expansion unit, and the switches in such an expansion mode. In the drawing, the expansion modes are respectively c: Kanji and Hiragana different notation expansion k: Katakana different notation expansion r: Roman character different notation expansion a: Alphabet different notation expansion and output. A plurality of characters indicates a plurality of differently specified output specifications. For example, deployment mode 'ck
a ′ indicates a mode in which different notations of Kanji Hiragana, Katakana and Alphabet are output as different notation development results. In the table, “○” indicates that the corresponding module outputs a character string. Conversely, where there is no circle,
Do not output character strings. For example, in the character string expansion mode of 'cka', the Roman character / kana conversion unit 3003, the kanji variant notation development unit 3004, and the katakana variant notation development unit 3005 output a developed character string, and the switches a3008 and b3009 convert the input character string. Pass, but indicates that the kana-romaji conversion unit 3007 does not output a character string.

Lastly, the synonym expansion processing will be described.

The synonym expansion processing unit 2803 has a synonym dictionary as shown in FIG. In the figure, a record number is a serial number assigned to each heading character string in the dictionary. Each heading character string defines a synonym, an upper word, a lower word, and a related word. Isotopes in the figure,
The numbers described in the items of upper words, lower words, and related words all indicate record numbers of the same dictionary. For example, the heading "computer" indicates that it has record numbers 2 and 3, that is, "computer" and "information processing device" as its cognates. In the synonym expansion, which item in the dictionary is used for expansion, the synonym expansion mode control signal 2 shown in FIG.
810 allows the user to set the mode. The modes that can be set are as follows. That is, u: expansion using an isotope b: expansion using a high-order word n: expansion using a low-order word r: expansion using a related word and expansion combining each mode of u, b, n, and r I can do it.

The processing of synonym expansion is performed by searching for a dictionary character string existing in the character string input to the synonym expansion section. In other words, as in the case of searching for a heading character string of a conversion rule in the variant notation expansion processing, the heading character string is searched by the longest match from the beginning of the input character string. Then, in the case of isotopic expansion, the partial character strings collated in the input character string are sequentially replaced with a list of isotopic character strings. At this time, rewriting is performed by adding the matched headline character string. In the case of upper word expansion, lower word expansion, and related word expansion, the above-described replacement output is performed only when the input character string completely matches the heading character string. That is, the expansion is not performed only by partially matching in the input character string. This is because partial character string replacement in upper word expansion, lower word expansion, and related word expansion creates a meaningless word.

The processing for isotopic expansion will be described using an example.

Assuming that the input character string is “large computer”, the heading character string “computer” is collated from the third character of the input character string by searching for the heading character string in the synonym dictionary. From the “computer” of the record number 1 of the synonym dictionary, the “computer” of the record number 2 and the “information processing device” of the record number 3 are the cognitive lists (“computer”, “computer”, “information processing device”). "). By replacing the corresponding part of the input character string with this list, a character string “large (computer, computer, information processing device)” including the expansion list can be obtained as in the case of the different notation expansion processing. By combining this expanded list (in this case, there is only one list, but three isotope character strings of (1) "large computer" (2) "large computer" (3) "large information processing device" are obtained. Will be.

Next, the word expansion process will be described with an example.

When the input character string is “computer”, the input character string and the heading character string “computer” completely match in the heading character string search of the synonym dictionary. Therefore, “electronic device” of record number 4 is output as a higher word. In this case, there is only one upper word, but of course there may be more than one. If there are a plurality of high-order words, they are output as a list as described above.

[0215] Processing for lower words and related words is exactly the same as that for expanding upper words. If there is no corresponding character string in the dictionary in synonym expansion, the synonym expansion processing unit 2
No character string is output from 803.

The embodiment of the processing of synonym expansion has been described above. By the way, in synonym expansion, if a dictionary is used and the number of dictionary records increases, it may take time to search for a heading character string. As a solution to this problem, there is a method of searching for a headline character string in a dictionary by using an index table. FIG. 44 shows an outline of this method. The synonym dictionary is arranged in alphabetical order by the heading character string in advance. In addition to the synonym dictionary, there is an index table in which only the first character of the heading character string is collected and which part of the dictionary starts with the heading starting from the character is registered. For example, a heading starting with the letter “A” indicates that the heading exists from record number 1. When searching for a heading character string, the index table is first referred to to determine a record number, and then the synonym dictionary is accessed based on the record number. By doing so, it is not necessary to scan all the headline character strings in the synonym dictionary, so that the processing time can be reduced. For example, when an attempt is made to search for a character string starting with the character "total", the index table indicates that a character string starting with "total" exists from the record number 501 of the dictionary. Therefore, the useless character string search before that can be omitted. Furthermore, by arranging the heading character strings in alphabetical order, if a heading with a different first character is searched during the search for the heading character string, the subsequent search can be omitted. For example, if a heading character string starting with “total” is searched, searching for a heading “information processing device” starting with a character other than “total” eliminates the need for subsequent unnecessary searching.

Although the record number is used in the description of the index table and the isotope in the dictionary, the access to the dictionary can be further speeded up by describing the record number with the address specifying the position in the dictionary. The address indicates the first position where the corresponding heading character string exists in the dictionary, and includes, for example, the number of bytes from the head of the dictionary. By doing so, the access to the dictionary can be directly specified, so that the speed can be further increased as compared with the case where the record number is specified.

Here, an embodiment of the automaton of the present invention will be described with reference to FIGS. 45 to 55.

For the automaton for different notation search, the operation when the state transition diagram of the set allowable automaton in FIG. 46 is used will be described. Hereinafter, a description will be given by abbreviating the collective allowable automaton as an automaton. The automaton in the figure is, similarly to the automaton shown in FIG. 5, a different notation of “interface”, “interface”, “interface”, “interface”, “interface”, “interface”, “interface”,
9 including “interface” and “interface”
It is for searching for a word search term.

These can be represented by a compound word expression character string shown in the lower part of FIG. The different notation of “Fee” (“Fay”, “Fee” (“−”, “−”)) will be described.

First, "fay" is replaced by "fay" due to its pronunciation notation, so it can be described as ("fay", "fay").

Next, since the long sound of "Fee" is replaced by "-" in the long sound notation ("-",
"-").

("Fay"("-","-")) can be obtained by applying ("-", "-") of the long note notation to ("Fay", "Fee"). If this compound word expression character string is used, since the partial character strings in parentheses are equivalent, it is possible to combine transitions by the last character of the partial character string into the same transition destination state.

However, if it is included in the transition of another partial character string, for example, (“TA” (“−”, “−”),
In the case of “ta”), the state 3 of the next transition character “f” is the transition destination state of “ta”, and the state 4 is the transition destination state of “tar” and “tar”. Therefore, a transition having these two locations as transition source states is described, and the transition destination state is defined as state 5.

By summarizing the transitions as described above, the number of states can be greatly reduced to about one third as compared with the automaton of FIG.

The method of preparing the automaton used here is described in the cited reference (A.V.A.H. and M.J.
Classic: “Efficient String Matching, Communications AC M, 18th
Vol. 6, No. 6, 1975, AV Aho and MJ Corasic
k: “Efficient String Matching”, CACM, VOL. 18, N
o.6, 1975). This automaton is controlled by the above-described concurrent state automaton method. Hereinafter, the contents will be specifically described.

Next, a state transition control method of the automaton will be described. This method is to control state transition without using “fail processing”. That is,
Instead of performing the “fail processing”, the state transition of the automaton is represented by using a plurality of tokens.

In the automaton system described so far, the state transition diagram of the automaton has an active state excluding the initial state, that is, only one transition state (a state where a token is placed) indicating that the collation is in progress. It was created under conditions. As a result, if a mismatch with the input character occurs during the collation, the movement of the token becomes discontinuous, so that “fail processing” must be performed.

In this method, a token is generated each time an active state occurs, and the token is deleted when a mismatch occurs during collation, thereby making the fail process unnecessary. Therefore, depending on the input character string, a plurality of tokens may simultaneously exist on the state transition diagram. In this sense, this method will be referred to as a concurrent state automaton method.

According to the present method, it is not necessary to use the "fail processing", so that it is possible to realize a character string search apparatus which does not need to calculate a fail destination state even when creating an automaton.

First, a token generation method in the starting point state will be described. In the starting point state, collation is performed each time an input character is entered. When matching with the transition character, a new token is generated and this token is moved from the start state to the transition destination state. However, in the case of the state transition from the start state to the start state, no token is generated. Therefore, the transition from the start state to the start state is invalid, and this transition can be omitted.

Next, the operation of the automaton in the case where, for example, a character string "interface" is input one by one will be described.

First, when "A" is input, the collation in the starting state matches, a token T1 is generated, and the process moves to state 1. If "n" is input when the token T1 has reached the state 1, the token T1 moves to the state 2. Also,
At the same time, even in the start point state, collation with “n” is performed, but no new token is generated because they do not match. Further, in the state 2, when the input character "ta" is input, the token T1
Moves to state 3. At the same time, no new token is generated because the matching in the starting state does not match. Next, when "Fe" continues to be input, the token T1 is in the state 4 →
Move from state 5 to state 6. Also, during this time, a new token is not generated because the matching in the starting point state does not match. Next, when "A" is input, the token T1 moves from the state 6 to the state 7. Also, since the matching in the starting point state matches, a new token T2 is generated and the process moves to state 1.
Next, when "S" enters, the token T1 moves from the state 7 to the state 8. The token T2 disappears here because the matching in the state 1 does not match. Also, since the matching in the starting point state does not match, no new token is generated. At this time, when the token T1 reaches the state 8, the character string "interface" has been searched.

By controlling the state transition using a plurality of tokens, the number of states of the automaton can be reduced to about 3
It is possible to realize a different notation-permissible search that requires only one part.

A description will now be given of a fixed-length don't care character designation search processing method in which a fixed-length don't care character is designated as a search term.

The automaton shown in FIG. 47 is used. This figure is an automaton for searching for “A? B” as in FIG. 7, and the number of states can be reduced to about 1/150 of that in FIG. 7 by using the above method employing set transition. ing.

The present automaton creation method is the same as the above-described automaton creation method with a different notation.

For example, the operation of the present method when the character string “AXB” is input will be described.

First, when "A" is input, the token T1 is newly generated because the collation matches in the start state, and the state moves to state 1. Next, when "X" is input, the token T1 moves from state 1 to state 2. In addition, since the matching in the starting point state does not match, the token T1 newly moves from the state 2 to the state 3. At the same time, no new token is generated because the matching in the starting point state does not match. Next, when "B" is input, no token is generated. State 3 is indicated by a double circle, and here, "A? B" has been searched.

By controlling the state transition using a plurality of tokens in this way, a fixed-length don't care character designation search that requires only a small number of states of the automaton to about 1/150 can be performed in the same manner as the variant notation allowable search. Can be realized.

A description will now be given of a processing method by the automaton method for a distance designation search in which a character distance such as an upper limit distance, a lower limit distance, or an upper and lower limit distance is designated.

First, a method of realizing the upper-distance designation will be described below. Here, an example in which the upper limit distance designation that the distance between “A” and “B” is within 4 characters is specified. The upper limit distance designation can be represented by a fixed-length don't care character. In this example, when the upper limit distance designation that the distance between “A” and “B” is within 4 characters, “AB”,
"A? B", "A ?? B", "A ??? B", "A ??
? ? B "can be represented by five keywords.

A method for creating an automaton from these keywords will be described below. First, an automaton of “AB” is created. Here, state 0, state 1 and state 7 are created. Next, an automaton of “A? B” is created. Since the second character “?” Represents all one character, it is necessary to newly create a transition destination by a transition character other than the transition from the state 1 to the state 7 by the transition character “B”. That is, a transition from state 1 to state 2 by the transition character {“B”} is created. Further, as the transition by the third transition character “B”, the transition from the state 2 and the state 7 to the transition destination of the second character “?” To the state 8 is created. Similarly, "A ?? B", "A ??? B", "A ???"
? The automaton shown in Fig. 48 is obtained by creating B ". The automaton creation method is the same as the above-described automaton creation method for fixed-length don't care characters.

Next, the operation of the automaton in the case where, for example, a character string "ABCBBBC" is input one character at a time will be described. First, when “A” is input, the matching in the starting point state matches, a token is generated, and the state moves to state 1. When "B" is input, the token moves to state 7, and "A" and "B" collate "AB" which is adjacent. Further, when "C" is input, the token moves to state 3. Next, when "B" is input, the token moves to state 9, and "A" and "B" are separated by two characters "A".
BCB ".

Next, when "B" is input, the token moves to state 10, and "A" and "B" collate "ABCBB" which is within a distance of three characters or less. Next, when "B" is input, the token moves to state 6, and "A" and "B"
“ABCBBB” located at the character distance is collated. Further, when "C" is input, the token disappears in state 6 because there is no transition destination of the token.

From the above, "AB", "ABCB", "ABCBB" and "ABCBB" which are search terms in which "A" and "B" are within four characters from "ABCBBC" are collated. You can see that there is. That is, it is shown that “AB”, “A ?? B”, “A ??? B”, and “A ???? B” have been searched.

This automaton also has a fixed length dont
By controlling the token in the same manner as in the case of the care character, it is possible to realize a distance designation search with an upper limit designation.

Next, a method for realizing the lower limit distance specification will be described below. Here, a case will be described as an example where the lower limit distance is specified such that the distance between "A" and "B" is two or more characters. When the lower limit distance is specified, the upper limit distance is infinite, so do
Cannot be represented by nt care characters. That is,
When the lower limit distance is specified so that the distance between “A” and “B” is two or more characters, “A ?? B”, “A ??? B”, “A ?? B?
… And the number of keywords becomes infinite.

A method for solving this problem will be described with reference to an automaton shown in FIG.

First, the lower limit distance is set to a fixed length dont car.
Create an automaton with a keyword represented by the letter e.
The method of creating this automaton is fixed-length dont car
Same as for the e character. Here, since the lower limit distance is 2, an automaton is created using “A ?? B” as a search term. Next, a state (state 3 in this example) transited by the lower limit distance is set as a temporary start point, and an automaton is created for states connected to the start point state and thereafter. This automaton uses the conventional method 1 that describes transitions for all input characters.
Can be created using In this way, an automaton can be created even when the upper limit distance is infinite. The method of creating the automaton is the same as that of the above-described automaton with the upper limit distance specified.

Next, the operation of the automaton when the character string "ACDEFB" is input one character at a time will be described. First, when “A” is input, the matching in the starting point state matches, a token is generated, and the state moves to state 1.

When "C" is input, the token moves to state 2. Further, when "D" is input, the token moves to state 3 because it is a character other than "B". next,
When "E" is input, the token loops in state 3.

Next, the token loops again in state 3 when "F" is input. When "B" is further input, the token moves to state 4. State 4 is a state of a double circle, and indicates that a character string in which “A” and “B” are separated by a distance of two or more characters has been collated.

That is, it can be seen that "ACDEFB" can be searched as a character string in which "A" and "B" are two or more characters, that is, four characters apart.

Next, a search method in which a variable-length don't care character “*” is specified as a keyword using the lower limit distance specification will be described.

The variable length don't care character "*"
This can be realized by using a distance designation when 0 is designated as the lower limit distance. In other words, "AB * CD" can be replaced with a lower limit distance designation in which the distance between "AB" and "CD" is a distance of 0 or more characters. The automaton in this case is as shown in FIG. Thus, variable length dont ca
The search specifying the re character can be realized in the same manner as the lower limit distance specification.

The method and operation of creating an automaton are the same as in the case of the automaton with the lower limit distance specified above.

Finally, a description will be given of a method of realizing the distance specification with the upper and lower limits specified. Here, the distance between “A” and “B” is 2
An upper and lower limit distance designation of a distance of not less than characters and not more than four characters is taken as an example. Upper and lower limit distance specification is fixed length dont c
are "A" and "B" in this example.
If the distance is more than 2 characters and less than 4 characters,
"A? B", "A ?? B", "A ??? B", "A ??
? ? B "can be represented by the four keywords" B ".
The automaton shown in FIG. 1 can be created.

The method and operation of creating an automaton are the same as those of the above-described automaton with the lower limit distance specified.

A description will be given of a processing method of a one-character error allowable search, which is a search allowing a one-character error.

An example in which “ABCD” is specified as a keyword will be described. In this example, “ABC” is used as a keyword without error and “ABC”, “ABD”, “ACD”, “BC” is used as one character deletion.
D ”, one character difference is“ A? CD "," AB
? D "," ABC? "For" A "
? BCD "," AB? CD "," ABC? D ”,“ AB
CD? An automaton is created for ". When these are converted into compound expression character strings, they are as shown in FIG. 76. Based on this, the automaton shown in FIG. 52 can be created similarly to the case of fixed-length don't care characters. it can.

The method and operation of creating an automaton are the same as those of the above-described automaton with upper and lower limit distances specified.

[0263] Search 1 that allows one character replacement
A description will be given of a processing method of the character replacement allowable search.
An example in which “ABCD” is specified as a keyword will be described. In this example, an automaton is created for "ABCD" as a keyword without error and for "BACD", "ACBD", and "ABCD" as one character replacement. When these are made into compound word expression character strings, they are as shown in FIG. Based on this, the automaton shown in FIG. 53 can be created as in the case of fixed-length don't care characters.

The method and operation of creating an automaton are the same as those of the above-described automaton allowing one-character error.

As described above, according to the present invention, a different notation search, a fixed length dontcare character designation search, a character distance designation search, a variable length dont care character designation search, a one-character error allowable search, and one character replacement are performed with a small number of states. An automaton that realizes a search function such as an allowable search can be created. Therefore, the time required to create an automaton can be shortened, and the state transition table can be made compact, so that a character string search device with a small amount of hardware can be realized.

FIG. 10 using the above-described character string search method will now be described.
An embodiment of a character string search device corresponding to the search engine 1106 will be described. FIG. 45 shows the configuration of this embodiment. The configuration of the present embodiment is a state transition table 2 that outputs a next state number by inputting a character code and a state number.
20 and a collation result table 260 that outputs a collation result ID indicating whether or not collation has been performed by inputting a state number, a selector 262 that controls the extinction of the token, and whether the token has no destination state as token extinction control information. It comprises a comparator 252 for judging whether or not it is present, a register 251 for storing an initial state number, and buffers 280 and 281 for storing a current state number and a next state number.

A state transition operation of the automaton using this embodiment will be described below. In FIG. 45, a character string 301 read from a predetermined character string storage unit is stored in the register 211 one character at a time. The character code 302 output from the register 211 is input as address information to the state transition table 220 storing the transition table of the automaton according to the present invention. The state transition table 220 outputs a transition destination state number 303 to be transitioned to next from the current state number 305 and the character code 302. When the next state number is the initial state number, it indicates that the transition of the automaton is not described. Therefore, when the next state number is the initial state number, it is necessary to erase the token. After the next state number 303 is stored in the register 250, it is stored in the buffer 280 or the buffer 281 whichever is selected via the selector 262 and the multiplexer 260. At this time, the selector 262 controls whether to erase the token. The determination as to whether or not to delete this token is made by comparing the next state number 303 with the initial next state number (state number 0 in this example) stored in the register 251 by the comparator 2.
This is realized by checking at 52.

That is, when the next state number 303 is the initial state number, it indicates that there is no state in which the token should be moved.
Do not select Therefore, the next state number 303 is not sent to the multiplexer 260, and the token disappears.

On the other hand, if the next state number 303 is not the initial state number, it indicates that there is a state in which the token should be moved. Therefore, the selector 262 selects the next state number 303 and sends it to the multiplexer 260. Not extinguished.

As described above, when the next state number 303 is the initial state number, the token is deleted so that the token of the initial state number is stored in the buffer 280 and the buffer 2.
81, redundant tokens accumulate in buffers 280 and 281 and redundant tokens accumulate in buffer 280.
Thus, the problem of overflow in the buffer 281 can be solved.

The buffers 280 and 281 are used as two-sided buffers for reading and writing data, respectively, to realize high-speed processing. These two buffers can be combined into one to reduce the circuit scale.
However, the processing speed will decrease. Buffer 28
The starting point next state number is set as the initial address in 0 and the buffer 281 as an initial value. The next state number 303 sent to the buffer 280 and the buffer 281 is stored from the next address of the start state. The current state number 305 is sequentially read out from any one of the buffer 280 and the buffer 281 selected by the selector 261, and when all are read out, a read end signal 307 is generated. The multiplexer 260 and the selector 261 are synchronized, and the selector 261 selects the buffer 281 when the multiplexer 260 selects the buffer 280 in the selection operation. When the multiplexer 260 selects the buffer 281, the selector 261 selects the buffer 280. Buffer 280 and buffer 281
Of the buffer 280 or 281 selected by the selector 261 in response to the read end signal 30
7 is performed. State transition table 2
20 stores the state transition table shown in FIG. This corresponds to the automaton in FIG. Normally, the register 211 takes in the character string data in synchronization with the register 250, but holds the character string data until a read end signal is generated, and waits for the next input until all the current state numbers are read. The search result table 260 stores a predetermined code for identifying each search term corresponding to the end point state which is the end point of the character string. FIG.
FIG. 55 shows the contents of the search result table 260 corresponding to the automaton of FIG. When the search term number is other than 0, it indicates a valid search term number. That is, when the search term number corresponding to the state number is other than 0, the search term number is sent to the complex condition determination means 1145 in FIG. 10 as a collation result.
The above-described operation is executed for each character constituting the input character string in the form of executing the automaton shown in FIG. 46, thereby realizing the search processing.

When an input character string is input, for example,
The collating operation of the present method when a character string “interface” is input will be described.

First, the following processing is performed as an initial setting.
The state transition table 220 stores the state transition table shown in FIG. 54, and the search result table 260 stores the search result table of FIG. These tables correspond to the automaton in FIG.

In the buffers 280 and 281, the starting point state number “0” is stored in the head address as an initial value. The register 250 and the register 251 store 0 as an initial state number. The multiplexer 260 selects the buffer 281 and the selector 261 selects the buffer 280. Therefore, the next state number 303 becomes 0, which is the start state number.

Next, the collating operation based on these initial settings will be described.

First, the first character “A” is stored in the register 211.
Is stored in Then, the next state number 1 is read from the state transition table 220 using the character code 302 and the current state number 305 as addresses, and stored in the register 250. At this time, the current state number 305 is 0.

The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 303 stored in the register 250.
Since they are not equal, the selector 262 selects the next state number 303. This indicates that the transition from the state 0 to the state 1 is described by the transition character “A”.

Since the search term number in search result table 260 in state 1 is 0, collation result 306 is not output. This indicates that the matching result is not stored in the state 1.

In the multiplexer 260, the buffer 28
Since 1 has been selected, the next state number 1 is stored in the buffer 281 as the second next state number following the start state number. Since all the current state numbers have been read from the buffer 280, the end signal 307 is generated.

As a result, the multiplexer 260 selects the buffer 280, and the selector 261 selects the buffer 281. That is, the two next state numbers in the buffer are used as transitions for the next character as the current state number.

Looking at these operations as state transitions of the automaton, first, it is checked whether or not the transition character "A" is described in state 0 which is the current state number stored in the buffer 280. Next, if the transition is not described, the processing of the next current state number is performed. If the transition is described, the next state number is stored in the buffer 281 and the collation result is stored at the same time. This is checked by checking whether a valid term ID is stored at the address indicating the next state number in the table. In this case, the transition is described,
State 1 which is the next state number is stored in the buffer 281, and when the collation result table is examined, the collation result is not output because the result is not stored.

Next, the second character "n" is read into the register 211. Then, the next state number 0 is output from the state transition table 220 having the character code 302 and the current state number 305 as addresses, and stored in the register 250.

The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 0 stored in the register 250. Since they are equal, the next state number 303 is not selected by the selector 262. Therefore, the next state number 303 is not stored in the buffer 280. This indicates that the fiber with the transition character “n” is not described in the state 0. Here, by controlling in this manner, the generation of a token in the transition from the start state to the start state is prevented. Next, the second next state number 1 is read from the buffer 281 and the character code 302 and the next state The next state number 2 is output from the state transition table 220 using the number 1 as an address,
Stored in register 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 303 stored in the register 250. Since they are not equal, the selector 262 selects the next state number 303. This indicates that the transition from the state 1 to the state 2 is described by the transition character “ン”.

Since the search term number of search result table 260 in state 2 is 0, collation result 306 is not output. This indicates that the comparison result is not stored in the state 2.

Since the multiplexer 260 selects the buffer 280, 2 which is the next state number 303 is stored in the buffer 280 as the second next state number following the start state number.

Since all the current state numbers have been read from the buffer 281, an end number 307 is generated.

Thus, the multiplexer 260 selects the buffer 281 and the selector 261 selects the buffer 280. That is, 2 in buffer 280
One next state number will be used as a transition to the next character as two current state numbers.

Looking at these operations as state transitions of the automaton, first, it is checked whether or not the transition character "n" is described in state 0 which is the current state number stored in the buffer 281. In this case, since it is not described, the collation is similarly performed for the next current state number, state 1. Since the transition to state 2 is described, state 2
Is stored in the buffer 280 as the next state number. Further, since no matching result is stored in state 2, no matching result is output.

Next, the third character “ta” is subjected to the same collation processing as the second character, so that the description is simplified. First, buffer 2
The collation operation is performed in the state 0, which is the current state number, registered in 80. In this case, since it is not described, the collation is similarly performed for the next state 2, which is the current state number.
Since the transition to state 3 is described, state 3 is stored in buffer 280 as the next state number. State 3
Since no matching result is stored in, no matching result is output.

Next, the fourth character “F” is subjected to the same collation processing as that of the third character, so that the description is simplified. First, buffer 2
The collation operation in the state 0, which is the current state number, registered in 81 is performed. In this case, since it is not described, collation is similarly performed for the next current state number, that is, state 3. Since the transition to state 4 is described, state 4 is stored in buffer 280 as the next state number. In addition, since no matching result is stored in state 4, no matching result is output.

Next, the fifth character "D" is subjected to the same collation processing as that of the fourth character, so that the description is simplified. First, buffer 2
The collation operation in the state 0, which is the current state number registered in 80, is performed. In this case, since it is not described, collation is similarly performed for the next current state number, which is state 4. Since the transition to state 5 is described, state 5 is stored in buffer 281 as the next state number. In addition, since no matching result is stored in state 5, no matching result is output.

Next, the sixth character "A" is read into the register 211. In this step, two to three tokens
The details will be described in detail.

[0293] From the state transition table 220 using the character code 302 and the next state number 0 as an address, 1 is output as the next state number and stored in the register 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 1 stored in the register 250. In this case, since they are not equal, the selector 262 selects the next state number 303. Since the keyword number of the search result table in state 1 is 0, the matching result 306 is not output. In the multiplexer 260, since the buffer 280 is selected,
The next state number 1 is stored in the buffer 280 as the second next state number following the start state number.

Next, the second next state number 6 is read from the buffer 281, and the next state number 7 is output from the state transition table 220 having the character code 302 and the next state number 6 as an address. 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 7 stored in the register 250. In this case, since they are not equal, the selector 262 selects the next state number. Since the keyword number of the search result table in state 7 is 0, the matching result 306 is not output. In the multiplexer 260, since the buffer 280 is selected,
The next state number 7 is stored in the buffer 280 as the third next state number. Since all the current state numbers have been read from the buffer 281, the end signal 307 is generated.

As a result, the multiplexer 260 selects the buffer 281 and the selector 261 selects the buffer 280. That is, 3 in buffer 280
One next state number is used as a transition to the next character as three current state numbers.

Next, the process proceeds to the collation processing for the seventh character "S", but is read into the register 211. Then, character code 3
0 is output as the next state number from the state transition table 220 having an address of 02 and the next state number 0, and is stored in the register 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 0 stored in the register 250. In this case, the next state number 303 is not selected by the selector 262 because they are equal. Therefore, the next state number is not stored in the buffer 281.

Next, 1 as the second next state number is read from the buffer 281, and 0 is output as the next state number from the state transition table 220 having the character code 302 and 0 as the next state number as addresses. , Are stored in the register 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 0 stored in the register 250. In this case, the next state number is not selected by the selector 262 because they are equal. Therefore, the next state number is not stored in the buffer 281.

In this embodiment, the extinction of the token is realized by such control.

Further, the third next state number 7 is read out from the buffer 281, and the next state number 8 is output from the state transition table 220 having the character code 302 and the next state number 7 as an address. 250. The comparator 252 compares the initial state number 0 stored in the register 251 with the next state number 8 stored in the register 250. In this case, since they are not equal, the next state number 30
3 is selected.

Since the keyword number of the search result table 260 in the state 8 is 1, the keyword number is 1
Is output as the collation result 306. Multiplexer 26
In the case of 0, since the buffer 281 is selected, the next state number 8 is stored in the buffer 281 as a 2
Stored as the next state number.

Since all the current state numbers have been read from the buffer 280, the end signal 307 is generated.

[0302] Thereby, the multiplexer 260 selects the buffer 281. That is, the two next state numbers are 2
One current state number is used for transition to the next character.

As described above, the search for the character string "interface" is realized by controlling the token.

According to the present embodiment, by controlling a plurality of tokens in this way, a character string search that does not require the concept of "fail" can be realized. Therefore, there is an advantage that the time required for creating the automaton can be shortened, and the number of states can be reduced, so that the state transition table can be made compact.

Next, an embodiment of a magnetic disk drive used to realize the present invention will be described based on the disclosure of FIGS.

FIG. 57 shows the structure of a collective magnetic disk device. The data storage devices 15 each include the magnetic disk device 1 and one cylinder of the magnetic disk device 1 connected to each of the data storage devices 15. It comprises an input / output buffer 3 having a capacity, a data storage device 15 and a multi-disk controller 4 for controlling the input / output buffer 3.

In this case, the data storage device 15 is constituted by one magnetic disk device 1 and the input / output buffer 3 is constituted by one memory of the magnetic disk device 1 having a capacity of one cylinder.

The multi-disk controller 4 has a communication memory 5 for directly setting the file ID of a file to be accessed from the host device 7, a multiplexer controller 8 for controlling the high-speed data bus 10, and a storage for the magnetic disk device based on the file ID. It is configured by a physical information table 6 which is a conversion table for obtaining destination physical information and a master controller 9 which controls them.

The host device 7 is composed of a host controller for giving instructions to the collective magnetic disk drive and a character string search device for detecting a specified character string from input data and outputting the detected information.

Before constructing a database constituting a data file in the present collective type magnetic disk device, a database structure definition process is performed.

In the present collective type magnetic disk device, as a means for arranging logically related files so that their physical storage locations are close to each other, first, physical cylinders are allocated according to a logical classification ID having a hierarchical structure. When multiple files are accessed at once, the related files are often targeted. Therefore, by making the storage positions close to each other, the distance that the magnetic head moves between the cylinders of the magnetic disk device is shortened, and the seek time, which is a part of the access time, is reduced.

The allocation of the physical cylinders according to the logical type ID having a hierarchical structure is performed by the host device 7 transmitting the database structure definition information composed of a set of the logical classification ID and the storage capacity required by the file classification to the communication memory 5. Then, a database structure definition command is issued to the multi-disk controller 4. Master controller 9 in multi-disk controller 4 receiving the structure definition command
58 shows a structure definition table having a structure as shown in FIG. 58 in a memory in the master controller 9 on the basis of the structure definition information of the database set in the communication memory 5 on how the physical position corresponds to the logical classification. create. FIG. 58 shows an example in which each of the two layers has two classes in each layer. The entire magnetic disk device is put together as one magnetic disk device, and the storage position for each classification is a cylinder position, and the storage capacity is the number of cylinders. It is shown by.

In the database structure definition process,
The master controller 9 in the multi-disk controller 4 stores the write file storage destination in the memory in the master controller 9 as shown in FIG. Create a storage position pointer table indicating the physical position. When the structure definition is completed, the storage position pointer table indicates the first cylinder, the first track, the first sector, and the first position in the sector of each logical classification set in the structure definition. In FIG. 59, storage position pointer information when a file is stored in the classification of the example shown in FIG. 58A is stored.

Next, the construction of the database will be described. In this set-type magnetic disk device, management information using a file ID is created as means for designating a file to be accessed by a file ID (consisting of a logical classification ID and a unique number in the logical classification). .

[0315] After the host device 7 stores, in the communication memory 5, file information composed of a plurality of sets of file IDs and file sizes of files to be written,
A write command is issued to the multi-disk controller 4. Upon receiving the write command, the multi-disk controller 4 executes processing according to the flow shown in FIG. Master controller 9 in multi-disk controller 4
Is the file ID in the file information from the communication memory 5.
Is read out, and the storage location for storing the file indicated by the file ID is read from the storage location pointer table.

When the storage position is determined, the remaining capacity that can be written to the physical cylinder is determined. If the size of the file given by the file size of the file information is smaller than the remaining capacity, the storage location (disk number, cylinder number, track number, sector) in the physical information table 6 having a file ID as an entry as shown in FIG. Number, position in sector), file size, and number of disks. The number of disks spans indicates how many magnetic disk devices 1 a file has.
If the file to be processed cannot be written to one cylinder of one magnetic disk device, the file is divided and the remaining file is written to the next disk. If the file is an unwritten file divided, the value is counted up. An entry in the physical information table 6 is indicated by a file ID given by the file information.

After writing to the physical information table, the storage position pointer is advanced by the file size.

If the file size is equal to the remaining capacity, the writing process to the magnetic disk device 1 is performed when the cylinder of one magnetic disk device 1 is full.

When the file size is larger than the remaining capacity, the remaining capacity is compared with the division reference size. The division reference size is a value set in the structure definition process. If a file is stored so as to straddle between the magnetic disk devices 1 even though the remaining capacity of the cylinder is very small, two files are required to read the file. The magnetic disk device 1 must be controlled, and the processing increases the overhead. Therefore, a certain reference is set, and when the remaining capacity is smaller than the reference value, writing is performed from the head of the cylinder of the next magnetic disk device 1.

If the remaining capacity is equal to or larger than the division reference size, the storage location and the file size are stored in the physical information table 6, and then the file is divided into a file that can be written into the remaining capacity and an unrecorded file that has not been written. In the physical information table 6, the storage physical position and the file size are written.

The magnetic disk device 1 that has created the physical information that fills one cylinder performs write processing. The unwritten file returns from the loop and becomes the next file to be processed.

If the remaining capacity is smaller than the division reference size, the storage position pointer table is advanced to the beginning of the next cylinder, and the process returns to the loop with the file to be processed as it is, and continues the processing. At this time,
The magnetic disk device that has created the physical information that fills one cylinder performs write processing.

In the writing process, the master controller 9 issues a seek command to the magnetic disk device 1 and starts a seek operation. Next, a file transfer request is issued to the host device 7, and the master controller 9 requests the host device 7 to transfer the file, and also controls the multiplex controller 8 to switch the data bus so that the transferred file is transferred. The file is transferred to the input / output buffer 3 specified by the physical information. When the seek operation is completed and the file transfer is completed, the master controller 9 issues a write command to the magnetic disk device 1 and
Performs a write operation.

The above operation is repeated to construct a database.

FIG. 62 shows the temporal relationship of the write processing. As shown in FIG.
"2-1", ... i, "n-1", "1-2", "2-
The data successively transferred as 2 "... Are stored in the multiplex controller 8 in the multi-disk controller 4.
, 3-n,..., 3-n,
3-1 to 3-2 are stored. At this time, for example, the magnetic database apparatus 1-1 has started a seek operation according to a command from the master controller 9 immediately before starting the transfer of the data "1-1". When the transfer of the data “1-1” is completed, the master controller 9 issues a write command to the magnetic disk device 1-1. Magnetic disk drive 1
-1 waits for rotation until a specified write position is reached, and then starts writing data "1-1" in the input / output buffer 3-1 to a predetermined cylinder, track, or sector.

During this time, the other magnetic disk devices perform the same processing as shown in the figure.

As is clear from FIG. 62 and the above description, each magnetic disk device is
The file can be written continuously, and the database can be constructed in a short time.

Next, a file reading process will be described. Also, when there are a plurality of files to be read on the same cylinder of the same magnetic disk device, the files which do not need to be read out between the files to be read out are also read out to the input / output buffer once, and the files which do not need to be read out when transferring to the higher-level device are transferred. The means for deleting will be described.

[0329] The host device 7 stores the file information composed of a plurality of file IDs of the files to be read in the communication memory 5, and issues a read command to the multi-disk controller 4.

The multi-disk controller 4 that has received the read command executes the processing according to the flow shown in FIG.

The master controller 9 in the multi-disk controller 4 reads the file ID of the file to be read first from the communication memory 5, and
From the physical information table 6 for the physical information in which the file is stored. This file is the destination file,
Let the physical information be the physical information of the destination file. Next, the file ID of the file to be read next is read from the communication memory 5, and the physical information table 6 is searched from the file ID for the physical information in which the file is stored. This file is referred to as a subsequent file, and the physical information is referred to as physical information of the subsequent file.

It is checked from the obtained physical information whether the preceding file and the succeeding file exist in the same cylinder, and if they exist in the same cylinder, whether there is an unspecified read-less file group between the preceding file and the succeeding file. Check, if any,
Obtain the total size of the file group. If the size of the file that does not need to be read is small, the physical information is combined so that the previous file and the subsequent file can be read with a single read command. Next, the loop is returned using the combined physical information as the physical information of the previous file, the next file ID is read from the communication memory 5, and the same processing is performed using the file as the subsequent file.

When the first file and the second file do not exist in the same cylinder and when the size of the unnecessary file is large, the read processing is executed from the magnetic disk device of the first file. The physical information of the rear file returns to the loop as the physical information of the previous file, reads the next file ID from the communication memory 5, and performs the same processing as the rear file.

The above operation is repeated until all the specified files are read.

In the process of reading the previous file from the magnetic disk device, first, the master controller 9 sends the magnetic file to the magnetic position indicated by the physical information in the magnetic disk controller 2-i of the magnetic disk device 1-i indicated by the physical information of the previous file. A seek command to move the head is issued, and the magnetic disk device 1-i starts a seek operation. When the seek operation is completed, if the input / output buffer 3-i is ready to write data, the master controller 9 issues a read command to the magnetic disk controller 2-i, and sends the read command to the input / output buffer 3-i. The storage of the file read from 1-i is started. When the storage is completed, the master controller 9 controls the multiplex controller 8 to start transferring data from the input / output buffer 3-i to the host device 7.

As shown in FIG. 64, the multiplex controller 8 is connected to the multiplexer 201 for selecting and connecting the data buses of the input / output buffers 3-1 to 3-i to the data bus of the host device 7 and the selected i-th input bus. Output buffer 3
A DMA controller 202 for outputting data from i to the host device 7 without the intervention of the master controller 9;
The A controller 202 includes a start address registration table 203 for storing a start address and an end address for designating a transfer range of the input / output buffer 3-i, and an end address registration table 204.

The master controller 9 controls the input / output buffer 3
After setting the start address at which the file to be transferred exists in the start address registration table 203 and the end address in the end address registration table 204, data transfer from the other input / output buffer 3 to the host device 7 is performed. If not, a start command is issued to the DMA controller 202. The DMA controller 202 refers to the start address registration table 203 and the end address registration table 204 and transfers only the data in the specified range at the transfer speed requested by the higher-level device 7 without the intervention of the master controller 9.

If the processing of synthesizing physical information is performed so that the preceding file and the succeeding file can be read by a single read command, and the data is read out to the input / output buffer 3-i, the start address registration table 203 and the end address registration table A plurality of addresses are set so that all necessary files are transferred to 204, and similar processing is performed.

The process of synthesizing physical information so that the first file and the second file can be read by one read command is performed when the following conditions are satisfied.

The size of the destination file is f1 [Byte],
The size of the subsequent file is f2 [Byte], the total size of the file group that does not need to be read is k [Byte], and the effective transfer speed not including the seek operation from the magnetic disk device 1 to the input / output buffer 3 is t [Byte / sec], the rotation speed is R [rps], and the average seek time is s [sec], the average rotation waiting time is (1 / 2R), and the time of reading at one time is shorter than the time of reading one by one. The conditions are as shown in (Equation 1).

[0341]

(Equation 1)

This (Equation 1) can be written as the following (Equation 2).

[0343]

(Equation 2)

[0344] The time relation of the file reading process is as follows. The transfer speed requested by the host device 7 is set to T [Byte / s].
ec], the capacity of one cylinder of each magnetic disk device 1 is M [Byte], the transfer speed from each magnetic disk device 1 to the input / output buffer 3 is t [Byte / sec], and the minimum seek of each magnetic disk device 1 is Assuming that the time is s [sec] and the rotation speed is R [rps], the minimum seek time s [sec]
If [c] is longer than the time (M / T) for transferring the file on the i-th input / output buffer 3-i to the host device 7, the result is as shown in FIG. To satisfy the transfer speed required by the host device 7, the i-th magnetic disk device 1-
The time (s + 1 / R + M / t) when i reads a file to the input / output buffer 3-i should be within the time (nM / T) for transferring the files on all the input / output buffers 3 to the host device 7. become. Here, the seek time was set to the minimum seek time in order to read out the continuous cylinders.
Regardless of the position of the magnetic head at the time when the read command is issued to the magnetic disk device 1,
The rotation waiting time was set to the maximum value (1 / R) so as to satisfy the transfer speed required by (1). When this relationship is expressed by a mathematical expression, it is as shown in (Equation 3).

[0345]

(Equation 3)

(Equation 3) can be written as shown in (Equation 4).

[0347]

(Equation 4)

When the minimum seek time s [sec] is equal to or less than the time (M / T) for transferring the file on the i-th input / output buffer 3-i to the higher-level device 7, the time required for the file read processing is reduced. The relationship is as shown in FIG. In this case, even if the seek operation is completed, the input / output buffer 3-
Since i is transferring the file to the host device 7, the read command cannot be issued to the i-th magnetic disk device 1-i. Therefore, a read command is issued to the i-th disk device 1-i when the transfer of the file in the input / output buffer 3-i to the host device 7 is completed. Therefore, in order to satisfy the transfer speed required by the host device 7,
The i-th magnetic disk device 1-i has an input / output buffer 3-
i to read the file (M / T + 1 / R + M /
It suffices that t) be within the time (nM / T) for transferring the files on all the input / output buffers 3 to the host device 7. When this relationship is expressed by a mathematical formula, it becomes as shown in (Equation 5).

[0349]

(Equation 5)

(Equation 5) can be written as shown in (Equation 6).

[0351]

(Equation 6)

From these conditional expressions, it is possible to determine how many magnetic disk devices 1 should be combined to satisfy the transfer speed required by the higher-level device 7. The minimum number of units that satisfies (Equation 1) can be obtained. If the collective magnetic disk device is constituted by the magnetic disk device 1 described above, the best cost performance can be obtained.

For example, the magnetic disk drive 1 is composed of six tracks each having a capacity of 20 k (bytes) and having a capacity of 120 k [bytes] for one cylinder, and the transfer speed requested by the host device 7. 2M (mega) [Byte / sec], the effective transfer speed not including the seek operation from each magnetic disk device 1 to the input / output buffer 3 is 1M [Byte / sec], and the minimum seek time of each magnetic disk device 1 is 10 m. Assuming (milli) [sec] and a rotation speed of 50 [rps], (Equation 4) becomes as (Equation 7) and (Equation 8). The minimum n that satisfies these equations is 4.

[0354]

(Equation 7)

[0355]

(Equation 8)

FIG. 67 shows the time relationship during reading of the collective magnetic disk device constituted by three magnetic disk devices 1, and FIG. 68 shows the read time of the collective magnetic disk device constituted by four magnetic disk devices 1. FIG. 19 shows the time relationship during reading of the collective magnetic disk device including the five magnetic disk devices 1.

In the case of the three magnetic disk devices 1 shown in FIG. 67, as can be seen from the figure, the time required to read data from the magnetic disk device 1 to the input / output buffer 3 is from the input / output buffer 3 to the host device 7. , A time a during which data cannot be transferred from the input / output buffer 3 to the host device 7 occurs, and the transfer speed from the input / output buffer 3 to the host device 7 becomes approximately 1.6 M [Byte / sec]. The transfer speed required by the host device cannot be satisfied.

The five magnetic disk drives 1 shown in FIG.
68, the transfer speed required by the host device 7 is satisfied, but the time b during which one magnetic disk device 1 does not process is longer than that in the case of the configuration with four magnetic disk devices 1 in FIG. The use efficiency of the magnetic disk device is long.

Therefore, it can be said that the case of a configuration comprising four magnetic disk devices 1 corresponding to the minimum n that satisfies Equation 1 is the collective magnetic disk device with the best cost performance.

Another example in which the present invention is applied to a character string search device
One embodiment will be described with reference to FIG.

In the collective magnetic disk device described with reference to FIG. 57, when only the specified file is read, if the specified file exists on average in the magnetic disk devices 1-1 to 1-n, the description will be made in the first embodiment. Perform the operation like
The data transfer speed to the host device 7 can be increased.
However, if the specified file exists only in one magnetic disk device 1-i, one magnetic disk device 1-i
Reading of i will be performed continuously. In this case, the data transfer to the host device 7 must be performed by two-stage reading in which data is temporarily read from the magnetic disk device 1-i to the input / output buffer 3-i and then transferred from the input / output buffer 3-i to the host device 7. Therefore, a situation occurs in which the data transfer is reduced. As described above, if the specified file is unevenly located in the magnetic disk device 1, a situation may occur in which the data transfer speed to the host device 7 cannot be effectively increased. Therefore, in the second embodiment, all the magnetic disk devices 1 are always read and the data transfer speed to the host device 7 is increased by preventing the files from being stored unevenly.

In this embodiment, the number of magnetic disk devices is increased in order to further increase the storage capacity.

FIG. 56 shows the structure of a collective magnetic disk drive using the present invention. The difference from FIG. 57 is that the magnetic disk drive 1 has two input / output buffers 3 having the same capacity as one cylinder, The film read from the magnetic disk drive 1 can be stored in the input / output buffer 3b on the second surface while the data in the input / output buffer 3a on the one surface is being transferred to the host device 7.

Further, one data storage device 15 is composed of m magnetic disk devices 1-i-1 to 1-im and the multiplexer 14, and the total storage capacity of the collective magnetic disk device is one magnetic disk device. Storage capacity of disk device (n ×
m) Doubled.

In operation, first, the structure of the database is defined in the same manner as in the configuration shown in FIG. 57, but information for identifying the m magnetic disk devices 1 connected to the input / output buffer 3 via the multiplexer 14 is obtained. Add to structure definition information.

The construction of the database is performed in the same manner as in the configuration of FIG. 57, but there are some differences. The difference from the configuration of FIG. 57 is that the file given by the file information is divided into the number of magnetic disk devices constituting the file and is distributed and stored in all the magnetic disk devices. In addition, the multiplexer 14 is controlled to store the data of the input / output buffer 3 in one of the m magnetic disk devices 1-ij given by the storage physical information.

[0367] As a method for dividing the file, a division size is obtained by dividing the file size by the number of units, and the first magnetic disk device 1-1 is divided for each division size from the head of the file.
The first magnetic disk device is stored for each determined size, such as -j to 1-2j, 1-3j in order, and 1 byte from the beginning of the file. Some items are stored in order from 1-1-j to 1-2-j and 1-3-j.

If the file size is not divisible by the number of magnetic disk devices, invalid data is added to the end so that the file size is a multiple of the magnetic disk, and the first magnetic disk device 1-1-j is always used. In the file so that the beginning of the file comes first.

Next, the reading of a file will be described.
This is also performed in the same manner as in the example of FIG. 57, but since the input / output buffer 3 has two surfaces (3a and 3b) in this configuration, the files read from the respective magnetic disk devices 1 to the input / output buffer 3 are stored. At this point, the reading process of the next file can be started.

The time relationship of the file reading process is as shown in FIG. 70. Compared with the example of FIG. 57, there is no waiting time until the data can be written into the input / output buffer 3, and the speed is higher. Transfer becomes possible. FIG.
The relationship that satisfies the transfer speed required by the host device 7 under the same conditions as in the example of Example 7 is that one magnetic disk device 1-ij has one input / output buffer 3a of two input / output buffers 3-i. i, the time to read the file (s + 1 / R + M /
t) may be within the time (nM / T) for transferring all the other files of the input / output buffers 3b-1 to 3b-n to the higher-level device 7, and this is expressed by the following equation. )become that way.

[0371]

(Equation 9)

(Equation 9) can be easily written as (Equation 10).

[0373]

(Equation 10)

Under these conditions, it is possible to determine the number of data storage devices 15 that satisfy the transfer speed required by the host device, as in the first embodiment.

When a large storage capacity is required, the data storage device 15 is composed of m magnetic disk drives 1 and the multiplexer 14, and the storage capacity can be increased by m times.

If the collective magnetic disk drive is constituted by the minimum number of magnetic disk drives 1 determined from the above, the cost performance is the best.

In the embodiment shown in FIG. 70, the start of the seek operation of each magnetic disk device is started by the input / output buffer 3-1 to the host device.
Obviously, the transfer may be performed at the time when the data transfer of .about.3-n is completed.

In the above two embodiments, the case where the magnetic disk device is used has been described. However, it is clear that the same applies to a storage device such as an optical disk device other than the magnetic disk device in which the storage medium rotates.

Next, an embodiment in which the document information retrieval apparatus of the present invention can be connected to the outside via a LAN or the like will be described based on the disclosure of FIGS. 71 to 74.

The document information search device (referred to as a search machine) 3000 shown in FIG. 71 has a LAN connection control function such that the search machine control computer can be connected to the communication line 1000 such as 1150 LAN. The search machine 3000 is a search machine control computer 1
150 and a search unit 3100.
In the search machine control computer 1150, a search machine control program 1100 is executed. This search machine control program 1100 is the search expression analysis program 11 described in the first embodiment (FIG. 10) of the present invention.
02, a synonym variant description expansion program 1103a, a complex condition analysis program 1141a, and a search execution control program 1108 are executed.

The search unit 3100 includes an automaton generation computer (CPU1) 1105a, a bit search computer (CPU3) 1107a, a string search engine 1106, a complex condition determination computer (CPU2) 1145a, and a semiconductor memory device 1110.
a, a RAM disk device 1110b and a collective magnetic disk device 1110c.

A computer for generating an automaton (CPU
1) In 1105a, the automaton generation program 110
5 is a bit search computer (CPU 3) 110
In 7a, the bit search program 1107 is executed, and in the compound condition judgment computer (CPU2) 1145a, the compound condition judgment program 1145 is executed.

Also, the collective magnetic disk drive 1110c
Is composed of a collective magnetic disk drive 1110d and magnetic disk drives 1110e1 to 1110e12. The collective magnetic disk device 1110d includes a multi-disk controller 1110f and a synchronous control buffer 111.
0g1 to 1110g12. The synchronization control buffers 1110g1 to 1110g12 are magnetic disk devices 1110e1 to 1110e1 that operate independently.
2 for synchronizing and synchronizing the output with the string search engine 1106. That is,
For example, when the text data in the magnetic disk device 1110e1 must be sent before the text data in the magnetic disk device 1110e2, and the text data in the magnetic disk device 1110e2 is read first. However, this data is stored in the synchronization control buffer 111.
0g2, the magnetic disk drive 1110e
1 is read out to the synchronization control buffer 1110g1, and the multi-disk controller 111
By reading the data in the synchronization control buffer 1110g2 to the string search engine 1106 after reading to the string search engine 1106 via 0f, the data can be read to the string search engine 1106 in the original order. Thus, the synchronization control buffers 1110g1 to 1110g12
Can be sent out to the outside in a correct and predetermined order regardless of how the read order of the magnetic disk devices 1110e1 to 1110e12 changes due to variations in the seek time and the rotation waiting time of each magnetic disk device. The multi-disk controller 1110f executes the search execution control program 1 in the search machine control program 1100.
108, the synchronization control buffer 1110g1
It functions as a multiplexer for selecting the output of ~ 1110g12.

The RAM disk device 1110b has a RAM
Disk controllers 4200b, 4100c, 410
0d. Semiconductor memory board 4100a,
4100b, 4100c and 4100d are connected to the same bus, and the pseudo text stored here is randomly accessed under the control of the RAM disk controller 4200. Then, the read data is sent to the string search engine 1106.

The search machine control program 1150 is
In response to a search command sent via the LAN 1000, first, search condition analysis, synonym expansion, different notation expansion, compound condition analysis, neighborhood condition analysis, context condition analysis, and logical condition analysis are performed. Are passed to the bit search program 1107, the automaton generation program 1105, and the complex condition determination program 1145. The state transition table data for keyword matching created by the automaton generation program 1105 is written to the string search engine 1106.

Second, when the setting of the search control information is completed, the execution of the search is started. First, the semiconductor memory 1110a
The above character component table is read out, and the bit search program 1107 performs a character component table search. The result of the character component table search is stored on the main memory of the search machine control computer 1150. Next, a pseudo-shortened text search is performed on the document set narrowed down by the character component table search. That is, the relevant document identifier as the result information of the character component table search stored on the main memory of the search machine control computer 1150 is read,
The corresponding shrunken text is stored in the RAM disk device 1110.
b, the collation information of the string search engine 1106 is passed to the complex condition determination program 1145, and it is determined whether or not it matches the complex condition specified here. The result of the pseudo text search is stored in the main memory of the search machine control computer 1150 in the same manner. Thereafter, if the neighborhood condition or the context condition is set in the compound condition, the process enters the text search. In the text search, the search machine control computer 115 is used.
0, the corresponding document identifier as the result information of the pseudo text search stored in the main memory is read, and the corresponding text is read from the collective magnetic disk device 1110c.
The string search engine 1106 performs a specified keyword matching process. This string search engine 110
The collation information of No. 6 is passed to the complex condition determination program 1145, where it is determined whether or not the designated complex condition, that is, the neighborhood condition and the context condition are matched. This text search result is stored in the main memory of the search machine control computer 1150 in the same manner.

The control of these search means is all performed by the search execution control program 1108 in the search machine control program 1100.

Third, when the above-described series of search processing is completed, the search result written in the main memory of the search machine control computer 1150 is transmitted to the request source via the LAN 1000 under the control of the search machine control program 1100. It is returned to a search dialogue terminal such as a workstation.

According to the modified example of the present invention described above, the document information search device is used as a server in the LAN, and
It is possible to perform a search from a plurality of search dialogue terminals connected to, and it is possible to make effective use as a shared resource.

Next, another embodiment of the present invention will be described with reference to FIG.

[0391] In this embodiment, the document information search device (called a search machine) 3000 is a communication line 10 such as a LAN.
00 LAN connection control adapter 2100
It has. The search machine 3000 includes a LAN connection control adapter 2100, a search machine control computer 2200 and a plurality of search units 3001, 3
002,....

Computer for controlling search machine 1150
Then, the search machine control program 1100 is executed. The search machine control program 1100 includes the search expression analysis program 1102 and the synonym variant expression expansion program 110 described in the first embodiment of the present invention (FIG. 10).
3a, a complex condition analysis program 1141a, and a search execution control program 1108.

The search unit 3001 includes an automaton generation computer (CPU1) 1105a, a bit search computer (CPU3) 1107a, a string search engine 1106, a complex condition determination computer (CPU2) 1145a, and the semiconductor memory device 111.
0a, a RAM disk device 1110b, a collective magnetic disk device 1110c, a search result storage memory 1146, and selectors 3610 and 3620.

A computer for generating an automaton (CPU
1) In 1105a, the automaton generation program 110
5 is a bit search computer (CPU 3) 110
In 7a, the bit search program 1107 is executed, and in the compound condition judgment computer (CPU2) 1145a, the compound condition judgment program 1145 is executed.

Also, the collective magnetic disk drive 1110c
Is composed of a collective magnetic disk drive 1110d and magnetic disk drives 1110e1 to 1110e1n. The magnetic disk devices 1110e1 to 1110e1n store text data, pseudo-text data, character component tables, bibliographic items, and the like in a distributed manner. From the text search, the text data is sent from here to the string search engine 1.
It is read into 106.

The semiconductor memory device 1110a has magnetic disk devices 1110e1 to 1110e when the system is started up.
The character component table is loaded from 10e1n, and is accessed by the bit search program 1105 as target data of the character component table search at the time of search.

Similarly, the RAM disk device 1110b has a magnetic disk device 1110 when the system is started up.
The pseudo text is loaded from e1 to 1110e1n, and accessed by the string search engine 1106 as target data of the pseudo text search at the time of search.

The string search engine 1106 reads the pseudo-contracted text from the RAM disk device 1110b and the main text from the collective magnetic disk device 1110c at the time of the pseudo-text search and the text search, respectively, and performs the search and collation processing of the designated keyword. The selector 3610 functions to switch the input to the string search engine 1106 between the RAM disk device 1110b and the collective magnetic disk device 1110c. Also, the selector 3620 functions to switch between inputting the character component table search result to the search result storage memory 1146 and inputting the pseudo text search result and the text search result.

The search machine control program 1150 is
In response to a search command sent via the LAN 1000, first, search condition analysis, synonym expansion, different notation expansion, compound condition analysis, neighborhood condition analysis, context condition analysis, and logical condition analysis are performed. The control information created in step (1) and the bit search program (1107) for each of the search units (3001, 3002,...) And the automaton generation program (110)
5 and the composite condition determination program 1145. Each search unit 3001, 3002, ...
… Then, each automaton generation program 1105
The table data is written to the string search engine 1106 in the number of states for keyword comparison created in the above.

Second, when the setting of the search control information is completed, the execution of the search is started. Here, the search execution control program 11 on the search machine control computer 1150 is used.
08 broadcasts search start information to each of the search units 3001, 3002,....

Each search unit 3001, 3002,...
.., First, the character component table on the semiconductor memory 1110a is read, and a character component table search is performed by the bit search program 1107. The result of the character component table search is written to the search result storage memory 1146. At this time, the search execution control program 1102 selects the writing from the bit search program 1107.
8 has been switched.

Next, a pseudo text search is executed on the document set narrowed down by the character component table search. That is, the relevant document identifier as the result information of the character component table search stored in the search result storage memory 1146 is referred to the pseudo-text storage information included in the search execution control program 1108, and the RAM disk of the relevant pseudo-text is stored. Device 11
The storage area information on 10b is set in the RAM disk controller 7200 (FIG. 22). Thereafter, the corresponding foreshortened text is read from the RAM disk device 1110b, and the string search engine 1106 performs matching processing of the designated keyword. The collation information of the string search engine 1106 is passed to the complex condition determination program 1145,
Here, it is determined whether or not the compound condition specified is met. The pseudo text search result is similarly written into the search result storage memory 1146. Naturally, the selector 3620 has been switched by the search execution control program 1108 to select writing from the complex condition determination program 1145.

Thereafter, if the neighborhood condition or the context condition is set in the compound condition, the process enters the text search. In the text search, the relevant document identifier as the result information of the pseudo-text search stored in the search result storage memory 1146 is referred to the text storage information included in the search execution control program 1108, and the set type magnetic disk of the relevant text is referred to. This is set in the control device 1110d (FIG. 20). After that, the corresponding text is read from the collective magnetic disk device 1110c, and the string search engine 1106 performs the specified keyword collation processing. The collation information of the string search engine 1106 is stored in the complex condition determination program 11
The determination is made as to whether or not the composite condition specified here, that is, the neighborhood condition and the context condition are met.
This text search result is written into the search result storage memory 1146. At this time, the selector 3610 selects reading from the collective magnetic disk device 1110c.
Further, the selector 3620 sets the compound condition determination program 114
5 is switched by the search execution control program 1108 so as to select writing from 5 on.

The above-described control of the search procedure is all performed by the search execution control program 1108 by broadcasting to the search units 3001, 3002,...

Third, when the above-described series of search processing is completed in all the search units 3001, 3002,..., The search execution control program 1108 compares the search results written in each search result storage memory 1146 with all the search units. 30
.., And are integrated to control LAN1 under the control of the search machine control program 1100.
000 to the requestor.

The search machine control computer 1
A magnetic disk device 2400 is attached to 150, and stores configuration information of the search machine 3000, that is, the number of search units and the like. further,
When search requests are received from a plurality of users via the LAN, the magnetic disk device 2400 temporarily stores these requests or temporarily stores search result information to be returned according to the operation status of the search unit. Also used to store.

Further, the operation status of the present search machine is appropriately displayed on the console 2300 attached to the search machine control computer 1150, or the maintenance operation can be instructed from here.

As shown fairly in this example,
According to the present invention, the number of magnetic disk devices and the number of search units in the collective magnetic disk device can be specified by the user as required specifications, that is, the required text data storage capacity,
The information retrieval apparatus can be configured very easily according to the retrieval time and the like.

FIG. 73 shows still another embodiment of the present invention. In the embodiments described so far, the collective magnetic disk drive 1110c, the bit search computer 1107a, or the string search engine 1
106, the compound condition determination computer 1145a and the search result storage memory 1146 are connected in cascade, and a pipeline operation is performed to improve the processing speed. On the other hand, in the present embodiment, the above components are connected by a bus 8000, thereby simplifying the hardware configuration, and thereby reducing the device scale. Also, a collective magnetic disk drive 1110c,
A control computer 1150a for the RAM disk device 1110b and the semiconductor memory device 1110a, a bit search computer 1107a, a string search engine 1106, and a complex condition determination computer 1
The load on the search machine control computer 1150 can be reduced by distributing one control computer 1150b for each of the 145a, and the load on the search machine control computer 1150 can be reduced as a whole, thereby reducing the overhead related to the search processing.

Finally, an embodiment in which the document information search device of the present invention is used in a network system will be described with reference to FIG.

In the figure, reference numeral 1000 denotes a network such as a LAN, to which a search machine 3000 is connected by a communication control means 2100 via a search machine control workstation 2200.

[0412] Reference numeral 5200 denotes an optical disk device 551.
., 5530 are image servers that integrally control 5530. The image server 5200 is also connected to the network 1000 by the communication control unit 5100. 5400 is an optical disk drive 5510, 552
A magnetic disk device that stores management information for managing the location of image data corresponding to documents at 0,.

[0413] Reference numeral 1200 denotes a search dialogue workstation capable of displaying data, which is also connected to the network 1000 by the communication control means 1100. In addition to this workstation, an image printer 1400, an image scanner 1500, a magnetic disk device 1600, and an optical disk device 1700 are connected.

[0414] Reference numeral 6200 denotes a search dialogue workstation, which is also connected to the same network by the communication control means 6100. This is a search and read-only workstation. The workstation 1200 requests image data corresponding to the corresponding document from the image server 5200 in accordance with the search result from the search machine 3000, receives the image data via the network, displays the image data on the console 1300, and reads the drawing including the drawing. It is possible to This image data can be hard copied to the image printer 1400. It is also possible to edit this image data on this workstation and store it in the optical disk device 1700 as a private file for personal use.
In this editing, an image input from the image scanner 1500 can be used.

Therefore, only the edited part is stored in the magnetic disk device 1600 and the optical disk device 1700 without modifying the public data stored in the database of the search machine or the image server, and the corresponding information is stored in the magnetic disk device. 1600.

[0416]

As a method of accelerating a scan type full text search, it is possible to realize registration of data which enables presearch. By performing the pre-search, it is possible to reduce the number of cases where the text body stored in the data storage means such as a magnetic disk is referred to, thereby reducing the amount of body search processing which accounts for a large portion of the search processing time. Becomes possible, and as a result, it becomes possible to shorten the entire search processing time.

By searching the search data file, the speed of the search can be increased. Specifically, it is possible to extract only documents containing all the characters specified by the character component table, and it is possible to narrow down the number of documents to be searched later to the minimum necessary. Time can be reduced. Furthermore, by scanning the mock text data, it is possible to extract only documents in which a specified keyword is described in word units,
Since the number of documents to be subjected to the subsequent text search can be reduced to a necessary minimum, the entire search processing time can be further reduced.

[0418] Therefore, for a document narrowed down as a result of the pre-search, data is read out and scanned, and a full-text search is performed according to the last compound condition. Therefore, a very high-speed full text search can be equivalently realized. become.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a conventional search system.

FIG. 2 is an explanatory diagram (part 1) showing a conventional character string search principle using a finite automaton.

FIG. 3 is an explanatory diagram (part 2) illustrating a conventional character string search principle using a finite automaton.

FIG. 4 is an explanatory diagram (part 1) of a fail table corresponding to a conventional example.

FIG. 5 is an explanatory diagram (part 3) illustrating a principle of a character string search using a conventional finite automaton.

FIG. 6 is an explanatory diagram (part 2) of a fail table corresponding to the conventional example.

FIG. 7 is an explanatory view (No. 4) showing the principle of character string search by the conventional finite automaton.

FIG. 8 is an explanatory view (3) of a fail table corresponding to the conventional example.

FIG. 9 is a block diagram showing a conventional configuration of different notation development.

FIG. 10 is a block diagram showing an outline of a first embodiment of the present invention.

FIG. 11 is a diagram illustrating an example of collation position information.

FIG. 12 is a diagram illustrating an example of output information of a search engine with a matching position added.

FIG. 13 is a diagram illustrating details of a composite condition determination unit.

FIG. 14 is a diagram illustrating a search example using two keywords.

FIG. 15 is a configuration diagram showing a means for accelerating a full text search.

FIG. 16 is a diagram showing a procedure of a text registration process.

17 is a diagram showing a means for performing a search process from a character component table registered and generated by the registration procedure shown in FIG. 16;

FIG. 18 is a diagram showing a configuration of a character component table and a specific example of a search using the same.

FIG. 19 is a diagram illustrating creation of a pseudo-text.

FIG. 20 is a PAD diagram (No. 1) showing a procedure of a character component table search.

FIG. 21 is a PAD diagram (No. 2) showing a procedure of a character component table search.

FIG. 22 is a PAD diagram (part 3) showing a procedure of a character component table search.

FIG. 23 is a PAD diagram (part 4) showing a procedure of a character component table search.

FIG. 24 is a PAD diagram (No. 5) showing a procedure of a character component table search.

FIG. 25 is a configuration diagram showing a modification of the embodiment shown in FIG. 10;

FIG. 26 is a block diagram of an embodiment for performing processing for developing synonyms and different notations.

FIG. 27 is a diagram for explaining an outline of processing in the embodiment shown in FIG. 26;

FIG. 28 is a configuration block diagram of one embodiment of the present invention.

FIG. 29 is a diagram illustrating an example of a process of developing a different notation.

FIG. 30 is a block diagram of a different notation developing unit.

FIG. 31 is a diagram illustrating a process of applying a conversion rule in a variant notation expansion processing unit using a katakana character string.

FIG. 32 is a PAD showing a different notation development process.

FIG. 33 is a diagram illustrating an example in which a search for a search character string is performed using an automaton.

FIG. 34 is a state transition table diagram of the automaton.

FIG. 35 is an output table diagram of an automaton.

FIG. 36 is a PAD diagram showing a method of creating a state transition table and an output table of a search automaton.

FIG. 37 is a diagram showing a katakana different notation conversion rule table.

FIG. 38 is a diagram showing a different notation conversion rule table for new and old kanji characters.

FIG. 39 is a diagram showing a different notation conversion rule table related to the kanji kana.

FIG. 40 is a diagram showing an example of a correspondence table between Roman characters and katakana;

FIG. 41 is a block diagram that enables setting of a development mode of a different notation development unit.

FIG. 42 is a diagram illustrating a control state of output of each conversion unit, expansion unit, and switch in different notation expansion.

FIG. 43 is a diagram showing a synonym dictionary.

FIG. 44 is a diagram showing an outline of searching for a heading character string of a synonym dictionary using an index table.

FIG. 45 is a block diagram showing the configuration of a character search or color using a finite state automaton according to an embodiment of the present invention.

FIG. 46 is an explanatory diagram (part 1) illustrating the principle of a character string search method using a finite automaton according to an embodiment of the present invention.

FIG. 47 is an explanatory diagram (part 2) illustrating the principle of the character string search method using the finite state automaton according to the embodiment of this invention.

FIG. 48 is an explanatory diagram (part 3) illustrating the principle of the character string search method using the finite state automaton according to the embodiment of this invention.

FIG. 49 is an explanatory diagram (No. 4) illustrating the principle of the character string search method using the finite automaton according to the embodiment of this invention.

FIG. 50 is an explanatory diagram (No. 5) illustrating the principle of the character string search method using the finite state automaton according to the embodiment of this invention.

FIG. 51 is an explanatory diagram (No. 6) illustrating the principle of the character string search method using the finite state automaton according to the embodiment of this invention.

FIG. 52 is an explanatory diagram (No. 7) illustrating the principle of the character string search method using the finite state automaton according to the embodiment of this invention.

FIG. 53 is an explanatory diagram (No. 8) of the principle of the character string search method using the finite state automaton according to the embodiment of this invention;

FIG. 54 is an explanatory diagram of a state transition table according to the embodiment of this invention.

FIG. 55 is an explanatory diagram of a search result table.

FIG. 56 is a configuration example diagram of a collective magnetic disk device according to an embodiment of the present invention.

FIG. 57 is a configuration diagram showing one embodiment of the present invention.

FIG. 58 is a diagram showing the structure of a structure definition table.

FIG. 59 is a diagram showing the structure of a storage position pointer table.

FIG. 60 is a diagram showing the structure of a physical information table.

FIG. 61 is a flowchart of writing a file in the embodiment shown in FIG. 57.

FIG. 62 is a time chart of a file write process in the collective magnetic disk device shown in FIG. 57;

FIG. 63 is a flowchart of a file reading process in the embodiment shown in FIG. 57.

FIG. 64 is a diagram illustrating a configuration of a multiplex controller.

FIG. 65 is a time chart of a file reading process in the collective magnetic disk device in the embodiment shown in FIG. 57;

FIG. 66 is a time chart of a file reading process in the collective magnetic disk device in the embodiment shown in FIG. 57;

FIG. 67 is a time chart of a file reading process in the collective magnetic disk device constituted by three magnetic disk devices in the embodiment shown in FIG. 57;

FIG. 68 is a time chart of a file read process in the collective magnetic disk device constituted by four magnetic disk devices in the embodiment shown in FIG. 57;

FIG. 69 is a time chart of reading a file in a collective magnetic disk device including five magnetic disk devices in the embodiment shown in FIG. 57;

FIG. 70 is a time chart of a file reading process in two collective magnetic disk devices in the embodiment shown in FIG. 56;

FIG. 71 is a configuration block diagram showing an embodiment connected to a LAN.

FIG. 72 is a block diagram showing a modification of the embodiment shown in FIG. 71.

FIG. 73 is a view showing a modification of the embodiment shown in FIG. 71;

FIG. 74 is a configuration block diagram showing a configuration of a modified example of FIG. 71.

FIG. 75 is a diagram showing a specific example of a RAM disk device.

FIG. 76 shows an example of a code word expression character string (part 1).
It is.

FIG. 77 shows an example of a code word expression character string (part 2).
It is.

[Explanation of symbols]

1101 ... keyboard, 1102 ... search expression analysis program, 1103a ... synonymous notation expansion program, 110
5: Bit search computer, 1106: String search engine, 1107: Bit search program, 1110: Text data file, 1145a ...
Computer for determining complex conditions, 1146: Search result storage memory, 1150: Computer for controlling search machine

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Hisamitsu Kawaguchi 1-280 Higashi Koigakubo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory of Hitachi, Ltd. (72) Inventor Atsushi Hatakeyama 1-280 Higashi Koikebo, Kokubunji-shi, Tokyo Central Research Laboratory (72) Inventor Noriyuki Kaneoka 1-280 Higashi Koikekubo, Kokubunji, Tokyo, Japan Inside Central Research Laboratory, Hitachi, Ltd. (72) Inventor Mitsuru Akizawa 1-280 Higashi Koikebo, Kokubunji, Tokyo, Japan Central Research Laboratory, Hitachi, Ltd

Claims (27)

[Claims] 1. A method of registering data in a data storage means capable of storing a plurality of data, wherein the data is registered in the data storage means, and it is determined whether or not each predetermined character is included in the registered data. A data registration method characterized by registering a character component table shown in association with the registered data. 2. The data registration method according to claim 1, wherein the data includes text data composed of a character code. 3. The data registration method according to claim 1, wherein the character component table is registered in the data storage unit. 4. The data registration method according to claim 1, wherein each of said predetermined characters is said data to be registered and data stored in said data storage means before said data to be registered. A data registration method characterized by being a character that appears in at least one of the following. 5. A method of registering data in a data storage means capable of storing a plurality of data, wherein the data is registered in the data storage means, and a word which repeatedly appears in the registered data is determined from the registered data. A data registration method characterized by storing condensed text data from which duplication has been eliminated in correspondence with the registered data. 6. The data registration method according to claim 5, wherein said condensed text data is registered in said data storage means. 7. The data registration method according to claim 5, wherein the condensed text data is included in a predetermined number or more of data registered in advance in the data storage unit and the registered data. A data registration method characterized in that a word to be registered is excluded. 8. The data registration method according to claim 5, wherein said condensed text data is registered by removing an attached word from said registered data. Method. 9. A method of registering data in a data storage means capable of storing a plurality of data, the method comprising: registering data in the data storage means; and determining whether or not each of predetermined characters is included in the registered data. Registering condensed text data from which duplicate words of words repeatedly appearing in the registered data are removed from the registered character component table and the registered data in correspondence with the registered data, respectively. Method. 10. The data registration method according to claim 9, wherein the predetermined character is a character that appears in the condensed text data. 11. A computer in which data is registered in data storage means capable of storing a plurality of data, and a character component table indicating whether or not each predetermined character is included in the registered data is stored in the registered data storage unit. A storage medium storing a program to be registered corresponding to data. 12. The storage medium according to claim 11, wherein the predetermined characters are characters that appear in at least one of the data to be registered and data stored in the data storage unit before the data to be registered. A storage medium characterized by the following. 13. A computer in which data is registered in data storage means capable of storing a plurality of data, and from the registered data, condensed text data in which duplication of words repeatedly appearing in the registered data is eliminated. A storage medium storing a program to be registered corresponding to the registered data. 14. A computer in which data is registered in a data storage means capable of storing a plurality of data, a character component table indicating whether or not each predetermined character is included in the registered data, and A storage medium storing a program for registering condensed body data in which duplicates of words repeatedly appearing in the registered data from the registered data are respectively associated with the registered data. 15. The storage medium according to claim 14, wherein the predetermined character is a character that appears in the condensed text data. 16. A method for indicating whether or not a predetermined character is included in the data corresponding to each of a plurality of data stored in the data storage means. A storage medium for storing a character component table for eliminating data which is searched when a search is performed and which is unlikely to include an input search keyword. 17. A method for removing duplication of words repeatedly appearing in the registered data from registered data corresponding to each of the plurality of data stored in the data storage means, and storing the data in the data storage means. A storage medium for storing condensed text data for eliminating data that is searched when a search is performed on data that has no possibility of including an input search keyword. 18. A search is performed when a search is performed on the data stored in the data storage means, the search data corresponding to each of the plurality of data stored in the data storage means, and the search keyword is included. It is for eliminating data that is not possible, and repeatedly appears in the registered data from a character component table indicating whether a predetermined character is included in the data and the registered data. A storage medium for storing condensed text data from which duplication of words has been eliminated. 19. The storage medium according to claim 18, wherein the predetermined character is a character that appears in the condensed text data. 20. A means for registering data in data storage means capable of storing a plurality of data, and a character component table indicating whether or not each predetermined character is included in the registered data. A data registration device comprising means for registering data in correspondence with data. 21. The data registration device according to claim 20, wherein each of the predetermined characters appears in at least one of the data to be registered and data stored in the data storage unit before the data to be registered. A data registration device, which is a character. 22. The data registration device according to claim 20, wherein the data includes document data having a character code. 23. A means for registering data in a data storage means capable of storing a plurality of data, and: extracting condensed text data from the registered data by eliminating duplication of words repeatedly appearing in the registered data. A data registration device comprising means for registering data in correspondence with data to be registered. 24. The data registration device according to claim 23, wherein the data includes document data having a character code. 25. A means for registering data in data storage means capable of storing a plurality of data, a character component table indicating whether or not each predetermined character is included in the registered data, and A data registration device, comprising: means for registering, from data, condensed text data in which duplication of words repeatedly appearing in the registered data has been eliminated in correspondence with the registered data. 26. The data registration device according to claim 25, wherein the predetermined character is a character that appears in the condensed text data. 27. The data registration device according to claim 25, wherein the data includes document data having a character code.