13. A computer program product encoded on a storage device, the computer program product including instructions which when executed by a processor cause the processor to perform operations comprising: generating a first vector for one or more first n-grams of a first query and calculating a respective first semantic weight for each of the first n-grams based at least in part on an entropy of the particular first n-gram in which the entropy is estimated from a set of search queries; generating a second vector for one or more second n-grams of a second query and calculating a respective second semantic weight for each of the second n-grams; and calculating a similarity measurement between the first query and the second query based on respective similarities of semantically weighted first n-grams to the second vector, and based on respective similarities of the semantically weighted second n-grams to the first vector.
13. A computer program product encoded on a storage device, the computer program product including instructions which when executed by a processor cause the processor to perform operations comprising: generating a first vector for one or more first n-grams of a first query and calculating a respective first semantic weight for each of the first n-grams based at least in part on an entropy of the particular first n-gram in which the entropy is estimated from a set of search queries; generating a second vector for one or more second n-grams of a second query and calculating a respective second semantic weight for each of the second n-grams; and calculating a similarity measurement between the first query and the second query based on respective similarities of semantically weighted first n-grams to the second vector, and based on respective similarities of the semantically weighted second n-grams to the first vector. 18. The program product of claim 13 , wherein the operations further comprise providing the second query as a query suggestion for the first query.