Consider the following scenario:

Suppose two lists of words $L_{1}$ and $L_{2}$ are given. $L_{1}$ contains just bad-written phrases (like 'age' instead of '4ge' or 'blwe' instead of 'blue' etc.). On the other hand, each element of $L_{2}$ is a well-written version of each element of $L_{1}$.

Here is an example:

$$L_{1}=[...,dqta \ 5ciencc,...,s7ack \ exch9nge,...],$$ $$L_{2}=[...,stack \ exchange,...,data \ science,...].$$

Problem: Is there any strategy to try to predict which element $w^{\prime}$ in $L_{2}$ is the syntactically correct counterpart of a given bad-written element $w$ of $L_{1}$?

By 'strategy' I mean some sort of syntactic word embeddings (that allow us to compare texts by using cosine similarity), any "syntactic" Word2Vec or a probabilistic model that could compute $P(w^{\prime} \mid w)$ (how likely is that $w^{\prime}$ could be the well-written version of $w$) etc.

Note: To be concrete, I'm asking for a measure of syntactic similarity among two pieces of text.


1 Answer 1


Yes, there’s a lot of research done on recovering from misspellings.

The seminal probabilistic framework is Probability scoring for spelling correction by Church and Gale, which takes a Bayesian noisy channel approach. It’s really very straightforward to implement. (In your case, you’d only allow substitutions errors, not insertions or deletions.)

More things to consider...

Word embeddings are not a reasonable foundation for a strategy of recovering from spelling errors of the kind you’ve shown.

An alternative way of framing the problem is as a “c-test”, which has a long history in psychometric literature: building a model of the individual character gaps.

As a final avenue to explore, notice that your misspellings always superficially resemble the right letters. OCR (optical character recognition) has to deal with this problem all the time: picking the right letter based on the scanned page, but also based on the surrounding context.

  • 1
    $\begingroup$ Oh, and to decode you should probably take the pigeonhole principle into account: if two passages are paired up, neither can be paired to another. This is doable with the Hungarian algorithm once you have the probabilities, once you’ve used the Gale and Church model. $\endgroup$ May 19 at 1:30
  • 1
    $\begingroup$ I can’t fully tell what you mean. I would encourage you to post that as a new question with more info. $\endgroup$ May 19 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.