Patent Publication Number: US-9412093-B2

Title: Computer-readable recording medium, extraction device, and extraction method

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2012-251668, filed on Nov. 15, 2012, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiments discussed herein are related to a computer-readable recording medium, an extraction device, and an extraction method. 
     BACKGROUND 
     There is an extraction device that extracts patterns included in patterns of events represented by event data that have actually occurred. As an example of the event data, there is exemplified event data that represents patterns of events indicating information and answers of a respondent who has replied to one questionnaire. A description will now be made of a case in which the event data includes an event A that “the respondent to the questionnaire is male”, an event B that “the respondent to the questionnaire is aged in the thirties”, and an event C that “the answer to Question 1 of the questionnaire is ‘A1’”. In this case, the extraction device extracts the following patterns. The extraction device extracts, for example, a pattern of the event A, a pattern of the events A and B, a pattern of the events A, B, and C, a pattern of the event B, a pattern of the events B and C, and a pattern of the event C. Extracting these patterns with the extraction device allows a user of the extraction device to understand that the respondent who is male and aged in his thirties has given the reply “A1” to Question 1. 
     The following extraction device is an example of the extraction device described above. For example, an extraction device generates a child from a parent in an enumeration tree and determines whether the generated child occurs in patterns of events represented by event data that have actually occurred, and thus extracts a pattern included in the patterns of events represented by the event data that have actually occurred. Such an extraction device generates a child pattern by adding events to a parent pattern. The extraction device then uses the newly generated child pattern as a parent pattern to generate again a child pattern. In this manner, the extraction device repeats generation of a child pattern until a predetermined condition is satisfied. Conventional examples are described in Japanese Laid-open Patent Publication No. 04-125734 and Japanese Laid-open Patent Publication No. 2009-17340. 
     However, the above-described extraction device has a problem in that it fails to extract patterns efficiently. Specifically, such an extraction device generates a pattern that does not exist as an extracted pattern. A description will be made of a case in which, for example, the following event is added to the parent pattern in addition to the above-described events A, B, and C. Specifically, a description will be made of a case in which there are an event D that “the respondent to the questionnaire is female”, an event E that “the respondent to the questionnaire is aged in the twenties”, and an event F that “the answer to Question 1 of the questionnaire is ‘A2’”. In this case, the events A and D do not occur together in a pattern of events represented by the event data that represents the pattern of events indicating information and answers of a respondent who has replied to one questionnaire. That is because the sex of the respondent is either male or female. In addition, the events B and E do not occur together in such a pattern of events. That is because it is impossible to belong to both generations of the twenties and the thirties. Moreover, when Question 1 of the questionnaire is to be replied in the form of giving one answer, the events C and F do not occur together in such a pattern of events. 
     However, when a parent pattern includes the event A, the above-described extraction device generates a child pattern including the events A and D by adding the event D to the parent pattern. In the same way, when a parent pattern includes the event B, the above-described extraction device generates a child pattern including the events B and E by adding the event E to the parent pattern. When a parent pattern includes the event C, the above-described extraction device generates a child pattern including the events C and F by adding the event F to the parent pattern. In other words, the above-described extraction device generates patterns that include combinations of events that do not occur in events represented by event data, that is, mutually exclusive events. Although the patterns include the combinations of events that do not occur in the events represented by the event data, the above-described extraction device performs unnecessary processing of determining whether such patterns occur in the patterns of the events represented by the event data. This poses a problem in that the above-described extraction device fails to extract patterns efficiently. 
     SUMMARY 
     According to an aspect of an embodiment, a non-transitory computer-readable recording medium stores therein an extraction program that causes a computer to execute a process. The process includes, when a second pattern is to be generated by adding an event to a first pattern including events, generating the second pattern when, based on combinations of events stored in a storage unit, number of occurrence, in the second pattern, of each of the events included in the combinations is not more than a threshold; based on data including a plurality of events stored in the storage unit, calculating a frequency at which the second pattern occurs in the data; extracting the second pattern having the frequency satisfying a predetermined condition; and adding an event to the extracted second pattern. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram illustrating an example of a functional configuration of an extraction device according to a first embodiment of the present invention; 
         FIG. 2  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 3  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 4  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 5  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 6  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 7  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 8  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 9  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment; 
         FIG. 10  is a flowchart illustrating the procedure of an extraction process according to the first embodiment; 
         FIG. 11  is a diagram illustrating an example of a functional configuration of an extraction device according to a second embodiment of the present invention; 
         FIG. 12  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 13  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 14  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 15  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 16  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 17  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 18  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 19  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 20  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 21  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 22  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 23  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 24  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment; 
         FIG. 25  is a flowchart illustrating the procedure of an extraction process according to the second embodiment; 
         FIG. 26  is a diagram illustrating an example of a functional configuration of an extraction device according to a third embodiment of the present invention; 
         FIG. 27  is a diagram for explaining an example of a process executed by the extraction device according to the third embodiment; 
         FIG. 28  is a flowchart illustrating the procedure of an extraction process according to the third embodiment; and 
         FIG. 29  is a diagram illustrating a computer that executes an extraction program. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Preferred embodiments of the present invention will be explained with reference to accompanying drawings. 
     It is to be noted that the embodiments do not limit the technique disclosed herein. 
     [a] First Embodiment 
     Configuration of Extraction Device 
     A description will be made of an extraction device according to a first embodiment of the present invention.  FIG. 1  is a diagram illustrating an example of a functional configuration of the extraction device according to the first embodiment. As illustrated in  FIG. 1 , this extraction device  10  includes an input unit  11 , a display unit  12 , a storage unit  13 , and a control unit  14 . 
     The input unit  11  enters information into the control unit  14 . For example, the input unit  11  accepts an instruction from a user, and enters, into the control unit  14 , an instruction to execute an extraction process to be described later. The input unit  11  also accepts an instruction from the user, and enters, into the control unit  14 , an instruction to acquire event data  13   a  to be described later from a predetermined server. The input unit  11  accepts an operation from the user, and supplies an event table  13   b  to be described later into the control unit  14 . A keyboard and a mouse are examples of devices of the input unit  11 . 
     The display unit  12  displays thereon various types of information. For example, the display unit  12  displays thereon a pattern extracted by an extraction unit  14   f  to be described later under the control of a display control unit  14   g  to be described later. 
     The storage unit  13  stores therein various programs executed by the control unit  14 . An acquisition unit  14   a  to be described later stores the event data  13   a  and the event table  13   b  into the storage unit  13 . 
     The event data  13   a  will now be described. The event data  13   a  is data representing patterns of events that have actually occurred. A description will be made below of a case in which the event data  13   a  represents patterns of events, each of the patterns indicating information and answers of a respondent who has replied to one questionnaire. However, the event data  13   a  can employ data that includes various events, not limited to these events. 
     The patterns of events represented by the event data  13   a  include an event indicated by an identifier A that “the respondent to the questionnaire is male” and an event indicated by an identifier B that “the respondent to the questionnaire is female”. The patterns of events represented by the event data  13   a  also include an event indicated by an identifier C that “there is no information or answer from the respondent to the questionnaire” and an event indicated by an identifier E that “the respondent to the questionnaire is aged in the thirties”. The patterns of events represented by the event data  13   a  do not include an event indicated by an identifier D to be described later that “the respondent to the questionnaire is aged in the twenties”. In the following description, the event indicated by the identifier A will be expressed as an “event A”. In the same way, the event indicated by the identifier B will be expressed as an “event B”; the event indicated by the identifier C will be expressed as an “event C”; the event indicated by the identifier D will be expressed as an “event D”; and the event indicated by the identifier E will be expressed as an “event E”. The patterns of events represented by the event data  13   a  include a pattern in which the event B occurs next to the event A, a pattern in which the event B occurs next to the event A and the event C occurs next to the event B, and a pattern in which the event E occurs next to the event A. The patterns of events represented by the event data  13   a  also include a pattern in which the event C occurs next to the event B and a pattern in which the event E occurs next to the event B. 
     The event table  13   b  will now be described. The event table  13   b  registers therein combinations of events that do not occur in the patterns of events represented by the event data  13   a . The user generates the event table  13   b .  FIG. 2  is a diagram illustrating an example of the event table. The example of  FIG. 2  illustrates the event table  13   b  that has been initialized by an initialization unit  14   b  to be described later. The event table  13   b  illustrated in  FIG. 2  illustrates a case in which the combinations of events that do not occur in the patterns of events represented by the event data  13   a  are registered in a column-wise manner. The event table  13   b  of the example of  FIG. 2  registers therein a combination of the events A, B, and C in a column-wise manner. The event table  13   b  of the example of  FIG. 2  also registers therein the event D that “the respondent to the questionnaire is aged in the twenties”, and the events E and C in a column-wise manner. Specifically, the event table  13   b  indicates that a combination of the events A and B does not occur in the patterns of events represented by the event data  13   a . The event table  13   b  indicates that a combination of the events A and C does not occur in the patterns of events represented by the event data  13   a . The event table  13   b  indicates that a combination of the events A, B, and C does not occur in the patterns of events represented by the event data  13   a . The event table  13   b  indicates that a combination of the events D and E does not occur in the patterns of events represented by the event data  13   a . The event table  13   b  indicates that a combination of the events D and C does not occur in the patterns of events represented by the event data  13   a . The event table  13   b  indicates that a combination of the events D, E, and C does not occur in the patterns of events represented by the event data  13   a.    
     The event table  13   b  is provided with counters  20   a  and  20   b  corresponding to the respective combinations of events that do not occur in the patterns of events represented by the event data  13   a . A counter control unit  14   e  to be described later controls increase and decrease of values registered in the counters  20   a  and  20   b.    
     The storage unit  13  is a storage device, such as a semiconductor memory device including a flash memory, a hard disk, or an optical disc. The storage unit  13  is not limited to the above-described types of storage devices, but may be a random access memory (RAM) or a read-only memory (ROM). 
     The control unit  14  includes an internal memory for storing therein programs defining various processing procedures and control data, and performs various processes using these programs and the control data. As illustrated in  FIG. 1 , the control unit  14  includes the acquisition unit  14   a , an initialization unit  14   b , a generation unit  14   c , a backtrack processing unit  14   d , a counter control unit  14   e , the extraction unit  14   f , and the display control unit  14   g.    
     The acquisition unit  14   a  acquires various types of information. For example, when an instruction to acquire the event data  13   a  from the predetermined server is entered from the input unit  11 , the acquisition unit  14   a  performs the following process based on the instruction. That is, the acquisition unit  14   a  accesses the predetermined server (not illustrated) via a network (not illustrated) to acquire the event data  13   a  from the predetermined server. Then, the acquisition unit  14   a  stores the acquired event data  13   a  into the storage unit  13 . When the event table  13   b  is supplied from the input unit  11 , the acquisition unit  14   a  acquires the supplied event table  13   b , and stores the acquired event table  13   b  into the storage unit  13 . 
     When the instruction to execute the extraction process is entered from the input unit  11 , the acquisition unit  14   a  acquires the event data  13   a  and the event table  13   b  from the storage unit  13 . 
     The initialization unit  14   b  performs various types of initialization. For example, when the acquisition unit  14   a  has acquired the event data  13   a  and the event table  13   b , the initialization unit  14   b  sets a pattern that is empty (empty pattern) as the first parent, that is, the root in an enumeration tree.  FIG. 3  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment. As illustrated in the example of  FIG. 3 , the initialization unit  14   b  sets an empty pattern  40  as a root pattern  30 . 
     Then, the initialization unit  14   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0”. Next, the initialization unit  14   b  sets to “1” the value of a threshold to be used in a process performed by the generation unit  14   c  to be described later to determine whether all of the counters in the columns including selected candidate event e are less than the threshold. 
     The generation unit  14   c  generates various patterns. An embodiment of the generation unit  14   c  will be described. The generation unit  14   c  first selects the root pattern  30 . 
     Then, the generation unit  14   c  determines whether there is any candidate event to be added to the selected pattern. In this case, when any one of the predetermined events A to E is unselected in combinations with the selected pattern, the generation unit  14   c  determines that there is a candidate event to be added to the selected pattern. Note that the present embodiment assumes that the same events are not included in the same pattern. When, instead, none of the predetermined events A to E is unselected in the combinations with the selected pattern, the generation unit  14   c  determines that there is no candidate event to be added to the selected pattern. For example, in the case illustrated in the example of  FIG. 3 , when the root pattern  30  is selected, the predetermined events A to E are all unselected in the combinations with the selected pattern. This causes the generation unit  14   c  to determine that the events A to E to be added to the selected pattern exist. In the case in which display of the display unit  12  is controlled so as to display the pattern using the display control unit  14   g , the generation unit  14   c  determines, in the same way, whether there is a candidate event to be added to the selected pattern. Also, in the case in which the counter control unit  14   e  has decremented a value of a counter in a column of the event table  13   b  by one, the generation unit  14   c  determines, in the same way, whether there is a candidate event to be added to the selected pattern. 
     When there is a candidate event to be added to the selected pattern, the generation unit  14   c  selects one unselected event as the candidate event e. For example, in the example of  FIG. 3 , when the events A to E are to be added to the selected root pattern  30 , the generation unit  14   c  selects the event A having an identifier that is the lowest in alphabetical order among those of the events A to E. Next, the generation unit  14   c  determines whether all of the counters in the columns including the selected candidate event e are less than the threshold “1” in the event table  13   b . For example, in the case illustrated in the example of  FIG. 3 , when the event A is selected, the generation unit  14   c  determines that the value “0” of the counter  20   a  in the column including the selected event A is less than the threshold “1” in the event table  13   b  illustrated in the example of  FIG. 2 . 
     When the generation unit  14   c  does not determine that all of the counters in the columns including the selected candidate event e are less than the threshold “1”, the generation unit  14   c  performs again the above-described process of determining whether there is a candidate event to be added to the selected pattern, and performs again the processes following that process. When, instead, the generation unit  14   c  determines that all of the counters in the columns including the selected candidate event e are less than the threshold “1”, the generation unit  14   c  generates a pattern by adding the selected candidate event e to the selected pattern. Then, the generation unit  14   c  selects the generated pattern.  FIG. 4  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment. For example, as illustrated in the example of  FIG. 4 , the generation unit  14   c  generates a pattern  31  by adding the event A serving as the selected candidate event to the selected pattern  30 . The generation unit  14   c  then selects the generated pattern  31 . After the pattern is generated, the counter control unit  14   e  to be described later increments by one the value of the counter in the column including the candidate event e. 
     In this manner, when all of the counters in the columns including the selected candidate event e are less than the threshold “1”, a pattern is generated by adding the selected candidate event e to the selected pattern. When, instead, it is not determined that all of the counters in the columns including the selected candidate event e are less than the threshold “1”, no pattern is generated. This is because, when it is not determined that all of the counters in the columns including the selected candidate event e are less than the threshold “1”, the combination between the event included in the selected pattern and the selected candidate event e is as follows. That is, the combination between the event included in the selected pattern and the selected candidate event e is a combination of events that does not occur in the patterns of events represented by the event data  13   a . In this manner, the present embodiment does not generate a pattern that includes a combination of events that does not occur in the events represented by the event data  13   a , that is, a pattern that includes mutually exclusive events. This keeps the present embodiment from performing unnecessary processes, such as a process to calculate the frequency of patterns including combinations of events that do not occur in the patterns of events represented by the event data  13   a  and a process to determine whether such patterns occur frequently. This, in turn, allows the present embodiment to efficiently extract the patterns. The process may be called “pruning” in which no pattern is generated when it is not determined that all of the counters in the columns including the selected candidate event e are less than the threshold “1”. 
     If, as a result of the determination of whether there is a candidate event to be added to the selected pattern, there is no candidate event to be added, the generation unit  14   c  determines whether all the patterns are generated except patterns that are no longer generated because of the pruning. If all the patterns are generated except patterns that are no longer generated because of the pruning, the process is terminated. 
     The backtrack processing unit  14   d  performs backtracking. For example, when the extraction unit  14   f  determines that the pattern generated by the generation unit  14   c  does not occur frequently, the backtrack processing unit  14   d  deletes the last added event e from the pattern generated by the generation unit  14   c  to generate a pattern. Then, the backtrack processing unit  14   d  selects the generated pattern. When the generation unit  14   c  does not determine that all the patterns are generated except patterns that are no longer generated because of the pruning, the backtrack processing unit  14   d  also performs the same processing. That is, the generation unit  14   c  deletes the last added event e from the selected pattern to generate a pattern, and selects the generated pattern. 
     When the generation unit  14   c  has generated a pattern, the counter control unit  14   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e having been added when the pattern was generated.  FIG. 5  is a diagram for explaining an example of a process executed by the extraction device according to the first embodiment. For example, when the generation unit  14   c  has generated the pattern  31  illustrated in  FIG. 4 , the counter control unit  14   e  increments by one the value of the counter  20   a  in the column of the event table  13   b  including the event A that was added when the pattern  31  was generated as illustrated in  FIG. 5 . 
     The counter control unit  14   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  14   d.    
     When the counter control unit  14   e  has incremented the value of the counter in the column including the candidate event e by one, the extraction unit  14   f  calculates the frequency of the generated pattern. For example, the extraction unit  14   f  calculates the frequency to have a value of “1” if the generated pattern occurs in the patterns of events represented by the event data  13   a , or to have a value of “0” if the generated pattern does not occur therein. Then, the extraction unit  14   f  determines whether the generated pattern occurs frequently by determining whether the calculated frequency is “1”. If the calculated frequency is “1”, the extraction unit  14   f  determines that the generated pattern occurs frequently. If the calculated frequency is not “1”, that is, “0”, the extraction unit  14   f  determines that the generated pattern does not occur frequently. For example, when the generated pattern is the pattern  31  including the event A as illustrated in the example of  FIG. 4 , the extraction unit  14   f  calculates the frequency to have a value of “1” because the event A occurs in the patterns of events represented by the event data  13   a  as described above. Then, the extraction unit  14   f  determines that the generated pattern  31  occurs frequently because the calculated frequency is “1”. 
     The extraction unit  14   f  extracts, as a pattern to be displayed, the pattern that is determined to occur frequently. For example, the extraction unit  14   f  extracts, as the pattern to be displayed, the pattern  31  illustrated in  FIG. 4 , which is determined to occur frequently. 
     The display control unit  14   g  controls the display of the display unit  12  so as to display various types of information. For example, the display control unit  14   g  controls the display of the display unit  12  so as to display the pattern, such as the pattern  31 , extracted by the extraction unit  14   f.    
     A description will next be made of specific examples of processes executed by the extraction device  10  with reference to  FIGS. 4 and 5  mentioned above, and  FIGS. 6 to 9 .  FIGS. 6 to 9  are diagrams for explaining examples of processes executed by the extraction device according to the first embodiment. 
     For example, after the pattern  31  is displayed on the display unit  12 , the extraction device  10  selects, in the case illustrated in  FIG. 4 , the event B that serves as a candidate event to be added to the selected pattern  31 . Then, the extraction device  10  selects the event C that serves as a candidate event to be added to the selected pattern  31 , because the counter  20   a  corresponding to the column of the event table  13   b  including the selected event B has the value of “1”, which is not less than the threshold “1”. 
     The counter  20   a  corresponding to the column of the event table  13   b  including the selected event C has the value of “1”, which is not less than the threshold “1”. Accordingly, the extraction device  10  selects the event D that serves as a candidate event to be added to the selected pattern  31 . The counter  20   b  corresponding to the column of the event table  13   b  including the selected event D has the value of “0”, which is less than the threshold “1”, as illustrated in  FIG. 5 . Therefore, the extraction device  10  subsequently performs the following process. That is, as illustrated in  FIG. 6 , the extraction device  10  adds the event D serving as the candidate event to the selected pattern  31  to generate a pattern  32 . Then, as illustrated in  FIG. 7 , the extraction device  10  increments by one the value of the counter  20   b  of the event table  13   b , the counter  20   b  including the event D in the column thereof. 
     The pattern  32  including the event D does not occur frequently. Therefore, the extraction device  10  deletes the event D from the pattern  32  to generate the pattern  31  as illustrated in  FIG. 8 , and decrements the value of the counter  20   b  by one as illustrated in  FIG. 5 . Then, the extraction device  10  selects the event E that serves as a candidate event to be added to the pattern  31 . The extraction device  10  then adds the event E to the pattern  31  to generate a pattern  33  as illustrated in  FIG. 9  because the counter  20   b  corresponding to the column of the event table  13   b  including the selected event E has the value of “0”, which is less than the threshold “1”, as illustrated in  FIG. 5 . No event can be added to the pattern  33 . Therefore, the extraction device  10  performs backtracking from the pattern  33 , and continues the process. At the time illustrated in  FIG. 9 , the extraction device  10  has extracted the pattern  31  including the event A and the pattern  33  including the events A and E. 
     The control unit  14  is an integrated circuit such as an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA), or an electronic circuit such as a central processing unit (CPU) or a microprocessing unit (MPU). 
     Procedure of Processes 
     A description will next be made of the procedure of the processes of the extraction device  10  according to the present embodiment.  FIG. 10  is a flowchart illustrating the procedure of the extraction process according to the first embodiment. Various types of timing can be considered as execution timing of the extraction process. For example, the control unit  14  executes the extraction process when an instruction to execute the extraction process is entered from the input unit  11 . 
     As illustrated in  FIG. 10 , the acquisition unit  14   a  acquires the event data  13   a  from the storage unit  13  (S 101 ). Then, the acquisition unit  14   a  acquires the event table  13   b  from the storage unit  13  (S 102 ). 
     Next, the initialization unit  14   b  sets an empty pattern as the first parent, that is, the root in the enumeration tree (S 103 ). Then, the initialization unit  14   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0” (S 104 ). Next, the initialization unit  14   b  sets to “1” the value of the threshold to be used in the process at S 109  (S 105 ). 
     The generation unit  14   c  selects the root pattern  30  (S 106 ). Then, the generation unit  14   c  determines whether there is any candidate event to be added to the selected pattern (S 107 ). 
     If there is a candidate event to be added to the selected pattern (Yes at S 107 ), the generation unit  14   c  selects one unselected event as the candidate event e (S 108 ). Then, the generation unit  14   c  determines whether all of the counters in the columns including the selected candidate event e are less than the threshold “1” in the event table  13   b  (S 109 ). 
     If at least one of the counters in the columns including the selected candidate event e has a value not less than the threshold “1” (No at S 109 ), the generation unit  14   c  returns to S 107 . If, instead, all of the counters in the columns including the selected candidate event e are less than the threshold “1”, the generation unit  14   c  generates a pattern by adding the selected candidate event e to the selected pattern (S 110 ). Then, the generation unit  14   c  selects the generated pattern (S 111 ). 
     The counter control unit  14   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e that was added when the pattern was generated (S 112 ). The extraction unit  14   f  calculates the frequency of the generated pattern (S 113 ). Then, the extraction unit  14   f  determines whether the generated pattern occurs frequently by determining whether the calculated frequency is “1” (S 114 ). If the calculated frequency is “1” (Yes at S 114 ), the extraction unit  14   f  extracts, as a pattern to be displayed, the pattern that is determined to occur frequently (S 115 ). Then, the display control unit  14   g  controls the display of the display unit  12  so as to display the pattern extracted by the extraction unit  14   f  (S 116 ), and the process returns to S 107 . 
     If the calculated frequency is not “1” (No at S 114 ), the backtrack processing unit  14   d  deletes the last added event e from the pattern generated by the generation unit  14   c  to generate a pattern (S 117 ). Then, the backtrack processing unit  14   d  selects the generated pattern (S 118 ). Thereafter, the counter control unit  14   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  14   d  (S 119 ), and the process returns to S 107 . 
     If there is no candidate event to be added (No at S 107 ), the generation unit  14   c  determines whether all the patterns are generated except patterns that are no longer generated because of the pruning (S 120 ). If all the patterns are generated except patterns that are no longer generated because of the pruning (Yes at S 120 ), the process is terminated. If any pattern is not generated among all the patterns except patterns that are no longer generated because of the pruning (No at S 120 ), the process proceeds to S 117 . 
     As described above, when a new pattern is to be generated by adding an event to a pattern including an event or events, the extraction device  10  according to the present embodiment performs the following process based on the event table  13   b  stored in the storage unit  13  and indicating combinations of mutually exclusive events. That is, the extraction device  10  generates a new pattern if the number of occurrence, in the new pattern, of each of the events included in the combinations is not more than the threshold “1”. Then, based on the event data  13   a  stored in the storage unit  13  and including a plurality of events, the extraction device  10  calculates the frequency at which one or more generated patterns occur in the event data  13   a . Next, the extraction device  10  extracts a new pattern whose frequency satisfies a predetermined condition. Thereafter, the extraction device  10  adds a new event to the extracted new pattern. Consequently, the extraction device  10  does not generate a pattern that includes a combination of events that does not occur in the events represented by the event data  13   a , that is, a pattern that includes mutually exclusive events. This keeps the extraction device  10  from performing unnecessary processes, such as the process to calculate the frequency of patterns including combinations of events that do not occur in the patterns of events represented by the event data  13   a  and the process to determine whether such patterns occur frequently. This, in turn, allows the extraction device  10  according to the present embodiment to efficiently extract the patterns. 
     Second Embodiment 
     Configuration of Extraction Device 
     A description will next be made of an extraction device according to a second embodiment of the present invention. As illustrated in  FIG. 11 , this extraction device  41  includes a storage unit  43  and a control unit  44 . The storage unit  43  differs from the storage unit  13  according to the first embodiment illustrated in  FIG. 1  in that the storage unit  43  stores therein event data  43   a  instead of the event data  13   a  as memory contents. The control unit  44  differs from the control unit  14  according to the first embodiment illustrated in  FIG. 1  in that the control unit  44  includes an initialization unit  44   b , a generation unit  44   c , a backtrack processing unit  44   d , a counter control unit  44   e , and an extraction unit  44   f . Note that, hereinafter, the same numerals as those in  FIG. 1  will be given to units and devices performing the same functions as those of the first embodiment above, and descriptions thereof may be omitted. 
     The input unit  11  enters information into the control unit  44 . For example, the input unit  11  accepts an instruction from the user, and enters, into the control unit  44 , an instruction to execute the extraction process. The input unit  11  also accepts an instruction from the user, and enters, into the control unit  44 , an instruction to acquire the event data  43   a  to be described later from a predetermined server. The input unit  11  accepts an operation from the user, and supplies the event table  13   b  into the control unit  44 . A keyboard and a mouse are examples of devices of the input unit  11 . 
     The display unit  12  displays thereon various types of information. For example, the display unit  12  displays thereon an episode extracted by the extraction unit  44   f  to be described later under the control of the display control unit  14   g  to be described later. 
     The storage unit  43  stores therein various programs executed by the control unit  44 . The acquisition unit  14   a  to be described later stores the event data  43   a  and the event table  13   b  into the storage unit  43 . 
     The event data  43   a  will now be described. The event data  43   a  is data in which an event that has actually occurred is associated with the time at which the event occurred. A description will be made below of a case in which the event data  43   a  includes a plurality of pieces of data each of which represents a pattern of events indicating information and answers of a respondent who has replied to one questionnaire. However, the event data  43   a  is not limited to that case. The event data  43   a  can employ data that includes various types of events. To describe it with a specific example, the event data  43   a  includes data that represents patterns of events indicating information and answers of respondents who have replied to a plurality of questionnaires that differ between times of occurrence. Therefore, although the above-mentioned pattern of a combination of mutually exclusive events does not occur in the event data  13   a  representing a pattern of events indicating information and answers of a respondent who has replied to one questionnaire, the pattern of a combination of mutually exclusive events can occur in the event data  43   a.    
     Hereinafter, the patterns of events represented by the event data  43   a  include the events A, B, C, and E, but do not include the event D. The patterns of events represented by the event data  43   a  include a pattern in which the event B occurs next to the event A, a pattern in which the event B occurs next to the event A and the event C occurs next to the event B, and a pattern in which the event E occurs next to the event A. The patterns of events represented by the event data  43   a  also include a pattern in which the event C occurs next to the event B and a pattern in which the event E occurs next to the event B. 
     The storage unit  43  is a storage device such as a semiconductor memory device including a flash memory, a hard disk, or an optical disc. The storage unit  43  is not limited to the above-described types of storage devices, but may be a random access memory (RAM) or a read-only memory (ROM). 
     The control unit  44  includes an internal memory for storing therein programs defining various processing procedures and control data, and performs various processes using these programs and the control data. The control unit  44  includes the acquisition unit  14   a , the initialization unit  44   b , the generation unit  44   c , the backtrack processing unit  44   d , the counter control unit  44   e , the extraction unit  44   f , and the display control unit  14   g.    
     The acquisition unit  14   a  acquires various types of information. For example, when an instruction to acquire the event data  43   a  from the predetermined server is entered from the input unit  11 , the acquisition unit  14   a  performs the following process based on the instruction. That is, the acquisition unit  14   a  accesses the predetermined server (not illustrated) via a network (not illustrated) to acquire the event data  43   a  from the predetermined server. Then, the acquisition unit  14   a  stores the acquired event data  43   a  into the storage unit  43 . When the event table  13   b  is supplied from the input unit  11 , the acquisition unit  14   a  acquires the supplied event table  13   b , and stores the acquired event table  13   b  into the storage unit  43 . 
     When an instruction to execute the extraction process is entered from the input unit  11 , the acquisition unit  14   a  acquires the event data  43   a  and the event table  13   b  from the storage unit  43 . 
     The initialization unit  44   b  performs various types of initialization. For example, when the acquisition unit  14   a  has acquired the event data  43   a  and the event table  13   b , the initialization unit  44   b  sets an episode that is empty (empty episode) as the first parent, that is, the root in the enumeration tree. Here, the episode is expressed in a form of a directed graph representing an order (occurrence order) in which events occur. For example, the episode includes a plurality of parts. Each of the parts includes events. Each of the parts is given an order. A description will now be made of a relation between events included in an N-th part and events included in an (N+1)-th part included in the episode. In the relation between the events included in the N-th part and the events included in the (N+1)-th part, the events included in the (N+1)-th part occur after all of the events included in the N-th part occur.  FIG. 12  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment. As illustrated in the example of  FIG. 12 , the initialization unit  44   b  sets an empty episode  50  as a root episode  60 . 
     Then, the initialization unit  44   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0”. Next, the initialization unit  44   b  sets, to a value described below, the value of a threshold to be used in a process performed by the generation unit  44   c  to be described later to determine whether all of the counters in the columns including selected candidate event e are less than the threshold. That is, the initialization unit  44   b  sets the value of the threshold to a value of a window width that is used when an episode is extracted and that is a temporal width used in searching for an event pattern of the event data  43   a . The window width is, for example, “2” in the case of attempting to extract event patterns that have occurred during time (2 to 3) from time “2” to time “3”. Although a case will be described below in which the window width is “2”, the window width is not limited to this. 
     The generation unit  44   c  generates various episodes. An embodiment of the generation unit  44   c  will be described. The generation unit  44   c  first selects the root episode  50 . 
     Then, the generation unit  44   c  determines whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. In the present embodiment, a case will be described in which the empty episode  50  includes a first part and a second part. The empty episode  50  includes the two parts, and therefore, a descendant episode of the empty episode  50  also includes the two parts. In this case, when there is any unselected event among the predetermined events A to E in a combination with either of the parts of the selected episode, the generation unit  44   c  determines that there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. Note that the present embodiment assumes that the same events are not included in the same part. When, instead, there is no unselected event among the predetermined events A to E in either of the combinations with the parts of the selected episode, the generation unit  44   c  determines that there is no candidate event to be added to the selected episode. For example, when the root episode  60  illustrated in  FIG. 12  is selected, there are unselected events A to E among the predetermined events A to E in any combination with either of the parts of the episode  60 . This causes the generation unit  44   c  to determine that there are the events A to E to be added to a part of the selected episode  60  and a part (the first part and the second part) to which the events are to be added. In the case in which display of the display unit  12  is controlled so as to display the episode by the display control unit  14   g , the generation unit  44   c  determines, in the same way, whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. Also, in the case in which the counter control unit has decremented the value of the counter in the column of the event table  13   b  by one, the generation unit  44   c  determines, in the same way, whether there are a candidate event to be added to the selected episode and a part to which the event is to be added. 
     When there are a candidate event to be added to the selected episode and a part to which the event is to be added, the generation unit  44   c  selects one unselected event as the candidate event e and selects one candidate part. For example, in the example of  FIG. 12 , when the events A to E to be added to the selected episode  60  and the first and the second parts to which the events are to be added exist, the generation unit  44   c  selects the event A having an identifier that is the lowest in alphabetical order among those of the events A to E. In addition, the generation unit  44   c  selects the first part that has a smaller order number between the first and the second parts to which the event can be added. Next, the generation unit  44   c  determines whether all of the counters in the columns including the selected candidate event e are less than a threshold “2” in the event table  13   b . For example, in the case illustrated in the example of  FIG. 13 , when the event A is selected, the generation unit  44   c  determines that the value “0” of the counter  20   a  in the column including the selected event A is less than the threshold “2” in the event table  13   b  illustrated in the above example of  FIG. 2 . 
     When at least one of the counters in the columns including the selected candidate event e has a value not less than the threshold “2”, the generation unit  44   c  performs again the above-described process to determine whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. Then, the generation unit  44   c  performs again the processes following that process. When, instead, all of the counters in the columns including the selected candidate event e are less than the threshold “2”, the generation unit  44   c  generates an episode by adding the selected candidate event e to the selected candidate part of the selected episode. Then, the generation unit  44   c  selects the generated episode.  FIG. 13  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment. For example, as illustrated in the example of  FIG. 13 , the generation unit  44   c  generates an episode  61  by adding the event A that is the selected candidate event to the selected candidate part of the selected episode  60 . The generation unit  44   c  then selects the generated episode  61 . After the episode is generated, the counter control unit  44   e  to be described later increments by one the value of the counter in the column including the candidate event e. 
     In this manner, when all of the counters in the columns including the selected candidate event e are less than the threshold “2”, an episode is generated by adding the selected candidate event e to the selected part of the selected episode. When the present embodiment does not determine that all of the counters in the columns including the selected candidate event e are less than the threshold “2”, no new episode is generated. That is, as described above, the event data  43   a  includes data that represents patterns of events indicating information and answers of respondents who have replied to a plurality of questionnaires. Therefore, a combination of events that does not occur in the patterns of events represented by the event data  13   a  occurs in the patterns of events represented by the event data  43   a . Therefore, the present embodiment does not generate a pattern that includes a number (larger than the size of the window width) of combinations of events that do not occur in the events represented by the event data  43   a , that is, a pattern that includes mutually exclusive events. This keeps the present embodiment from performing unnecessary processes, such as the process to calculate the frequency of patterns including combinations of events that do not occur in the patterns of events represented by the event data  43   a  and the process to determine whether such patterns occur frequently. This, in turn, allows the present embodiment to efficiently extract the patterns. The process may be called “pruning” in which no episode is generated when it is not determined that all of the counters in the columns including the selected candidate event e are less than the threshold “2”. 
     If, as a result of the determination of whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added, there is no candidate event to be added or no candidate part to which the event is to be added, the generation unit  44   c  performs the following process. That is, the generation unit  44   c  determines whether all the episodes are generated except episodes that are no longer generated because of the pruning. If all the episodes are generated except episodes that are no longer generated because of the pruning, the process is terminated. 
     The backtrack processing unit  44   d  performs backtracking. For example, when the extraction unit  44   f  determines that an episode generated by the generation unit  44   c  does not occur frequently, the backtrack processing unit  44   d  deletes the last added event e from the episode generated by the generation unit  44   c  to generate an episode. Then, the backtrack processing unit  44   d  selects the generated episode. When the generation unit  44   c  does not determine that all the episodes are generated except episodes that are no longer generated because of the pruning, the backtrack processing unit  44   d  also performs the same processing. That is, the backtrack processing unit  44   d  deletes the last added event e from the selected episode to generate an episode, and selects the generated episode. 
     When the generation unit  44   c  has generated an episode, the counter control unit  44   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e that was added when the episode was generated.  FIG. 14  is a diagram for explaining an example of a process executed by the extraction device according to the second embodiment. For example, when the generation unit  44   c  has generated the episode  61  illustrated in  FIG. 13 , the counter control unit  44   e  increments by one the value of the counter  20   a  in the column of the event table  13   b  including the event A that was added when the episode  61  was generated as illustrated in  FIG. 14 . 
     The counter control unit  44   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  44   d.    
     When the counter control unit  44   e  has incremented the value of the counter in the column including the candidate event e by one, the extraction unit  44   f  calculates the frequency of the generated episode. For example, the extraction unit  44   f  calculates, as the frequency, a value of “1” if a minimal occurrence of the generated episode exists, or a value of “0” if no minimal occurrence of the generated episode exists. Here, the minimal occurrence refers to the minimum time interval during which events ranging from the event in the part at the start of the episode to the event in the part at the end of the episode exist in a pattern of events represented by the event data  43   a . The frequency is also called “binary frequency”. The generation unit  44   c  determines whether the calculated frequency is “1”. If the calculated frequency is “1”, the generation unit  44   c  determines that the episode occurs frequently. If the calculated frequency is not “1”, that is, “0”, the generation unit  44   c  determines that the episode does not occur frequently. 
     Although a case will be described below in which the device disclosed herein calculates the “binary frequency” as the frequency, the device disclosed herein is not limited to this. For example, if the frequency is such that the frequency of children is not more than the frequency of parents in the enumeration tree, the device disclosed herein can calculate a frequency other than the binary frequency, and, based on the calculated frequency, can determine whether the episode occurs frequently. A “window frequency” is an example of such a frequency. The “window frequency” refers to the number of intervals including the minimal occurrence among a predetermined set of intervals, or the number of intervals including the minimal occurrence among a set of a plurality of intervals in which adjacent intervals partially overlap each other. In the case of calculating the “window frequency” as the frequency, the extraction unit  44   f  can determine whether the episode occurs frequently by determining whether the “window frequency” of the episode is a predetermined threshold or more. 
     A “non-overlapping minimal occurrence frequency” is another example. The “non-overlapping minimal occurrence frequency” refers to the maximum number of minimal occurrences that do not overlap each other in time (that do not include the same time as each other). In the case of calculating the “non-overlapping minimal occurrence frequency” as the frequency, the extraction unit  44   f  can determine whether the episode occurs frequently by determining whether the “non-overlapping minimal occurrence frequency” of the episode is a predetermined threshold or more. The extraction unit  44   f  extracts, as an episode to be displayed, the episode that is determined to occur frequently. For example, the extraction unit  44   f  extracts, as the episode to be displayed, the episode  61  illustrated in  FIG. 13  that is determined to occur frequently. 
     The display control unit  14   g  controls the display of the display unit  12  so as to display various types of information. For example, the display control unit  14   g  controls the display of the display unit  12  so as to display the episode, such as the episode  61 , extracted by the extraction unit  44   f.    
     A description will next be made of specific examples of processes executed by the extraction device  41  with reference to  FIGS. 12 to 14  mentioned above, and  FIGS. 15 to 24 .  FIGS. 15 to 24  are diagrams for explaining examples of processes executed by the extraction device according to the second embodiment. For example, after the episode  61  is displayed on the display unit  12 , the extraction device  41  selects, in the case illustrated in  FIG. 13 , the event B that serves as a candidate event to be added to the selected episode  61  and the (first or second) part to which the event is to be added. Here, the value of the counter  20   a  corresponding to the column of the event table  13   b  including the selected event B is “1”, which is less than the threshold “2”. Accordingly, as illustrated in  FIG. 15 , the extraction device  41  adds the event B to the selected part of the selected episode  61  to generate an episode  62 . Then, as illustrated in  FIG. 16 , the extraction device  41  increments by one the value of the counter  20   a  in the column of the event table  13   b  including the event B. The extraction device  41  then calculates the frequency of the episode  62  to be “1”, and determines that the episode  62  occurs frequently. Next, the extraction device  41  extracts the episode  62 , and controls the display unit  12  so as to display the extracted episode  62 . Thereafter, the extraction device  41  selects the event C that serves as a candidate event to be added to the episode  62 , and the part to which the event is to be added. 
     However, as illustrated in  FIG. 16 , the value “2” of the counter  20   a  corresponding to the column including the event C is not less than the threshold “2”. Accordingly, the extraction device  41  selects the event D that serves as a candidate event to be added to the episode  62 , and the part to which the event is to be added. As illustrated in  FIG. 16 , the value “0” of the counter  20   b  corresponding to the column including the event D is less than the threshold “2”. Therefore, the extraction device  41  performs the following process. That is, as illustrated in  FIG. 17 , the extraction device  41  adds the event D to the selected part of the episode  62  to generate an episode  63 . Next, as illustrated in  FIG. 18 , the extraction device  41  increments by one the value of the counter  20   b  in the column of the event table  13   b  including the candidate event D that was added when the episode  63  was generated. The extraction device  41  then calculates the frequency of the episode  63  to be “0”, and determines that the episode  63  does not occur frequently. Then, as illustrated in  FIG. 19 , the extraction device  41  deletes the last added event D from the episode  63  to generate the episode  62 . As illustrated in  FIG. 16 , the extraction device  41  decrements by one the value of the counter  20   b  in the column of the event table  13   b  including the deleted event D. 
     Then, the extraction device  41  selects the event E that serves as a candidate event to be added to the episode  62 , and the part to which the event is to be added. As illustrated in  FIG. 16 , the value “0” of the counter  20   b  corresponding to the column of the event table  13   b  including the selected event E is less than the threshold “2”. Accordingly, the extraction device  41  adds the event E to the selected part of the episode  62  to generate an episode  64  as illustrated in  FIG. 20 . Next, as illustrated in  FIG. 18 , the extraction device  41  increments by one the value of the counter  20   b  in the column of the event table  13   b  including the candidate event E that was added when the episode  64  was generated. The extraction device  41  then calculates the frequency of the episode  64  to be “1”, and determines that the episode  64  occurs frequently. Next, the extraction device  41  extracts the episode  64 , and controls the display unit  12  so as to display the extracted episode  64 . There is no candidate event to be added to the episode  64 . Therefore, as illustrated in  FIG. 21 , the extraction device  41  generates the episode  62  by deleting the event E last added to the episode  64 . As illustrated in  FIG. 16 , the extraction device  41  decrements by one the value of the counter  20   b  in the column of the event table  13   b  including the deleted event E. 
     There is no candidate event to be added to the episode  62 . Therefore, as illustrated in  FIG. 22 , the extraction device  41  generates the episode  61  by deleting the event B last added to the episode  62  from the episode  62 . As illustrated in  FIG. 14 , the extraction device  41  decrements by one the value of the counter  20   a  in the column of the event table  13   b  including the deleted event B. Next, the extraction device  41  selects the event C that serves as a candidate event to be added to the episode  61 , and the part to which the event is to be added. As illustrated in  FIG. 14 , the counters  20   a  and  20   b  corresponding to the columns of the event table  13   b  including the selected event C have values “1” and “0”, respectively, which are less than the threshold “2”. Accordingly, as illustrated in  FIG. 23 , the extraction device  41  adds the event C to the selected part of the episode  61  to generate an episode  65 . 
     Next, as illustrated in  FIG. 18 , the extraction device  41  increments by one each of the values of the counters  20   a  and  20   b  corresponding to the columns of the event table  13   b  including the event C that was added when the episode  65  was generated. The extraction device  41  then calculates the frequency of the episode  65  to be “0”, and determines that the episode  65  does not occur frequently. Then, as illustrated in  FIG. 24 , the extraction device  41  generates the episode  61  by deleting the event C last added to the episode  65  from the episode  65 . Then, as illustrated in  FIG. 14 , the extraction device  41  decrements by one each of the values of the counters  20   a  and  20   b  in the columns of the event table  13   b  including the deleted event C. The extraction device  41  subsequently continues performing various processes. 
     The control unit  44  is an integrated circuit such as an ASIC or an FPGA, or an electronic circuit such as a CPU or an MPU. 
     Procedure of Processes 
     A description will next be made of the procedure of the processes of the extraction device  41  according to the present embodiment.  FIG. 25  is a flowchart illustrating the procedure of the extraction process according to the second embodiment. Various types of timing can be considered as execution timing of the extraction process. For example, the control unit  44  executes the extraction process when an instruction to execute the extraction process is entered from the input unit  11 . 
     As illustrated in  FIG. 25 , the acquisition unit  14   a  acquires the event data  43   a  from the storage unit  43  (S 201 ). Next, the acquisition unit  14   a  acquires the event table  13   b  from the storage unit  43  (S 202 ). 
     Next, the initialization unit  44   b  sets an empty episode as the first parent, that is, the root in the enumeration tree (S 203 ). Then, the initialization unit  44   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0” (S 204 ). Next, the initialization unit  44   b  sets the value of the threshold to be used in the process at S 209  to the window width (S 205 ). 
     The generation unit  44   c  selects the root episode  60  (S 206 ). Then, the generation unit  44   c  determines whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added (S 207 ). 
     If there are a candidate event to be added to the selected episode and a candidate part (Yes at S 207 ), the generation unit  44   c  selects one unselected event as the candidate event e and selects one candidate part (S 208 ). Next, the generation unit  44   c  determines whether all of the counters in the columns including the selected candidate event e are less than the threshold “2” in the event table  13   b  (S 209 ). 
     If at least one of the counters in the columns including the selected candidate event e has a value not less than the threshold “2” (No at S 209 ), the generation unit  44   c  returns to S 207 . If, instead, all of the counters in the columns including the selected candidate event e are less than the threshold “2” (Yes at S 209 ), the generation unit  44   c  generates an episode by adding the selected candidate event e to the selected episode (S 210 ). Then, the generation unit  44   c  selects the generated episode (S 211 ). 
     The counter control unit  44   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e that was added when the selected episode was generated (S 212 ). The extraction unit  44   f  calculates the frequency of the generated episode (S 213 ). Then, the extraction unit  44   f  determines whether the generated episode occurs frequently by determining whether the calculated frequency is “1” (S 214 ). If the calculated frequency is “1” (Yes at S 214 ), the extraction unit  44   f  extracts, as an episode to be displayed, the episode that is determined to occur frequently (S 215 ). Then, the display control unit  14   g  controls the display of the display unit  12  so as to display the episode extracted by the extraction unit  44   f  (S 216 ), and the process returns to S 207 . 
     If the calculated frequency is not “1” (No at S 214 ), the backtrack processing unit  44   d  deletes the last added event e from the episode generated by the generation unit  44   c  to generate an episode (S 217 ). Then, the backtrack processing unit  44   d  selects the generated episode (S 218 ). Thereafter, the counter control unit  44   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  44   d  (S 219 ), and the process proceeds to S 207 . 
     If there is no candidate event to be added or no candidate part to which the event is to be added (No at S 207 ), the generation unit  44   c  determines whether all the episodes are generated except episodes that are no longer generated because of the pruning (S 220 ). If all the episodes are generated except episodes that are no longer generated because of the pruning (Yes at S 220 ), the process is terminated. If any episode is not generated among all the episodes except episodes that are no longer generated because of the pruning (No at S 220 ), the process proceeds to S 217 . 
     As described above, the extraction device  41  according to the present embodiment performs the following process when generating a new episode. That is, the extraction device  41  generates a new pattern if the number of occurrence, in the new episode, of each of the events included in the combinations of mutually exclusive events indicated by the event table  13   b  is not more than the threshold “2” determined based on a predetermined window width. Then, based on the events associated with occurrence times thereof within the window width, the extraction device  41  calculates the frequency. In this manner, the extraction device  41  does not generate an episode that includes a number (larger than the size of the window width) of events included in combinations of events that do not occur in the events represented by the event data  43   a . This keeps the extraction device  41  from performing unnecessary processes, such as a process to calculate the frequency of episodes including combinations of events that do not occur in the patterns of events represented by the event data  43   a  and a process to determine whether such episodes occur frequently. This, in turn, allows the extraction device  41  to efficiently extract the episodes. 
     Third Embodiment 
     Configuration of Extraction Device 
     A description will next be made of an extraction device according to a third embodiment of the present invention. As illustrated in  FIG. 26 , an extraction device  70  includes a control unit  74 . The control unit  74  differs from the control unit  44  according to the second embodiment illustrated in  FIG. 11  in that the control unit  74  includes an initialization unit  74   b , a generation unit  74   c , a backtrack processing unit  74   d , a counter control unit  74   e , and an extraction unit  74   f . Note that, hereinafter, the same numerals as those in  FIGS. 1 and 11  will be given to units and devices performing the same functions as those of the first and the second embodiment above, and descriptions thereof may be omitted. 
     The input unit  11  enters information into the control unit  74 . For example, the input unit  11  accepts an instruction from the user, and enters, into the control unit  74 , an instruction to execute the extraction process. The input unit  11  also accepts an instruction from the user, and enters, into the control unit  74 , an instruction to acquire the event data  43   a  to be described later from a predetermined server. The input unit  11  accepts an operation from the user, and supplies the event table  13   b  into the control unit  74 . A keyboard and a mouse are examples of devices of the input unit  11 . 
     The display unit  12  displays thereon various types of information. For example, the display unit  12  displays thereon an episode extracted by the extraction unit  74   f  to be described later under the control of the display control unit  14   g  to be described later. 
     The control unit  74  includes an internal memory for storing therein programs defining various processing procedures and control data, and performs various processes using these programs and the control data. The control unit  74  includes the acquisition unit  14   a , the initialization unit  74   b , the generation unit  74   c , the backtrack processing unit  74   d , the counter control unit  74   e , the extraction unit  74   f , and the display control unit  14   g.    
     The initialization unit  74   b  performs various types of initialization. For example, when the acquisition unit  14   a  has acquired the event data  43   a  and the event table  13   b , the initialization unit  74   b  sets an empty episode as the first parent, that is, the root in the enumeration tree. The initialization unit  74   b  sets a definite portion to be described later to be empty. 
     Then, the initialization unit  74   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0”. Next, the initialization unit  74   b  sets, to the value of the window width, the value of a threshold to be used in a process performed by the generation unit  74   c  to be described later to determine whether all of the counters in the columns including the selected candidate event e are less than the threshold. 
     The generation unit  74   c  generates various episodes. An embodiment of the generation unit  74   c  will be described. The generation unit  74   c  first selects the root episode  50  as illustrated in  FIG. 12  mentioned above. 
     Then, the generation unit  74   c  determines whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. Here, in the present embodiment, the event is added behind or in front of the definite portion. The definite portion refers to an event group or a part of an episode whose descendant episode is to have no new event added thereto. The following description gives an example in which the event is added behind the definite portion. In the present embodiment, a case will be described in which the empty episode  50  includes the first to the third parts. The present embodiment assumes that the same events are not included in the same part. When there is any unselected candidate event among the predetermined events A to E in combinations with the parts behind the definite portion of the selected episode, the generation unit  74   c  determines that there is a candidate event to be added to the selected episode. When, instead, there is no unselected candidate event among the predetermined events A to E in the combinations with the parts behind the definite portion, the generation unit  74   c  determines that there is no candidate event to be added to the selected episode. 
     In the case in which the display of the display unit  12  is controlled so as to display the episode using the display control unit  14   g , the generation unit  74   c  also determines whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. In the case in which the backtrack processing unit  74   d  determines that the deleted event is not the last event of the episode, the generation unit  74   c  determines, in the same way, whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. In the case in which the backtrack processing unit  74   d  has added the maximum value of counters to the threshold, the generation unit  74   c  also determines, in the same way, whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added. 
     When there are a candidate event to be added to the selected episode and a part to which the event is to be added, the generation unit  74   c  selects one unselected event as the candidate event e and selects one candidate part. Then, the generation unit  74   c  determines whether the place of addition of the selected candidate event e is behind the other events included in the selected episode.  FIG. 27  is a diagram for explaining an example of a process executed by the extraction device according to the third embodiment. In the example of  FIG. 27 , suppose a case in which an episode  80  is selected. When the event D is selected as an event to be added, and a part behind a part including the events A to C is selected as a part to which the event is to be added, the place of addition of the event D is located in the following position. That is, the place of addition of the selected event D is located behind the events A to C included in the episode  80 . In such a case, the generation unit  74   c  determines that the place of addition of the event D serving as the selected candidate event is behind the other events A to C included in the selected episode  80 . 
     When an episode  81  is selected in the example of  FIG. 27 , the place of addition of the selected event C is behind the events A and B included in the episode  81 . Therefore, when the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  determines that the place of addition of the event C serving as the selected candidate event is behind the other events A and B included in the selected episode  81 . 
     When the place of addition of the selected candidate event e is behind the other events included in the selected episode, the generation unit  74   c  determines whether the maximum value of the counters is less than the threshold. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part behind the part including the events A to C is selected as a part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  determines that the maximum value “1” of counters  80   a  (counters corresponding to the episode  80 ) is less than a corresponding threshold “3” indicated by numeral “90”. When the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  determines that the maximum value “2” of counters  81   a  (counters corresponding to the episode  81 ) is less than a corresponding threshold “5” indicated by numeral “91”. 
     When the maximum value of the counters is not less than the threshold, the generation unit  74   c  performs the above-described process of determining whether there are a candidate event to be added to the selected episode and a part to which the event is to be added, and performs again the processes following that process. 
     When the maximum value of the counters is less than the threshold, the generation unit  74   c  updates the threshold by subtracting the maximum value of the counters from the threshold. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part behind the part including the events A to C is selected as a part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  subtracts the maximum value “1” of the counters  80   a  from the threshold “3” indicated by numeral “90” to update the threshold to a threshold “2” indicated by numeral “92”. When the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  subtracts the maximum value “2” of the counters  81   a  from the threshold “5” indicated by numeral “91” to update the threshold to the threshold “3” indicated by numeral “90”. 
     Then, the generation unit  74   c  saves all of the counters into stacks, and thereafter sets all of the counters to “0”. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part behind the part including the events A to C is selected as a part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  saves three values “1”, “1”, and “1” of the counters  80   a  corresponding to the episode  80  into stacks  82   b , and thereafter sets all of the counters  82   a  to “0”. When the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  saves three values “0”, “2”, and “0” of the counters  81   a  corresponding to the episode  81  into stacks  80   b , and thereafter sets all of the counters  80   a  to “0”. 
     Then, the generation unit  74   c  sets the events in front of the added event to be the definite portion. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part behind the part including the events A to C is selected as a part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  sets the events A to C (part of the events A to C) in front of the added event D to be the definite portion. When the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  sets the events A and B (part of the events A and B) in front of the added event C to be the definite portion. 
     Then, the generation unit  74   c  generates an episode by adding the selected candidate event e to the selected part of the selected episode. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part behind the part including the events A to C is selected as a part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  generates an episode  82  by adding the event D to the selected part of the selected episode  80 . When the episode  81  is selected in the example of  FIG. 27 , the generation unit  74   c  generates the episode  80  by adding the event C to the selected part of the selected episode  81 . The generation unit  74   c  subsequently selects the generated episode. 
     If, as a result of the determination of whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added, there is no candidate event to be added or no candidate part to which the event is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  determines whether all the episodes are generated except episodes that are no longer generated because of the pruning. If all the episodes are generated except episodes that are no longer generated because of the pruning, the process is terminated. 
     When the place of addition of the selected candidate event e is not behind the other events included in the selected episode, the generation unit  74   c  determines whether all of the counters in the columns including the selected candidate event e are less than the threshold in the event table  13   b . When it is not determined that all of the counters are less than the threshold, the generation unit  74   c  performs the above-described process of determining whether there are a candidate event and a candidate part, and performs again the processes following that process. When all of the counters are less than the threshold, the generation unit  74   c  performs the process of generating an episode by adding the selected candidate event e to the selected part of the selected episode, and performs again the processes following that process. For example, in the example of  FIG. 27 , when, in the case in which the episode  80  is selected, the event D is selected, and the part including the event C is selected as a part to which the event D is to be added, the generation unit  74   c  performs the following process. That is, the generation unit  74   c  generates the episode  82  by adding the event D to the selected part of the selected episode  80 . 
     The backtrack processing unit  74   d  performs backtracking. For example, when the generation unit  74   c  determines that an episode generated by the generation unit  74   c  does not occur frequently, the backtrack processing unit  74   d  deletes the last added event e from the episode to generate an episode. Then, the backtrack processing unit  74   d  selects the generated episode. When the generation unit  74   c  does not determine that all the episodes are generated except episodes that are no longer generated because of the pruning, the backtrack processing unit  74   d  also performs the same processing. That is, the backtrack processing unit  74   d  deletes the last added event e from the selected episode to generate an episode, and selects the generated episode. 
     When the counter control unit  74   e  has decremented a value of a counter by one, the backtrack processing unit  74   d  determines whether the deleted event is the last event of the episode before the deletion. For example, in the example of  FIG. 27 , when the episode  80  is selected and the episode before the deletion is the episode  82 , the backtrack processing unit  74   d  determines that the deleted event D is the last event of the episode  82  before the deletion. When the episode  80  is selected and the episode before the deletion is an episode  83  in the example of  FIG. 27 , the backtrack processing unit  74   d  determines that the deleted event C is not the last event of the episode  83  before the deletion. When the episode  81  is selected and the episode before the deletion is the episode  80  in the example of  FIG. 27 , the backtrack processing unit  74   d  determines that the deleted event C is the last event of the episode  80  before the deletion. 
     When the event is the last event, the backtrack processing unit  74   d  updates the definite portion by setting the immediately previous definite portion as a new definite portion. For example, when the episode  81  is selected and the episode before the deletion is the episode  80  in the example of  FIG. 27 , the backtrack processing unit  74   d  sets the definite portion to be an empty episode. When the episode  80  is selected and the episode before the deletion is the episode  82  in the example of  FIG. 27 , the backtrack processing unit  74   d  sets the events A and B (part of the events A and B) to be the definite portion. 
     Then, the backtrack processing unit  74   d  restores all of the counters from the stacks. For example, when the episode  81  is selected and the episode before the deletion is the episode  80  in the example of  FIG. 27 , the backtrack processing unit  74   d  performs the following process. That is, the backtrack processing unit  74   d  returns “0”, “2”, and “0” stored in the stacks  80   b  to restore the values of the counters  81   a  to “0”, “2”, and “0”. When the episode  80  is selected and the episode before the deletion is the episode  82  in the example of  FIG. 27 , the backtrack processing unit  74   d  returns “1”, “1”, and “1” stored in the stacks  82   b  to restore the values of the counters  80   a  to “1”, “1”, and “1”. 
     Next, the backtrack processing unit  74   d  updates the threshold by adding the maximum value of the counters to the threshold. For example, when the episode  80  is selected and the episode before the deletion is the episode  82  in the case illustrated in  FIG. 27 , the backtrack processing unit  74   d  performs the following process. That is, the backtrack processing unit  74   d  sets the threshold indicated by numeral “90” to a value “3” obtained by adding the maximum value “1” of the values “1”, “1”, and “1” of the counters  80   a  to the threshold “2” indicated by numeral “92”, thus updating the threshold. When the episode  81  is selected and the episode before the deletion is the episode  80  in the case illustrated in  FIG. 27 , the backtrack processing unit  74   d  performs the following process. That is, the backtrack processing unit  74   d  sets the threshold indicated by numeral “91” to a value “5” obtained by adding the maximum value “2” of the values “0”, “2”, and “2” of the counters  81   a  to the threshold “3” indicated by numeral “90”, thus updating the threshold. 
     When the generation unit  74   c  has generated the episode, the counter control unit  74   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e that was added when the episode was generated. The counter control unit  74   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  74   d.    
     When the counter control unit  74   e  has incremented the value of the counter in the column including the candidate event e by one, the extraction unit  74   f  calculates the frequency of the generated episode. Based on the frequency of the generated episode, the extraction unit  74   f  determines whether the episode occurs frequently. The extraction unit  74   f  extracts, as an episode to be displayed, the episode that is determined to occur frequently. 
     The display control unit  14   g  controls the display of the display unit  12  so as to display various types of information. For example, the display control unit  14   g  controls the display of the display unit  12  so as to display the episode extracted by the extraction unit  74   f.    
     The control unit  74  is an integrated circuit such as an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA), or an electronic circuit such as a central processing unit (CPU) or a microprocessing unit (MPU). 
     Procedure of Processes 
     A description will next be made of the procedure of the processes of the extraction device  70  according to the present embodiment.  FIG. 28  is a flowchart illustrating the procedure of the extraction process according to the third embodiment. Various types of timing can be considered as execution timing of the extraction process. For example, the control unit  74  executes the extraction process when an instruction to execute the extraction process is entered from the input unit  11 . 
     As illustrated in  FIG. 28 , the acquisition unit  14   a  acquires the event data  43   a  (S 301 ). Next, the acquisition unit  14   a  acquires the event table  13   b  (S 302 ). Then, the initialization unit  74   b  sets an empty episode as the first parent, that is, the root in the enumeration tree (S 303 ). The initialization unit  74   b  sets the definite portion to be empty (S 304 ). 
     Then, the initialization unit  74   b  initializes the counters  20   a  and  20   b  of the event table  13   b  by setting the values of the counters  20   a  and  20   b  to “0” (S 305 ). Next, the initialization unit  74   b  sets, to the value of the window width, the value of the threshold used in determination of whether the episode occurs frequently (S 306 ). 
     The generation unit  74   c  selects the root episode  50  (S 307 ). Then, the generation unit  74   c  determines whether there are a candidate event to be added to the selected episode and a candidate part to which the event is to be added (S 308 ). 
     If there are a candidate event to be added to the selected episode and a part to which the event is to be added (Yes at S 308 ), the generation unit  74   c  selects one unselected event as the candidate event e and one candidate part (S 309 ). Next, the generation unit  74   c  determines whether the place of addition of the selected candidate event e is behind the other events included in the selected episode (S 310 ). 
     If the place of addition of the selected candidate event e is behind the other events included in the selected episode (Yes at S 310 ), the generation unit  74   c  determines whether the counter maximum value is less than the threshold (S 311 ). If the counter maximum value is not less than the threshold (No at S 311 ), the generation unit  74   c  returns to S 308 . 
     If the maximum value of the counters is less than the threshold (Yes at S 311 ), the generation unit  74   c  updates the threshold by subtracting the maximum value of the counters from the threshold (S 312 ). Then, the generation unit  74   c  saves all of the counters into the stacks (S 313 ). The generation unit  74   c  then sets all of the counters to “0” (S 314 ). The generation unit  74   c  sets the events in front of the added event to be the definite portion (S 315 ). 
     Then, the generation unit  74   c  generates an episode by adding the selected candidate event e to the selected part of the selected episode, and selects the generated episode (S 316 ). Then, the counter control unit  74   e  increments by one the value of the counter in the column of the event table  13   b  including the candidate event e that was added when the episode was generated (S 317 ). Next, the extraction unit  74   f  calculates the frequency of the generated episode (S 318 ). Based on the frequency of the generated episode, the extraction unit  74   f  determines whether the episode occurs frequently (S 319 ). If the episode occurs frequently (Yes at S 319 ), the extraction unit  74   f  extracts, as an episode to be displayed, the episode that is determined to occur frequently (S 320 ). Then, the display control unit  14   g  controls the display of the display unit  12  so as to display the episode extracted by the extraction unit  44   f  (S 321 ), and the process returns to S 308 . 
     If there is no candidate event to be added or no candidate part to which the event is to be added (No at S 308 ), the generation unit  74   c  performs the following process. That is, the generation unit  74   c  determines whether all the episodes are generated except episodes that are no longer generated because of the pruning (S 330 ). If all the episodes are generated except episodes that are no longer generated because of the pruning (Yes at S 330 ), the process is terminated. 
     If the place of addition of the selected candidate event e is not behind the other events included in the selected episode (No at S 310 ), the generation unit  74   c  performs the following process. That is, the generation unit  74   c  determines whether all of the counters in the columns including the selected candidate event e are less than the threshold in the event table  13   b  (S 322 ). If all of the counters are less than the threshold (Yes at S 322 ), the process proceeds to S 316 . If it is not determined that all of the counters are less than the threshold (No at S 322 ), the process proceeds to S 308 . 
     If the episode does not occur frequently (No at S 319 ), or if it is not determined that all the episodes are generated except episodes that are no longer generated because of the pruning (No at S 330 ), the backtrack processing unit  74   d  performs the following process. That is, the backtrack processing unit  74   d  deletes the last added event e from the episode generated by the generation unit  74   c  to generate an episode (S 323 ). The backtrack processing unit  74   d  then selects the generated episode (S 324 ). Next, the counter control unit  74   e  decrements by one the value of the counter in the column of the event table  13   b  including the event e deleted by the backtrack processing unit  74   d  (S 325 ). 
     Next, the backtrack processing unit  74   d  determines whether the deleted event is the last event of the episode (S 326 ). If the deleted event is the last event (Yes at S 326 ), the backtrack processing unit  74   d  updates the definite portion by setting the immediately previous definite portion as a new definite portion (S 327 ). Then, the backtrack processing unit  74   d  restores all of the counters from the stacks (S 328 ). The backtrack processing unit  74   d  subsequently updates the threshold by adding the maximum value of the counters to the threshold (S 329 ), and the process returns to S 308 . The process also returns to S 308  if the deleted event is not the last event (No at S 326 ). 
     As described above, when adding an event to an episode to generate a new episode, the extraction device  70  according to the present embodiment performs the following process if the event added to the episode is an event added at the end of events. That is, the extraction device  70  updates the threshold by setting it, as a new threshold, to a value obtained by subtracting, from the threshold representing the size of the window width, the number of events included in the combinations of mutually exclusive events indicated by the event table  13   b  among the events of the episode other than the added event. Then, when the threshold has been updated, the extraction device  70  performs the following process based on the combinations of mutually exclusive events indicated by the event table  13   b  when adding the event at the end of events of the episode to generate a new episode. That is, if the number of occurrence, among the added events, of each of the events included in the combinations is not more than the threshold after being updated, the extraction device  70  generates a new episode. This keeps the extraction device  70  from generating episodes that include time exceeding the window width. This, in turn, keeps the extraction device  70  from performing unnecessary processes, such as the process to calculate the frequency of episodes that exceed the window width and are not extracted, and the process to determine whether such episodes occur frequently. This, in turn, allows the extraction device  70  to efficiently extract the episodes. 
     The extraction device  70  according to the present embodiment also generates an episode by deleting an event last added to an episode from the episode that has a frequency not satisfying a predetermined condition and thus does not occur frequently. If the event deleted when the episode is generated is the event at the end, the extraction device  70  performs the following process. That is, the extraction device  70  obtains a value as a threshold by adding, to the updated threshold, the number of events included in the combinations of mutually exclusive events indicated by the event table  13   b  among the events of the generated episode, and thereby newly updates the threshold. Then, when a further new episode is to be generated from the newly generated episode, the extraction device  70  performs the following process based on the combinations of mutually exclusive events indicated by the event table  13   b . That is, if the number of occurrence, in the further new episode, of each of the events included in the combinations is not more than the newly updated threshold, the extraction device  70  generates a further new episode. Therefore, when an episode is generated by deleting an event, the extraction device  70  updates the threshold to a value corresponding to the number of events included in the generated episode. This keeps the extraction device  70  from generating an episode that includes time exceeding the window width when the episode is generated by deleting an event. This, in turn, keeps the extraction device  70  from performing the following unnecessary processes when an episode is generated by deleting an event. That is, the extraction device  70  is kept from performing unnecessary processes, such as the process to calculate the frequency of episodes that exceed the window width and are not extracted, and the process to determine whether such episodes occur frequently. This, in turn, allows the extraction device  70  to efficiently extract the episodes. 
     Although description has been made of the embodiments related to the device disclosed herein, the present invention can be implemented in various different forms other than those of the embodiments described above. A description will now be made below of other embodiments included in the present invention. 
     A case has been described in which, for example, the device disclosed herein adds an event behind the definite portion, and determines whether the place of addition of the selected candidate event e is behind the other events included in the selected episode. However, the disclosed device is not limited to this. The disclosed device can add an event in front of the definite portion, and can determine whether the place of addition of the selected candidate event e is in front of the other events included in the selected episode. This case allows the disclosed device to perform the same process as that described above. In other words, the disclosed device generates an episode by deleting an event last added to an episode from the episode that has a frequency not satisfying a predetermined condition and thus does not occur frequently. If the event deleted when the episode is generated is the event at the start, the disclosed device performs the following process. That is, the disclosed device obtains a value as a threshold by adding, to the updated threshold, the number of events included in the combinations of mutually exclusive events indicated by the event table  13   b  among the events of the generated episode, and thereby newly updates the threshold. Then, when a further new episode is to be generated from the newly generated episode, the disclosed device performs the following process based on the combinations of mutually exclusive events indicated by the event table  13   b . That is, if the number of occurrence, in the further new episode, of each of the events included in the combinations is not more than the newly updated threshold, the disclosed device generates a further new episode. This keeps the disclosed device from performing unnecessary processes, such as the process to calculate the frequency of episodes that exceed the window width and are not extracted, and the process to determine whether such episodes occur frequently. This, in turn, allows the disclosed device to efficiently extract the episodes. 
     Among the processes described in the embodiments, all or some of the processes described as being performed automatically can be performed manually. 
     The processes at the steps of the processes described in the embodiments can be optionally subdivided or integrated according to various conditions of load and/or use. Some steps can also be omitted. 
     The orders of processes at the steps of the processes described in the embodiments can be changed according to various conditions of load and/or use. 
     The constituent elements of the illustrated devices are functionally conceptual, and need not be physically configured as illustrated. In other words, the specific state of dispersion and integration of each of the devices is not limited to be as illustrated, but can be entirely or partially configured to be functionally or physically dispersed or integrated in any units according to various conditions of load and/or use. 
     Extraction Program 
     The extraction process of each of the above-described extraction devices ( 10 ,  41 , and  70 ) can also be achieved by executing a prepared program on a computer system such as a personal computer or a workstation. A description will now be made below, using  FIG. 29 , of an example of a computer that executes an extraction program including the same functions as those of the extraction devices described above. 
       FIG. 29  is a diagram illustrating the computer that executes the extraction program. As illustrated in  FIG. 29 , this computer  300  includes a central processing unit (CPU)  310 , a read-only memory (ROM)  320 , a hard disk drive (HDD)  330 , and a random access memory (RAM)  340 . These units  300  to  340  are connected via a bus  350 . 
     The HDD  330  stores therein in advance an extraction program  330   a  that implements the same functions as those of the units  14   a  to  14   g  described in the first embodiment, of the units  14   a ,  44   b  to  44   f , and  14   g  described in the second embodiment, or of the units  14   a ,  74   b  to  74   f , and  14   g  described in the third embodiment, each described above. The extraction program  330   a  may be fragmented as appropriate. 
     The CPU  310  reads the extraction program  330   a  from the HDD  330  and executes the program. 
     The event data and the event table are provided in the HDD  330 . 
     The CPU  310  reads the event data and the event table, and stores them into the RAM  340 . The CPU  310  executes the extraction program  330   a  using the event data and the event table stored in the RAM  340 . The RAM  340  need not always store therein all the data, but needs to store therein only pieces of data used for processing among all pieces of the data. 
     The extraction program  330   a  need not be stored in the HDD  330  from the start. 
     For example, the program may be stored in a “physical medium for portable use” to be inserted into the computer  300 , such as a flexible disk (FD), a CD-ROM, a DVD, a magneto-optical disk, or an IC card. The program may be read from such a medium, and executed by the computer  300 . 
     Furthermore, the program may be stored in another computer (or a server) connected to the computer  300  via a public line, the Internet, a LAN, a WAN, and/or the like. The program may be read from such a computer or a server, and executed by the computer  300 . 
     According to an aspect of an extraction program, an extraction device, and an extraction method, patterns can be efficiently extracted. 
     All examples and conditional language recited herein are intended for pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present invention has been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.