1. An apparatus for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: a pattern storage section for storing the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns; a pattern registration section for generating an index element for a given registration pattern of the plurality of registration patterns and registering the given registration pattern and the index element for the given registration pattern into the pattern storage section, wherein the index element for the given registration pattern is a prefix of the given registration pattern, wherein the length of the prefix is a member of a predetermined list of lengths of prefixes which differ from each other, and wherein the length of the prefix is the longest member of the list of lengths of prefixes which is not larger than the length of the given registration pattern; and a pattern retrieval section comprises: a prefix extractor for extracting a plurality of retrieval key prefixes from a given retrieval key, wherein the pattern retrieval section has the predetermined list of lengths which is same as the list of lengths used in the pattern registration section, and wherein lengths of the plurality of retrieval key prefixes are respectively the members of the predetermined list of lengths which are smaller than or equal to the length of the given retrieval key; and a prefix retriever for retrieving an index element for the given retrieval key using a plurality of retrieval key prefixes extracted by the prefix extractor to narrow the scope of retrieval.