A method for generating a data structure corresponding to a phrase tree, comprising: first generating, for each kind of characters, a data block including: a first memory area for holding a code for a specific character or specific character string; a second memory area for holding, for each kind of the characters, an appearance sequential number of a second character that appears in an input character string next to the specific character or specific character string; and a third memory area for holding, in order of the appearance sequential number for the second character, the number of appearances of the second character if the number of appearances does not exceed a specific threshold or a code generated for a certain character string comprising the specific character or specific character string and the second character if the number of appearances exceeds the specific threshold; upon detecting (a) that, in a second memory area of a data block for a character or character string being processed among a plurality of characters included in the input character string, an appearance sequential number for a next character of the character or character string being processed in the input character string is held, (b) that, in a third memory area of the data block for the character or character string being processed, the number of appearances is held, and (c) that the number of appearances after increment in response to detection of appearance of the next character exceeds the specific threshold, storing a code generated for a second character string comprising the character or character string being processed and the next character in the third memory area of the data block for the character or character string being processed; and generating a data block for the second character string, which has a same structure as the data block generated in the first generating. first generating, for each kind of characters, a data block including: a first memory area for holding a code for a specific character or specific character string; a second memory area for holding, for each kind of the characters, an appearance sequential number of a second character that appears in an input character string next to the specific character or specific character string; and a third memory area for holding, in order of the appearance sequential number for the second character, the number of appearances of the second character if the number of appearances does not exceed a specific threshold or a code generated for a certain character string comprising the specific character or specific character string and the second character if the number of appearances exceeds the specific threshold; upon detecting (a) that, in a second memory area of a data block for a character or character string being processed among a plurality of characters included in the input character string, an appearance sequential number for a next character of the character or character string being processed in the input character string is held, (b) that, in a third memory area of the data block for the character or character string being processed, the number of appearances is held, and (c) that the number of appearances after increment in response to detection of appearance of the next character exceeds the specific threshold, storing a code generated for a second character string comprising the character or character string being processed and the next character in the third memory area of the data block for the character or character string being processed; and generating a data block for the second character string, which has a same structure as the data block generated in the first generating.