JPH04199364A - Retrieval method with fuzziness - Google Patents

Abstract

PURPOSE:To retrieve data or a data group to satisfy a condition at high speed by retrieving the data on a fuzzy condition that the data positioned at the vicinity of a retrieving key is searched at the time of the retrieval of the data. CONSTITUTION:The objective data to be retrieved is developed on the memory 2 of a computer, and is arranged in ascending order. Besides, the condition representing fuzziness to decide how much deviation from the retrieving key to be near when there is no data to coincide with the retrieving key is instructed from the outside. Then, a CPU 1 retrieves the data by a binary search method, and if there is the data to coincide with the retrieving key, it outputs this data. When there is no coincident data, it searches the data successively from the last data position retrieved by the binary search method toward the forward direction of the data on the combined condition of the retrieving key and the fuzzy condition until the condition comes not to be satisfied, and next, it searches the data toward a backward direction by the same method, and searches the data group to satisfy the condition, and outputs this data. Thus, the data positioned at the vicinity of the retrieving key can be searched at high speed from a table developed on the memory 2.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention is useful for searching for stores around any point on a map, and searching for component pin groups and through holes around any point on a printed circuit board. The present invention relates to a search method suitable for searching for a group of holes.

[Prior Art] A method of searching for data existing within a radius r around a search point in an n-dimensional space is disclosed in Japanese Patent Laid-Open No. 2-11.
2071r Information Search Method”.

Regarding the binary search method, the implementation method is discussed in detail in "Modern Data Structures and Programming Techniques" published by Ohmsha in 1987.

[Problems to be Solved by the Invention] The prior art described in the above-mentioned JP-A-2-112071R Information Retrieval Method describes the concept of a data retrieval method with ambiguity, but the specific implementation means thereof are not explained. has not been discussed.

In addition, in the binary search method that is the prior art described above, two ways of implementation are discussed: when the search condition is matched and when the search condition is not matched, but if there is no data that matches one condition, There was no discussion on how to search for data located near . For this reason,
To search for data that does not match at high speed,
First, it was necessary to use a binary search method to check whether search condition data existed, and if the data did not exist, reset the conditions and try again.

In this way, the conventional technology does not take into consideration the search for ambiguous data, such as where the search data is located in the searched data string when matching data does not exist, and this creates a burden on software development. It had become.

The present invention searches for data under ambiguous conditions such as searching for data located near a search key when searching for data,
The purpose is to quickly search for data or data groups that satisfy conditions.

[Means for solving the problem] In order to achieve the above purpose, a central processing unit (CPU) and
In a data search method using a computer system having an output means, an input means, and a memory, two data are searched according to specified search conditions from data arranged in ascending order or descending order registered on the memory of the computer. Search for data using the split search method, and if matching data exists, output this data, and if there is no matching data in the data string above, search for the specified width above and below the search condition. Enter (hereinafter referred to as close to the search conditions)
Search for a data group consisting of one or more data from the above data string, and if one or more data close to the search condition exists, output that data, and search for data using conditions that include ambiguity. That is.

[Operation] Expands the search target data onto the computer's memory and arranges it in ascending order. Further, when there is no match with the search key, a condition indicating the ambiguity of how close to the search key is determined is externally specified.

When these conditions are met, a binary search method is first performed using the specified search key. At this time, if there is any data that matches the search key, that data is output.

If there is no match, the last data position searched using the binary search method is the data position closest to the directed search key, so from this position the data can be searched using the search key and the ambiguity condition. A search is performed sequentially in the forward direction until the condition is no longer satisfied, and then searched backward in the same manner to find a data group that satisfies the condition and output that data.

[Example code] A first embodiment of the present invention will be described below with reference to FIG.

FIG. 1 is a diagram of a computer constituting the present invention.

The memory 2 stores a table to be searched and a program according to the present invention. The CPUI operates the program in this memory to execute the search method according to the present invention.

The CRT 3 is used to instruct the start of execution or to display execution results.

Figure 2 shows the areas necessary to carry out the present invention.
This is a conceptual diagram on the memory 2 and their mutual relationships.

Here, the table 21 to be searched, the area PA22 where the search key is set, the area PB23 where ambiguity of neighborhood is recorded, the area RF24 where the starting point of the search result range is stored, and the ending point are stored. Area RT2
5, a table pointer SP2 is prepared for recording the results of the conventional binary search method.

Here, n pieces of data to be searched are registered in ascending order in table T21, search key value k is in area PA22, and matching data does not exist in area PB23 as a result of the search. A value r is set in which the range is determined to be the neighborhood.

FIG. 3 shows a flowchart of an embodiment of the present invention using the data shown in FIG.

First, a search 41 is performed using a conventional binary search method.

Based on this result, area P A, 2 is selected in decision box 411.
It is determined whether data located near the search key in 2 exists.

At this time, the table pointer 5P26 which is the binary search result
If the value of data on table T21 indicated by is outside the range of values in area PB23 indicating ambiguity that includes search key k, the condition that it does not exist is satisfied.

In this case, in step 412, a parameter that means there is no nearby point is returned, and the process ends.

Next, if there is a nearby point, in a judgment process 42 it is compared with the value of the convergence point on table T21 to see if there is data that matches the search key. If it is not found in , perform a search that takes ambiguity into account.

At this time, the value of the pointer in the table pointer 5P26 for searching the table T21 is 2 if m is the position in the table 21 that has the value closest to the search key.
The value of the search pointer of the convergence point, which is the result of the minute search, indicates the position of m, which is the last search point.

Here, a search is performed to find the end position of the valid data range.

First, a process 421 is performed to set the value of m as a result of the binary search in area RT25, and in order to perform a rear range search,
In process 44, the value of area RT25 is updated and table 21
Comparison processing 45 is performed to focus on the data within and determine whether it is nearby data.

At this time, the value of area RT25 is j and T(i)>k,
If the relationship is +r, it is obvious that there is no valid data after i, and the end position of the data is i-1, so this is performed in process 46.

However, if the relationship 10r holds for T (i)≦,
It is possible that there is still valid data at the back, so it is necessary to search for further data at the back, but if the data you are looking at is the last data in table T21,
This is determined in process 451. The value of area RT25 is
In process 453, it is set as the effective number of table T21.

If the data of interest is not the last data in table T21, the backward search continues in loop 452.

This is repeated until the relationship T(i)>k+r is established.

When this relationship is established, the process advances to step 46, and the area RT25
Determine the value of At this time, since the data at this point is outside the range, the end position of the effective range is 1-1.

Next, a search is performed to find the starting position of the valid data range.

First, a process 471 is performed to set the value of m as a result of the binary search in the area RF24, and in a process 47, the value of the area RF24 is updated in order to perform a front range search. Then, focusing on the data in the table 21, a comparison 45 is performed to determine whether the data is nearby.

At this time, if the value of area RF24 is i, T (i) < k
If the relationship is -r, it is obvious that there is no valid data before i, and the end position of the data is i+1, so this is performed in process 47.

However, if the relationship +r holds true for T (i)≧, it is possible that there is still valid data ahead, so it is necessary to search for data further ahead. Therefore, it is determined in process 481 whether the data of interest is the first data of table T21, and if it is the first data, the value of area RF24 is set to 1 in process 483, and if it is not the first data, continues the forward search in loop 482.

This is repeated until the relationship T(i)<k-r is established.

When this relationship is established, the process proceeds to step 49 and the value of area RF24 is determined.

At this time, since the data at this point is outside the range, the starting position of the effective range is i+1.

If matching data exists in the table 21 using the binary search method, in process 43 area RF24=area RT
25=binary search result m and the process ends.

The explanation of the operation of the first embodiment is one or more.

In this example, the reason why the table is arranged in ascending order by search key is because it is an essential condition for performing a binary search, and because it requires fewer searches when searching for a range of data that has ambiguity. It's for a reason.

Also, by having the start and end values as external interfaces, if multiple consecutive data on the table are selected as a result of an ambiguous search, the start and end points can be returned. I can do it.

Also, if data that satisfies the conditions cannot be found, the value of the starting point is set to the value of the ending point in order to improve the efficiency of programming.

Use this value for the start and end points of the DO loop.

This is because the process is skipped even if no special judgment statement is included.

Furthermore, when data matching the search key is found, the value on the starting point side is set to the value on the ending point side for the same reason.

A second embodiment will be explained with reference to FIG.

The difference from Fig. 3 is that even when matching data is found using the binary search method, data existing in the vicinity of the matching data is searched for, and this is achieved by removing the judgment process 42 and process 43 in Fig. 3. can.

Even when data having the same value exists consecutively in the table 21, the position of this data group can be searched by executing the process shown in FIG.

When there is no valid data after execution of the process according to the present invention, area R, F 24 <area RT25.

FIG. 5 shows an embodiment in which the position of a through hole existing around an arbitrary point on a printed circuit board is searched.

In the figure, 61 is a printed circuit board area to be searched, 611 indicates an arbitrary point, and a shaded area 612 is the search range.

When determining the coordinates of the through holes included in this area 612, the coordinates of the through holes existing on the printed circuit board 61 are arranged in ascending order, and the -X coordinate 624 is taken as one item. Then, the X component table 63 is divided into an X component table 62 and an X component table 63 having a pointer 621 indicating the start position on the X component table 63 and a pointer 622 indicating the end position of the X component included in the X coordinate 624 in Lecote. Therefore,
When in the X component table 21, the -X coordinate appears only in one place.

Next, when an arbitrary point 611 and a value r625 representing the neighborhood are given, a search is performed in the X component table 62 using the method according to the present invention using this X coordinate as a search key. This makes it possible to obtain the X area 623 that needs to be searched.

Next, the X component in the X component area 623 is sequentially
With reference to the component table 63, the value of y indicated by the start pointer 621 and end pointer 622 is the neighborhood distance w1r 62
By searching for points existing within 5, the neighborhood r6 of point 611
It is possible to find the through hole that exists in 25.

[Effects of the Invention] According to the present invention, data located near a search key can be quickly searched out from a table developed in a memory.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a system according to a first embodiment of the present invention, FIG. 2 is an explanatory diagram of a table to be searched in a computer memory used in the present invention, and FIG. FIG. 4 is a flowchart of a second embodiment of the binary search method with width according to the present invention, and FIG. 5 is an explanatory diagram of an embodiment of the through-hole search according to the present invention. [Explanation of symbols] ]...CPU, 2...Memory, 3...CRT, 2] Table.

Claims (1)

[Scope of Claims] 1. A data retrieval method using a computer system having a central processing unit (CPU), an output means, an input means, and a memory, comprising: Search for data from the data arranged in descending order using the binary search method according to the specified search conditions, and if matching data exists, output this data, and if the data that matches the conditions is in the above data string If not,
Search for one or more data in the above data string that falls within the width specified above and below the search condition (hereinafter referred to as close to the search condition), and search for data using conditions that include ambiguity. Characteristic data search method. 2. In the data search method according to claim 1, data is searched using a binary search method according to specified search conditions, and even if there is data matching the search conditions, if there is data close to the search conditions, A data search method characterized by outputting that data as well. 3. In the data search method according to claim 1, when data having the same value exists consecutively in the memory and the value of this data is specified as a search key, the same data group in the memory and its A data search method characterized by searching for the position of a data group existing in the vicinity. 4. The data retrieval method according to claim 1, 2 or 3, wherein the data is position coordinates on a printed circuit board.