JP5771971B2 - Information processing apparatus, information processing method, and computer program - Google Patents

Description

  The present invention relates to a technique suitable for efficiently storing a plurality of character strings in a data structure, adding a character string to the data structure, storing the character string, and retrieving the character string from the data structure.

  Conventionally, a method using a trie structure has been proposed as a data structure for quickly determining whether or not a designated character string exists in a set of a plurality of character strings.

  The trie structure expresses a common prefix in a plurality of character string sets as a state transition structure, thereby reducing duplicate storage areas and reducing unnecessary processing in search processing.

  A double array method is disclosed as a method for efficiently mounting this trie structure and performing a high-speed search (Non-Patent Document 1). In the double array method, the trie structure is efficiently stored in two integer type arrays (hereinafter referred to as the BASE array and the CHECK array), and the state transition on the trie structure is performed by an addition operation on the BASE array and a comparison operation on the CHECK array. A very fast search technique is disclosed. Furthermore, for the suffix part, state transitions that do not cause branching of state transitions are aggregated and stored in one character string type array (hereinafter referred to as TAIL array), so that the storage areas of the BASE array and the CHECK array representing the state transition are stored. To improve the search speed.

  Non-Patent Document 2 discloses a method for improving the double arrangement method and mounting a more compact double arrangement structure. Specifically, the TAIL sequence is further compressed by merging a common suffix that matches the rear end of the TAIL sequence.

  As described above, in the double array method, a portion where no branch occurs in the state transition on the tri structure is mounted as a TAIL array, thereby reducing the space area and improving the search speed.

  On the other hand, a concise tree method is disclosed as a mounting method that places importance on the space efficiency of the trie structure (Non-Patent Document 3). The concise tree method performs a breadth-first search on the trie structure and converts the trie structure into a bit string. By storing the bit string structure and the character set representing the state transition on the trie structure together, a very compact trie structure can be implemented.

However, the simple tree method always performs state transition using a function that counts the bit string structure from the top. Specifically, a rank ₁ function that returns the number of bits 1 from the head and a select ₀ function that returns the position of the nth 0 bit from the head are used. These state transition functions have a high calculation cost, and in particular, the select ₀ function has a very high calculation cost. Therefore, in general, the above-described bit string structure is implemented by using an index in which the number of bits is calculated in advance for each arbitrarily sized partition.

Junichi Aoe, "High-speed digital search algorithm using double array", IEICE Transactions, Vol.J71-D, No.4, pp.1592-1600, 1988 Satoshi Yada et al. “Efficiency of cache in double array”, FIT2006, pp.71-72, 2006 G. Jacobson, "Space-efficent static trees and graphs", In Proc. 30th FOCS, pp. 549-554, 1989

  The double array method is characterized by a very high-speed search method. However, the double array method has a data structure having the same or larger size than the size of the original character string set. In addition, the concise tree method has a very compact data structure with respect to the size of the original character string set, but the search method is not accelerated in the search for bit strings.

The present invention has been made to solve the above-described problem, and an object of the present invention is to provide a technique for improving the efficiency of processing for searching a character string registered as a data structure using a specified character string. And

In order to achieve the above-described object, an information processing apparatus according to the present invention includes a registration unit that registers a plurality of first keywords to be searched as data in a double array, and a double-array data registered by the registration unit. Creating means for creating data to be registered in a concise tree structure for performing breadth-first search, storage means for storing a concise tree structure comprising data created by the creating means, and the plurality of first Receiving means for receiving an input of a second keyword which is a search keyword for searching for the keyword, and whether the second keyword received by the receiving means is included in the plurality of first keywords. Search means for searching using the concise tree structure stored by the node, wherein the creation means comprises nodes constituting the double array trie structure. The data is generated by using the link to the TAIL array as the link to the TAIL array for the node of the concise tree structure, and the search means reads the first character of the second keyword accepted by the accepting means, and The root node of the tree structure is set as the first node, it is determined whether there is a child node indicating the read character in the child node of the first node, and it is determined that there is a child node indicating the read character In this case, the child node is set as the first node, the next character after the second keyword is read, and the child node indicating the read one character exists in the changed first node. If it is determined that there is no child node indicating the read character, the previous node is referred to by referring to the link from the child node to the TAIL array. It transitions to TAIL sequence by determining whether the rest of the string is registered in the TAIL sequence that comprises searching whether the second keyword is included in the plurality of first keywords Features.

In order to achieve the above object, an information processing method of the present invention is an information processing method performed by an information processing apparatus that performs data search processing, and the information processing apparatus includes a plurality of first information to be searched . A registration step of registering the keyword in the double array as data, and a creation step of creating data for registering in a simple tree structure for performing a breadth-first search using the double array data registered in the registration step; A storage step for storing a concise tree structure including data created by the creation step, a reception step for receiving input of a second keyword that is a search keyword for searching the plurality of first keywords, and the reception Whether the second keyword received in the step is included in the plurality of first keywords is the simple tree structure stored in the storage step. And a search step for searching, and the creation step creates data as a link to the TAIL array for the node constituting the tri-structure of the double array as a link to the TAIL array for the node of the concise tree structure The search step reads the first character of the second keyword accepted by the accepting means, sets the root node of the concise tree structure as the first node, and sets the child node of the first node as the child node. It is determined whether or not there is a child node indicating the read character. If it is determined that there is a child node indicating the read character, the child node is set as the first node, and the next keyword after the second keyword. The process of determining whether there is a child node indicating the read one character in the first node after the change is repeated to indicate the read character When it is determined that there is no node, the transition to the TAIL array is made by referring to the link from the child node to the TAIL array, and it is determined whether the remaining character string is registered in the TAIL array. , Searching whether the second keyword is included in the plurality of first keywords .

In order to achieve the above object, a computer program of the present invention is a computer program that can be read and executed by an information processing apparatus that performs data search processing, and the information processing apparatus is a plurality of first targets to be searched . Registering means for registering the keywords in the double array as data, creating means for creating data for registering in a concise tree structure for performing breadth-first search using the double array data registered by the registering means, Storage means for storing a concise tree structure having data created by the creating means, accepting means for accepting input of a second keyword which is a search keyword for retrieving the plurality of first keywords, and accepting the accepting Whether the second keyword received by the means is included in the plurality of first keywords is determined by the storage means. And a search means for searching using the stored simple tree structure, wherein the creating means sets a link to the TAIL array for the nodes constituting the double array trie structure for the nodes of the simple tree structure. Creating data as a link to the TAIL array, the search means reads the first character of the second keyword accepted by the acceptance means, sets the root node of the concise tree structure as the first node, It is determined whether there is a child node indicating the read character in the child node of the first node, and if it is determined that there is a child node indicating the read character, the child node is set as the first node. Setting, reading the next one character of the second keyword, and determining whether there is a child node indicating the read one character in the first node after the change. If it is determined that there is no child node indicating the read character, the transition to the TAIL array is made by referring to the link from the child node to the TAIL array, and the remaining character strings are stored in the TAIL array. It is a computer program for functioning as a search to determine whether the second keyword is included in the plurality of first keywords by determining whether the second keyword is registered .

  According to the present invention, it is possible to provide a system capable of executing a dictionary structure file in which a large set of character strings is compactly implemented to a size that can be realized on a single computer, and further, limited resources such as embedded devices can be provided. In an environment that has a dictionary, it is possible to implement a dictionary more compactly and search practically.

It is a figure which shows the structure of the character string registration search system in embodiment of this invention. It is a figure which shows the hardware constitutions of the various terminals in embodiment of this invention. It is a flowchart of the character string registration process in embodiment of this invention. It is a flowchart of the TAIL merge process in the embodiment of the present invention. It is a flowchart of the simple tree production | generation process in embodiment of this invention. It is a flowchart of the transition possible set addition process in the embodiment of the present invention. It is an example of the keyword set in the embodiment of the present invention. It is an example of the double arrangement | sequence structure using the merged TAIL arrangement | sequence in embodiment of this invention. It is an example of the simple tree structure using the merged TAIL arrangement | sequence in embodiment of this invention. It is a flowchart of the simple tree search process in the embodiment of the present invention.

  Hereinafter, an example of an embodiment of the present invention will be described with reference to the drawings.

  FIG. 1 is a diagram showing a configuration of a character string registration / retrieval apparatus according to an embodiment of the present invention.

  The character string registration / retrieval apparatus 100 includes a double array construction unit 102, a concise tree construction unit 103, a concise tree data 104, a search result display unit 105, and a concise tree search unit 106. The concise tree data 104 is stored in a storage device such as an external memory 211 described later.

  The double array construction unit 102 constructs a double array using the keyword set 101 as an input. The constructed double array is sent to the concise tree construction unit 103 to generate concise tree data 104. The simple tree search unit 106 searches the simple tree data 104 with the search keyword 107 as an input, and displays the search result on the search result display unit 105. The series of data registration processing and data search processing will be described later in detail.

  Next, the hardware configuration of the character string registration / retrieval apparatus 100 in FIG. 1 will be described with reference to FIG.

  In the figure, a CPU 201 comprehensively controls each device and controller described later connected to a system bus 204. In addition, the ROM 203 or the external memory 211 causes a BIOS (Basic Input / Output System) or an operating system program (hereinafter referred to as OS), which is a control program of the CPU 201, or the character string registration / retrieval apparatus 100 to execute various processes described later. Various programs and data necessary for this are stored. The RAM 202 functions as a main memory, work area, and the like for the CPU 201.

  The CPU 201 implements various processes to be described later by loading a program or the like necessary for executing the process into the RAM 202 and executing the program. An input controller (input C) 205 controls input from an input device 209 configured with a keyboard, a pointing device, and the like. A video controller (VC) 206 controls display on a display device such as the display device 210. The display device 210 is composed of, for example, a CRT display or a liquid crystal display.

  A memory controller (MC) 207 is a hard disk (HD), floppy disk (registered trademark FD) or PCMCIA card slot for storing boot programs, browser software, various applications, font data, user files, editing files, various data, and the like. Controls access to an external memory 211 such as a compact flash memory connected via an adapter.

  A communication I / F controller (communication I / FC) 208 is connected to and communicates with an external device via a network, and executes communication control processing in the network. For example, Internet communication using TCP / IP is possible.

  Note that the CPU 201 enables display on the display device 210 by executing outline font rasterization processing on a display information area in the RAM 202, for example. Further, the CPU 201 enables a user instruction with a mouse cursor (not shown) on the display device 210. The above is the description of the hardware configuration of the character string registration / retrieval device 100. However, the hardware configuration illustrated in FIG. 2 is not necessarily required as long as various processes described below can be performed. Needless to say.

  Next, the character string registration process in the character string registration / retrieval apparatus 100 will be described in detail with reference to FIGS.

  FIG. 3 is an overall flowchart of the character string registration process. In the character string registration process, the CPU 201 reads the keyword set 101, builds a double array structure, and then creates a concise tree data structure. This character string registration processing is processing performed according to control by a program for causing the CPU 201 to function as the double array construction unit 102 and the simple tree construction unit 103. Prior to the description of the character string registration process, an example of a keyword set handled in this process will be described with reference to FIG.

  FIG. 7 is an example of the keyword set 101. The keyword 701 has a numerical value “10” defined for the character string “Yamagata Prefecture”. Similarly, the keyword 702 has a numerical value “20” defined for the character string “Yamanashi Prefecture”, and the keyword 703 has a numerical value “30” defined for the character string “Osaka City, Osaka Prefecture”. The same applies to the keywords 704 to 706. The numerical value is, for example, an ID number, and the like, and is a numerical value having meaning on software using a keyword set (hereinafter referred to as an OUTPUT value).

  Returning to FIG. 3, in step S301, the CPU 201 reads the keyword set shown in FIG. 7 line by line. At this time, the line information is decomposed into a character string and an OUTPUT value according to a predetermined format, and added to the double array in step S302. The double array in this embodiment returns an OUTPUT value when a search process using a character string is successful.

  Subsequently, in step S303, the CPU 201 determines whether or not the registration process has been completed for all keyword sets. If it is determined that there is unprocessed information, the process proceeds to step S301. If it is determined that all keywords have been registered in the double array ("YES" in step S303), the process proceeds to step S304, and TAIL merge processing is performed.

  In the TAIL merge processing, an unused area in the TAIL sequence that is generated when the data structure of the TAIL sequence merged with the common suffix disclosed in Non-Patent Document 2 is added to the double array (step S302). A process of creating the data structure while reducing the number is shown. Details of this processing will be described with reference to FIG.

  Here, the details of the TAIL merging process in step S304 in FIG. 3 will be described with reference to FIG. FIG. 4 is a flowchart showing details of the TAIL merging process. In the TAIL merging process, in order to collect unused areas in the TAIL sequence, a search is made for those in which a link from the BASE sequence to the TAIL sequence is defined.

  In step S401, the CPU 201 initializes a list for registering the link, and starts searching for a BASE array from the subsequent step S402. Specifically, a negative value of the BASE array represents a link to the TAIL array, and the absolute value is a subscript of the TAIL array. Therefore, for a valid BASE array having a negative value, a TAIL character string registered in the linked TAIL array is acquired (step S403), and the inverted TAIL character obtained by inverting the acquired TAIL character string A subscript of the BASE array as a column and a link source is added as a set to the list (step S404).

  After all the TAIL character strings have been added, in the subsequent step S405, the list is sorted in reverse order using the inverted TAIL character string as a key. That is, the inverted TAIL character string can be acquired in reverse dictionary order by tracing the list in order.

  In the subsequent step S406, the CPU 201 secures an area for storing a new TAIL array (hereinafter referred to as a merged TAIL array), and acquires the first element from the list in step S407. In subsequent step S408, the original non-inverted original TAIL character string is registered in the merged TAIL array secured in step S406. The original positive TAIL character string can be obtained by inverting the inverted TAIL character string, or may be set in another element and added to the list in step S404. In the subsequent step S409, the BASE array is updated. By referring to the subscript of the BASE array added as a set with the inverted TAIL character string, the value of the BASE array is updated to the negative number of the subscript to the merged TAIL array, and the link from the BASE array to the merged TAIL array is updated. .

  A specific example will be described. When BASE [26] = − 12, it is assumed that the normal TAIL character string “ABC” can be acquired from TAIL [12]. At this time, the set to be registered in the list in step S404 is (26, “CBA”). Also, if the destination registered in the merged TAIL array is TAIL [1], it is updated to BASE [26] = − 1 in step S409.

  Thereafter, in step S410, the CPU 201 determines whether or not all BASE arrays have been searched. If it is determined that all searches have been completed (in the case of “YES” in step S410), the TAIL merging process ends. If it is determined that the search has not ended (in the case of “NO” in step S410), the process proceeds to step S411.

  In step S411, the CPU 201 acquires the next element set from the list, and in subsequent step S412, compares the inverted TAIL character string of the acquired set with the inverted TAIL character string of the set acquired in step S407. At this time, if it is determined that the inverted TAIL character string acquired in step S411 is included in the inverted TAIL character string acquired in step S407 (if it is a common prefix, that is, “YES” in step S412) ), The process returns to step S409, and only the BASE array is updated. If “NO” in the step S 412, the process returns to the step S 408 to register the original TAL character string in the merged TAIL array, and the BASE array is updated in the subsequent step S 409.

  This will be described with reference to the above specific example. If it is the inverted TAIL character string “CBA” of the first element and the set of the next element is (7, “CB”), it is determined in step S412 that it is a common prefix (in the case of “YES”) , BASE [7] = − 2. That is, TAIL [1] can obtain a positive TAIL character string “ABC”, and TAIL [2] can obtain a positive TAIL character string “BC”. If the next element set is (7, “DA”), “NO” in step S412, TAIL [5] = AD is registered (step S408), and BASE [7] = − 5. (Step S409).

  In this way, the data structure disclosed in Non-Patent Document 2 can be obtained by performing the BASE array update process and the merged TAIL array registration process for all element sets added to the list. . The above is the detailed description of the TAIL merge process.

  FIG. 8 shows an example of a double array structure using the merged TAIL array with the keyword set 700 shown in FIG. 7 as an input. The double array structure includes a BASE array section 801, a CHECK array section 802, a merged TAIL array section 803, and an OUTPUT section (index section 804 and value section 805). The conversion table 806 is obtained by replacing characters with numerical values with respect to character strings registered in the double array structure. Normally, character codes are used, but in the present invention, they are defined for the sake of convenience in order to simplify the following description.

The OUTPUT index unit 804 defines 1 for those in which a link to the merged TAIL array unit 803 is defined in the BASE array unit 801, and the others are represented by a bit string of 0. That is, in order to obtain the OUTPUT value may be used rank ₁ function at OUTPUT index portion 804. For example, since BASE [4] = − 1, BASE [4] means a link to TAIL [1]. At this time, in the OUTPUT index unit 804, rank ₁ (4) is obtained with the subscript 4 of the BASE array as an argument, which is 2. Therefore, OUTPUT [2] is referenced to obtain the OUTPUT value “20” (FIG. 7). The search result of the keyword 702 in FIG.

  Returning to the description of FIG. When the TAIL merging process (step S304) ends, the CPU 201 advances the process to step S305, and performs a concise tree generation process with the double array structure using the merged TAIL array as an input. Details of this processing will be described with reference to FIG.

  Here, with reference to FIG. 5, the details of the concise tree generation process in step S305 of FIG. 3 will be described. FIG. 5 is a flowchart showing details of the concise tree generation process. In the succinct tree generation process, a succinct tree is generated by tracing a double array structure using a breadth-first search method.

  First, in step S501, the CPU 201 adds the first bit string “10” in the simple tree structure. In step S502, the status queue is initialized. The state queue is used to implement a breadth-first search in a double array structure.

  In step S503, the state s is initialized to 1, and a transitionable set addition process is performed in step S504. In the transitionable set addition process, a process for searching for a transitionable character from the state s and adding it to the state queue is performed. Details of this transitionable set addition processing will be described with reference to FIG.

  Here, with reference to FIG. 6, the details of the transitionable set addition processing in step S504 (and step S511) in FIG. 5 will be described. FIG. 6 is a flowchart showing details of the transitionable set addition processing.

  First, in step S601, the CPU 201 initializes a list for holding transitionable characters. In subsequent steps S602 to S603, all characters that can be changed from the state s are searched. As described above, since it is disclosed that the value of the CHECK array indicates the state number of the transition source in the double array structure, the value of the CHECK array becomes a BASE array index within the valid character set. Just search.

  Specifically, for example, when a valid character set is 26 alphabets and A is defined as 1, B is defined as 2 ... Z is defined as 26, and BASE [1] = 2, BASE [1] In the range from +1 to BASE [1] +26, that is, in the range from CHECK [3] to CHECK [28], a character satisfying s where CHECK [s] = 1 is searched.

  Thereafter, in step S604, the CPU 201 adds a character Ci satisfying the condition to the list.

  In subsequent processing in step S605, all the characters Ci added to the list are added to the state queue initialized in step S502 of FIG.

  Here, if BASE [s] is a positive value (“YES” in step S606), this means a transition state having a branch in the double array structure, so the process proceeds to step S607, and the state number of the transition destination The state (BASE [s] + Ci, Ci) is added to the state queue. If BASE [s] is not a positive value (in the case of “NO” in step S606), since BASE [s] indicates a link to the TAIL array or a termination state described later, the process proceeds to step S608 and the state (BASE [S], Ci) is added to the state queue.

  Through the above-described transitionable set addition process, all characters that can be transitioned from the state s are added to the state queue together with the state number of the transition destination. In the subsequent step S609, a terminal state (0, 0) indicating that the transition search from the state s is completed is added to the state queue. The above is the detailed description of the transitionable set addition process.

  Returning to the description of FIG. After completion of the transitionable set addition process in step S504, the CPU 201 determines in step S505 whether the state queue is empty. If it is determined that it is not empty (“NO” in step S505), the process proceeds to step S506, and one state (s, c) is acquired from the state queue.

  If the CPU 201 determines that the state s is a positive value in the determination process in the subsequent step S507 (if “YES” in the step S507), the process proceeds to a step S508. Here, when BASE [s] is a positive number (in the case of “NO” in step S508), the state s acquired in step S506 is a transition state having a branch, so the process proceeds to step S511, and the transitionable set described above The addition process is recursively performed, and the process proceeds to step S512. By using the state queue in this way, a breadth-first search is realized in a double array structure.

If the CPU 201 determines “YES” in step S508, that is, if BASE [s] is a negative number, the state indicates a link to the merged TAIL array, so the process proceeds to step S509 to newly merge the merged TAIL array. Create a link to In the simple tree structure, it is necessary to set a link to the merged TAIL array for the bit number corresponding to the state s. Therefore, as in the OUTPUT index unit 804 and the OUTPUT value unit 805 in FIG. 8 described above, the link to the merged TAIL array is set so as to have the structure of the index unit and the link unit using the rank ₁ function. Details of the link structure will be described later.

  After the process of step S509 is completed, the process proceeds to step S510, and there is no transition that can branch from the state s (there is only a state transition without branching to the merged TAIL array). And proceeds to step S512.

  If it is determined as “NO” in the determination process in step S507, that is, if the state s is not a positive value, the process proceeds to step S512.

  In step S512, the character c acquired in step S506 is registered as an edge character in the concise tree. If the character c is not 0, 1 is added to the bit string of the concise tree, and the character c is added to the edge character string. If the character c is 0 (terminal state), 0 is added to the bit string of the concise tree.

  When the registration process of the character c in step S512 is completed, the process proceeds to step S505, and the above-described process is repeated until the state queue becomes empty.

If the status queue is empty (in the case of “YES” in step S505), the process proceeds to step S513, and index generation processing is performed. The index generation process is a process of generating an index in which the number of bits is calculated in advance for each arbitrarily sized partition in order to reduce the calculation cost of the rank ₁ function and the select ₀ function in the bit string.

  Through the above processing, a breadth-first search is performed in the double array structure, and conversion to a simple tree structure is realized.

  FIG. 9 shows a simple tree structure generated from the double array structure shown in FIG. 8 as an example. The concise tree structure includes a bit array 901 and an edge character string 902 representing a trie structure, a TAIL bit array 903 and a TAIL link array 904 indicating a link to the merged TAIL array, an OUTPUT array 905 holding an OUTPUT value, and a merged TAIL array 906. Consists of The merged TAIL sequence 906 is equivalent to the merged TAIL sequence 803 in FIG. Further, the characters held in the edge character string 902 and the merged TAIL array 906 are replaced with numerical values using the conversion table 806 in FIG.

The bit array 901 and the TAIL bit array 903 are represented by bit strings. Therefore, as described above, index information for reducing the calculation cost of the rank ₁ function and the select ₀ function is given to these data.

  FIG. 10 shows a flowchart of the search method for the simple tree structure in the previous period. The search method will be specifically described with reference to FIG.

  First, the CPU 201 acquires the character c from the search keyword in step S1001. If the character c is obtained (“YES” in step S1002), the process proceeds to step S1003 to search for the first child node in the concise tree structure. The search for the first child node is disclosed in Non-Patent Document 3 as the following function.

first-child (n) = select ₀ (rank ₁ (n)) + 1

This will be specifically described with reference to FIG. The search start position is the first bit array 901 and rank ₁ (1) = 1. Therefore, since select ₀ (1) = 2 and first-child (1) = 3, it is known that the first child node number is 3. Here, when the third bit arrangement 901 is seen, it is 1 and it can be seen that there is a child node. If 0 or out of the area, there are no child nodes.

  In a succeeding step S1004, it is confirmed whether or not a child node exists. If there is a child node (“YES” in step S1004), the process proceeds to step S1005. In step S1005, an edge character corresponding to the child node is acquired. The edge character is registered in the edge character string 902 in FIG. 9, and the calculation formula is as follows.

e = edge [rank ₁ (n) -1]

This will be described with reference to the example of FIG. Since the third edge character of the bit array 901 is rank ₁ (3) = 2, edge [1] = 1 is selected. It can be seen that the character code “1” is the character “mountain” in the conversion table 806 in FIG. Therefore, the third edge character of the bit array 901 is “mountain”.

  In step S1005 in FIG. 10, it is further determined whether the acquired edge character e matches the character c of the search keyword acquired in step S1001. If the CPU 201 determines that they match (in the case of “YES” in step S1005), since the state transition is established, the process returns to step S1001, acquires the next character in the search keyword, and the character is displayed on the concise tree structure. Check the state transition.

  If the CPU 201 determines in the determination processing in step S1005 that the acquired edge character e and the character c of the search keyword acquired in step S1001 do not match (in the case of “NO” in step S1005), the process proceeds to step S1006, and the sibling node Perform a search for. Since the simple tree structure is created using the breadth-first search, the search for sibling nodes is successful if the adjacent bit is 1 in the bit string. In the example of the bit array 901 in FIG. 9, since the bit of the child node number 4 adjacent to the child node number 3 is 1, it can be understood that the child node number 4 is a sibling node of the child node number 3.

  If it is determined in step S1007 that no sibling node exists (in the case of “NO” in step S1007), the state transition can no longer be established in the concise tree structure using the search keyword, and the concise tree search is determined as a search failure. The process ends.

  On the other hand, if the CPU 201 determines in step S1007 that a sibling node exists (“YES” in step S1007), the process returns to step S1005, and the edge character of the bit number and the character c acquired from the search keyword are returned. Perform a comparison of

  In this way, the search keyword is searched on the concise tree structure character by character, but when there is no child node (in the case of “NO” in step S1004), or all characters of the search keyword are searched. In the case ("NO" in step S1002), the process proceeds to step S1008.

In step S1008 and after, the state transition on the bit array 901 is completed, and a search using the merged TAIL array 906 having no transition branch is performed. In step S1008, a link to the merged TAIL array 906 is acquired. For example, when the search keyword is “Yamagata Prefecture”, the bit sequence 901 transitions from 1⇒3⇒6⇒13 and bit [13] = 0, so that the state transition up to bit number 6 is established. Here, when rank ₁ (6) is calculated with respect to the TAIL bit array 903, it is 1. Therefore, the link value tail_link [1] = 1 to the merged TAIL array 906 is obtained with reference to the TAIL link array 904.

  In a succeeding step S1009, it is determined whether or not the link value has been acquired. If it is determined that acquisition has failed (in the case of “NO” in step S1009), since there is no link to the merged TAIL array, the concise tree search process ends as a search failure. If it is determined that it has been acquired (in the case of “YES” in step S1009), the process proceeds to step S1010.

  In step S1010, it is checked whether or not the suffix part, which is an unsearched part of the search keyword, matches the character string stored in the merged TAIL array 906. If they do not match (in the case of “NO” in step S1010), the search keyword does not exist, so the concise tree search process is terminated as a search failure.

  In the above example, in the search keyword “Yamagata Prefecture”, up to “Yamagata” is confirmed on the bit array 901, and the remaining suffix “prefecture” is to be compared with the merged TAIL array 906. Since the link value obtained from the TAIL link array 904 is 1, character string comparison is performed starting from the first of the merged TAIL array 906. Since Tail [1] = 10, referring to the conversion table 806, it is “prefecture”, and the next Tail [2] = 0 ends. Therefore, it can be seen that the suffix “prefecture” of the search keyword matches the character string “prefecture” registered in the merged TAIL array 906.

  If “YES” is determined in the step S1010, that is, if the character string comparisons match, the process proceeds to a step S1011. In step S1011, the OUTPUT value is acquired from the OUTPUT array 905. The acquisition method is the same as that of the TAIL link array 904 and is acquired using the TAIL bit array 903.

  With the above processing, the search keyword search is successful, and the concise tree search processing can return an OUTPUT value.

  As described above, according to the present embodiment, the trie structure can be compactly implemented by constructing the simple tree structure via the double array structure. Further, in the search of a simple tree structure, state transition using a bit array having a high calculation cost is minimized, and the search speed is improved.

  Although the embodiments have been described in detail above, the present invention can take an embodiment as, for example, a system, an apparatus, a method, a program, or a storage medium, and specifically includes a plurality of devices. The present invention may be applied to a system that is configured, or may be applied to an apparatus that includes a single device.

  It should be noted that the configuration and contents of the various data described above are not limited to this, and it is needless to say that they are configured with various contents according to applications and purposes.

  Needless to say, the present invention can also be applied to a case where the present invention is achieved by supplying a program to a system or apparatus. In this case, by reading out a recording medium storing a program represented by software for achieving the present invention to the system or apparatus, the system or apparatus can enjoy the effects of the present invention.

  Furthermore, by downloading and reading a program represented by software for achieving the present invention from a server, database, etc. on a network using a communication program, the system or apparatus can enjoy the effects of the present invention. It becomes possible.

  In addition, all the structures which combined each embodiment mentioned above and its modification are also included in this invention.

DESCRIPTION OF SYMBOLS 100 Character string registration search apparatus 101 Keyword set 102 Double arrangement | sequence construction part 103 Simple tree construction part 104 Simple tree data 105 Search result display part 106 Simple tree search part 107 Search keyword 201 CPU
202 RAM
203 ROM
204 System Bus 205 Input Controller 206 Video Controller 207 Memory Controller 208 Communication I / F (Interface) Controller 209 Keyboard 210 Display Device 211 External Memory

Claims (6)

Registration means for registering a plurality of first keywords to be searched as data in a double array;
Creating means for creating data for registration in a concise tree structure for performing breadth-first search using double array data registered by the registration means;
Storage means for storing a concise tree structure comprising data created by the creating means;
Receiving means for receiving an input of a second keyword that is a search keyword for searching for the plurality of first keywords;
Search means for searching whether the second keyword received by the receiving means is included in the plurality of first keywords using the simple tree structure stored by the storage means;
With
The creation means creates data as a link to the TAIL array for the node constituting the tri-structure of the double array as a link to the TAIL array for the node of the concise tree structure,
The search means reads the first character of the second keyword received by the reception means, sets the root node of the concise tree structure as the first node, and reads the read into the child node of the first node Determine if there is a child node indicating a character,
When it is determined that there is a child node indicating the read character, the child node is set as the first node, the next character after the second keyword is read, and the changed first node is set. Repeating the process of determining whether or not there is a child node indicating the read one character;
If it is determined that there is no child node indicating the read character, the transition to the TAIL array is made by referring to the link from the child node to the TAIL array, and the remaining character strings are registered in the TAIL array. And determining whether the second keyword is included in the plurality of first keywords by determining whether the second keyword is included.   2. The information processing apparatus according to claim 1, wherein the creation unit registers data for a node that can transition from a node constituting the double array trie structure in the node of the simple tree structure.   3. The creation means, wherein a node that can transition from a predetermined node is a transition source node obtained from a value of a CHECK array that constitutes the double array for the transitionable node, as the predetermined node. The information processing apparatus described in 1.   The information according to any one of claims 1 to 3, wherein the creating means creates the TAIL array by merging suffix portions that are not common among the plurality of first keywords. Processing equipment. An information processing method performed by an information processing apparatus that performs data search processing,
The information processing apparatus includes:
A registration step of registering a plurality of first keywords to be searched as data in a double array;
A creation step of creating data for registering in a concise tree structure for performing a breadth-first search using double array data registered in the registration step;
A storage step of storing a concise tree structure comprising data created by the creation step;
An accepting step of receiving an input of a second keyword that is a search keyword for searching for the plurality of first keywords;
A search step for searching whether the second keyword received in the receiving step is included in the plurality of first keywords using the simple tree structure stored in the storage step;
Run
The creating step creates data as a link to a TAIL array for a node constituting the tri-structure of the double array as a link to the TAIL array for a node of the concise tree structure,
The search step reads the first character of the second keyword accepted in the acceptance step , sets the root node of the concise tree structure as the first node, and reads the child node of the first node Determine if there is a child node indicating a character,
When it is determined that there is a child node indicating the read character, the child node is set as the first node, the next character after the second keyword is read, and the changed first node is set. Repeating the process of determining whether or not there is a child node indicating the read one character;
If it is determined that there is no child node indicating the read character, the transition to the TAIL array is made by referring to the link from the child node to the TAIL array, and the remaining character strings are registered in the TAIL array. And determining whether or not the second keyword is included in the plurality of first keywords by determining whether the second keyword is included. A computer program that can be read and executed in an information processing apparatus that performs data search processing,
The information processing apparatus;
Registration means for registering a plurality of first keywords to be searched as data in a double array;
Creating means for creating data for registration in a concise tree structure for performing breadth-first search using double array data registered by the registration means;
Storage means for storing a concise tree structure comprising data created by the creating means;
Receiving means for receiving an input of a second keyword that is a search keyword for searching for the plurality of first keywords;
Search means for searching whether the second keyword received by the receiving means is included in the plurality of first keywords using the simple tree structure stored by the storage means;
To function,
The creation means creates data as a link to the TAIL array for the node constituting the tri-structure of the double array as a link to the TAIL array for the node of the concise tree structure,
The search means reads the first character of the second keyword received by the reception means, sets the root node of the concise tree structure as the first node, and reads the read into the child node of the first node Determine if there is a child node indicating a character,
When it is determined that there is a child node indicating the read character, the child node is set as the first node, the next character after the second keyword is read, and the changed first node is set. Repeating the process of determining whether or not there is a child node indicating the read one character;
If it is determined that there is no child node indicating the read character, the transition to the TAIL array is made by referring to the link from the child node to the TAIL array, and the remaining character strings are registered in the TAIL array. A computer program for functioning as a search to determine whether the second keyword is included in the plurality of first keywords by determining whether the second keyword is included.

Images