Weighted edit distance
Similar to Levenshtein distance (Edit distance)
Weight of an operation depends on the character(s) involved.
Meant to capture OCR / keyboard errors.
e.g. m more likely to be mis-typed as n than as q.
Therefore, replacing m by n is a smaller edit distance than by q.
Requires a weighted matrix as input.
Modify DP to handle weights.
Given a misspelled query - do we compute its edit distance to every dictionary term?