Недавно я натолкнулся на [вопрос][1] на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из _wtrbtl_ получать _water bottle_, а из _bsktball_ — _basketball_. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.



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



Вооружившись этими знаниями и Питоном, я за вечер создал с нуля модельку, способную, обучившись на тексте "Властелина колец" (!), распознавать сокращения вполне современных спортивных терминов.


![][3] [Читать дальше →][4]

[1]: https://stackoverflow.com/questions/43510778
[2]: http://web.stanford.edu/~jurafsky/slp3/5.pdf
[3]: https://habrastorage.org/webt/1a/fo/ar/1afoarhel5lgye2tszzns09ny9u.png
[4]: https://habrahabr.ru/post/346578/?utm_source=habrahabr&utm_medium=rss&utm_campaign=346578#habracut