JP4833025B2 - Combination extraction program, combination extraction method, and combination extraction device - Google Patents

Description

  The present invention relates to a combination extraction program, a combination extraction method, and a combination extraction device, and more particularly, to a combination extraction program, a combination extraction method, and a combination extraction device that extract a combination of items.

  In mail order sales or the like, a set product (value pack) that is composed of a combination of single item items (for example, a television channel) and that is lower in price than purchasing individual item items is generally performed.

  In sales of such products, when there is no set product that matches the item desired by the user, the user selects either purchase of a single item only or purchase of a combination of a single item and a set product. It will be.

  In this case, the sales side shall provide the user with a combination that includes all the items that the user wishes to purchase from all combinations of the set products and that the purchase price is lower than purchasing all the items separately. become.

As a method of extracting combinations, for example, a method of creating a syntax tree and extracting a specific combination is known (for example, see Non-Patent Document 1).
“Efficiently mining long patterns from databases” Proceedings of SIGMOD'98, pp85-93. (ISBN: 0-89791-995-5) .1998

  However, as the types of items and set products increase, the number of combination candidates increases, and the amount of calculations (combination extraction calculation, post-extraction charge calculation) increases, so the load on both the CPU and memory increases. As a result, the calculation time is delayed, and it is difficult to quickly provide an appropriate combination.

  The present invention has been made in view of these points, and an object of the present invention is to provide a combination extraction program, a combination extraction method, and a combination extraction device that can quickly extract a desired combination.

In the present invention, in order to solve the above problem, a combination extraction program for causing the computer 1 to execute a process as shown in FIG. 1 is provided.
The combination extraction program according to the present invention is a program for extracting a combination of items.

  The set data storage means 2 stores set data 4, 5 having a set 3, 3a of a plurality of items (#item) each having a value and a value associated with each of the sets 3, 3a.

  The set search unit 6 searches the set data storage unit 2 for a set including two or more items in the item data 7 in response to the input of the item data 7 including a plurality of items.

  The set list creation means 8 arranges the sets searched by the set search means 6 and the single item groups composed of items not included in the set searched by the set search means 6 in the item data 7 in this order. A set list 9 including at least one array is created.

  The pruning means 10 refers to the set list 9, creates a search tree that represents the array sequence as a transition between nodes with the single item group as the final transition destination, and each array when performing a depth-first search of this search tree Then, the value associated with the set and the total value of each item in the single item group are added, and when the threshold value is exceeded, the branch of the node being searched is pruned.

The combination output unit 11 outputs a combination of an array set having a total value smaller than a threshold and a single item group.
According to such a combination extraction program, the set data 4 and 5 are stored by the set data storage means 2. When the item data 7 including a plurality of items is input, the set search unit 6 searches the set data storage unit 2 for a set including two or more items in the item data 7. Then, the set list creating means 8 creates a set list 9 having an array in which the sets retrieved by the set retrieving means 6 and the single item groups are arranged in this order. Then, the pruning means 10 refers to the set list 9 to create a search tree. When a depth-first search is performed on this search tree, the value associated with the set in the array and the value of each item in the single item group The total value is added, and when the threshold value exceeds a given threshold value, the branch of the node being searched is pruned. Thereafter, the combination output unit 11 outputs a set of arrays having a total value smaller than the threshold value and a combination of the single item group.

In the present invention, the branch of the node being searched is pruned when the value exceeds a given threshold value, so there is no need to perform subsequent calculations and the amount of computation can be reduced.
In addition, by performing depth-first search, it is possible to omit the overlap calculation at the top of the search tree and reduce the amount of calculation.

  Thereby, it is possible to quickly provide a combination of a set of arrays having a total value smaller than the threshold and a combination of single item groups, that is, a combination including all items in the item data and having a small value.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
First, an outline of the present invention will be described, and then an embodiment will be described.
FIG. 1 is a diagram showing an outline of the present invention.

A combination extraction program for performing processing as shown in FIG. 1 using the computer 1 is provided.
The computer 1 shown in FIG. 1 includes a set data storage unit 2, a set search unit 6, a set list creation unit 8, a pruning unit 10, and a combination output unit 11.

The set data storage means 2 stores set data 4 having a value associated with the set 3 and set data 5 having a value associated with the set 3a.
Each of the sets 3 and 3a includes a plurality of items (#item) each having a value.

The values (400, 300) associated with the sets 3, 3a are set to be smaller than the values obtained by adding the values of the individual items constituting the sets 3, 3a, respectively.
The set search unit 6 searches the set data storage unit 2 for a set including two or more items in the item data 7 in response to the input of the item data 7 including a plurality of items. The item data 7 is all composed of a single item and does not include a set. Although not shown in FIG. 1, it is preferable that the computer 1 is provided with means for creating the item data 7 from data in which a set and a single item are mixed.

  The set list creation means 8 arranges the sets searched by the set search means 6 and the single item groups composed of items not included in the set searched by the set search means 6 in the item data 7 in this order. A set list 9 including at least one array is created. In FIG. 1, the contents of set 3 are set # 3, and the contents of set 3a are set # 3a.

  The pruning means 10 refers to the set list 9, creates a search tree that represents the array sequence as a transition between nodes with the single item group as the final transition destination, and each array when performing a depth-first search of this search tree In this case, the value associated with the set and the total value of each item in the single item group are added, and when the value exceeds a given threshold, the branch of the node being searched is pruned. The value associated with the set and the value of each item in the item group may be attached in advance to the set searched by the set search means 6, or when the set list creation means 8 creates the set list. May be obtained from the set search means 6 or may be obtained from the set search means 6 when the pruning means 10 creates a search tree.

The combination output unit 11 outputs a combination of an array set having a total value smaller than a threshold and a single item group.
According to such a combination extraction program, the set data 4 and 5 are stored by the set data storage means 2. When the item data 7 including a plurality of items is input, the set search unit 6 searches the set data storage unit 2 for a set including two or more items in the item data 7. Then, the set list creating means 8 creates a set list 9 having an array in which the sets retrieved by the set retrieving means 6 and the single item groups are arranged in this order. Then, the pruning means 10 refers to the set list 9 to create a search tree. When a depth-first search is performed on this search tree, the value associated with the set in the array and the value of each item in the single item group The total value is added, and when the threshold value exceeds a given threshold value, the branch of the node being searched is pruned. Thereafter, the combination output unit 11 outputs a set of arrays having a total value smaller than the threshold value and a combination of the single item group.

FIG. 2 is a diagram illustrating the combination extraction system according to the embodiment.
In the combination extraction system 300, a combination extraction device (server) 100 and a terminal device (client) 200 are connected via a network (Internet) 15.

  Upon receiving the product data (combination extraction request) of the item (purchased product) from the terminal device 200, the combination extraction device 100 extracts the optimal combination of items and transmits it to the terminal device 200.

  The terminal device 200 transmits the above-described product data to the combination extraction device 100 in response to an input from a user or an operator. The terminal device 200 is, for example, a call center terminal device or a terminal device used by a user. In FIG. 2, one terminal device 200 is illustrated, but a plurality of terminal devices 200 may be connected to the combination extraction device 100.

FIG. 3 is a diagram illustrating a hardware configuration example of the combination extraction device.
The entire combination extraction apparatus 100 is controlled by a CPU (Central Processing Unit) 101. A random access memory (RAM) 102, a hard disk drive (HDD) 103, a graphic processing device 104, an input interface 105, and a communication interface 106 are connected to the CPU 101 via a bus 107.

  The RAM 102 temporarily stores at least part of an OS (Operating System) program and application programs to be executed by the CPU 101. The RAM 102 stores various data necessary for processing by the CPU 101. The HDD 103 stores an OS and application programs. A program file is stored in the HDD 103.

  A monitor 16 is connected to the graphic processing device 104. The graphic processing device 104 displays an image on the screen of the monitor 16 in accordance with a command from the CPU 101. A keyboard 17 and a mouse 18 are connected to the input interface 105. The input interface 105 transmits a signal sent from the keyboard 17 or the mouse 18 to the CPU 101 via the bus 107.

  The communication interface 106 is connected to the network 15. The communication interface 106 transmits / receives data to / from other computers via the network 15.

  With the hardware configuration as described above, the processing functions of the present embodiment can be realized. Although FIG. 3 shows the hardware configuration of the combination extraction apparatus 100, the terminal apparatus 200 can also be realized with the same hardware configuration. In order to perform combination extraction in a system having such a hardware configuration, the following functions are provided in the combination extraction apparatus 100.

FIG. 4 is a block diagram illustrating functions of the combination extraction device and the terminal device.
The combination extraction apparatus 100 includes a product data reception unit 110, an item decomposition unit 120, an item list storage unit 130, a set list storage unit 140, a set search unit 150, an optimum combination search unit 160, and a result transmission unit 170. And have.

The product data receiving unit 110 receives the product data 30 from the terminal device 200.
FIG. 5 is a diagram showing product data.
The product data 30 includes a product number for specifying an item and a set composed of a plurality of product numbers. Although the combination of the product number and the set in the product data 30 is not particularly limited, it is assumed that the product data 30 includes at least one set. Product data 30 shown in FIG. 5 includes a set A composed of product numbers # 101, # 102, and # 103, a set B composed of product numbers # 103, # 104, and # 105, and product numbers # 302, # 201, And a single item group composed of # 301.

Returning to FIG.
The item disassembly unit 120 refers to the data stored in the item list storage unit 130 that stores data related to items and the set list storage unit 140 that stores data related to sets. The total amount of the item alone when the set is disassembled into the item alone is calculated.

The contents of the item list storage unit 130 and the set list storage unit 140 will be described later.
The set search unit 150 refers to the data stored in the set list storage unit 140 and searches for a set including two or more item numbers of items in the product data 30.

  The optimum combination search unit 160 creates a combination search tree using the search result of the set search unit 150, and extracts the combination with the lowest total amount. The contents of the combination search tree will be described later.

The optimum combination search unit 160 constitutes a main part of the set list creation unit, the pruning unit, and the combination output unit.
The result transmission unit 170 transmits the combination extraction result to the terminal device 200.

The terminal device 200 includes a data transmission unit 210 and a result display unit 220.
The data transmission unit 210 transmits the product data 30 to the combination extraction apparatus 100 in response to an input from a user or an operator.

The result display unit 220 receives the combination extraction result obtained from the combination extraction device 100 and displays the result on the monitor provided in the terminal device 200.
Next, the operation of the combination extraction apparatus 100 will be described.

FIG. 6 is a flowchart showing the operation of the combination extraction apparatus.
First, when the merchandise data receiving unit 110 receives the merchandise data 30, the item disassembling unit 120 converts each of the application set sets S (S = {s1,..., SN} ⊆S0 (S0: all set sets)). The set is disassembled into items and added to the application item set i (step Sa1). That is, U = i∪s1∪... ∪sN (⊆I (I: all items set)).

  Next, the set search unit 150 adds to SetList if the set s includes two or more elements of U with respect to an arbitrary set sεS0 (step Sa2). It is assumed that a set in SetList is given a unique order ≦ in the order including many U elements.

  Next, the optimum combination search unit 160 performs a depth-first search for a virtual collective tree for (SetList, ≦). Note that the initial threshold for pruning is a total amount α0 (total amount of items and sets). Then, the lowest price obtained by the search, the item number of the item that gives this lowest price, and the combination of the set are passed to the result transmission unit 170 as a combination extraction result (step Sa3).

Next, the result transmission unit 170 transmits the combination extraction result (step Sa4).
The operation of the combination extraction apparatus 100 is thus completed.
Next, the operation of the combination extraction apparatus 100 will be described using a specific example.

7 and 8 are diagrams illustrating the operation of the item disassembling unit.
As shown in FIG. 7, the item list storage unit 130 stores an item list table 131.

The item list table 131 has columns of product number, unit price, presence / absence of set, and set. Information arranged in the horizontal direction of each column is associated with each other.
A product number for specifying an item is set in the product number column.

A unit price for each item is set in the unit price column.
The presence / absence of a set including this item is set in the set presence / absence column.
In the set column, when a set exists (O), a set name including this item is set.

The set list storage unit 140 stores a set list table 141.
The set list table 141 has columns for sets, set prices, and product numbers. Information arranged in the horizontal direction of each column is associated with each other.

In the set column, a name for identifying the set is set.
The set price of the set is set in the set price column.
The item number of the item included in the set is set in the item number column.

  The item disassembly unit 120 refers to the item list table 131 for the single item group (items # 302, # 201, # 301) included in the product data 30, and acquires the unit price of each item. Next, for the sets included in the product data 30, the set list table 141 is referred to, and the set prices of the sets A and B are acquired. Next, the product data 40 including the total amount α0 obtained by adding the unit price of each item and each set price is created. For example, when the total amount α0 is known in advance (when input by the user or operator, etc.), this operation is omitted.

  Next, as shown in FIG. 8, the item disassembling unit 120 disassembles the set A and the set B (all sets) included in the product data 40 into individual items, and disassembles the items by referring to the item list table 131. The total amount of each single item is calculated, and product unit price data 50 including the item number and unit price of each item and the total amount α1 of the item unit is created.

FIG. 9 is a diagram illustrating the operation of the set search unit.
The set search unit 150 searches the set list table 141 for a set including two or more item numbers of items included in the product unit price data 50, and arranges the sets in the order of the set having a large number of matches with the item number. Search result data 60 is created.

FIG. 10 is a diagram illustrating the SetList creation operation of the optimum combination search unit.
The optimum combination search unit 160 connects sets in order from the set with the largest number of matches in the search result data 60, and searches a tree structure (array) in which the item numbers of the individual items that do not belong to the set are connected to the subsequent stage of the set as a single item group. And SetList 70 having this search tree structure is created.

  At this time, priorities are assigned to the sets, and sets having the same number of matches are connected in the order of A to Z. For example, for the set A and the set B having the same number of matches, the set A is always arranged in the previous stage (left side in FIG. 10). As a result, for example, the structure of set B → set A is eliminated, so that the search tree structure of SetList 70 can be simplified.

Thereafter, the combination search tree T created based on the search tree structure in the SetList 70 is searched to search for the lowest price.
FIG. 11 is a diagram illustrating a tree structure of the combination search tree.

  The combinatorial search tree T has nodes and edges (edges) that connect the nodes. The node 71 is a root node, and the other nodes are subordinate to the node 71. Nodes (lower nodes) 72 to 78 are created for the node 71 based on the SetList 70. Each node 72-78 is associated with a set name and a set price. Below each of the nodes 72 to 78, leaf nodes (Leaf) L71 to L77 configured by a single item group are created.

Next, a general example of the search operation will be described using a flowchart.
FIG. 12 is a flowchart showing the search operation.
Hereinafter, current node (position): node v, current total amount: value, current threshold value: threshold value α, price of node u: kakaku (u), stack: Stack [0. . maxdepth (T1)].

As an initial state, node v = root, threshold α = α0 (¥ 2400), and Stack [0] = 0 are set (step S11). The threshold α may be α1 (¥ 2500).
Next, it is determined whether or not the next node u exists in the order of the combination search tree T (step S12). The pre-order order is an order obtained by performing a depth-first search clockwise and counterclockwise in the order tree and outputting each node for the first time.

When the next node u exists (Yes in step S12), the process proceeds to node u, and node v = node u is set (step S12a).
Next, it is determined whether or not the node v is a leaf node of the combination search tree T (step S13).

If the node v is a leaf node (Yes in step S13), val_items, which is the amount of a single item included in the leaf node, is added to value (step S14).
Next, it is determined whether or not value is smaller than a threshold value α (step S15).

When the value is equal to or greater than the threshold value α (No in step S15), the process proceeds to step S12 and the operations after step S12 are continuously performed.
On the other hand, when the value is smaller than the threshold value α (Yes in step S15), the value is set to the threshold value α (step S16).

  Next, the current set, the combination of the single item group, and the value are recorded (held) in the RAM 102 (step S17). And it transfers to step S12 and performs the operation | movement after step S12 continuously.

By the way, when the node v is not a leaf node in step S13 (No in step S13),
value = Stack [depth (u) -1] + kakaku (u)
Stack [depth (u)] = value
(Step S18). That is, the set price at the node u is added to the stack (total amount) up to the node one node above the node u, and the added price is used as a new stack.

Next, it is determined whether or not the value is smaller than the threshold value α (step S19).
When the value is smaller than the threshold value α (Yes in step S19), the process proceeds to step S12, and the search operation is continued.

  On the other hand, if the value is equal to or greater than the threshold value α (No in step S19), the combinatorial search tree T is pruned, that is, all descendants of the node u are regarded as deleted from the combinatorial search tree T, and the search is omitted (step S20). ). Then, the process proceeds to step S12, and the search operation is continued.

  If the next node u does not exist in step S12 (No in step S12), the result transmission unit 170 uses the combination of the value (lowest price) recorded in the RAM 102, the set, and the combination of the single item group as a combination extraction result. (Step S21), the search operation is terminated.

  Thus, at the end of the search operation, the value that is the lowest value and the combination that gives it are obtained. As described above, the optimum combination search unit 160 prunes branches that exceed the amount of money previously calculated during the calculation, and stops the calculation without performing calculation until the end. Thereby, shortening of calculation time can be aimed at.

Next, a specific example of the search operation will be described using the combination search tree T shown in FIG. Here, the threshold value α = total amount α1 = ¥ 2500 is set as the initial state.
First, a search is performed for a group (a combination of a set and a single item group) G1 including the nodes 71 to 74 and the leaf node L71 of the combination search tree T. In this group G1, since the node 72 (node u) exists, the process proceeds to the node 72 (node u), and the current position (node v) is set as the node 72 (node u). Since node 72 (node u) is not a leaf node, the set price ¥ 500 of set A is added to value.

  Then, the value is compared with the threshold value α. Since value (¥ 500) <threshold α (¥ 2500) and node 73 (node u) exists, the process proceeds to node 73 (node u), and the current position (node v) is set as node 73 (node u). . Since node 73 (node u) is not a leaf node, set price ¥ 500 of set B is added to value.

  Then, the value is compared with the threshold value α. Since value (¥ 1000) <threshold α (¥ 2500) and node 74 (node u) exists, the process proceeds to node 74 (node u), and the current position (node v) is set to node 74 (node u). . Since node 74 (node u) is not a leaf node, the set price ¥ 2000 of set D is added to value.

  Then, the value is compared with the threshold value α. Since value (¥ 3000)> threshold α (¥ 2500), the branch between the node 74 and the leaf node L71 is pruned (the calculation is not performed for the leaf node L71).

Since the next node (leaf node L72) exists, the leaf node L72 becomes the node u (= node v).
Next, the group G2 including the nodes 71 to 73 and the leaf node L72 of the combination search tree T is searched. This group G2 is the same as the group G1 up to the process of set B. That is, since value (¥ 1000) <threshold α (¥ 2500) and leaf node L72 (node v) is a leaf node, the total amount of individual items included in leaf node L72 was calculated and obtained. Add the amount of ¥ 1400 to value.

Then, the value is compared with the threshold value α. Since value (¥ 2400) <threshold α (¥ 2500), it is assumed that threshold α = value (¥ 2400).
Then, the current set, the combination of the single item group, and value (¥ 2400) are recorded in the RAM 102.

The node 75 becomes the node u (node v). Thereafter, the search is performed in the same manner.
Since the group including the nodes 71, 72, 75 and the leaf node L73 becomes value (¥ 2500) when searching for the node 75, the branch between the node 75 and the leaf node L73 is pruned at this time.

Since the group including the nodes 71 and 72 and the leaf node L74 becomes value (¥ 2350) when searching for the leaf node L74, α = Value (¥ 2350).
Then, the combination of the current set and the single item group and the value (¥ 2350) are recorded (overwritten) in the RAM 102.

  Since the group including the nodes 71, 76, 77 and the leaf node L75 becomes value (¥ 2500) when searching for the node 77, the edge between the node 77 and the leaf node 75 is pruned (pruned by the node 77). , Its descendants are not searched).

  Since the group including the nodes 71 and 76 and the leaf node L76 becomes value (¥ 2250) when searching for the leaf node L76, α = Value (¥ 2250) and the branch between the node 76 and the leaf node L76 is pruned. .

Then, the combination of the current set and item single group and value (¥ 2250) is recorded (overwritten) in the RAM 102.
In the group including the nodes 71 and 78 and the leaf node L77, value (¥ 3950) is obtained when searching for the leaf node L77, so the branch between the node 78 and the leaf node L77 is pruned at this time.

  When the search is completed up to the leaf node L77, the value (lowest price) recorded in the RAM 102, the set, and the combination of the item group are passed to the result transmission unit 170 as a combination extraction result.

  Here, the value (¥ 2250), the set B, and the combinations of the single item groups of the product numbers # 101, # 102, # 201, # 301, and # 302 are delivered as the combination extraction result.

  As described above, according to the combination extraction apparatus 100, it is possible to easily and reliably output (present) a combination including all items that the user desires to purchase and having the lowest total price.

  In addition, by performing a search using the combination search tree T, it is possible to omit the calculation of overlapping calculation parts, so that the amount of calculation decreases exponentially compared to the conventional case. Therefore, the load on the CPU can be reduced, and the calculation can be completed in a short time.

  Further, by pruning a group that exceeds the threshold value α at the time of searching, the load on the CPU can be further reduced, and the calculation can be completed in a shorter time.

Furthermore, depending on the combination extraction result that is output, combinations that the user, operator, or the like did not notice when inputting the product data 30 can be presented.
In addition, by providing logic (pruning, judgment of the lowest price) to the intermediate node, it is possible to mount logic other than simple charge calculation. This makes it possible to easily determine campaign discounts set for each item for a limited time, purchase availability due to age restrictions, etc., and reduce the amount of calculation including other calculation conditions at intermediate nodes. It can be done easily.

  Therefore, for example, even when a change occurs in the price of an item or a set, it is possible to easily select the combination of the lowest prices with the latest information. In particular, as new sets appear from one to the next and the number of combination candidates becomes enormous, the effect becomes more prominent.

Next, the combination extraction system of the second embodiment will be described.
Hereinafter, the combination extraction system according to the second embodiment will be described with a focus on differences from the first embodiment described above, and description of similar matters will be omitted.

The combination extraction system of the second embodiment is characterized by the processing method of the optimum combination search unit 160 when there are a plurality of lowest prices.
FIG. 13 is a diagram illustrating the operation of the item decomposition unit according to the second embodiment, and FIG. 14 is a diagram illustrating the operation of the set search unit according to the second embodiment.

  The set list storage unit 140 according to the second embodiment stores a set list table 141a in which the set price of the set D is different from the set list table 141. Note that the operations of the item disassembling unit 120 and the set search unit 150 are the same as those in the first embodiment, and a description thereof will be omitted.

FIG. 15 is a diagram illustrating a SetList creation operation of the optimum combination search unit according to the second embodiment.
The optimal combination search unit 160 creates the SetList 70a in the same manner as in the first embodiment. After that, the combination search tree T1 created based on the search tree structure in the SetList 70 is searched for the lowest price.

FIG. 16 is a diagram illustrating a tree structure of the combination search tree according to the second embodiment.
Also in the second embodiment, as in the first embodiment, the optimum combination search unit 160 searches in the order of the combination search tree T1. Each time the lowest price is found, α = value is set, and the combinatorial search tree T1 is pruned. At this time, when the value and the threshold value α are compared, and there are a plurality of groups where value = threshold value α, the set, the combination of the single item group, and the value (¥ 2400) are recorded in the RAM 102.

  When the search is completed, the result transmitting unit 170 obtains a combination extraction result of the combination of the set and item single group and the value in the group having the largest number of items including the set and single item group in these groups as a combination extraction result. To pass. In FIG. 16, the lowest price ¥ 2150, the set B and the set D, and the product numbers # 102, # 201, and # 302 are delivered as the combination extraction result.

According to the combination search system of the second embodiment, the same effect as the combination search system of the first embodiment can be obtained.
And according to the combination search system of 2nd Embodiment, since the group which has the cheapest and the largest number of items can be extracted easily, the combination with a more bargain feeling is provided with respect to a user. be able to.

Next, a combination extraction system according to the third embodiment will be described.
Hereinafter, the combination extraction system of the third embodiment will be described focusing on the differences from the first embodiment described above, and the description of the same matters will be omitted.

  The combination extraction system according to the third embodiment is characterized in the processing method of the optimum combination search unit 160 when there are a plurality of groups having values lower than the total price α1 of the product data 30.

FIG. 17 is a diagram illustrating an item list table according to the third embodiment.
The data structure of the item list table 131a is the same as that of the item list table 131, but the item number # 203 is added, and details of items below the item number # 402 are shown.

Also, a new content column is set in the item list table 131a. In the contents column, the contents of the item (program name in FIG. 17) are set.
FIG. 18 illustrates a set list table according to the third embodiment.

The data structure of the set list table 141b is the same as that of the set list table 141, but the product numbers included in the set A and the set B are different.
FIG. 19 is a diagram illustrating the operation of the item disassembling unit.

The item disassembly unit 120 creates search result data 60b.
FIG. 20 is a diagram illustrating the operation of the set search unit.
The set search unit 150 creates a SetList 70b.

FIG. 21 is a flowchart illustrating a search operation according to the third embodiment.
Steps S31 to S35 perform the same operations as steps S11 to S15, respectively.

  When the value is smaller than the threshold value α (Yes in step S35), the value is not set to the threshold value α, and the combination of the current set and the single item group and the value are passed to the result transmission unit 170 as a combination extraction result. (Step S36). At this time, the number of items that the user included in this combination has not applied for and the item names are passed simultaneously.

Steps S37 to S39: The same operations as in steps S18 to S20 are performed.
As described in step S36, the combination extraction result is passed to the result transmission unit 170 when a combination of a set with a lower price than the threshold value α and a combination of the single item group is found, so the operation corresponding to step S21 is as follows. Not performed.

Next, a specific example of the search operation according to the third embodiment will be described.
FIG. 22 is a diagram illustrating a tree structure of the combination search tree according to the third embodiment.
Also in the third embodiment, similarly to the first embodiment, the optimum combination search unit 160 searches in the order of the combination search tree T2. Even when a group having a value that is lower than the threshold value α is found, the combinatorial search tree T2 is pruned with the threshold value α = 2500 (not α = value). When a group having a value that is lower than the threshold value α is found, a combination of the value of the group and the item and the content of the item of the item number not included in the product data 30 are obtained as a combination extraction result, and the result transmission unit 170 To pass. In FIG. 22, first, value (¥ 2400), set A and set B, combinations of item single groups of item numbers # 201, # 301, and # 302, the number of these items, and item numbers not included in the item data 30 The contents of the item are combined and passed as an extraction result.

  Next, value (¥ 2350), the combination of the single item group of set A and product numbers # 104, # 105, # 201, # 301, and # 302, the number of these items, and the product number not included in the product data 30 The contents of the item are combined and passed as an extraction result.

  Next, value (¥ 2250), set B and set D, combination of item groups # 101, # 102, # 201, # 301, and # 302, the number of these items, and the product data 30 The content of the item with the part number that is not valid is passed as a combination extraction result.

FIG. 23 is a diagram illustrating a combination extraction result displayed by the result display unit.
The combination extraction result screen 221 includes columns for items other than candidates, amounts, items, and applications, and information arranged in the horizontal direction of each column is associated with each other.

In the candidate field, a name for identifying the combination extraction result is set.
The value output as the combination extraction result is set in the amount column.
The number of all items is set in the item number column.

In the item column other than the application, the item number of the item not described in the product data 30 and its content are set.
According to the combination search system of the third embodiment, the same effect as the combination search system 300 of the first embodiment can be obtained.

  And according to the combination search system of 3rd Embodiment, the combination with a bargain feeling (the number of items, the amount of money, the balance of the item to buy) can be further easily selected with respect to a user.

  In this embodiment, each time a low price is found, the combination extraction result is passed to the result transmission unit 170. However, the present invention is not limited to this, and for example, the number of combination extraction results passed to the result transmission unit 170 in advance is set in advance. The combination extraction result is recorded in the RAM 102 every time a low price is found, and when the combination extraction result recorded in the RAM 102 exceeds three, the newly extracted combination extraction result is stored in the RAM 102. Compared with the three combination extraction results recorded, three of these extracted from the combination extraction result having the largest value are recorded in the RAM 102, and the three recorded in the RAM 102 when the search is completed. The combination extraction result may be passed to the result transmission unit 170.

  The combination extraction program, the combination extraction method, and the combination extraction apparatus of the present invention have been described based on the illustrated embodiment. However, the present invention is not limited to this, and the configuration of each unit has the same function. Can be replaced with any structure having Moreover, other arbitrary structures and processes may be added to the present invention.

  Further, the present invention may be a combination of any two or more configurations (features) of the above-described embodiments. For example, the search is performed with a constant value of the threshold value α, and the threshold value is set. A set in the group having the largest number of items including a set and a single item group among groups having a value lower than α and a combination of the single item group and the value are passed to the result transmission unit 170 as a combination extraction result. You may do it.

  The above processing functions can be realized by a computer. In that case, a program describing the processing contents of the functions that the combination extraction apparatus 100 should have is provided. By executing the program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. Examples of the computer-readable recording medium include a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory. Examples of the magnetic recording device include a hard disk device (HDD), a flexible disk (FD), and a magnetic tape. Examples of the optical disc include a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), a CD-ROM (Compact Disc Read Only Memory), and a CD-R (Recordable) / RW (ReWritable). Examples of the magneto-optical recording medium include MO (Magneto-Optical disk).

  When distributing the program, for example, a portable recording medium such as a DVD or a CD-ROM in which the program is recorded is sold. It is also possible to store the program in a storage device of a server computer and transfer the program from the server computer to another computer via a network.

  The computer that executes the combination extraction program stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. Then, the computer reads the program from its own storage device and executes processing according to the program. The computer can also read the program directly from the portable recording medium and execute processing according to the program. In addition, each time the program is transferred from the server computer, the computer can sequentially execute processing according to the received program.

(Supplementary note 1) In a combination extraction program for extracting a combination of items,
Computer
Set data storage means for storing a plurality of set data each having a set of items each having a value and a value associated with the set;
A set search means for searching the set data storage means for the set including two or more items in the item data in response to input of item data including a plurality of the items;
The set searched by the set search means and at least one item group composed of the items not included in the set searched by the set search means in the item data in this order A set list creation means for creating a set list with an array;
Referencing the set list, creating a search tree that represents the array sequence as a transition between nodes with the single item group as a final transition destination, and in each array when performing a depth-first search of the search tree, A pruning means for pruning the branch of the node being searched when the value associated with the set and the total value of each of the items in the single item group are added, and when the value exceeds a given threshold value,
A combination output means for outputting a combination of the set of the arrays having the total value smaller than the threshold and the item single group;
As a combination extraction program characterized by functioning as

(Supplementary note 2)
Data storage means in which value information of the value of each item is stored;
In response to mixed data input in which at least one item and the set are mixed, the value of each item of the set included in the mixed data is extracted from the value information, and the single item included in the mixed data Calculating means for calculating the total value of the item data to create the item data;
The combination extraction program according to supplementary note 1, wherein the combination extraction program is made to function as:

  (Additional remark 3) The said pruning means uses the total value of the value of the said set contained in the said mixed data, and the value of each said item as said threshold value, The combination extraction program of Additional remark 2 characterized by the above-mentioned.

(Additional remark 4) The said pruning means uses the sum total value of each said item of the said item data as said threshold value, The combination extraction program of Additional remark 1 characterized by the above-mentioned.
(Additional remark 5) The said set list preparation means produces the said arrangement | sequence arranged in order from the said many sets containing the said item in the said item data among the said sets searched by the said set search means. The combination extraction program according to appendix 1, which is characterized.

  (Supplementary Note 6) When the pruning means in the array has a value associated with the set and a total value of the values of the items of the single item group being smaller than the threshold value, the pruning means calculates the total value as a depth after that. The combination extraction program according to supplementary note 1, wherein the threshold value is used for the priority search.

  (Supplementary Note 7) When there are a plurality of combinations of the set and the item single group that are smaller than the threshold, the combination output unit has the largest number of the combinations of the set and the item single group that are smaller than the threshold. The combination extraction program according to appendix 1, wherein a combination including

(Supplementary Note 8) The computer is further caused to function as supplementary information storage means for storing supplementary information related to the item,
The combination output means adds and outputs the additional information for each of the items that are not included in all the items or the item data when outputting the combination of the set and the single item group that is equal to or less than the threshold. The combination extraction program according to supplementary note 1, wherein:

(Supplementary Note 9) In a combination extraction method for extracting a combination of items,
The set data storage means stores a plurality of set data each having a set of items each having a value and a value associated with the set;
A set search means is responsive to an input of item data comprising a plurality of the items, and searches the set data storage means for the set including two or more items in the item data,
The set list creation means includes the set searched by the set search means and the single item group composed of the items not included in the set searched by the set search means in the item data in this order. Create a setlist with at least one array arranged in
The pruning means refers to the set list, creates a search tree that represents the sequence of the array as a transition between nodes with the single item group as a final transition destination, and performs the depth-first search for the search tree. In each array, the value associated with the set and the sum of the values of the items of the item group are added together, and when the value exceeds a given threshold, the branch of the node being searched is pruned. And
A combination output means outputs the combination of the set of the array and the item single group including the total value smaller than the threshold;
A combination extraction method characterized by that.

(Additional remark 10) In the combination extraction apparatus which extracts the combination of an item,
Set data storage means for storing a plurality of set data each having a set of items each having a value and a value associated with the set;
A set search means for searching the set data storage means for the set including two or more items in the item data in response to input of item data including a plurality of the items;
The set searched by the set search means and at least one item group composed of the items not included in the set searched by the set search means in the item data in this order A set list creating means for creating a set list having an array;
Referencing the set list, creating a search tree that represents the array sequence as a transition between nodes with the single item group as a final transition destination, and in each array when performing a depth-first search of the search tree, A pruning means for pruning a branch of a node being searched when a value associated with the set and a total value of each of the items of the single item group are added and when a given threshold value is exceeded; ,
A combination output means for outputting a combination of the set of the arrays having the total value smaller than the threshold and the single item group;
A combination extraction apparatus characterized by comprising:

It is a figure which shows the outline | summary of this invention. It is a figure which shows the combination extraction system of embodiment. It is a figure which shows the hardware structural example of a combination extraction apparatus. It is a block diagram which shows the function of a combination extraction apparatus and a terminal device. It is a figure which shows goods data. It is a flowchart which shows operation | movement of a combination extraction apparatus. It is a figure which shows operation | movement of an item decomposition | disassembly part. It is a figure which shows operation | movement of an item decomposition | disassembly part. It is a figure which shows operation | movement of a set search part. It is a figure which shows SetList creation operation | movement of an optimal combination search part. It is a figure which shows the tree structure of a combination search tree. It is a flowchart which shows search operation. It is a figure which shows operation | movement of the item decomposition | disassembly part of 2nd Embodiment. It is a figure which shows operation | movement of the set search part of 2nd Embodiment. It is a figure which shows SetList creation operation | movement of the optimal combination search part of 2nd Embodiment. It is a figure which shows the tree structure of the combination search tree of 2nd Embodiment. It is a figure which shows the item list table of 3rd Embodiment. It is a figure which shows the set list table of 3rd Embodiment. It is a figure which shows operation | movement of an item decomposition | disassembly part. It is a figure which shows operation | movement of a set search part. It is a flowchart which shows the search operation | movement of 3rd Embodiment. It is a figure which shows the tree structure of the combination search tree of 3rd Embodiment. It is a figure which shows the combination extraction result displayed by the result display part.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Computer 2 Set data storage means 3, 3a set 4, 5 set data 6 Set search means 7 Item data 8 Set list preparation means 9 Set list 10 Pruning means 11 Combination output means 30, 40 Product data 50 Product unit price data 60, 60a, 60b Search result data 71-78 Node 100 Combination extraction device 110 Product data reception unit 120 Item decomposition unit 130 Item list storage unit 131, 131a Item list table 140 Set list storage unit 141, 141a, 141b Set list table 150 Set search Unit 160 optimum combination search unit 170 result transmission unit 200 terminal device 210 data transmission unit 220 result display unit 300 extraction system A, B, D set G1 group G2 group L71 77 leaf node T, T1, T2 search tree α threshold

Claims (4)

In a combination extraction program that extracts a combination of items,
Computer
Set data storage means for storing a plurality of set data each having a set of items each having a value and a value associated with the set;
A set search means for searching the set data storage means for the set including two or more items in the item data in response to input of item data including a plurality of the items;
And the set searched by the set retrieval means, when the Ru arranged in this order and configured item alone group by the item that is not included in the retrieved said sets by the set retrieval means in said item data, Among the sets, at least one in which the set is arranged in the order of the set including the items in the item data in the order of the set including the items, and the set including the items in the order of the identifiers attached to the sets. Set list creation means for creating a set list comprising two arrays,
Referencing the set list, creating a search tree that represents the array sequence as a transition between nodes with the single item group as a final transition destination, and in each array when performing a depth-first search of the search tree, A pruning means for pruning the branch of the node being searched when the value associated with the set and the total value of each of the items in the single item group are added, and when the value exceeds a given threshold value,
A combination output means for outputting a combination of the set of the arrays having the total value smaller than the threshold and the item single group;
As a combination extraction program characterized by functioning as   The pruning means, in the array, when the value associated with the set and the total value of each item of the item single group is smaller than the threshold value, the total value is used for the depth-first search thereafter. The combination extraction program according to claim 1, wherein a threshold value is set.   In a combination extraction method for extracting a combination of items,
  The set data storage means stores a plurality of set data each having a set of items each having a value and a value associated with the set;
  A set search means is responsive to an input of item data comprising a plurality of the items, and searches the set data storage means for the set including two or more items in the item data,
  The set list creation means includes the set searched by the set search means and the single item group composed of the items not included in the set searched by the set search means in the item data in this order. Among the sets, in the order of the set including the items in the item data, and in the order of the identifiers attached to the sets for the sets having the same number including the items. Create a setlist with at least one array of
  The pruning means refers to the set list, creates a search tree that represents the sequence of the array as a transition between nodes with the single item group as a final transition destination, and performs the depth-first search for the search tree. In each array, the value associated with the set and the sum of the values of the items of the item group are added together, and when the value exceeds a given threshold, the branch of the node being searched is pruned. And
  A combination output means outputs the combination of the set of the array and the item single group including the total value smaller than the threshold;
  A combination extraction method characterized by that.   In a combination extraction device that extracts a combination of items,
  Set data storage means for storing a plurality of set data each having a set of items each having a value and a value associated with the set;
  A set search means for searching the set data storage means for the set including two or more items in the item data in response to input of item data including a plurality of the items;
  When arranging the set searched by the set search means and the single item group composed of the items not included in the set searched by the set search means in the item data in this order, Among the sets, at least one of the sets including the items in the item data is arranged in the order of the sets including the items, and the sets including the items are arranged in the order of the identifiers attached to the sets. A set list creating means for creating a set list having an array;
  Referencing the set list, creating a search tree that represents the array sequence as a transition between nodes with the single item group as a final transition destination, and in each array when performing a depth-first search of the search tree, A pruning means for pruning a branch of a node being searched when a value associated with the set and a total value of each of the items of the single item group are added and when a given threshold value is exceeded; ,
  A combination output means for outputting a combination of the set of the arrays having the total value smaller than the threshold and the single item group;
  A combination extraction apparatus characterized by comprising:

Images