1. A processor-executing instruction-trace generating method of generating an instruction trace of a first instruction string from a second instruction string obtained by sampling, at predetermined intervals, the first instruction string executed a plurality of times, the instruction-trace generating method comprising: dividing the second instruction string into partial instruction strings and storing the partial instruction strings obtained through division in a storage unit; calculating a similarity for each combination of all of the partial instruction strings stored in the storage unit; selecting one of the combinations of the partial instruction strings based on the similarity calculated in the calculating of the similarity; generating a plurality of combination patterns by combining instructions included in the partial instruction strings selected in the selecting; calculating a likelihood for each of the combination patterns generated in the generating; and storing one of the combination patterns in the storage unit based on the likelihood calculated in the calculating of the likelihood, wherein the calculating of the likelihood, the likelihood is calculated based on a function name of a function to which an instruction included in the partial instruction string belongs, a basic block in which the instruction in included, and an offset of the instruction from a head of the basic block.