5. The method of claim 1 , further comprising: receiving a current query and a plurality of suggested queries, each of the current and suggested queries including one or more terms; for each suggested query: calculating a transition cost between the suggested query and the current query based on a transition cost of a current term and a suggested term; and selecting a suggested query from the plurality of suggested queries based on the edit distance.
7. The method of claim 5 , wherein the calculating the edit distance comprises: identifying values in a plurality of cost matrices based on a substitution query pair including the current term and the suggested term; and averaging the identified values.