A dictionary of typos
The search box of an electronic library must correct typos on the fly: a person types a word, and a fraction of a second later “Did you mean…” appears under the box. There are tens of thousands of words in the dictionary, thousands of queries a second, and there is no time to compare each query with each word.
For each query print a suggestion. If the query is in the dictionary, the suggestion is the query itself. Otherwise it is a dictionary word at edit distance exactly 1: one insertion, one deletion or one substitution of a letter. If there are several such words, the most frequent one is chosen, and among equally frequent ones the smaller when strings are compared by character codes. If there is no word at distance 1, there is no suggestion. A transposition of two neighbouring letters is two edits, not one.
One of the tests is the whole dictionary of the Russian original of “War and Peace”, 47,585 words with frequencies, and 20,000 typos in its frequent words; another is the English translation of the novel.
Input
The first line holds the number of dictionary words n (1 ≤ n ≤ 50,000). Then n lines: a word and how many times it occurred (from 1 to 106). The words are distinct. Then the number of queries q (1 ≤ q ≤ 20,000) and q query lines. Words and queries consist of lower-case Russian (а–я, ё) or Latin letters, of length 1 to 30.
Output
q lines: the suggestion for each query, or - if there is none.
Examples
Example 1
5 князь 1329 казнь 9 кнезу 1 мир 120 мор 120 5 кнезь мир мхр кнзяь ветер
князь мир мир - -
Example 2
2 ba 50 abc 2 4 ab bc abcd a
abc ba abc ba
Limits
- Time · Python
- 8000 ms
- Time · Go
- 3000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Comparing a query with all words of similar length is correct, but it is 20,000 × 30,000 checks. One needs a way to get a short list of candidates at once, as in a hash table.
2Hint 2
Generate all strings at distance 1 from the query and look them up in the dictionary? For a word of eight Russian letters that is 8 deletions, 8 · 33 substitutions and 9 · 33 insertions, more than five hundred lookups per query. Can deletions alone be enough?
3Hint 3
If a and b differ by one substitution at position i, deleting the i-th letter from both gives the same string. If b is obtained from a by an insertion, deleting that letter from b gives a itself. What can be prepared in advance for each dictionary word?
4The idea
Call the shadow of a word the word itself and all strings obtained from it by deleting one letter. If the distance between a and b is at most 1, their shadows intersect: for a substitution the common string is both words without the changed letter, for an insertion the short word itself. So put each dictionary word into a hash table in advance under each string of its shadow, and for a query look only at the buckets of its shadow. The converse is false: “ab” and “ba” share the shadow string “a”, but are at distance 2. So each candidate is checked.
5Walkthrough
Preparation: for a word of length L, L + 1 shadow strings, 9.3 per word on average: for the novel's dictionary that is 444 thousand entries in 408 thousand buckets. A query: build its shadow, gather everyone lying in its buckets, and check each candidate in linear time. Distance exactly 1 is checked without a table: for equal lengths, exactly one mismatched position; for lengths differing by one, after the first mismatch the tail of the short word coincides with the tail of the long one minus one letter.
The second sample is a trap for a solution without the check. The shadows of “ab” and “ba” intersect, “ba” is 25 times more frequent than “abc”, but the suggestion for “ab” is “abc”: “ba” is two edits away.
This technique is called symmetric deletion; Wolf Garbe's SymSpell library is built on it. For distance k the shadow is all strings obtained by deleting up to k letters, and it grows as Lk, but it does not depend on the size of the alphabet: substitutions and insertions in Chinese or Japanese would have to be tried over thousands of characters.
5+Solution
6Complexity
Preparation is O(Σ L²): each word has L + 1 strings of length up to L. A query is O(L² + c · L), where c is the number of candidates, usually a few. A direct scan would cost O(q · n · L), hundreds of millions of comparisons on 20,000 queries.
7Common mistakes
- A shadow without the check. A common string in the shadows is a hint, not a proof: “ab” and “ba”, «ад» and «да», share strings but are at distance 2. Without the check the solution suggests words at distance 2 (the second sample).
- Bytes instead of letters. A Russian letter in UTF-8 is two bytes. Deleting “one byte” in Go corrupts the string; work with runes.
- Scanning the whole dictionary. Even with a length filter it is tens of thousands of checks per query.
- The query itself forgotten. If the query is in the dictionary, the suggestion is the query itself, even if a more frequent word is nearby.