JPH08272814A - Character string retrieval device - Google Patents

Abstract

PURPOSE: To provide a character string retrieval device capable of shortening retrieval time and reducing the using memory amount of dictionary file. CONSTITUTION: A file (dictionary file) 70 for dictionary retrieval is constituted of a directory block 710, plural character string blocks 720 and a EOF block 730. The leading addresses of the respective character string blocks are stored in the directory block 710 and blocks are related to each other by the kinds of the heads of character strings and character numbers. The actual character strings are stored in the respective character string blocks 720. By the character number of an input character string and the kind of a leading character, the address of the character string block is obtained from the directory block 710, the character string group of the character string block 720 is read by the address and retrieval is reformed.

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 device,
More specifically, the present invention relates to a character string search device that is effective for searching character strings for books and papers and for searching for codes and product numbers.

[0002]

2. Description of the Related Art In a conventional character string search apparatus, a method is generally used in which a key is designated and a search that matches a key value is performed. FIG. 5 shows a configuration example of a dictionary file used in this type of character string search device. For example, searching for the character string "Komatsu" will result in the following. First, based on the input character string "Komatsu", search the corresponding key value (the number of characters is "3" and the first character is the "K" line) from the index section, and then search the data section based on the corresponding key value. Search for the presence of the character string "Komatsu".

[0003]

In the above-mentioned prior art, 2
Since it is necessary to perform a step-wise search (index part and data part), there is a problem in that if the number of searches increases, it takes a very long time and efficiency deteriorates. For example, when searching for whether or not the same name is already registered in the dictionary file, a two-step search is performed, so the search takes time. In addition, there is also a problem that the amount of used memory increases as the amount of data (character string) increases because the search cannot be performed unless the data portion also has a key value.

It is an object of the present invention to provide a character string search device which can reduce the search time and the amount of memory used for a dictionary file as compared with the prior art.

[0005]

The character string search device of the present invention, as a dictionary file, classifies the contents of the character string by the combination of the number of characters and the contents of the first character, and stores the character string in each block. A plurality of character string blocks and a directory block in which the addresses where the character string blocks exist are registered, and the address of the corresponding character string block is obtained from the directory block by the number of characters of the input character string and the first character, It is characterized in that a means for reading the character string of the corresponding character string block by the address and searching for a character string that matches or is similar to the input character string is provided.

[0006]

Function: The address where the corresponding character string block exists can be directly obtained from the directory block based on the number of characters of the input character string and the first character. The data (character string group) of the corresponding character string block is read at this address, and a search is made to see if there is a match or similar to the input character string. As a result, the search count is 1 for the character string group of the character string block.
Since the data can be read in block units, the number of accesses is small and the search time can be shortened. Further, the index part is managed as one block as a directory block, and the data part stores only a character string, so that the memory requires a minimum area.

[0007]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is an overall configuration diagram of an embodiment of a character string search device of the present invention. This system includes a display 10 that displays an input character string to be searched and a search result, a keyboard 20 that inputs a character string to be searched and a command, a printer 30 that outputs the search result, and an input file that stores the character string to be searched. 40, a dictionary input file 50 that stores a character string to be registered in the dictionary, an input search file 60 that stores a search character string created from the input file 40, and a search dictionary created from the dictionary input file 50. Auxiliary storage device 8 for storing the stored dictionary search file 70, the in-process file, the process result file, and the like.
0, and a CPU (central processing unit) 100 that performs processing such as creation, coding, search, and editing of expanded character strings. Here, the input file 40 and the dictionary input file 50 are sequential organization (SAM) files, which are magnetic tapes or magnetic disks. The input search file 60 and the dictionary search file 70 are direct access (DAM) files. A kanji printer is used as the printer 30, for example.

FIG. 2 is a flow chart showing the flow of the overall operation of the CPU 100. The input file 40 and the dictionary input file 50 are SAM files. A developed character string is created based on these files 40 and 50, and the character string is encoded (steps 110 and 210). The contents output are the expanded input file 120 and the expanded dictionary file 220, and these files are also SAM.
It is a file. Next, these expanded files 12
When the same character string exists in 0 and 220, these are combined into one and the input search file 60 and the dictionary search file 70 are created (steps 130 and 230). These files 60 and 70 are DAM files. The input search file 60 is searched for a character string by referring to the dictionary search file 70 (step 140).
This will be described in detail later. The input search result file 150 and the dictionary search result file 250 are output as search results, and the input search result file 150 contains all the information of the character strings extracted from the input file 40 and any character string in the dictionary input file 50. Information such as whether or not they are similar is stored. Further, the dictionary search result file 250 stores similar character strings. Based on these search result files 150 and 250, integrated editing is performed to create a search result list 170 (step 1
60). In this integrated editing process, the information other than the character string is the first input, namely the input file 40 and the dictionary input file 5.
Get information from 0. This is because when searching for a character string, the character string data alone is a huge amount of data, and therefore no extra data is stored in the file when searching. The created search result list 170 is output to the display 10 and the printer 30.

If the dictionary search file 70 has already been prepared and the character string to be searched is input from the keyboard 20, in step 140, the dictionary search file is directly input for this input character string. The search may be performed by referring to 70.

FIG. 3 shows an example of the structure of the dictionary search file 70. The dictionary search file 70 includes a directory block 710, a plurality of character string blocks 720, and an EOF block 730. Directory block 71
0 is for classifying the content of the character string (data) according to the combination of the number of characters and the content of the first character, dividing it into a plurality of blocks (character string block), and storing the address where the block exists. This directory block 710
Plays the role of index. In FIG. 3, the directory block 710 divides the first character of the character string into “A line”, “K” line, ... And stores the start address of each character string block for each number of characters. The actual character string is stored in each character string block 720, and the EOF block 730 represents the end of the file. In the embodiment of FIG. 3, the character string is shown in Japanese for easy understanding, but the character string is actually handled as a code.

Next, using the dictionary search file 70 of FIG. 3, how the character string search is actually performed is described.
The case where the input character string is "Komatsu" will be described as an example. The processing flow in this case is shown in FIG.

When the input character string is "Komatsu", first, the head address "0103" of the character string block of three rows and three characters is acquired from the directory block 810 (step 810). Next, the data (character string) is read from the character string block of the address "0103" (step 820), and the character string of the block is searched in order (step 830). Then, it is determined whether or not there is a character string that matches or is similar to the input character string "Komatsu" (step 840),
If there is, the search result is output (step 850), the search for the next character string is performed (step 860), and if there is not, step 850 is skipped. A flag indicating whether or not there is a continuation in the next block is attached to the end of each character string block, and it is determined whether or not to search the next block by looking at the flag.

[0014]

As described above, according to the character string retrieving apparatus of the present invention, the number of retrievals is only once for the data in the character string block of the dictionary file, and the data can be read in block units. Since it can be done, the number of accesses is small and the search time can be shortened. Further, since the index part is managed by one block of the directory block, and the data part stores only the character string in the character string block, the memory requires a minimum area. Therefore, the character string search device of the present invention is particularly suitable for a search target having a large number of searches and a large amount of data.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of an embodiment of a character string search device of the present invention.

FIG. 2 is a flowchart showing the flow of the overall operation of FIG.

FIG. 3 is a diagram showing a configuration example of a dictionary search file according to the present invention.

FIG. 4 is a flowchart showing a specific processing example of character string search according to the present invention.

FIG. 5 is a diagram illustrating a conventional character string search process.

[Explanation of symbols]

 10 Display 20 Keyboard 30 Printer 40 Input File 50 Dictionary Input File 60 Input Search File 70 Dictionary Search File 710 Directory Block 720 Character String Block 100 CPU

Claims (1)

[Claims] 1. A character string search device that searches a dictionary file for a character string that matches or is similar to an input character string, wherein the dictionary file is classified by the combination of the number of characters and the content of the first character, It is composed of a plurality of character string blocks storing the character string in each block unit and a directory block in which the address where the character string block exists is registered, and from the directory block depending on the number of characters of the input character string and the first character. A character string search device comprising means for acquiring an address of a corresponding character string block, reading a character string of the corresponding character string block at the address, and searching for a character string that matches or is similar to the input character string.