For many retrieval systems, correcting spelling errors in the queries that searchers submit is an essential step of query understanding. Inspired by a blog post on spelling correction from 2018, we implement and analyze a simple embedding-based query spelling correction approach, and we compare the impact on retrieval efectiveness to Hunspell-, pyspellchecker-, and GPT-3.5-based spelling correction. Our experiments with BM25 and PL2 on corpora of the TIRA / TIREx evaluation platform show that especially Hunspell and pyspellchecker are much worse than a do-nothing baseline that does not even try to correct errors. The embedding-based approach comes closest to the baseline but also does not correct many errors, while the GPT-3.5-based approach corrects more errors but at the same time already changes many correct queries and thus worsens the overall retrieval efectiveness. As a software contribution, we provide the four spelling correctors in a Docker image so that they can be easily included as components in retrieval systems and retrieval pipelines.
When searchers type a query to express an information need, it can easily happen that spelling errors
are included—for instance, by “fat-fingering” on the keyboard or by not knowing how to spell a word.
Previous studies showed that about 10–20% of queries contain some spelling errors [
Typical spelling errors include missing or additional characters (deletion, insertion), missing or additional spaces and special characters, wrong characters (substitution), and swapped characters (transposition); Table 1 shows some examples. In a retrieval pipeline, query spelling errors may lead to several problems ranging from tokenization issues (e.g., for missing or additional spaces), over issues with stemming / lemmatization or entity linking (e.g., misspellings may not match stemming rules or gazetteer entries), to problems with lexically matching a misspelled query to relevant documents.
In this paper, inspired by a 2018 blog post [
Spelling errors are either so-called real-word errors (the misspelling is another existing word like ‘their’
instead of ‘there’) or non-word errors (a misspelling that is not in a dictionary) [
Early approaches for query spelling correction were based on query log analyses [
As for the accuracy of detecting and correcting query spelling errors, a 2017 study by Hagen et al. [
In 2018, Rushton described an idea for general spelling correction based on a “correction vector” in a
word embedding space [
As illustrated in Figure 1, the vector representation of ‘king’ lies in a similar direction from ‘man’ as the representation of ‘queen’ lies to ‘woman’ (a “royal” direction / vector), and the representation of ‘queen’ lies in a similar direction from ‘king’ as ‘woman’ lies to ‘man’ (a “female” vector).
Rushton [
Starting with an Oxford Dictionary list of common misspellings and corrections,1 Rushton calculated a spelling correction vector s⃗c by averaging the diferences of the respective pairs of GloVe embeddings. As for the actual spelling correction, Rushton tried to add s⃗c to the embedding of a potentially misspelled word (in our case, we simply do it for every query word), and to then search for the cosine similarity-wise nearest neighbor as the respective correct word (also using some further heuristics that check for plural forms or common sufixes). In experiments, Rushton found that corrections can be found better when linearly stretching or shortening s⃗c based on the angle between a potential misspelling’s embedding and s⃗c. He empirically optimized the linear transformation’s parameters and then suggested to use the transformed s⃗copt as the basis of an embedding-based spelling correction approach.
For our re-implementation of Rushton’s idea, we use 300-dimensional GloVe embeddings2 of the 2 million most frequent words trained on 840 billion Common Crawl tokens [17]. We calculate Rushton’s exact spell correction vector s⃗c from his initial data and we use the linear transformation he found to optimize the spelling correction to arrive at s⃗copt . In a further pre-processing to speed up the actual query spell correction, we create an error correction hash table of words and their “best” spell correction by adding s⃗copt to each of the 2 million embeddings and looking for the respective nearest neighbor. To reduce the size of the table, we remove pairs where the nearest-neighbor “correction” actually has the same spelling as the original word, and thus only store pairs with diferent spelling in the table. To spell-correct a query, we lowercase all words, and check for each individually whether the hash table has a match. Words that are not found in the hash table, are simply considered correct.
We compare the embedding-based approach to Hunspell-, pyspellchecker-, and GPT-3.5-based approaches. Hunspell3 is an often used spell checker (e.g., OpenOfice and Mozilla), while pyspellchecker 4 is based on a blog post by Peter Norvig;5 from simple edits of a word (Levenshtein distance), it chooses the one with the highest frequency in a word frequency list. For the GPT-3.5-based approach, we use the prompt: “You are a spelling corrector for search queries. You respond always exactly with the corrected search query. Please correct all spelling errors in the query: <query>”.
Our implementations of these query spelling correction approaches are freely accessible on GitHub.6 Listing 1 shows a code snippet that applies the embedding-based spelling correction (rushton) and evaluates it for retrieval with BM25 and PL2 on the ANTIQUE dataset.
For our experiments, we run the query spelling correction approaches on the queries of the ANTIQUE dataset [19] and on the TREC 2019 and 2020 Deep Learning tracks [20, 21] before submitting the queries to BM25 and PL2. Our experiments were conducted on the TIRA [22] / TIREx [23] evaluation platform.
Table 2 shows the retrieval efectiveness results (nDCG@10). As kind of an upper bound for using any of the spell correctors, we also give the results of an “oracle” that always chooses the nDCG@10-wise best output of the do-nothing baseline and of the four spell correctors. For all three datasets, the oracle 1languages.oup.com/ 2https://nlp.stanford.edu/projects/glove/ 3github.com/hunspell/hunspell 4pypi.org/project/pyspellchecker/ 5norvig.com/spell-correct.html 6https://github.com/OpenWebSearch/wows24-query-spelling-correction Listing 1: Code snippet to run and evaluate the embedding-based query spelling correction (rushton) for the retrieval models BM25 and PL2 on the ANTIQUE dataset. from tira.third_party_integrations import ensure_pyterrier_is_loaded() import pyterrier as pt from tira.rest_api_client import Client tira = Client() ensure_pyterrier_is_loaded data = ’antique-test-20230107-training’ dataset = pt.get_dataset(f’irds:ir-benchmarks/{data}’) index = tira.get_run_output(’ir-benchmarks/tira-ir-starter/Index (tira-ir-starterpyterrier)’, data) + ’/index’ index = pt.IndexFactory.of(index) bm25 = pt.BatchRetrieve(index, wmodel="BM25") pl2 = pt.BatchRetrieve(index, wmodel="PL2") tokeniser = pt.autoclass("org.terrier.indexing.tokenisation.Tokeniser").getTokeniser() def pt_tokenise(text):
return ’ ’.join(tokeniser.getTokens(text)) rushton = tira.pt.transform_queries(’workshop-on-open-web-search/qspell/rushton’, data) toks = pt.apply.query(lambda i: pt_tokenise(i[’query’])) sys = [bm25, pl2, rushton >> toks >> bm25, rushton >> toks >> pl2] names = [’BM25’, ’PL2’, ’rushton >> BM25’, ’rushton >> PL2’] pt.Experiment(sys, dataset.get_topics(’query’), dataset.get_qrels(), [’ndcg_cut.10’], names=names, verbose=True) efectiveness is a bit better than not correcting any error (sometimes only in the third decimal, though). The do-nothing baseline on average is better than the individual correction approaches among which the embedding-based approach (line ‘Rushton’ in the table) is best and substantially better than the “standard” Hunspell- and pyspellchecker-based approaches. The corrections of GPT-3.5 also yield a worse retrieval efectiveness than the embedding-based approach. On TREC DL ’20, the embeddingbased approach is as efective as the do-nothing baseline (as both do not change any query), while on TREC DL ’19, the embedding-based approach is slightly better than doing nothing and as efective as the oracle. Still, on TREC DL ’19, the oracle and the embedding-based approach only change one query (why did the us volunterilay enter ww1) and, interestingly, not even correct the actual spelling error ‘volunterilay’, but change the abbreviation ‘ww1’ to the more general term ‘war’.
Possible reasons for the do-nothing baseline overall being so close to the oracle while some correction approaches are much worse are (1) that the queries of the TREC DL tracks hardly contain misspellings, (2) that the correction approaches also do not correct many misspellings, and (3) that the correction approaches often even “worsen” queries by changing correctly spelled words. Table 3 gives the respective statistics of spelling errors per error type (manually identified), of the number of corrected errors per type and approach, and of the number of incorrectly changed queries per approach. The most frequent error are missing apostrophes (e.g., ‘don t’) probably introduced by some query parser before logging.
Among the correction approaches, the GPT-3.5-based one has the most corrections. But it also often incorrectly changes queries which leads to an overall worse average retrieval efectiveness than the embedding-based approach that corrects hardly any of the misspellings but—just like the do-nothing baseline—also does not worsen most of the already correct queries. The many incorrect changes of the Hunspell- and pyspellchecker-based approaches explain their bad overall nDCG impact. For example, on the ANTIQUE dataset with 63 misspellings in 53 of the 200 queries, the embedding-based approach corrects 9 errors and has no incorrect changes, whereas Hunspell and pyspellchecker correct 14 and 17 errors, respectively, but at the same time incorrectly change 52 and 75 queries.
Inspecting the approaches’ changes in more detail, we found that GPT-3.5 often appends question marks to queries formulated as questions and corrects the queries’ grammar (e.g., why *does* hot air rise up*?*). These changes might not be incorrect, but they do not help BM25 or PL2 during retrieval. Some few incorrect changes and artifacts like ‘corrected search query’ reduce the retrieval efectiveness for GPT-3.5. At the same time, GPT-3.5 is the only approach that corrects misspellings in person names like ‘natalie holloway’ → ‘natalee holloway’ or in product names like ‘citriscidal’ → ‘citricidal’. Some “normal” typos like ‘prsented’ are corrected by all four approaches, while only the embedding- and GPT-3.5-based approaches correct the query ‘how can i keep my rabit indoors’. Hunspell and pyspellchecker change ‘rabit’ to ‘barit’ or ‘habit’ instead. Other incorrect changes by Hunspell and pyspellchecker are unrelated words chosen as “correction” (e.g., ‘wifi’ to ‘wife’). For pyspellchecker, for example, this phenomenon can be explained by the use of the word frequency list that leads to replacing unknown or uncommon words with more frequent lexically similar words—with a negative impact on the retrieval results. This does not happen for the embedding-based approach as unknown words (i.e., words without GloVe embeddings) are considered as correctly spelled—with the downside that many typos are not part of the GloVe vocabulary. Limitations Even though the embedding-based query spelling correction achieves acceptable results in the evaluation, it also comes with some severe limitations. First, the approach can only correct errors for which both the misspelled word and the correct word have a corresponding GloVe embedding. Misspelled words where either the misspelling or the correct word were not present in the GloVe embedding training data cannot be corrected. Second, the embedding-based correction works on single words only and thus cannot detect errors involving missing or additional spaces (either the correction or the misspelling would be at least two words). And third, again due to the single-word characteristic of the embeddings, context-dependent spelling errors (i.e., real-word errors) cannot be corrected.
In this paper, we analyzed four query spelling correction approaches that we implemented as a software
contribution to the WOWS 2024 workshop [
As hardly any of the TREC Deep Learning track queries contain misspellings, it could be an interesting idea for a further study to artificially create variants of the queries with some realistic typos and to measure the retrieval impact on these. Another interesting direction to further analyze the strengths and weaknesses of embedding-based query spelling correction is to test other embedding approaches (e.g., word2vec or fastText) and to combine embedding-based correction with other approaches in some system that might try to choose the best correction approach on a per-query basis.
Partially supported by the European Union’s Horizon Europe research and innovation programme under grant agreement No 101070014 (OpenWebSearch.eu, https://doi.org/10.3030/101070014). [15] S. Zhuang, G. Zuccon, Dealing with Typos for BERT-based Passage Retrieval and Ranking, in:
Proceedings of EMNLP, 2021, pp. 2836–2842. [16] S. Zhuang, G. Zuccon, CharacterBERT and Self-Teaching for Improving the Robustness of Dense
Retrievers on Queries with Typos, in: Proceedings of SIGIR, 2022, pp. 1444–1454. [17] J. Pennington, R. Socher, C. D. Manning, Glove: Global Vectors for Word Representation, in:
Proceedings of EMNLP, 2014, pp. 1532–1543. [18] K. Ethayarajh, D. Duvenaud, G. Hirst, Towards Understanding Linear Word Analogies, in:
Proceedings of ACL, 2019, pp. 3253–3262. [19] H. Hashemi, M. Aliannejadi, H. Zamani, W. B. Croft, ANTIQUE: A Non-factoid Question Answering
Benchmark, in: Proceedings of ECIR, 2020, pp. 166–173. [20] N. Craswell, B. Mitra, E. Yilmaz, D. Campos, E. M. Voorhees, Overview of the TREC 2019 Deep
Learning Track, in: Proceedings of TREC, volume abs/2003.07820, 2019. [21] N. Craswell, B. Mitra, E. Yilmaz, D. Campos, Overview of the TREC 2020 Deep Learning Track, in:
Proceedings of TREC, volume 1266, 2020. [22] M. Fröbe, M. Wiegmann, N. Kolyada, B. Grahm, T. Elstner, F. Loebe, M. Hagen, B. Stein, M. Potthast, Continuous Integration for Reproducible Shared Tasks with TIRA.io, in: Proceedings of ECIR, Berlin Heidelberg New York, 2023, pp. 236–241. [23] M. Fröbe, J. Reimer, S. MacAvaney, N. Deckers, S. Reich, J. Bevendorf, B. Stein, M. Hagen, M. Potthast, The Information Retrieval Experiment Platform, in: Proceedings of SIGIR, 2023, pp. 2826–2836.