Methods and systems for fast translation memory search include, in response to an input query string, identifying a plurality of hypothesis strings stored in a translation memory as candidates to match the query string. One or more candidates are eliminated, using a processor, where string lengths between the candidates and the query string are at least a cutoff value representing a string edit distance. One or more candidates are eliminated where differences in word frequency distributions between the candidates and the query string are at least the cutoff value. One or more candidates are eliminated by employing a dynamic programming matrix where string edit distances between the candidates and the query string are at least the cutoff value. A number of remaining candidates are outputted as matches to the query string.