An instruction trace of a first instruction string is generated from a second instruction string obtained by sampling, at predetermined intervals, the first instruction string. The second instruction string is divided into partial instruction strings. A combination of the partial instruction strings is selected based on the similarity of stored partial instruction strings. A plurality of combination patterns are generated by combining instructions included in the selected partial instruction strings. A likelihood is calculated for each of the combination patterns, and the combination patterns are stored in the storage unit based on the likelihood.