1. A system, comprising: a processor; a gram logic configured to cause the processor to produce a gram from a string; a candidate logic configured to cause the processor to identify one or more candidate documents based on identifying at least one match between a query gram produced by the gram logic from a query string and a document gram associated with a document, where document grams are stored in an inverted index that relates grams to documents, where an entry in the inverted index includes a document identifier and one or more of, a gram offset, a term offset, and a gram type; a reconstruction logic configured to cause the processor to produce a partially reconstructed candidate document from one or more entries in the inverted index, the entries being associated with the candidate document, the entries corresponding to one or more query grams that match one or more document grams; an edit distance logic configured to cause the processor to compute an edit distance between a first string associated with the query string and a second string associated with the partially reconstructed candidate document, where the edit distance logic is embodied as executable instructions stored on a computer-readable medium; a signal logic configured to cause the processor to provide data corresponding to the edit distance; and where the reconstruction logic causes the processor to produce the second string, the second string having one or more of, a known substring, and an unknown substring, the location and content of the known substring being determined by information stored in one or more entries in the inverted index, the information comprising offset information, the one or more entries corresponding to matches between document grams associated with the candidate document and query grams associated with the query string.