An aspect includes phrase searching using exclusion tokens. A token division unit is configured to divide an input character string to be searched into a plurality of tokens. A token position definition unit is configured to set each token to be excluded in an occurrence position calculation as an exclusion token and to set each token to be included in the occurrence position calculation as a headword token, and define an occurrence position for each headword token. A position offset information assigning unit is configured to assign, to each of the exclusion tokens, position information obtained with the headword token followed by the exclusion tokens and to assign the headword token followed by the exclusion tokens as a starting point. An indexing processing unit is configured to perform indexing on the plurality tokens such that whether or not the exclusion tokens follow one of the plurality of tokens is identifiable.