JP4020362B2 - Yes / No type question tree creation device, program and recording medium - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention creates a Yes / No type query tree so that data can be efficiently selected even in an interface with few input / output means when searching data from a large amount of database using search conditions registered in advance. The present invention relates to a Yes / No question tree creation device, a Yes / No question tree creation method, a program, and a recording medium.
[0002]
[Prior art]
At present, it is possible to connect to the Internet not only from a personal computer but also from any terminal such as a mobile phone, a fixed phone, a television, and a radio.
[0003]
The personal computer has a display (output means) with a high resolution, and has a keyboard and mouse (input means) capable of inputting a relatively large amount of information per unit time. Then, a stable operation posture of facing the office or home desk, sitting on a chair, and operating the input / output means is a premise of the personal computer operation.
[0004]
On the other hand, the interface with non-PC is an extension of home appliances that can be used easily, but has few input / output means. For example, since a mobile phone has a small and simple terminal, the display is small and the resolution is low. The input means are a numeric keypad and an arrow key, and the amount of information that can be input per unit time is relatively small compared to a personal computer. Also, the operation posture is quite unstable, such as holding a mobile phone with one hand while standing and operating with a thumb. The lack of the above input means is common to televisions, radios and landlines.
[0005]
In recent years, Internet access services using telephone voice calls are also emerging. There is no audio output listing, and information flows along the time axis. Furthermore, although voice input has a high degree of freedom, the recognition rate decreases when the utterance vocabulary is large. Furthermore, when the ambient noise is large, such as a mobile phone, or when the call quality is low, it is assumed that the recognition rate is guaranteed by reducing the number of utterance words. Further, since the voice interface is hands-free, it is assumed to be used in a car. In this case, the operating posture is driving and is further unstable.
[0006]
In other words, in the interface by a non-PC device, input / output means are greatly restricted. For this reason, in order to search for desired data from a large amount of database by a non-PC device, it is often difficult to input a search condition with a large amount of information such as a free keyword.
[0007]
Therefore, a search interface is required in which the apparatus searches the database according to a plurality of search conditions registered in advance and selects the search result well.
[0008]
In this regard, Miyamoto et al. Have proposed a narrowing-down method based on a prior narrowing-down menu in Japanese Patent Application No. 2000-040094 (Title of the invention: data retrieval support method and apparatus and storage case storing a data search support program). .
[0009]
In this conventional apparatus, based on a recommended refinement condition group prepared in advance by a search service provider, a refinement search based on a logical product of the recommended refinement conditions is performed on the search target set, and an acceptable degree of refinement is performed. Depending on the number of times, even on a mobile terminal with a small screen such as a mobile phone, search conditions that can be narrowed down to a list are extracted and displayed as a menu.
[0010]
If the allowable number of times of narrowing is set to a very small number of times, for example, two times, it is possible to select a narrowing screen recommended for a search service provider twice using this narrowing menu, even on a narrow screen of a mobile phone. , To ensure that the search results can be listed.
[0011]
[Problems to be solved by the invention]
However, since the above-described prior narrowed menu uses a menu for selecting an arbitrary menu item from a plurality of menu items (hereinafter, a multi-item type menu), the interface is the same as that of a general menu.
[0012]
Accordingly, when the output means is extremely low in listability like voice, the operation load for selecting and storing a plurality of menu items while listening to the voice is equivalent to that of the conventional menu.
[0013]
Therefore, the amount of information sequentially input by the user to select information is limited to the minimum 1 bit, and the most thimble selection means is provided. That is, by presenting a question tree in a Yes / No question format (hereinafter referred to as “Yes / No-type question tree”) to the user and sequentially responding with Yes / No, the search target is 1 bit at a time. An interface that narrows down is assumed. As a result, it is possible to provide an interface that allows easy input even with simple input means of a non-personal computer.
[0014]
Here, the search interface based on the above-mentioned question tree has a binary tree structure like the optimal question tree 9 shown in FIG.
[0015]
Each node corresponds to each search condition, and when the presented search condition is adopted, the process proceeds to the child node on the left side of the node, and the data that hits the search expression is the presentation target. Conversely, when the presented search condition is not adopted, the process proceeds to the child node on the right side of the node, and data that does not hit the search formula is the presentation target.
[0016]
In order to narrow down the search target efficiently, what kind of search condition is assigned to each node is an important point.
[0017]
However, there are many patterns as a question tree that can be created based on search conditions registered in advance, and there is a problem that the amount of calculation increases if all patterns are compared and evaluated in the dark clouds.
[0018]
The present invention creates a Yes / No type query tree so that data can be selected efficiently even in an interface with few input / output means when data is selected from a large number of databases using pre-registered search conditions. An object of the present invention is to provide a Yes / No question tree creation device, a Yes / No question tree creation method, a program, and a recording medium.
[0019]
Further, there is a problem that processing time inevitably increases when the number of data to be searched increases or when the number of search conditions to be considered increases.
[0020]
The present invention selectively evaluates search conditions that are highly likely to obtain an optimal query tree without recursively evaluating all search conditions, and reduces the processing time, while creating a created query tree. An object of the present invention is to provide a Yes / No question tree creation device, a Yes / No question tree creation method, a program, and a recording medium that can ensure accuracy.
[0021]
Furthermore, the present invention can automatically create a query tree that preferentially accesses data having a high degree of matching when the degree of matching of search conditions for each data is an order measure that can be compared with each other. Further, it is an object of the present invention to provide a Yes / No question tree creation device, a Yes / No question tree creation method, a program, and a recording medium, which can be processed at high speed.
[0022]
And this invention, after a user answers a Yes / No type | mold question tree, even when the list property of the terminal to browse is low when browsing a search data group, it is only Yes / No selection upper limit. If you answer No, you can narrow down to the number of search data groups that you can browse, and therefore you can reduce the possibility that a large number of search results will remain even if you narrow down the question repeatedly. It is an object of the present invention to provide a type question tree creation device, a Yes / No type question tree creation method, a program, and a recording medium.
[0023]
[Means for Solving the Problems]
  The present invention comprises a search condition registered in advance and a database of search data to be searched, and a Yes / No type question tree for narrowing down the search data by answering Yes / No for the search condition. In the Yes / No type question tree creation device to be created, a route node processing means for setting a node to be a route having the search data to be searched as a search data set and calling the node processing means, and a search data set are provided. And setting the evaluation value obtained by inputting the search data set to the predetermined function as the maximum evaluation value of the node, and if the current hierarchy number is equal to or greater than the Yes / No selection upper limit number, the maximum evaluation value is If it is returned to the caller and the current number of hierarchies is less than the Yes / No selection upper limit, the search data set corresponding to the node For each search condition as a target, the search data set that satisfies the search condition and the search data set that does not satisfy the search condition are divided, and each node of the two divided search data sets is generated, and the generated node The evaluation value of the node that is generated by recursively calling the node processing means that is itself is obtained, the evaluation value of the node of the search data set that satisfies the search condition, and the node of the search data set that does not satisfy the search condition A node processing unit that obtains a sum of the evaluation value of each of the search conditions, obtains a maximum evaluation value that maximizes the sum among the search conditions, and returns the maximum evaluation value to the caller. This is a No-type question tree creation device.
[0024]
BEST MODE FOR CARRYING OUT THE INVENTION
[First embodiment]
FIG. 1 is a diagram showing a Yes / No type question tree creating apparatus 100 according to the first embodiment of the present invention.
[0025]
The Yes / No question tree creation device 100 does not create all possible question tree configuration patterns, but creates search results in the search data group to be divided before creating a Yes / No question tree pattern. This is a device that excludes search conditions that do not exist, and thereby creates an optimal Yes / No question tree at high speed.
[0026]
The Yes / No type question tree creation device 100 includes a registered search condition list 1, a search target database 2, a split target list 3, a non-split target list 4, a split target list creating unit 5, and an optimum pattern table 6. The optimum pattern table creation unit 7 and the optimum question tree creation unit 8 are provided. When an “listable upper limit number” to be described later and a “Yes / No selection upper limit number” to be described later are input as inputs, an optimal Yes is obtained. / No type query tree 9 is output.
[0027]
The registered search condition list 1 is a list of search conditions registered in advance, and this pre-registered search condition is held for each user, but is a list of search conditions recommended by the search service provider. May be.
[0028]
The search target database 2 is a database that stores search data to be searched, and may be a relational database or a text file group for full text search. As long as the database returns the search result, another database may be used.
[0029]
FIG. 2 is a diagram showing the division target list 3, and is a diagram showing the relationship between the search data and the search condition group (fitness).
[0030]
The division target list 3 is a list created by the division target list creation unit 5 based on the search target database 2, and as shown in FIG. 2, the search data, the search condition group, and the matching of the search condition and the data It is composed of degrees.
[0031]
That is, the division target list 3 is search data included in a search result searched from the search target database 2 according to at least one search condition. When there are few search results for the search condition in the search target database 2, the compression efficiency is high.
[0032]
The non-division target list 4 is a list obtained by extracting from the search target database 1 search data that is not included in the search results of any of the search conditions registered in advance. The list creation unit 5 creates the non-dividing target list 4. This non-dividing target list 4 is not a list that exists for each search condition, but is a list that exists only for one database.
[0033]
FIG. 3 is a diagram illustrating an example of the degree of matching that is the degree to which the search condition matches each data.
[0034]
As illustrated in FIG. 3, the division target list creation unit 5 assigns a matching degree indicating a degree to which the search condition matches each data. This conformity is basically binary data indicating whether or not it is included in the search result of each search condition. Further, when the predetermined search data is included in the search result of the predetermined search condition, the degree to which the predetermined search data matches the predetermined search condition is expressed as an order scale using a TF / IDF value or the like. . This order scale is an integer value between 0 and 100. Other measures may be used instead of the order measure using the TF / IDF value or the like as long as the search data indicates the degree of matching with the search condition.
[0035]
Further, in this embodiment, search data having a fitness level greater than “0” is considered to be search data that matches, and therefore, from a table of search data versus search conditions to which the fitness level is assigned, from “0”. Only a combination of data having a higher matching degree and a search condition is extracted, and a division target list 3 composed of the data and a corresponding search condition group (fitness degree) is created as shown in FIG. .
[0036]
FIG. 4 is a diagram illustrating an example of the non-dividing target list 4.
[0037]
Of the search conditions registered in advance, data that is not included in the search results of any search condition is extracted as a list, and as shown in FIG.
[0038]
FIG. 5 is a diagram showing an example of the contents of the optimum pattern table 6.
[0039]
In FIG. 5, a plurality of rows having a node ID “2” are described. This is because when the parent node is “ABC”, “Terror”,..., The node ID “2” may be used to inquire about the content described in the item label. A plurality of rows having a node ID “2” are described. Therefore, in FIG. 5, a plurality of rows with the node ID “3” are also described.
[0040]
The optimum pattern table 6 is a table created by the optimum pattern table creation unit 7 based on the division target list 3, and as shown in FIG. 5, the node ID of the Yes / No question tree and the parent node search condition list And table-format data having the length of the division target list, the maximum evaluation value, the branch / leaf flag, and the item label.
[0041]
The “parent node search condition list” is a list expressing search conditions in the parent node of the node. This parent node search condition list is used so that the search condition existing in the path from the root (node ID = 1) to the parent node is not evaluated twice.
[0042]
The “length of the division target list” is the number of data included in the division target list that the node intends to divide. In other words, the length of the division target list is a set of “data, search conditions, goodness of fit” pairs remaining as presentation targets among Yes / No branches in the middle, and is the number of elements.
[0043]
The “maximum evaluation value” is a function indicating the maximum evaluation value at the node. This evaluation value changes depending on what kind of question tree is considered optimal, that is, it changes depending on how the question tree is formed.
[0044]
The “branch / leaf flag” is “1” if the node in the Yes / No question tree is a node (branch) indicating a question, and the search data group that appears after answering the question Is a node (leaf) indicating “0”. That is, if the branch / leaf flag is 1, it indicates a branch, and if the branch / leaf flag is 0, it is a leaf. That is, the question tree is composed of nodes (branches) indicating questions and nodes (leaves) indicating search data groups, and the “branch / leaf flag” distinguishes whether it is a branch or a leaf. Flag.
[0045]
The “item label” is a search condition indicating a question in the branch node, and is a search data group output after answering the Yes / No question tree in the leaf node.
[0046]
Next, a rule for creating a node ID of a Yes type question tree will be described.
[0047]
FIG. 6 is a diagram illustrating an example of a question tree in which a node ID is entered in the question tree.
[0048]
When creating a node ID of a Yes-type question tree, as shown in FIG. 6, the root ID of the query tree is “1”, and the child node ID described on the left among the child nodes of the node i is “ 2i ”and the child node ID described on the right is“ 2i + 1 ”.
[0049]
Returning to FIG. 1, the optimum pattern table creation unit 7 creates the optimum pattern table 6 based on the division target list 3.
[0050]
The optimum question tree creation unit 8 creates an optimum question tree 9 based on the non-divided logarithm list 4 and the optimum pattern table 6. In the optimum pattern table 6, as shown in FIG. 5, the optimum search condition (search condition having the maximum evaluation value) depending on the parent node search condition list is recorded in the item label for each node ID.
[0051]
Then, the combination of the parent node search condition list at the root of the question tree and the item label is used as the parent node search condition list in the next question tree hierarchy, and the optimum question item having this parent node search condition list is Such a process is recursively executed.
[0052]
For example, the parent node search condition list of the root of the query tree is “root” Terror "and the item label is" Korea " The combination of “terrorism” and “Korea” is “root” "Terror, Korea" and this "root" “Terror, Korea” is the parent node search condition list of the next question tree hierarchy, and the best question item (search condition with the maximum evaluation value) having this parent node search condition list, that is, “Korea” This process is recursively executed as a question item.
[0053]
In this way, the optimal question tree 9 is extracted. In addition, a set indicating terminal nodes that have replied No to the query tree is added to the non-division target list 4.
[0054]
FIG. 7 is a diagram showing tabular data held by the optimal question tree 9.
[0055]
As shown in FIG. 7, the optimal question tree 9 has a tabular format having a node ID, a length of a division target list, a maximum evaluation value, a branch / leaf flag, and an item label in the Yes / No type question tree. Have data.
[0056]
The table format data of the optimum question tree 9 shown in FIG. 7 is obtained by removing the “parent node search condition list” from the items of the optimum pattern table 6 shown in FIG.
[0057]
Next, an operation for creating a Yes / No type question tree in the above embodiment will be described.
[0058]
FIG. 8 is a flowchart showing a basic operation for creating a Yes / No question tree in the above embodiment.
[0059]
First, initial setting is performed by inputting the list upper limit possible number and the query tree selection upper limit number (S1).
[0060]
The “list upper limit possible number” is the number of cases that can be listed in the interface for browsing information. For example, in the case of a mobile terminal or a voice interface, the maximum number of lists that can be listed is about 3-7. Any number of cases other than 3 to 7 can be set as the list upper limit possible number.
[0061]
The “question tree selection upper limit number” is the number of times that the user can tolerate among the number of times the user selects Yes / No. For example, a few times. Any number of times other than 2, 3 can be set.
[0062]
Then, the division target list 3 and the non-division target list 4 are created (S2). That is, the division target list creation unit 5 gives a degree of suitability indicating the degree of suitability of any search condition shown in FIG. 3 to each data. This fitness is basically binary data indicating whether or not it is included in the search result of each search condition.
[0063]
Further, when the search data is included in the search result of each search condition (when the condition is met), the degree to which the search data matches each search condition is expressed as an order scale using TF / IDF values or the like. .
[0064]
The order scale is an integer value between 0 and 100, but other scales may be used as long as the data meets the search conditions. Further, in this embodiment, since the matching data is obtained when the matching degree is larger than “0”, the matching larger than “0” is obtained from the table of the data vs. search condition given the matching degree shown in FIG. Only a combination of data having a degree and a search condition is extracted, and as shown in FIG. 2, a division target list 3 composed of a pair of data and a corresponding search condition group (match) is created.
[0065]
In addition, as shown in FIG. 4, a non-division target list 4 is created by extracting, as a list, data that is not included in the search results of any search condition among the search conditions registered in advance.
[0066]
Then, the optimum pattern table 6 shown in FIG. 5 is created (S3). That is, the optimum pattern table creation unit 7 creates the optimum pattern table 6 shown in FIG. 5 based on the division target list 3. Details of the operation for creating the optimum pattern table 6 will be described later.
[0067]
Thereafter, the optimum question tree 9 is extracted (S4). That is, the optimum question tree creation unit 8 creates the optimum question tree 9 based on the non-division target list 4 and the optimum pattern table 6. In the optimum pattern table 6, an optimum search condition depending on the parent node search condition list is recorded in the item label for each node ID.
[0068]
Then, a combination of the parent node search condition list at the root of the question tree and the item label is used as a parent node search condition list of the next question tree hierarchy. The optimum question tree 9 is extracted by recursively executing the process of setting the optimum question item having the parent node search condition list as the next question item. In addition, the non-division target list 4 is added to a set indicating terminal nodes that have all replied No to the query tree.
[0069]
FIG. 9 is a flowchart showing in detail the operation (S3) for creating the optimum pattern table 6.
[0070]
When the optimum pattern table 9 is created (S3), recursive processing is performed.
[0071]
First, the optimum pattern table creation unit 7 acquires a node ID, a division target list, and a parent node search condition list (S3-1). Since the recursive process is performed when the optimum pattern table 6 is created, in the initial state, “1” indicating the root node of the query tree is given as the node ID, and the search data included in the document database as the division target list is given. The whole is given, and the character string “root” indicating the root is given to the parent node search condition list.
[0072]
In S 3-2, the optimum pattern table creation unit 7 uses, as a buffer for the record to be added to the optimum pattern table 6, the values related to the current division target list, the length of the division target list 3, the maximum evaluation value, and the branch / leaf flag. And assign to the item label items respectively.
[0073]
“Division target list length” is the number of data in the division target list 3. An evaluation value obtained based on some function when the division target list is input is substituted as the maximum evaluation value. This evaluation value may be any value as long as it represents the accuracy of the query tree, and 0 indicating a leaf is substituted as a branch / leaf flag. In addition, the search data group included in the division target list is substituted as an item label in a list format in descending order of suitability at the current node.
[0074]
In S3-3, if the current number of hierarchies is equal to or greater than the Yes / No selection upper limit number already input, the process proceeds to step S3-4, and if the current number of hierarchies is less than the Yes / No selection upper limit number. The process proceeds to step S3-5.
[0075]
In S3-4, the data held as the buffer in step S3-2 or S3-14 is added to the optimum pattern table 6 as a new record. The maximum evaluation value is returned to the caller of this flowchart, and the process ends.
[0076]
In S3-5, if the length of the division target list 3 is equal to or smaller than the listable upper limit number already input, the process proceeds to step S3-4. If the length is longer than the listable upper limit number, the process proceeds to step S3-6. .
[0077]
In S3-6, search conditions are extracted from the division target list 3, and search conditions not included in the parent node search condition list are extracted as search conditions to be evaluated.
[0078]
FIG. 10 is a diagram illustrating an example of a table indicating a relationship between data and a search condition group (goodness of fit) and an example of a query tree.
[0079]
For example, as shown in FIG. 10 (2), when the search condition of the evaluation target (search data) is acquired in the node whose node ID is 10, “terror”, “Yokosuka”, “ It is assumed that the search condition “China” is extracted. However, in this case, since the search condition “Yokosuka” is included in the parent node search condition list as shown in FIG. 10 (2), in order to prevent the question “Yokosuka?” The search condition “Yokosuka” is excluded, and “terrorism” and “China” are acquired as search conditions to be evaluated.
[0080]
In S3-7, if the number of search conditions to be evaluated is 0, the process proceeds to step S34, and if other than 0, the process proceeds to step S3-8.
[0081]
In S3-8, the operation of evaluating the search conditions to be evaluated one by one is repeated. If all the search conditions to be evaluated have been evaluated, the process proceeds to step S3-4. If there is a search condition to be evaluated that has not been evaluated, the search condition to be evaluated is extracted, and the process proceeds to step S3-9.
[0082]
In S3-9, the division target list 3 is divided according to the search condition extracted as the evaluation target in step S3-8. Among the data included in the division target list 3, data having an adaptability that the evaluation target matches with the search condition is larger than 0 is extracted as a list on the Yes side, and the remaining data is used as a list on the No side. Divided. Further, the currently evaluated search condition is added to the parent node search condition list of the current node as the parent node search condition list of the next hierarchy.
[0083]
In S3-10, in order to obtain the maximum evaluation value of the Yes side node of the next hierarchy, a value obtained by doubling the current node ID is set as a new node ID, and the Yes side list is set as the division target list 3. Furthermore, the parent node search condition list of the next hierarchy acquired in step S3-9 is recursively called.
[0084]
In S3-11, in order to obtain the maximum evaluation value of the No side node in the next hierarchy, a value obtained by adding 1 to the value obtained by doubling the current node ID is set as a new node ID, and the list on the No side is also displayed. The division target list 3 is used, and the parent node search condition list of the next hierarchy acquired in step S3-9 is recursively called.
[0085]
In S3-12, a value obtained by adding the maximum evaluation value on the Yes side acquired in Step S3-10 and the maximum evaluation value on the No side acquired in S3-11 to the search condition currently evaluated is divided. Substitute for “evaluation value”.
[0086]
In S3-13, if the evaluation value of the division acquired in step S3-12 is larger than the maximum evaluation value in the flowchart, the process proceeds to step S3-14. If it is equal to or less than the maximum evaluation value in the flowchart, step S3- Proceed to step 8.
[0087]
In S3-14, as the buffer of the record to be added to the optimum pattern table 6, the division information according to the currently evaluated search condition is substituted into the maximum evaluation value, the branch / leaf flag, and the item label. Since the evaluation value of the division is larger than the maximum evaluation value (S3-13), “1” indicating a branch is substituted as the branch / leaf flag. In addition, the currently evaluated search condition is substituted as the item label. As the length of the division target list 3, the value substituted in step S3-2 is used as it is.
[0088]
According to the first embodiment, when there is a search condition registered in advance and a database to be searched, and the degree of suitability indicating the degree of suitability of each search condition for each data can be calculated. In addition, when creating a Yes / No question tree to be displayed by narrowing down the search target by the question tree that selects the search condition by Yes / No, a search data group that can be searched by an arbitrary search condition is extracted and extracted. The search data group is divided into a search data group that can be searched with an arbitrary search condition and a search data group that cannot be searched, and a target of division among the registered search conditions. For the search data group, a search condition for which a search result exists only is created as a search condition constituting a question tree, and a method for recursively dividing and a method for recursively dividing a search data group A means for setting the evaluation value when the search data group is input as the maximum evaluation value of the search data group, and a maximum evaluation value of the search data group that can be searched by a search condition that recursively divides the search data group, The search data is divided by the search condition so that the sum of the maximum evaluation values of the search data group that cannot be searched is the maximum evaluation value of the division in the search condition and the maximum evaluation value is maximized. Since it is provided with a question tree setting means for setting a query tree or a search data group to be divided as a question tree, instead of creating all possible question tree configuration patterns, a Yes / No question tree pattern Before creating a query, exclude search conditions that do not have search results in the search data group to be split, and therefore create an optimal Yes / No question tree at high speed. Rukoto can.
[0089]
[Second Embodiment]
FIG. 11 is a flowchart showing an operation of creating the optimum pattern table 6 in the Yes / No type question tree creating apparatus according to the second embodiment of the present invention.
[0090]
The second embodiment is basically the same as the first embodiment. In the flowchart shown in FIG. 9, steps S3-15-2 and S3-8-2 are used instead of step S3-8. This is an embodiment that can ensure the accuracy of the created query tree while reducing the processing time even when the number of data to be searched increases or the number of search conditions to be considered increases.
[0091]
Steps other than steps S3-15-2 and S3-8-2 are the same as those in the first embodiment, and a description thereof will be omitted.
[0092]
In S3-15-2, the optimum search condition expected value is calculated for each search condition to be evaluated acquired in step S3-6.
[0093]
The “optimum search condition expected value” is a scale that can maximize the evaluation value of the division by dividing the division target list 3 using an arbitrary search condition.
In S3-8-2, the search conditions to be evaluated are sorted in descending order of the optimum search condition expected value, and only the search conditions having the highest optimum search condition expected value are evaluated one by one.
[0094]
Here, a certain number of search conditions from the top may be determined that the optimum search condition expected value is higher, and a search condition that is higher than an arbitrary expected value is the highest optimum search condition expected value. You may make it determine. If all the search conditions with the highest expected value of the optimal search condition are evaluated, the process proceeds to step S3-4. If all the evaluations are not completed, the search condition to be evaluated is extracted, and the process proceeds to step S3-9.
[0095]
According to the second embodiment, among the registered search conditions, only the search conditions that have search results for the search data group to be divided are created as the search conditions constituting the question tree. Then, when recursively dividing, using only means for calculating the optimum search condition expected value indicating the possibility that each search condition leads to the maximum evaluation value, and the search condition having the highest optimum search condition expected value, A means for recursively dividing the search data group, even if the number of search target data increases or the number of search conditions to be considered increases, while reducing the processing time, Accuracy can be ensured.
[0096]
[Third embodiment]
FIG. 12 is a flowchart showing an operation of creating the optimum pattern table 6 in the Yes / No type question tree creating apparatus according to the third embodiment of the present invention.
[0097]
In the third embodiment, a query tree that preferentially accesses data having a high degree of fitness can be created.
[0098]
Steps other than steps S3-16-3 and S3-17-3 are the same as those in the first embodiment, and a description thereof will be omitted.
[0099]
In S3-16-3, the optimum pattern table creation unit 7 calculates the fitness of each data at the current node.
[0100]
The “goodness level at the current node” is the total value of the goodness level for the keyword that answered Yes in the parent node search condition list of the current node.
[0101]
FIG. 13 is a diagram illustrating an example of the relationship between data and search conditions, and a diagram illustrating an example of a query tree.
[0102]
For example, as shown in FIG. 13, when the node ID of the current node is 10, the fitness of the data x at the current node is evaluated. In the node where the data x is currently classified, the search conditions “ABC” and “Yokosuka” are answered as Yes. Then, the total value of the matching levels between these search conditions and the data x is set as the matching level at the current node.
[0103]
In addition, although the answer to the keyword “ISDN” is also made, since “No” is answered, “ISDN” is not included in the search condition of the user in the current node and is excluded. In the same manner, the matching level at this current node is evaluated for all documents existing in the division target list.
[0104]
In S3-17-3, the optimum pattern table creation unit 7 extracts, from among the data included in the division target list 3, the data having the highest fitness at the current node by the number within the listable upper limit. Then, the sum of these values is calculated as the evaluation value of the division target list 3.
[0105]
According to the third embodiment, in the first embodiment, when the degree of matching indicating the degree of matching of each search condition with each data is an order scale that can be compared with each other, recursively. In dividing the search data group, a means for answering Yes at the parent node of the query tree and calculating the total value of the suitability of the arbitrary data for the selected search condition as the suitability at the current node of the data, When recursively dividing the search data group, the data with the highest degree of association in the current node is extracted from the data to be divided by the number of items (predetermined number) that can be listed even on terminals with low listability. And a means for using the sum of the matching levels at the current node as an evaluation value of the search data group to be divided, so that a query tree that preferentially accesses data having a high matching level can be created.
[0106]
[Fourth embodiment]
FIG. 14 is a flowchart showing the operation (S3) for creating the optimum pattern table 6 in the Yes / No type question tree creating apparatus according to the fourth embodiment of the present invention.
[0107]
In the fourth embodiment, even when the number of data to be searched increases or the number of search conditions to be considered increases, a question that preferentially accesses data having high fitness while reducing processing time. This is an embodiment that can ensure the accuracy of the tree.
[0108]
Further, in the flowchart shown in FIG. 14, steps other than steps S3-15-4 and S3-8-4 are the same as those in the third embodiment, and thus the description thereof is omitted.
[0109]
In S3-15-4, an optimum search condition expected value is calculated for each evaluation target keyword acquired in step S3-6.
[0110]
The “optimum search condition expected value” is a value obtained by summing the degree of fitness for each piece of data in the division target list 3 for each keyword.
[0111]
FIG. 15 is a diagram illustrating an example of the relationship between data and search conditions.
[0112]
For example, as shown in FIG. 15, when there is a division target list 3 composed of two pieces of data, a value obtained by summing the degree of matching with respect to data 1 and the degree of matching with data 2 of each search condition is the optimum search condition expectation. Value.
[0113]
In S3-8-4, the search conditions to be evaluated are sorted in descending order of the optimum search condition expected value, and the operation of evaluating only the search conditions having the highest optimum search condition expected value one by one is repeated.
[0114]
Here, a certain number of search conditions from the top may be determined that the optimum search condition expected value is higher, and a search condition that is higher than the expected value is an optimum search condition expected value is higher. Sometimes it is judged. When all the search conditions having the highest optimum search condition expected value are evaluated, the process proceeds to step S3-4. If search conditions that have not been evaluated remain among the search conditions having the highest optimum search condition expected value, the search conditions to be evaluated are extracted, and the process proceeds to step S3-9.
[0115]
According to the fourth embodiment, the query tree is formed only from the registered search conditions that have the matching degree in which the search result exists for the search data group to be divided. When the search condition is created and recursively divided, a value obtained by summing up the degree of fitness for the search data group to be divided for each search condition is provided, so that the optimum search condition expected value of the search condition is provided. Whether the number of data to be searched increases or the number of search conditions to be considered increases, the processing time is reduced and the accuracy of the query tree that preferentially accesses data with high fitness is ensured. Can do.
[0116]
[Fifth embodiment]
FIG. 16 is a flowchart showing an operation of creating the optimum pattern table 6 of the Yes / No type question tree creating apparatus according to the fifth embodiment of the present invention.
[0117]
In the fifth embodiment, after the user answers the Yes / No question tree, the Yes / No selection upper limit even when the list of browsing terminals is low (predetermined) when browsing the search data group. If you answer “Yes / No”, the number of search data groups to be browsed will be narrowed down to the number that can be listed, so the possibility that a large number of search results will remain even if you narrow down the questions repeatedly. This is an example.
[0118]
In the flowchart shown in FIG. 16, steps other than steps S3-18-5, S3-19-5, and S3-20-5 are the same as those in the first embodiment, and a description thereof will be omitted. .
[0119]
In S3-18-5, if the length of the division target list 3 is equal to or less than the listable upper limit number, the process proceeds to step S3-19-5. If it is longer than the listable upper limit number, the process proceeds to step S3-20-5. move on.
[0120]
In S3-19-5, the length of the division target list 3 is substituted for the evaluation value of the division target list 3, and the process proceeds to step S3-2.
[0121]
In S3-19-5, 0 is substituted into the evaluation value of the division target list 3, and the process proceeds to Step S3-2.
[0122]
According to the fifth embodiment, in the first embodiment, when the user answers the Yes / No question tree and browses the search data group, the list of the terminals to be browsed is low. When the number of data to be divided is less than the number of items that can be listed (predetermined number) even if the number of data to be divided is less than the list, the number of data to be divided is divided into If the number of data to be divided is greater than the number of items that can be listed (predetermined number), 0 is provided as the evaluation value of the search data group to be divided. After the user answers the Yes / No question tree, when browsing the search data group, even if the list of terminals to be browsed is low, answer Yes / No only within the Yes / No selection upper limit. Then, the search data group to browse Narrowed down on the number that can be run, also narrowed down repeated many times question, decreases the possibility that a large amount of search results remain.
[0123]
The above embodiment can be grasped as a program invention. That is, in the above embodiment, there is a search condition registered in advance and a database composed of search data to be searched, and the search data is narrowed down by answering Yes / No for the search condition. When creating a / No type query tree, a search data group is extracted according to a predetermined search condition, and the extracted search data group can be searched under an arbitrary search condition, and a search is performed under the arbitrary search condition. A data division procedure for dividing into search data groups that cannot be performed, and among the registered search conditions, only search conditions for which there are search results for the search data groups are created as search conditions that constitute the query tree. And the recursive division procedure for recursively dividing the search data group, and the recursive division procedure for dividing the search data group The function substitution procedure for assigning the evaluation value of the search data group to the function called the maximum evaluation value in the search data group, the maximum evaluation value of the search data group that can be searched under a predetermined search condition, and the search cannot be performed with the predetermined search condition The maximum evaluation value determination procedure for determining the value obtained by adding the maximum evaluation values of the search data group as the maximum evaluation value of the division in the search condition, and the search data in the search condition so that the maximum evaluation value is maximized. This is an example of a program that causes a computer to execute a query tree setting procedure for setting a query tree or a search data group to be split as a query tree.
[0124]
Further, the program may be recorded on a computer-readable recording medium. In this case, FD, CD, DVD, HD, semiconductor memory, etc. can be considered as the upper recording medium.
[0125]
【The invention's effect】
According to the present invention, it is possible to selectively evaluate a search condition that is highly likely to obtain an optimal query tree without recursively evaluating all the search conditions, and reduce the processing time, while creating a created question tree. There is an effect that accuracy can be secured.
[Brief description of the drawings]
FIG. 1 is a diagram showing a Yes / No question tree creation apparatus 100 according to a first embodiment of the present invention.
FIG. 2 is a diagram showing a division target list 3, which shows a relationship between search data and a search condition group (fitness).
FIG. 3 is a diagram illustrating an example of a degree of matching that is a degree to which a search condition matches each data.
FIG. 4 is a diagram illustrating an example of a non-dividing target list 4;
5 is a diagram showing an example of the contents of an optimum pattern table 6. FIG.
FIG. 6 is a diagram illustrating an example of a question tree in which a node ID is entered in the question tree.
FIG. 7 is a diagram showing tabular data possessed by an optimal question tree 9;
FIG. 8 is a flowchart showing a basic operation for creating a Yes / No question tree in the embodiment.
FIG. 9 is a flowchart showing in detail an operation (S3) for creating an optimum pattern table 6;
FIG. 10 is a diagram illustrating an example of a table indicating a relationship between data and a search condition group (goodness of fit) and an example of a query tree.
FIG. 11 is a flowchart showing an operation of creating an optimum pattern table 6 in the Yes / No type question tree creating apparatus according to the second embodiment of the present invention.
FIG. 12 is a flowchart showing an operation of creating an optimum pattern table 6 in the Yes / No type question tree creating apparatus according to the third embodiment of the present invention.
FIG. 13 is a diagram illustrating an example of a relationship between data and search conditions, and a diagram illustrating an example of a query tree.
FIG. 14 is a flowchart showing an operation (S3) for creating an optimum pattern table 6 in the Yes / No type question tree creation apparatus according to the fourth embodiment of the present invention.
FIG. 15 is a diagram illustrating an example of a relationship between data and a search condition.
FIG. 16 is a flowchart showing an operation of creating the optimum pattern table 6 of the Yes / No type question tree creating apparatus according to the fifth embodiment of the present invention.
[Explanation of symbols]
100 ... Yes / No question tree creation device,
1 ... Registration search condition list,
2… Search target database,
3 ... split target list,
4 ... Non-divided target list,
5 ... division target list creation section,
6 ... Optimal pattern table,
7: Optimal pattern table creation unit,
8 ... Optimal question tree creation department,
9 ... Optimal question tree.

Claims (7)

It is composed of a search condition registered in advance and a database made up of search data to be searched, and a Yes / No type question tree for narrowing down the search data by answering Yes / No with respect to the search condition. In the No-type question tree creation device,
Route node processing means for setting a node as a route having the search data to be searched as a search data set and calling the node processing means;
When a search data set is given, an evaluation value obtained by inputting the search data set to a predetermined function is set as the maximum evaluation value of the node, and if the current hierarchy number is equal to or greater than the Yes / No selection upper limit number If the above-mentioned maximum evaluation value is returned to the caller and the current number of hierarchies is less than the Yes / No selection upper limit number, search data satisfying the search condition for each search condition for the search data set corresponding to the node Divide into sets and search data sets that do not satisfy the search conditions, generate each node of the two search data sets that are divided, and call the node processing means that is itself recursively to the generated nodes The evaluation value of the generated node is obtained, the evaluation value of the node of the search data set that satisfies the search condition, and the evaluation of the node of the search data set that does not satisfy the search condition Calculates the sum of, determine the maximum evaluation value in which the sum has a maximum in the respective search conditions, a node processing unit that returns the maximum evaluation value to the caller;
Yes / No type question tree creation device characterized by having. In claim 1,
The node processing means is
An optimum search condition expected value calculation means for calculating an optimum search condition expected value indicating a possibility that each search condition leads to a maximum evaluation value;
A Yes / No type question tree creating apparatus, characterized in that a maximum evaluation value and a search condition thereof are obtained for a search condition having a higher expected value of the optimum search condition. In claim 1,
A degree-of-fit calculation means for obtaining a degree of suitability indicating the degree of suitability of each search condition to each search data;
The Yes / No type question tree creation device, wherein the predetermined function is a sum of a predetermined number of cases having a high degree of fitness in a given search data set. In claim 2,
A degree-of-fit calculation means for obtaining a degree of suitability indicating the degree of suitability of each search condition to each search data;
The Yes / No-type query tree creation device, wherein the optimum search condition expected value is a total of a predetermined number of cases having a high degree of fitness for the search condition in a given search data set. In claim 1,
The predetermined function is characterized in that when the number of given search data sets is equal to or less than a predetermined number, the number is set as an evaluation value, and when the number is larger than the predetermined number, the evaluation value is set as 0. Yes / No type question tree creation device.   A Yes / No question tree creation program that causes a computer to function as each unit of the Yes / No question tree creation device according to any one of claims 1 to 5.   A computer-readable recording medium on which the Yes / No question tree creation program according to claim 6 is recorded.

Images