To provide a retrieval information generation device, a retrieval information generation method, and a program, which are capable of suppressing increase of a memory capacity for storing character string information constituting retrieval objects.

A retrieval information generation device includes: first storage information generation means for generating first storage information including a first permutation part in which reading-character strings of retrieval words constituting retrieval objects are expressed in a permutation of all character codes respectively discriminating all character categories that can be used for reading the retrieval words; second storage information generation means for generating second storage information including an index part in which character categories constituting the character strings are expressed and a second permutation part in which the character strings are expressed by a permutation of discrimination bit codes respectively discriminating the character categories expressed in the index part; and retrieval information storage means for storing, of data sizes of first and second storage information, one with smaller data-size as the reading-character strings of the retrieval words.