1. A system comprising: one or more processors; memory; and programming instructions stored on the memory that, when executed by the one or more processors, configure the one or more processors to perform operations comprising: receiving a search string; selecting a plurality of transformation rules based on a composition of the search string; and generating a set of candidate string transformations for the search string based on the plurality of transformation rules and on weights associated with the plurality of transformation rules, the weights being determined based on probability distributions of string pairs associated with the transformation rules, the generating further comprising eliminating one or more candidate string transformations, the eliminating being based at least in part on a score associated with the candidate string transformation; the eliminating comprises comparing an intermediate score of a candidate string transformation with a minimum score, wherein the candidate string transformation is eliminated if the intermediate score is less than the minimum score.