Description: Some languages considered by linguistics as languages with extreme phonetic irregularities which mean that many words doesn't sounds like the way they "should" sound by just reading the phonemes.
The spelling for such languages can be significantly improved if knowledge about pronunciation and sound becomes the central part of the spelling algorithm.

English is a language with high irregularity corresponds to its pronunciation.
(One of the many examples for the high irregularity of the English language is the word "school" where among others the following writings produce the same sound: skool, scool, scule, skule. The sources of irregularity are positional spelling, i. e., the sound of letters varies according to the position in a word, and polyethylene, i.e., letters can produce different sounds.)

The difficulty of a spelling problem depends on both the type of the spelling error to be detected and the underlying language.
The algorithm can never know (even by using brute force) what is the correct word that the person thought of, this property of the problem make this problem a problem that can solved by specific heuristics.
Typical types of misspelling: (1) Permutations or dropped letters (2) Misremembering spelling details (3) Trying to spell out pronunciation
This problem focuses on #3

Phonetic misspelling is an algorithm that try to solves misspelling of irregular languages, English in particular.

Algorithmic problem:
Input - a dictionary D ,a possibly misspelled word w and k a number of wanted results.
Output - the most similar words w(1); : : : ;w(k) from D with respect to w.

Algorithmic Solution:
for a word w, we will look for a word v that generate the maximum value for the function below:
pi.JPG
while:
pi2.JPG
while P(Sv,t,Sw,t) is language-dependent and contains about 2500 segment similarities for the English language
For Instance:
pic3.JPG

Heuristics:
1) Segmentation Heuristic. Segmentations are constructed stepwise,
striving for a minimum length difference of the residual strings.

2) Early Pruning. Exploitation of the monotonicity of for pruning.

3) Iterative Deepening. Candidates for a Depth-First Search are chosen
from a pool whose pruning threshold is successively lowered.

4) Nogood Construction. Segments that are unlikely to match
stored in a special nogood table for.

5) Memorization. Strings with high -values are remembered.

References: Phonetic Spelling and Heuristic Search by Benno Stein and Daniel Curatolo
See Also: algorithm to find phonetic spell mistakes in English names