JP2002312364A - Character string retrieval method and character string retrieval device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a character string retrieval method and a device therefor capable of reducing a processing time of character string retrieval. SOLUTION: This character string retrieval device 10 holds a longer data length of a collating character string and a collated character string in a register 102, holds shorter data in a register 104 such that the shorter data can be shifted, holds data on a first character of the character string held by the register 104 by the character string held by the register 102 once in a register 106, and holds a calculation result of the exclusive OR of the data on the character strings held by the registers 102, 106. The device 10 shifts the character string of the register 104 by the calculation result and holds the calculation result of the exclusive OR of the data held by the registers 102, 104 in a register 108. A decision circuit 116 decides propriety of a retrieval output or propriety of a further shift on the basis of the calculation result of the register 108 and a shift position of the character string of the register 104, and supplies the decision result to a data control circuit 100 or a shift control circuit 114.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a character string search method and a character string search apparatus, and more particularly, to a character string search method suitable for use, for example, when there are a large number of data to be matched and data to be matched. And a character string search device.

[0002]

2. Description of the Related Art A character string search is utilized in various scenes such as a search engine on the Internet or the like, a depositor inquiry at a bank, and a seat reservation. In addition, the target data was enormous. At that time, for example, techniques such as the sequential search shown in FIG. 11 and the binary search shown in FIG. 12 have been used.

The sequential search shown in FIG. 11 is a method of sequentially searching from the end element of an array, and is used when there is no regularity of data. The binary search shown in FIG. 12 is used when the data is arranged in ascending or descending order according to a specific item (key), and compares the condition with the key of the data located substantially at the center. , The search range can be divided into two, and the second search, the third search,... Narrow the search range and search for desired data.

[0004]

However, in the above-mentioned prior art, since the basic character string collation used for the comparison of each element is performed for each character, it takes time, and it is still time consuming. There was a problem that an inefficient part was left. For example, assuming that the length of a character string to be collated is n, the length of a character string to be collated is m, and the number thereof is s, the sequential search requires a processing time of at most n × m × s. In the binary search, the number t is (t <s /
2) and processing is performed while halving the search, and by devising the key conditions, the average is n × m × t, and the number of collation for each character string can be reduced. That is, in the related art, the overall processing time is reduced by software processing of a search method based on search conditions or the like. However, in each case, n × m processing time is required for each character string, and if the desired character string does not exist on the searched side, n × m × s processing time is eventually required. I was Further, when there are a large number of character strings to be searched, it takes more processing time.

[0005] The present invention solves the above-mentioned problems of the prior art, and can perform the collation for each character string at high speed and efficiently. It is an object of the present invention to provide a character string search method and a character string search device that can reduce the processing time even in a certain case.

[0006]

According to the present invention, there is provided a character string search method for searching for a desired character string from a data file in which a plurality of predetermined character strings are stored. In the method, of a character string from a data file or a character string to be matched with the data file, data of a character string having a long data length is stored in a first register, and data of a short character string is stored in a second register. Process and
A second step of storing data representing the first character of the character string held in the second register in the third register by the data length of the character string held in the first register in the first register; A third step of calculating an exclusive OR of the data held in the third register and the data held in the third register, and holding the result in the third register; A fourth step of shifting the data of the character string held in the second register to the position of the character at which the value held in the register becomes zero, and a second step shifted by the fourth step.
A fifth step of calculating an exclusive OR of the data of the first register and the data of the first register and storing the result in the fourth register, and storing the result in the fourth register by the fifth step A sixth step of determining whether or not the value is zero for the character string in the second register, and the fourth to sixth steps are repeated when the determination result of the sixth step is negative. A seventh step of outputting the character string when the result of the determination in the sixth step is positive;
And repeating the above step for each character string in the data file to search for a desired character string.

Further, a character string search method according to the present invention
A plurality of character strings to be collated are stored in advance as a second data file, and the first to seventh steps are repeated for each of the character strings in the second data file. It is characterized by searching for a character string.

On the other hand, a character string search apparatus according to the present invention is a character string search apparatus for searching for a desired character string from a data file in which a plurality of predetermined character strings are stored. A first register for holding one data of a character string to be collated, and a second register for holding the other data of a character string from a data file or a character string to be collated therewith,
A second register for storing the held data in a freely shiftable manner, and the data of the first character of the character string held in the second register are stored for the number of characters held in the first register; A third register in which the result of the exclusive OR of the character string and the data of the character string in the first register is held; a character string held in the first register and a character held in the second register A fourth register in which the result of the exclusive OR of the respective data of the columns is held, and an exclusive logical sum of the data of the character string of the first register and the character string of the third register for each corresponding character. And a first operation means for supplying the result to a third register;
The exclusive OR of the data of the character string of the register and the data of the character string of the second register is calculated for each corresponding character,
Second operation means for supplying the result to the fourth register, data control means for setting respective data in the first to third registers, and data of the character string held in the second register to the fourth register. Shift control means for shifting based on the result of the exclusive OR held in the third register, the shift position of the data in the second register by the shift control means, and the exclusive OR of the fourth register at that time. Determining means for determining the output of the search result based on the operation result of the data file, wherein the data control means compares the length of the character string data to be matched with the character string from the data file to determine the long character string data. The first register is set, the short character string data is set in the second register, and the first character data of the character string set in the second register is stored in the first register for the number of characters set in the first register. And sets the register.

In this case, the shift control means sequentially shifts the data of the character string in the second register to a position where the result of the exclusive OR held in the third register becomes zero. It is determined whether or not the result of the exclusive OR held in the fourth register at each shifted position has become zero for the number of characters in the second register. If the determination result is positive, the data control means May be instructed to output the search result, and when the result of the determination is negative, the shift control means may be instructed to shift the data of the second register.

When the data in the second register is shifted, the shift control means rewrites the result of the exclusive OR of the third register at that position with "1", and the judgment means makes a decision on the third register. It is determined whether or not there is a zero. If there is a zero, the shift means is instructed to shift, and if there is no zero, the data control means is instructed to end the search for the data. In response to an instruction to output the search result or an instruction to end the search result, the next character string is set in each register, and the search may be further performed.

[0011]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, an embodiment of a character string search method and a character string search device according to the present invention will be described in detail with reference to the accompanying drawings. FIG. 1 shows an embodiment of a character string search apparatus to which a character string search method according to the present invention is applied. The character string search device 10 in the present embodiment searches for a similar character string between the data file P (12) and the data file T (14) in which a predetermined character string is stored in advance, and outputs the search result to an output file. O (16), for example, in this embodiment, a plurality of character strings representing the formal names of electronic components and the like are stored in advance in the data file P (12), and the data file T (14) File P
A description will be given of an example in which a plurality of character strings input externally when searching for a desired electronic component name from (12) are stored and applied to, for example, checking the inventory of electronic components.
In particular, the main feature of the present embodiment is that when matching each character string, registers 102 to 108 are prepared and the main part of the search processing is executed by hardware processing using these registers. . FIG. 1 shows only parts directly related to the present invention, and illustration and description of parts such as an input device not directly related to the present invention are omitted.

More specifically, as shown in FIG. 1, a character string search apparatus 10 according to this embodiment includes a data control circuit 100, registers 102 to 108, arithmetic circuits 110 and 112, a shift control circuit 114, Circuit 116.

The data control circuit 100 includes a data file P
(12) and a data setting circuit for setting the character string data 120, 140 read from the data file T (14) in the registers 102, 104, respectively.
, Respectively. In this embodiment, the character string from the data file P (12) and the data file T (1
4) has a comparison function of comparing the data length of the character string from (4), and sets the long character string data 100a in the register 102;
The short character string data 100b is set in the register 104. Further, in this embodiment, the data of the first character of the short character string set in the register 104 is detected, and the data 100c for the number of characters of the long character string set in the register 102 is stored in the register 106.
(Third register) setting function and determination circuit 11
Output instruction signal 11 supplied based on the judgment result from 6
An output function for outputting the search result 100d to the output file O (16) by 6a is included.

The register 102 is a data holding circuit for holding data 100a of a long character string among the character strings of the data file P (12) or the data file T (14) supplied through the data control circuit 100. In this embodiment, for example,
This register can hold character string data 100a of about 100 characters. Here, in the character string data from the data files P and T, each character is represented by, for example, a 16-bit code.
108 is a register capable of holding 1500 to 1600 bits of data.

The register 104 is a register for holding short character string data 100b among the character string data of the data file P or the data file T held in the register 102. In the present embodiment, the held data 100b Has been effectively applied. The register 104 is supplied with a shift control signal 114a from the shift control unit 114 for freely controlling the shift.

The register 106 is supplied with data 100c corresponding to the number of characters supplied from the data control circuit 100 to the register 104 to the first character of the character string supplied to the register 104, and temporarily retains the data 100c. Circuit
In the present embodiment, the result of calculating the held data 18 and the data 20 held in the register 102 by the arithmetic circuit 110
Reference numeral 22 denotes a third register that is held thereafter. In this embodiment, the data 22 from the arithmetic circuit 110 which is stored later is supplied to the shift control circuit 114 as data 24.

The register 108 is a register for holding a result 28 obtained by calculating the data 20 held in the register 102 and the data 26 held in the register 104 by the arithmetic circuit 112, and corresponds to a fourth register. In this embodiment, the register 108 supplies the result 28 as data 30 to the decision circuit 116.

The arithmetic circuit 110 is an arithmetic element that performs an exclusive OR operation on the character string data 20 held in the register 102 and the character string data 18 initially held in the register 106 for each character at a corresponding position. The result 22 corresponds to the first arithmetic circuit, and the result 22 is calculated as "0" for a matching character and "1" for a non-matching character, and is supplied to the register 106.

The arithmetic circuit 112 is an arithmetic element that performs an exclusive OR operation on the character string data 20 held in the register 102 and the character string data 26 held in the register 104 for each character at a corresponding position. Corresponding to the second arithmetic circuit, the result 28 is the same as the arithmetic circuit 110, and the matching character is "0".
Is supplied to the register 108 with the unmatched character being "1".

The shift control circuit 114 stores the data in the register 10 based on the operation result 22 of the operation circuit 110 held in the register 106.
4 is a control circuit for shifting the data 100b of the character string held in FIG.
The shift instruction signal 116b from the
A shift control signal for shifting the character string data held in the register 104 to the same position as the bit position representing 0 "
Generate and supply 114a. At that time, the shift control circuit 114
Is "0" at the position already matched in register 106
It also has a function of generating a control signal 114b for replacing each of these bits with “1” and supplying it to the register 106.

The judgment circuit 116 is a judgment circuit for judging whether or not to output a search result based on the data 30 output in response to the value of the data 28 held in the register 108. The determination circuit 116 of the present embodiment stores the register 10 shifted by the shift control signal 114a supplied from the shift control circuit 114.
When all bits of register 108 corresponding to the character string position in step 4 are "0", output instruction signal 116a is output to data control circuit.
Feed to 100 to indicate output.

Also, the judgment circuit 116 in this embodiment determines that the data held in the register 106 has "0",
If any of the bits corresponding to the above is 1, a shift instruction signal 116b is supplied to the shift control circuit 114, and the register
When there is no "0" in the data held in 106, this is an instruction circuit for issuing a data collation end instruction signal 116c to the data control circuit 100.

Next, the character string search method according to the present embodiment will be described with reference to FIGS. 2 to 10 together with the operation of the character string search device 10. First, as shown in FIG. The data of each character string to be collated is read from the data file P and the data file T (steps S10, S12). Next, the data length of the read character string is compared to determine which character string is longer (step S14). For example, if the string from data file P is longer than the string from data file T,
For example, as shown in FIG. 4, the character string data 100a of "ABCDEFG" is set in the register 102 (step S16).
).

Next, a short character string from the data file P, for example, the data 100b of the character string "BEF" as shown in FIG. 4 is set in the register 104 (step S18).
). Next, in step S20, the data control circuit 100 stores, in the register 106, the number of characters 100c representing the first character "B" of the character string set in the register 104 in the register 102, as shown in FIG. (Step S20).

When the first character "B" of the character string in the register 104 is set in the register 106, the arithmetic circuit 110
Then, the exclusive OR of the character data 100c corresponding to the character string data 100a held in the register 102 and the character string held in the register 106 is calculated, and the result is supplied to the register 106 (step S22). ). This allows
As shown in FIG. 6, "0" is held in the register 106 in correspondence with the position of the character "B" of the register 102 that matches the character "B" at the head of the register 104, and the position of the other characters is stored. "
1 "is held (step S24).

The held operation result 22 is output from the register 106 as output data 24 by the shift control circuit 114 and the decision circuit 11.
The determination circuit 116 determines whether the output data 24, that is, the register 106, contains "0" (step S26). In this case, since there is "0" in the data position corresponding to the second and fifth characters in the register 106, the determination circuit 116 notifies the shift control circuit 114 of the shift instruction signal 116b. In the judgment circuit 116, when "0" is not included in the register 106 (NO), the flow proceeds to step S36 in FIG.

Next, upon receiving the shift instruction signal 116b, the shift control circuit 114 converts the character string data 100b held in the register 104 to "0" corresponding to the second character of the register 106 as shown in FIG. Is shifted to the data position (step S2
8). At that time, the shift control circuit 114 supplies the control signal 114b to the register 106 to
At 104, the value of "0" at the position where the character string data 100b is shifted is rewritten to "1". After this, the connection shown in FIG.
Proceed to. When the character string in the register 106 is shifted, the arithmetic circuit 112 calculates the exclusive OR at the corresponding position between the data of the character string held in the register 102 and the data shifted and held in the register 106. Then, the result is supplied to the register 108 (step S30). As a result, the operation result 28 is held in the register 108 as shown in FIG.

Next, the operation proceeds to step S32, where the judgment circuit 116
Is the operation result 28 held in the register 108 and the register 104
Then, it is determined whether or not the character string held in the register 102 and the character string held in the register 104 match based on the shift position of the character string data 100b. In this case, as shown in FIG. 8, "1" is included in the position of the character string of the register 104 in the register 108, so that the determination circuit 116 makes a determination of no and returns to the step S26 in FIG. It is determined again whether or not "0" is present in the register 106. As a result, since "0" is at the position of the fifth character, the determination circuit 116 notifies the shift control circuit 114 of the shift instruction signal 116b again.
As a result, the shift control circuit 114 converts the character string data 100b of the register 104 into the shift control signal in step S28.
In accordance with 114a, as shown in FIG. 10, the character is shifted to the position of the fifth character.

Next, again in step S30, the arithmetic circuit 110 calculates the exclusive OR of the character string data 100a held in the register 102 and the shifted character string data 100b in the register 104. The result 28 is supplied to the register 108 and held as shown in FIG.

Next, in the same manner as described above, the decision circuit 116 receives the data value of the register 108 in step S32, and as a result, there is "0" for the number of characters corresponding to the position of the shifted character string in the register 106. It is determined whether or not. In this case, as shown in FIG. 10, since the data value corresponding to each character is "0", the determination circuit 116 outputs the search instruction signal to the data control circuit 100 so as to output the search output.
6a is notified (step S34). As a result, the data control circuit 100 outputs the data (character string) supplied to the register 102.
A partial match between 100a and the data (character string) 100b supplied to the register 104 is detected, and the result is output to an output file O (16).

Incidentally, if it is determined in step S32 that the corresponding data value of the register 108 contains "1" again, and further in step S26 it is determined that there is no "0" in the register 106, the determination circuit 116 sets the data control circuit 100 Is notified of a collation end instruction signal 116c indicating the end of collation of the character string. Accordingly, the data control circuit 100 proceeds to step S36 without outputting the search output.

Next, the data control circuit 100 proceeds to step S3
In step 6, it is determined whether or not the data file T has a character string to be searched.
The process returns to step S12 of FIG. 2 again, and the next character string to be searched is read from the data file T. Hereinafter, similarly to the above, Steps S14 to S20 are repeated,
The long character string data is set to register 102, the short character string data is set to register 104, and the first character data of the character string set to register 104 is set to register 106. Set for a minute. Next, the exclusive OR of the data in the register 102 and the data in the register 106 is calculated in step S22 as described above, and the result is stored in the register 106 in step S24 as described above. Further, steps S26 to S30 are repeated in the same manner as described above, and the data of the character string held in the register 104 is shifted so that the first character thereof matches the character held in the register 102, and the shifted character Columns and registers 10
The exclusive OR with the character string data held in 2 is calculated, and the result is held in the register 108.

Next, in step S32, it is determined whether the character string held in the register 102 matches the character string held in the register 104 based on the value of the register 108 and the position of the shifted character string in the same manner as described above. Is determined. If they do not match, the processing of steps S26 to S32 is repeated via the connector C until the "0" held in the register 106 is exhausted, and the shift of the register 104 and the shifted data and the register 102 are repeated. The operation of exclusive OR with the data held in is repeated. As a result, if it is determined in step S32 that the character strings match, a search output is obtained in step S34. Further, the process returns from the step S36 to the step S12 via the connector D, and the steps S12 to S36 are repeated for all the search character strings stored in the data file T.

Next, in step S36, the data file P is searched for all the search character strings in the data file T.
When matching with the first character string of
It is determined whether or not P has the next character string to be collated (step S38). If there is a character string to be collated, the process returns to step S10 via the connector E, and then returns to step S12.
Steps S36 to S36 are repeated in the same manner as described above, and the next matching character string of the data file P is searched by the character string from the data file T. Similarly,
The search for the character strings from the data file T is performed for all the character strings in the data file P, and a step S3
When there are no more character strings to be matched in the data file P in 8, all the search is terminated.

As described above, according to the character string search method and the character string search apparatus of the present embodiment, the registers 102 to 108 are prepared, and a substantial part of the search processing is executed by hardware processing. Thus, the search can be performed faster and more efficiently than in the case of performing the search processing. In particular, the first character data of the character string held in the register 104 is temporarily held in the register 106 for the number of characters held in the register 102, and the data and the character string data held in the register 102 are exclusively processed by the arithmetic circuit 110. The ORed value is stored in the register 106, the character string data held in the register 104 is shifted to a position where the data value becomes "0", and the data does not match with the character string data in the register 102. Therefore, compared with the case where the matching process is performed for each character, a useless matching process is omitted, and the process can be executed efficiently and at high speed by performing the matching several times. That is, the number of characters to be collated n
Even if the number of characters to be matched is m, the matching process can be executed several times at most and dozens of times without performing the n × m matching process.

At this time, high-speed operation can be performed by the exclusive OR of the operation circuits 110 and 112. The comparison result is held in the register 108, and the effective judgment is made based on the shift position of the register 106. be able to.

Further, as registers 102 to 108, 1500 to
Using a 1600-bit register, it is possible to process up to about 100 character strings at once.
One character (16
The processing time can be remarkably reduced as compared with the case where the processing is performed for each bit) or every two characters (32 bits).

In the above embodiment, the case where the present invention is applied to a search for a character string of an electronic component or the like has been described as an example. However, in the present invention, other character strings, such as a depositor inquiry at a bank, a seat reservation, etc. The search may be applied to a search or an Internet search engine.

[0039]

As described above, according to the character string search method and the character string search apparatus of the present invention, the first to fourth registers are prepared, and the substantial part of the search processing is performed by hardware processing. Since the search is executed, the search can be performed faster and more efficiently than in the case where the search processing is performed by software. In particular, the first register that matches the first character of the character string held in the second register is set by the third register.
Holds the result of the exclusive OR operation indicating the position of the character in the character string held in the register, shifts the character string in the second register to that position, and shifts the character string in the first register. Since exclusive OR is obtained with the character string in the second register to determine the match or non-match, the comparison can be performed more efficiently and at a higher speed than in the case where the comparison is performed for each character.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of a character string search device according to the present invention.

FIG. 2 is a flowchart for explaining a character string search method to which the character string search device in the embodiment of FIG. 1 is applied.

FIG. 3 is a flowchart illustrating a procedure following FIG. 2 for explaining a character string search method to which the character string search device of FIG. 1 is applied.

FIG. 4 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 5 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 6 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 7 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 8 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 9 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 10 is a diagram showing the contents of respective registers for explaining the operation of the character string search device in the embodiment of FIG. 1;

FIG. 11 is a diagram showing a conventional sequential search method by software processing.

FIG. 12 is a diagram showing a conventional binary search method using software processing.

[Explanation of symbols]

 10 Character string search device 102 to 108 Register 110, 112 Operation circuit (XOR circuit) 114 Data control circuit 116 Shift control circuit 118 Judgment circuit

Claims (5)

[Claims] 1. A character string search method for searching for a desired character string from a data file in which a plurality of predetermined character strings are stored, the method comprising: a character string from the data file or a character string to be collated with the character string A first step of holding data of a character string having a long data length in a first register and holding data of a short character string in a second register; and holding the data of the short string in the second register by the first step. A second step of storing data representing the first character of the converted character string in the third register by the data length of the character string stored in the first register; and a method of storing the data stored in the first register and the third register. A third step of calculating an exclusive OR with the data held in the third register, and holding the result in the third register; and a third step in which the value held in the third register by the third step becomes zero. Second cashier in position A fourth step of shifting the data string held in the data, the exclusive OR of the fourth of the second register is shifted by step data and the data of the first register by calculating,
A fifth step of holding the result in the fourth register; and a fifth step of determining whether the value held in the fourth register in the fifth step is zero for the character string in the second register. Step 6 and the fourth to sixth steps are repeated when the result of the determination in the sixth step is negative. When the result of the determination in the sixth step is positive, the character string And a seventh step of repeating the first to seventh steps for each character string in the data file to search for a desired character string. retrieval method. 2. The method according to claim 1, wherein the plurality of character strings to be collated are stored in advance as a second data file, and a first character string is stored for each character string in the second data file. A character string search method comprising repeating the seventh to seventh steps and further repeating the eighth step to search for respective character strings. 3. A character string search device for searching for a desired character string from a data file storing a plurality of predetermined character strings, the device comprising: a character string from the data file or a character string to be collated with the character string. A first register holding one of the data, and a second register holding the other data of a character string from the data file or a character string to be matched with the first data, A second register for storing the character string in a shiftable manner, and data of the first character of the character string held in the second register are stored for the number of characters held in the first register. A third register in which the result of the exclusive OR with the data of the character string in the first register is held, and a character string held in the first register and a character string held in the second register And a fourth register that holds the result of the exclusive OR of these data, and the exclusive logic of each character of the character string of the first register and the character string of the third register for each corresponding character. A first operation means for supplying the result to a third register; and an exclusive OR of the data of the character string of the first register and the data of the character string of the second register for each corresponding character. Second operation means for supplying the result to a fourth register; data control means for setting respective data in the first to third registers; and character string data held in the second register. , Based on the result of the exclusive OR held in the third register, and the shift position of the data in the second register and the exclusion of the fourth register at that time. Logical disjunction Determination means for determining the output of the search result based on the calculation result, wherein the data control means compares the length of the character string data to be matched with the character string from the data file, and the data of the long character string Is set in the first register, the short character string data is set in the second register, and the first character data of the character string set in the second register is stored in the first register for the number of characters set in the first register. 3. A character string search device, wherein the character string search device is set in a register of No. 3. 4. The apparatus according to claim 3, wherein the shift control means stores the character string data of the second register at a position where the result of the exclusive OR held in the third register becomes zero. Sequentially shifting, and the determination means determines whether or not the result of the exclusive OR held in the fourth register at each shifted position is zero by the number of characters in the second register. When the result is positive, the data control means is instructed to output a search result, and when the determination result is negative, the shift control means is instructed to shift the data of the second register. String search device. 5. The apparatus according to claim 4, wherein the shift control means sets the result of the exclusive OR of the third register at the position when the data of the second register is shifted to “1”. Rewriting, the determining means determines whether or not the third register has zero, and instructs the shift means to shift when there is zero, and instructs the data control means to shift the data when there is no zero. The data control means sets the next character string in each register in response to an instruction to output a search result or an instruction to end the search result from the determination means. Column search device.