A search engine supports error correction in the following way: If an error is suspected in a query term, the system provides a link labeled “Did you mean X?”, where X is the corrected term, in...

A search engine supports error correction in the following way: If an error is suspected in a query term, the system provides a link labeled “Did you mean X?”, where X is the corrected term, in addition to its normal results. The link leads to a list of retrieved documents, corresponding to a variant of the original query, with X replacing the misspelled term.

a) Explain why it is non-trivial to implement this feature efficiently.

b) Discuss methods for implementing this feature in a realistic setting.