JPH0365571B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field The present invention relates to an address storage control method for data to be searched by ranking and searching a plurality of pieces of data in priority order.

Prior Art When performing information retrieval using conventional hardware, as a method of storing addresses of searched data that match the search data, a memory dedicated to storing addresses is prepared, and the matching record address is stored. There are two methods: to temporarily end the process, or to sequentially update new corresponding record addresses. However, with conventional search methods, the number of records that can be extracted in a single process is one, making it difficult to extract multiple records in real time and requiring large hardware to make it possible.

When extracting desired information from an information retrieval device equipped with an external storage device such as a magnetic disk, there is a method of storing a large amount of information in the external storage device in the main memory of a central processing unit and searching within the memory. was taken. In addition, in order to process the read information from the magnetic disk in real time and extract the desired information, only one piece of information can be obtained per access, and in applications that require a large number of pieces of information, it is difficult to extract the desired information. It is necessary to access the external storage device for the number of cases, which has the disadvantage of requiring a lot of time.

Purpose The present invention improves the above-mentioned conventional drawbacks, makes it possible to extract multiple items of information within a single processing time, and makes it possible to store the corresponding record address of the search result in a flexible, inexpensive, and high-speed processing manner. The purpose of the present invention is to provide an address storage control method with a configuration of:

Embodiment An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a block diaphragm of an information retrieval device embodying the present invention.

1 is an external storage device under the control of this information retrieval device; 2 is an interface A for controlling, transmitting and receiving data and clocks of the external storage device 1;
3 is an interface B for transmitting and receiving the address of the external storage device 1 and return information from the external storage device 1; 4 is a control unit MCT which controls the above-mentioned 1, 2, 3 and the entire information retrieval device of the present invention. 5
switches the internal bus line, which will be described later, and
A three-state gate that also controls the direction of data according to instructions from MCT4. 6 is a memory JM that temporarily stores information instructing a search method for search information. 7 is a memory Q1 that stores initial values of search information. The memories Q2, 8 and memories Q3, 9 temporarily store the searched data extracted from the external storage device 1, or temporarily store the temporarily stored searched data, according to the contents of the memories JM6 and memories Q1, 7. This is a search register that also serves as a buffer memory and serves as a search data storage memory for searching the third extracted data. 10
Comparator CM1.1 compares data read from external storage device 1 via interface A2 with data read from memories Q1 and 7.
1 and 12 are comparators CM2 or CM2, which compare the read data with the data read from the memories Q2, 8 or the memories Q3, 9, similar to the above-mentioned CM1, 10.
CM3.13 is memory JM6, memory Q1,7,
Length counters L, C that control the addresses of memories Q2, 8, memories Q3, 9 and the length of searched data. 14 is CM1, 10, CM2, 11,
Controls the logic control of each comparator output of CM3 and 12.
A search logic circuit control unit IRCT that controls the operation of the LC 13 and sends predetermined control information to a corresponding record address storage memory ADM16 and a corresponding record status storage memory STM7, which will be described later. 15 is
According to the output information of MCT4, the division of searched data is counted, each set of data (record) is held as the corresponding address, and IRCT1
Record address counter RADC sent to APM 16 according to the instruction of 4. 16, as mentioned above,
A memory that temporarily stores the contents of RADC16 and record addresses according to instructions from IRCT14.
ADM. Reference numeral 17 denotes a memory STM that stores the state of searched data (presence or absence of a match, information on the presence or absence of multiple matches indicating that the same data previously existed, etc.). 1
Reference numeral 8 denotes a bus interface BIF for connecting the information retrieval device of the present invention and higher-level devices. 19 is a high-speed bus line MBCS through which raw information from the external storage device 1 mentioned above is exchanged. 20 is an SBUS through which the status of each memory, counter values, and information to the BI 18 are exchanged under the control of the MLT4. 21 is a communication means LBUS between this information retrieval device and a host device, and an arbitrary communication means can be constructed using the BIF 18.

Next, the principle of operation of an information retrieval device according to a preferred embodiment of the present invention will be explained in detail with reference to the drawings.

FIG. 2 is an operational flowchart of the present invention.
An external storage device 1 in which instructions and search data to be searched are stored in the information processing apparatus in a predetermined format via the LBUS 21 in FIG.
address or file name for each file is sent from the host device, the sent information is decoded by the control unit (MCT) 4, and controlled to the external storage device 1 via each search register and interface B3. etc., and the search process begins. When predetermined initial values are set in the search registers JM and Q1 (steps 100 and 101), the external storage device 1 enters a data read cycle (step 10).
2). There is a waiting time until the external storage device 1 reaches the address to be searched, and when the search instruction address is reached (step 103-Y),
A search start command is sent from MCH4 to LC13 and RADC15 (step 104), and in synchronization with the read speed of external storage device 1, according to the contents of JM6, via Q1, 7 and interface A2,
External storage device 1 output on MBUS19
A comparison with the read data is performed (step 105). This comparison uses the first and second half of one clock cycle to compare two types of information, which are the upper limit value (or lower limit value) and the initial value of the lower limit value (or upper limit value), to the searched data. is included in the initialized values. Next “Q
If it is determined that the data is applicable in step 1, it is selected whether the data has the first priority or not (step 106), and if it is not the first priority, then whether or not the data has the second priority is selected. selected (step 10)
7).

The conditions for selection as the first priority are (1) When the first match is found within the specified search range.

(2) When the value is closer to the limit value than the corresponding data stored in Q2 and Q3.

The conditions to be selected as the second priority are: (1) If a match is found for the second time within the specified search range, and the corresponding data is further from the extreme value than the first time, or the first match data is found. If equal to .

(2) When the first priority and second priority data stored in Q2 and Q3 are farther from the extreme value than the existing first priority data and closer to the extreme value than the existing second priority data (in this case This data replaces the existing second priority data and becomes second priority data).

If it is determined that the data has the first priority (step 106-Y), the flag; FSDB is determined as to whether the data stored in Q2, 8 and Q3, 9 have the same content (step 108 ), if FSDB≠1 (if not the same content), it is the first corresponding data from the start of the search, or Q2, 8
This means that data with a higher priority than the data stored in Q3 and Q9 has been input as searched data. Therefore, it indicates that there was searched data with the same data as the first priority data in the past.
It is determined whether the FDBL flag is set (step 113), and if so, it is reset (step 114). After that, in order to make the searched data stored in the work area the first priority data, the value of the record address counter where the searched data was recorded is stored in memory.
In addition to setting it to ADM (step 111),
The work area stored in the searched data in Q2, 8, Q3, and 9 is set as the search data area, and Q2,
8, Q3, and 9 are deleted, and the data storage location becomes a new work area (step 112).

Also, if FSDB=1, the corresponding data stored in Q2, 8, Q3, and 9 are equally searched data, that is, the first priority data is closer to the limit value than the existing data, so one of the existing data is deleted. However, the FDBL flag is set to indicate that data equal to the previously applicable data existed in the past (step 109), and then the FSDB flag is reset to indicate that the previously applicable data is the same (step 110). ).

Then, in the same way as when FSDB = 1 mentioned above, the value of the record address counter is set in the memory ADM, and the corresponding data that is later in time (referring to the existing data that is near the end of the address within the search instruction range) is deleted (the step is started). 111), the deleted data area of Q2 or Q3 mentioned above is secured as a work area for the next record (step 112).

Next, if it is determined that it is not the first priority (step 106-N), it is determined whether the above-mentioned conditions for the second priority are satisfied (step 106-N).
7) When it is determined that the second priority data is the second priority data, it is determined whether the second priority data is equal to the existing first priority data (step 115), and if they are equal, the Q
This means that the data stored in the 2, 8, Q3, and 9 registers are equal, and the next time the corresponding data interrupts the upper rank as first priority data,
Flag for setting the above FDBL, FSDB
(This indicates that the corresponding data of Q2 and Q3 are equal.) is set (step 116), and the value of the record address counter is set in the memory ADM (step 114). The area used to be used as a new work area,
The area where the searched data was stored is set as the new search data for the second priority data (step 112).

Also, if the second priority data is different from the first priority data, for example, in a descending sort process, if the first priority data < the second priority data, it will be treated as normal applicable data and a special flag will be set. Does not involve setting or resetting. That is, the record address is set in the memory ADM (step 111), and the deleted data area is secured as a new work area (step 112).

If it is determined in step 107 that the data is not the second priority data, it is determined whether the data is equal to the second priority data (step 117), and if they are equal, the data is stored in Q2, 8, Q3, and 9. Indicates that the same data as the corresponding data exists.
Set the FDBL flag (step 118).
Thereafter, it is processed as "not applicable" (step 119).

Next, using FIG. 3, the actual data storage state and comparison state will be explained in terms of the flow of time. Third
The figure shows the flow of data when arbitrary numerical information is sorted in descending order from 50 to 125, and Q1, 7, Q2,
8, Q3, and 9, and the record address storage state. In the figure, time is T
0 to T1, T2, ...Tn, the data to be searched is read output from an external storage device such as a disk device, and records N0, R0, R0, etc. are used to distinguish each data.
There are R1,...Rn. The limit values, lower limit and upper limit for sorting are stored in Q1 and Q7, and the comparator 7 shown in FIG. 1 checks whether the data to be searched is included in the desired values. That is, step 105 of the flowchart, and at T0 50<123<
125, therefore R0=123 is determined to be “applicable” and Q
It is stored in work areas W 2 and 8. Q at T1
1, 50<99<125, and similarly, R1=99 is determined to be "applicable", and 99<123 holds true for Q2 and 8, so R1=99 becomes the first priority data and R0
=123 becomes second priority data. Further, each corresponding record address is shown in the storage state of record addresses in FIG. 3, with the upper one representing the first priority and the lower one representing the second priority. In T2, 50 < 105 < 125 in Q1, so it is "applicable", but in Q2 and Q3, 99
Since <105<123 holds, R0=123, which has been the second priority, is deleted. The record address also stores 1 and R2. In T3, the conditions of Q1 are the same as T2, but in Q2 and Q3, 99=99<105
R2=105 is deleted, and since the first and second priority data are equal, FSDB is set. T4
Then, the condition of Q1 is satisfied, but the condition of Q2 and Q3 is 99=99<102, and the data of R4 has a low priority, so it is determined as "not applicable". In T5, Q1 is "Applicable", in Q2, 91 < 99 = 99
Since this holds true, it becomes the first priority data and R3=99
will be deleted. Since R3 = 99 and R1 = 99 are equal, as mentioned above, FSDB = 1 and first priority data exists, so FDBL is set and it is possible to know whether or not equivalent data exists other than the data stored in the register. can. In T6, the condition of Q1 is satisfied, but in Q2 and Q3, 91<R6≦99 does not hold because R6=100, so it becomes "not applicable". Q1 at T7
conditions are satisfied, R7(85)<91< for Q2 and Q3
Since 99 holds, it becomes the first priority data and R
7=85 is the first priority, R5=91 is the second priority, and R1=99 is deleted. Therefore, since (99) is no longer present in Q2 and Q3, FDBL is reset.

The record address is stored in the record memory ADM for each record, but if it is determined that there is a match, matching information is added to the beginning of the record address.
Stored in ADM. ADM has an n-stage stack structure, and ACT checks the data in ADM at any time (any time until the end of reading this record). Search data) can be extracted and the address of that record can also be found.
By physically bringing the sizes of Q2 and Q3 closer to the size of the external storage device, more data can be extracted at one time. In other words, information stored randomly in a disk device, etc. (representing random order when numerically representing a magnitude relationship) is stored on one of the disks.
By searching twice, it is possible to sort the items in ascending or ascending order. The structure of this record address is shown in FIG. Further, FIG. 5 shows the relationship between each register and the data to be searched. I1, I2,...15
represents an item within each record (RN, RN+1...). Each item is a unit of information that can be used as a key symmetry at the time of a search, and it is possible to perform a logical product search of each item such as I1, I2, and I3, and a starting logical OR search of I1+I2+I3. In such a search, multiple comparison search data are compared against the same searched data in a time-sharing manner depending on the size of Q2 and Q3, thereby realizing high-speed search processing with an extremely simple configuration. .

Effects As described above, by using the address storage control method of the present invention, it is possible to search for multiple pieces of information within a single processing time, and also to realize an information search that enables high-speed processing. are sequentially processed one by one, and when the processing has completed one cycle for all target data, it becomes possible to rank and search a plurality of pieces of data in order of priority.

[Brief explanation of drawings]

FIG. 1 is a block diagram of this embodiment, FIG. 2 is an operation flowchart, FIG. 3 is a diagram showing the flow of data when performing sorting in ascending order, FIG. 4 is a diagram showing the structure of record addresses, and FIG. The figure is a diagram showing the correspondence between searched data and each register. In the figure, 1...external storage device, 2...interface A, 3...interface B, 4...
Control unit, 6...Memory JM, 7...Memory Q1,
8...Memory Q2, 9...Q3, 10...Comparator
CM1, 11... Comparator CM2, 12... Comparator
CM3, 13...Length counter, 14...Search logic circuit control unit, 15...Record address counter, 16...Memory ADM, 17...Memory
STM, 18... bus interface.

Claims (1)

[Scope of Claims] 1. An information retrieval device using an external storage device, comprising: data storage means for storing one piece of search target data read from the external storage device and a plurality of predetermined pieces of search data; a comparison means for comparing search data with the plurality of search data; a comparison condition storage means for providing a comparison condition to the comparison means; and a plurality of addresses of the corresponding data according to the comparison by the comparison means. and an address storage means for storing, if the searched data is found to be applicable as a result of the comparison by the comparison means, the address of the data is stored in the address storage means, and the data stored in the data storage means is subsequently stored. An address storage control method characterized in that when the number of items searched exceeds the predetermined number, the lowest search data in the priority order is excluded from the search data.