Как обучть мдль пнмть упртые скрщня

Недавно я натолкнулся на вопрос на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из wtrbtl получать water bottle, а из bsktball — basketball. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.

Вопрос меня заинтриговал, и я полез разбираться, какие алгоритмы и математика лежат в основе современных опечаточников (spell-checkers). Оказалось, что хороший опечаточник можно собрать из n-граммной языковой модели, модели вероятности искажений слов, и жадного алгоритма поиска по лучу (beam search). Вся конструкция вместе называется модель зашумлённого канала (noisy channel).