Rule-Based Generation of Candidate String Transformations

A method of string transformation, the method comprising:

• under control of one or more processors configured with executable instructions,
• generating one or more transformation rules from training data, the generating comprising extracting transformation rules from the training data and expanding the extracted transformation rules;
• associating weights with the transformation rules, the weights determined based at least in part on a conditional probability distribution of a set of transformational rules and the training data, the conditional probability distribution being based in part on a log linear probabilistic model, the weights being non-positive real numbers;
• assembling at least a part of the one or more transformation rules into a rules index based at least in part on the weights;
• selecting a plurality of transformation rules based on a composition of a search string;
• associating a score with a candidate string transformation, the score being based at least in part on the weights associated with transformation rules applied to generate the candidate string transformation;
• eliminating a candidate string transformation, if
• a score of the candidate string transformation is less than a minimum score;
• an intermediate score of the candidate string transformation is less than a minimum score;
• or
• the intermediate score of the candidate string transformation is less than a second intermediate score of a second candidate string transformation, a current position of the candidate string transformation matches a second current position of the second candidate string transformation, and a current partial string of the candidate string transformation matches a second current partial string of the second candidate string transformation.