A recording medium having stored therein an encoding program that causes a computer to execute a process, the process including first generating a plurality of word codes by assigning a compression code to each of a plurality of words contained in a sentence in a compression target document, second generating a plurality of pieces of semantic structure information respectively corresponding to the plurality of words by performing a semantic analysis of the sentence, third generating a plurality of semantic structure codes by assigning each of the plurality of compression codes to corresponding semantic structure information, and outputting the plurality of word codes and the plurality of semantic structure codes with a specific order.