{"id":202908,"date":"2013-11-20T18:29:03","date_gmt":"2013-11-20T14:29:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=202908"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=202908","title":{"rendered":"<span class=\"post_title\">\u0410\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u043c\u043e\u0434\u0435\u043b\u044c Noisy Channel<\/span>"},"content":{"rendered":"<div class=\"content html_format\">   \t<img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/8c6\/7d0\/cc1\/8c67d0cc19860840fc2f3a60635f98d7.jpg\" align=\"right\"\/> \u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a. \u041d\u0430 \u0434\u043d\u044f\u0445 \u0443 \u043c\u0435\u043d\u044f \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0441\u0442-\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043e\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0441\u0442\u0430. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043d\u0435 \u043f\u043b\u043e\u0445\u043e \u043f\u043e\u0434\u043e\u0448\u043b\u0430 \u043e\u0434\u043d\u0430 \u0438\u0437 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435, \u0445\u043e\u0442\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0441\u043b\u0435\u0433\u043a\u0430 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u043e\u0434 \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442 \u0437\u0430\u0434\u0430\u0447\u0438. \u042d\u0442\u043e\u0442 \u043f\u043e\u0441\u0442 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d <a href=\"http:\/\/en.wikipedia.org\/wiki\/Noisy_channel_model\">\u043c\u043e\u0434\u0435\u043b\u0438 Noisy Channel<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u043c\u044b \u0438\u0437\u0443\u0447\u0438\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c, \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043d\u0430 c# \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430, \u043e\u0431\u0443\u0447\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c <a href=\"http:\/\/norvig.com\/ngrams\/\">\u043d\u0430 \u0431\u0430\u0437\u0435 \u041f\u0438\u0442\u0435\u0440\u0430 \u041d\u043e\u0440\u0432\u0438\u0433\u0430<\/a>, \u0438 \u043f\u043e\u0434 \u043a\u043e\u043d\u0435\u0446 \u043f\u0440\u043e\u0442\u0435\u0441\u0442\u0438\u0440\u0443\u0435\u043c \u0442\u043e \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f.<\/p>\n<p>  <a name=\"habracut\"><\/a><\/p>\n<h4>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u2014 1<\/h4>\n<p>  \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438. \u0418\u0442\u0430\u043a \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u043b\u043e\u0432\u043e <b>w<\/b> \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0438\u0437 <b>m<\/b> \u0431\u0443\u043a\u0432, \u043d\u043e \u043a\u0430\u043a\u0438\u043c \u0442\u043e \u043d\u0435\u0432\u0435\u0434\u043e\u043c\u044b\u043c \u0432\u0430\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c \u043d\u0430 \u0431\u0443\u043c\u0430\u0433\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0441\u043b\u043e\u0432\u043e <b>x<\/b> \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0438\u0437 <b>n<\/b> \u0431\u0443\u043a\u0432. \u041a\u0441\u0442\u0430\u0442\u0438 \u0432\u044b \u043a\u0430\u043a \u0440\u0430\u0437 \u0438 \u0435\u0441\u0442\u044c \u0442\u043e\u0442 \u0441\u0430\u043c\u044b\u0439 <i>noisy channel<\/i>, \u043a\u0430\u043d\u0430\u043b \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0441 \u0448\u0443\u043c\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0441\u043a\u0430\u0437\u0438\u043b \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e <b>w<\/b> (\u0438\u0437 \u0432\u0441\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432) \u0434\u043e \u043d\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0433\u043e <b>x<\/b> (\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0441\u0435\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u0441\u043b\u043e\u0432). <\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/164\/739\/ac1\/164739ac11d0aa25e31db1f31df3f1b9.png\"\/><\/p>\n<p>  \u041c\u044b \u0445\u043e\u0442\u0438\u043c \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u043e\u0435 \u0441\u043b\u043e\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432\u044b \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u043b\u0438 \u043f\u0440\u0438 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0438 \u0441\u043b\u043e\u0432\u0430 <b>x<\/b>. \u0417\u0430\u043f\u0438\u0448\u0435\u043c \u044d\u0442\u0443 \u043c\u044b\u0441\u043b\u044c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u043c\u043e\u0434\u0435\u043b\u044c \u043f\u043e \u0441\u0432\u043e\u0435\u0439 \u0438\u0434\u0435\u0435 \u043f\u043e\u0445\u043e\u0436\u0430 \u043d\u0430 \u043c\u043e\u0434\u0435\u043b\u044c <a href=\"http:\/\/habrahabr.ru\/post\/184574\/\">\u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u0431\u0430\u0439\u0435\u0441\u043e\u0432\u0441\u043a\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430<\/a>, \u0445\u043e\u0442\u044f \u0434\u0430\u0436\u0435 \u043f\u0440\u043e\u0449\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/270\/e97\/d6b\/270e97d6b378256fb0493d8b87b1679e.gif\"\/>  <\/p>\n<ul>\n<li> <b>V<\/b> \u2014 \u0441\u043f\u0438\u0441\u043e\u043a \u0432\u0441\u0435\u0445 \u0441\u043b\u043e\u0432 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430.<\/li>\n<\/ul>\n<p>  \u0414\u0430\u043b\u0435\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0443 \u0411\u0430\u0439\u0435\u0441\u0430 \u0440\u0430\u0437\u0432\u0435\u0440\u043d\u0435\u043c \u043f\u0440\u0438\u0447\u0438\u043d\u0443 \u0438 \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435, \u043f\u043e\u043b\u043d\u0443\u044e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c <b>x<\/b> \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0443\u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f, \u0442.\u043a. \u043e\u043d \u043f\u0440\u0438 <i>argmax<\/i> \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 <b>w<\/b>:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/11f\/4a5\/3bd\/11f4a53bd450c2b456c6ee18c829a7d6.gif\"\/><\/p>\n<ul>\n<li> <b>P(w)<\/b> \u2014 \u0430\u043f\u0440\u0438\u043e\u0440\u043d\u0430\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u043b\u043e\u0432\u0430 <b>w<\/b> \u0432 \u044f\u0437\u044b\u043a\u0435; \u044d\u0442\u043e\u0442 \u0447\u043b\u0435\u043d \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0438\u0437 \u0441\u0435\u0431\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430 (<i>language model<\/i>), \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <a href=\"http:\/\/en.wikipedia.org\/wiki\/Language_model\">\u043c\u043e\u0434\u0435\u043b\u044c<\/a> <a href=\"http:\/\/en.wikipedia.org\/wiki\/N-gram\">unigram<\/a>, \u0445\u043e\u0442\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0432\u044b \u0432 \u043f\u0440\u0430\u0432\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u043c\u043e\u0434\u0435\u043b\u0438; \u0442\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u0447\u043b\u0435\u043d\u0430 \u043b\u0435\u0433\u043a\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0437 \u0431\u0430\u0437\u044b \u0441\u043b\u043e\u0432 \u044f\u0437\u044b\u043a\u0430;<\/li>\n<li> <b>P(x | w)<\/b> \u2014 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e <b>w<\/b> \u0431\u044b\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043e \u043a\u0430\u043a <b>x<\/b>, \u044d\u0442\u043e\u0442 \u0447\u043b\u0435\u043d \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <i>channel model<\/i>; \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u043e\u0431\u043b\u0430\u0434\u0430\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0431\u0430\u0437\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u043e\u0448\u0438\u0431\u0438\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u044f\u0437\u044b\u043a\u0430, \u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u0447\u043b\u0435\u043d\u0430 \u043d\u0435 \u0432\u044b\u0437\u0432\u0430\u043b\u043e \u0431\u044b \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u0435\u0439, \u043d\u043e \u043a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e \u0442\u0430\u043a\u043e\u0439 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0431\u0430\u0437\u044b \u043d\u0435\u0442, \u043d\u043e \u0435\u0441\u0442\u044c \u043f\u043e\u0445\u043e\u0436\u0438\u0435 \u0431\u0430\u0437\u044b \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430, \u0442\u0430\u043a \u0447\u0442\u043e \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0442\u043e \u0432\u044b\u043a\u0440\u0443\u0447\u0438\u0432\u0430\u0442\u044c\u0441\u044f (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 <a href=\"http:\/\/norvig.com\/ngrams\/\">\u0437\u0434\u0435\u0441\u044c<\/a> \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0431\u0430\u0437\u0430 \u0438\u0437 333333 \u0441\u043b\u043e\u0432 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430, \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f 7481 \u0435\u0441\u0442\u044c \u0441\u043b\u043e\u0432\u0430 \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438).<\/li>\n<\/ul>\n<h4>\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 <b>P(x | w)<\/b><\/h4>\n<p>  \u0422\u0443\u0442 \u043a \u043d\u0430\u043c \u043d\u0430 \u043f\u043e\u043c\u043e\u0449\u044c \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Damerau%E2%80%93Levenshtein_distance\">\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0414\u0430\u043c\u0435\u0440\u0430\u0443-\u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430<\/a> \u2014 \u044d\u0442\u043e \u043c\u0435\u0440\u0430 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u0430\u044f \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, \u0437\u0430\u043c\u0435\u043d\u044b \u0438 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u043e\u043a\u0438 <i>source<\/i> \u043a \u0441\u0442\u0440\u043e\u043a\u0435 <i>target<\/i>. \u041c\u044b \u0436\u0435 \u0434\u0430\u043b\u0435\u0435 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <a href=\"http:\/\/en.wikipedia.org\/wiki\/Levenshtein_distance\">\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430<\/a>, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0442\u0430\u043a \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0449\u0435. <a href=\"http:\/\/habrahabr.ru\/post\/114997\/\">\u041e\u0431\u0430 \u044d\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u043c\u0438 \u0445\u043e\u0440\u043e\u0448\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u0432 \u0442\u0443\u0442<\/a>, \u0442\u0430\u043a \u0447\u0442\u043e \u044f \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f \u043d\u0435 \u0431\u0443\u0434\u0443, \u0430 \u0441\u0440\u0430\u0437\u0443 \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u043a\u043e\u0434:<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cs\">public static int LevenshteinDistance(string s, string t) {     int[,] d = new int[s.Length + 1, t.Length + 1];     for (int i = 0; i &lt; s.Length + 1; i++)     {         d[i, 0] = i;     }     for (int j = 1; j &lt; t.Length + 1; j++)     {         d[0, j] = j;     }      for (int i = 1; i &lt;= s.Length; i++)     {         for (int j = 1; j &lt;= t.Length; j++)         {             d[i, j] = (new int[]             {                 d[i - 1, j] + 1, \/\/ del                 d[i, j - 1] + 1, \/\/ ins                 d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub             }).Min();         }     }     return d[s.Length, t.Length]; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u043e\u043e\u0431\u0449\u0430\u0435\u0442 \u043d\u0430\u043c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 \u0437\u0430\u043c\u0435\u043d\u044b \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0434\u043b\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u043a \u0434\u0440\u0443\u0433\u043e\u043c\u0443, \u043d\u043e \u043d\u0430\u043c \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e, \u0430 \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a \u0436\u0435 \u0441\u043f\u0438\u0441\u043e\u043a \u044d\u0442\u0438\u0445 \u0441\u0430\u043c\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043d\u0430\u0437\u043e\u0432\u0435\u043c \u044d\u0442\u043e backtrace \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u041d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u0434 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e \u0431\u044b \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 <b>d<\/b>, \u0442\u0430\u043a \u0436\u0435 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u043b\u0430\u0441\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 <i>b<\/i>. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u0441\u043b\u043e\u0432 <b>ca<\/b> \u0438 <b>abc<\/b>:<\/p>\n<table>\n<tr>\n<td><b>d<\/b><\/td>\n<td><b>b<\/b> (0 \u2014 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 <i>source<\/i>, \u0441\u043b\u0435\u0432\u0430; 1 \u2014 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0438\u0437 <i>target <\/i>\u0432 <i>source<\/i>; 2 \u2014 \u0437\u0430\u043c\u0435\u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 <i>source <\/i>\u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0437 <i>target<\/i>)<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/5fb\/3a6\/4a1\/5fb3a64a1699fa04bd8823b151b49ca9.png\"\/><\/td>\n<td><img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/45b\/b3e\/539\/45bb3e5399e934de49bd726f87abd14d.png\"\/><\/td>\n<\/tr>\n<\/table>\n<p>  \u041a\u0430\u043a \u0432\u044b \u043f\u043e\u043c\u043d\u0438\u0442\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 <b>(i,j)<\/b> \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 <b>d<\/b> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<pre><code class=\"cs\">d[i, j] = (new int[] {     d[i - 1, j] + 1, \/\/ del - 0     d[i, j - 1] + 1, \/\/ ins - 1     d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub - 2 }).Min(); <\/code><\/pre>\n<p>  \u041d\u0430\u043c \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0432 \u044f\u0447\u0435\u0439\u043a\u0443 <b>(i,j)<\/b> \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 <b>b<\/b> \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 (0 \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, 1 \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 2 \u0434\u043b\u044f \u0437\u0430\u043c\u0435\u043d\u044b), \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044d\u0442\u043e\u0442 \u043a\u0443\u0441\u043e\u043a \u043a\u043e\u0434\u0430 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<pre><code class=\"cs\">IList&lt;int&gt; vals = new List&lt;int&gt;() {     d[i - 1, j] + 1, \/\/ del     d[i, j - 1] + 1, \/\/ ins     d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub }; d[i, j] = vals.Min(); int idx = vals.IndexOf(d[i, j]); b[i, j] = idx; <\/code><\/pre>\n<p>  \u041a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b, \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u0440\u0443\u0434\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c backtrace (\u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u0438 \u043d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0430\u0445 \u0432\u044b\u0448\u0435). \u042d\u0442\u043e \u043f\u0443\u0442\u044c \u0438\u0437 \u043f\u0440\u0430\u0432\u043e\u0439 \u043d\u0438\u0436\u043d\u0435\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043f\u043e \u043f\u0443\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u041e\u043f\u0438\u0448\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:  <\/p>\n<ol>\n<li> \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u043f\u0440\u0430\u0432\u0443\u044e \u043d\u0438\u0436\u043d\u044e\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u043a\u0430\u043a \u0442\u0435\u043a\u0443\u0449\u0443\u044e<\/li>\n<li> \u0434\u0435\u043b\u0430\u0435\u043c \u043e\u0434\u043d\u043e \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439<br \/> \n<ul>\n<li> \u0435\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u0438 \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u0432\u0432\u0435\u0440\u0445 (\u043a\u0440\u0430\u0441\u043d\u0430\u044f \u0441\u0442\u0440\u0435\u043b\u043a\u0430)<\/li>\n<li> \u0435\u0441\u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438 \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u0432\u043b\u0435\u0432\u043e (\u043a\u0440\u0430\u0441\u043d\u0430\u044f \u0441\u0442\u0440\u0435\u043b\u043a\u0430)<\/li>\n<li> \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u0430, \u0430 \u0442\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b <b>\u043d\u0435<\/b> \u0440\u0430\u0432\u043d\u044b, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0438 \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u043d\u0430\u043b\u0435\u0432\u043e \u0438 \u0432\u0432\u0435\u0440\u0445 (\u043a\u0440\u0430\u0441\u043d\u0430\u044f \u0441\u0442\u0440\u0435\u043b\u043a\u0430)<\/li>\n<li> \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u0430, \u043d\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0440\u0430\u0432\u043d\u044b, \u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u043d\u0430\u043b\u0435\u0432\u043e \u0438 \u0432\u0432\u0435\u0440\u0445 (\u0441\u0438\u043d\u044f\u044f \u0441\u0442\u0440\u0435\u043b\u043a\u0430)<\/li>\n<\/ul>\n<p>   <\/li>\n<li> \u0435\u0441\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0435 \u0440\u0430\u0432\u043d\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430, \u0442\u043e \u043d\u0430 \u043f\u0443\u043d\u043a\u0442 \u043d\u0430\u0437\u0430\u0434, \u0438\u043d\u0430\u0447\u0435 \u0441\u0442\u043e\u043f<\/li>\n<\/ol>\n<p>  \u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0449\u0443\u044e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430, \u0430 \u0442\u0430\u043a \u0436\u0435 backtrace:<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u0441 backtrace&#39;\u043e\u043c<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cs\">\/\/del - 0, ins - 1, sub - 2  public static Tuple&lt;int, IList&lt;Tuple&lt;int, string&gt;&gt;&gt; LevenshteinDistanceWithBacktrace(string s, string t) {     int[,] d = new int[s.Length + 1, t.Length + 1];     int[,] b = new int[s.Length + 1, t.Length + 1];     for (int i = 0; i &lt; s.Length + 1; i++)     {         d[i, 0] = i;     }     for (int j = 1; j &lt; t.Length + 1; j++)     {         d[0, j] = j;         b[0, j] = 1;     }      for (int i = 1; i &lt;= s.Length; i++)     {         for (int j = 1; j &lt;= t.Length; j++)         {             IList&lt;int&gt; vals = new List&lt;int&gt;()             {                 d[i - 1, j] + 1, \/\/ del                 d[i, j - 1] + 1, \/\/ ins                 d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub             };             d[i, j] = vals.Min();             int idx = vals.IndexOf(d[i, j]);             b[i, j] = idx;         }     }      List&lt;Tuple&lt;int, string&gt;&gt; bt = new List&lt;Tuple&lt;int, string&gt;&gt;();     int x = s.Length;     int y = t.Length;     while (bt.Count != d[s.Length, t.Length])     {         switch (b[x, y])         {             case 0:                 x--;                 bt.Add(new Tuple&lt;int, string&gt;(0, s[x].ToString()));                 break;             case 1:                 y--;                 bt.Add(new Tuple&lt;int, string&gt;(1, t[y].ToString()));                 break;             case 2:                 x--;                 y--;                 if (s[x] != t[y])                 {                     bt.Add(new Tuple&lt;int, string&gt;(2, s[x] + &quot;&quot; + t[y]));                 }                 break;         }     }     bt.Reverse();      return new Tuple&lt;int, IList&lt;Tuple&lt;int, string&gt;&gt;&gt;(d[s.Length, t.Length], bt); } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u0440\u0442\u0435\u0436, \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430, \u0430 \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u0430\u0440 &lt;id \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0441\u0442\u0440\u043e\u043a\u0430&gt;, \u0441\u0442\u0440\u043e\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0438 \u0438\u0437 \u0434\u0432\u0443\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0437\u0430\u043c\u0435\u043d\u044b (\u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u043c\u0435\u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439). <\/p>\n<p>  PS: \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u043c\u0435\u0442\u0438\u0442, \u0447\u0442\u043e \u0438\u0437 \u043f\u0440\u0430\u0432\u043e\u0439 \u043d\u0438\u0436\u043d\u0435\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u043f\u043e \u043f\u0443\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438, \u044d\u0442\u043e \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u043d\u043e \u043c\u044b \u0435\u0433\u043e \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0442\u0430\u043a \u0436\u0435 \u043e\u043f\u0443\u0441\u0442\u0438\u043c. <\/p>\n<h4>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u2014 2<\/h4>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043e\u043f\u0438\u0448\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u0432\u044b\u0448\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u0444\u043e\u0440\u043c\u0443\u043b. \u0414\u043b\u044f \u0434\u0432\u0443\u0445 \u0441\u043b\u043e\u0432 <b>x<\/b> \u0438 <b>w<\/b> \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u043a\u043e \u0432\u0442\u043e\u0440\u043e\u043c\u0443, \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0431\u0443\u043a\u0432\u043e\u0439 <b>f<\/b>, \u0442\u043e\u0433\u0434\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043b\u043e\u0432\u043e <b>x<\/b> \u043a\u0430\u043a <b>w<\/b> \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0432\u0435\u0441\u044c \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u0448\u0438\u0431\u043e\u043a <b>f<\/b> \u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438, \u0447\u0442\u043e \u043c\u044b \u043f\u0438\u0441\u0430\u043b\u0438 \u0438\u043c\u0435\u043d\u043d\u043e <b>x<\/b>, \u0430 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u043b\u0438 <b>w<\/b>:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/c6d\/5b1\/4e2\/c6d5b14e2ff002a4fa50027465e7003c.gif\"\/><\/p>\n<p>  \u0412\u043e\u0442 \u0442\u0443\u0442 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u044f, \u043f\u043e\u0445\u043e\u0436\u0438\u0435 \u043d\u0430 \u0442\u0435 \u0447\u0442\u043e \u0431\u044b\u043b\u0438 \u0432 <a href=\"http:\/\/habrahabr.ru\/post\/184574\/\">\u043d\u0430\u0438\u0432\u043d\u043e\u043c \u0431\u0430\u0439\u0435\u0441\u043e\u0432\u0441\u043a\u043e\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0435<\/a>:  <\/p>\n<ul>\n<li> \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0448\u0438\u0431\u043a\u0438 \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f<\/li>\n<li> \u043e\u0448\u0438\u0431\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u0442\u043e\u0433\u043e \u043a\u0430\u043a\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u043c\u044b \u043d\u0430\u043f\u0438\u0441\u0430\u043b\u0438 \u0438 \u043e\u0442 \u0442\u043e\u0433\u043e \u0447\u0442\u043e \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u043b\u0438<\/li>\n<\/ul>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/6a0\/401\/02c\/6a040102c941d06cc3ee057ca3a9347d.gif\"\/><\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e \u0431\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u043e\u0448\u0438\u0431\u043e\u043a (\u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u0442\u043e\u0433\u043e \u0432 \u043a\u0430\u043a\u0438\u0445 \u0441\u043b\u043e\u0432\u0430\u0445 \u043e\u043d\u0438 \u0431\u044b\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u043d\u044b) \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u043c\u0435\u0442\u044c \u043d\u0430 \u0440\u0443\u043a\u0430\u0445 \u043b\u044e\u0431\u0443\u044e \u0431\u0430\u0437\u0443 \u0441\u043b\u043e\u0432 \u0441 \u0438\u0445 \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u044b\u043c \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0435\u043c. \u0417\u0430\u043f\u0438\u0448\u0435\u043c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443, \u0432\u043e \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0431\u043b\u0438\u0437\u043a\u0438\u043c\u0438 \u043a \u043d\u0443\u043b\u044e, \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 log space:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/081\/ac4\/57e\/081ac457eb5b09189f4465432db7d4d8.gif\"\/><\/p>\n<p>  \u0418\u0442\u0430\u043a, \u0447\u0442\u043e \u0436\u0435 \u043c\u044b \u0438\u043c\u0435\u0435\u043c? \u0415\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u043d\u0430 \u0440\u0443\u043a\u0430\u0445 \u0435\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0442\u0435\u043a\u0441\u0442\u043e\u0432 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0430\u043f\u0440\u0438\u043e\u0440\u043d\u044b\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u043b\u043e\u0432 \u0432 \u044f\u0437\u044b\u043a\u0435; \u0442\u0430\u043a \u0436\u0435 \u0438\u043c\u0435\u044f \u043d\u0430 \u0440\u0443\u043a\u0430\u0445 \u0431\u0430\u0437\u0443 \u0441\u043b\u043e\u0432 \u0441 \u0438\u0445 \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u044b\u043c \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0435\u043c, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u043e\u0448\u0438\u0431\u043e\u043a, \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u0431\u0430\u0437 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0447\u0442\u043e \u0431\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c.<\/p>\n<h4>\u0420\u0430\u0437\u043c\u044b\u0442\u0438\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u043e\u0448\u0438\u0431\u043e\u043a<\/h4>\n<p>  \u041f\u0440\u0438 \u043f\u0440\u043e\u0431\u0435\u0433\u0435 \u043f\u043e \u0432\u0441\u0435 \u0431\u0430\u0437\u0435 \u0441\u043b\u043e\u0432 \u043f\u0440\u0438 <i>argmax<\/i>, \u043c\u044b \u043d\u0438 \u0440\u0430\u0437\u0443 \u043d\u0435 \u043d\u0430\u0442\u043a\u043d\u0435\u043c\u0441\u044f \u043d\u0430 \u0441\u043b\u043e\u0432\u0430 \u0441 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e. \u041d\u043e \u0432\u043e\u0442 \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0441\u043b\u043e\u0432\u0430 <b>x<\/b> \u043a \u0441\u043b\u043e\u0432\u0443 <b>w<\/b> \u043c\u043e\u0433\u0443\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b\u0438\u0441\u044c \u0432 \u043d\u0430\u0448\u0435\u0439 \u0431\u0430\u0437\u0435 \u043e\u0448\u0438\u0431\u043e\u043a. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u043c \u043f\u043e\u043c\u043e\u0436\u0435\u0442 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Additive_smoothing\">additive smoothing \u0438\u043b\u0438 \u0440\u0430\u0437\u043c\u044b\u0442\u0438\u0435 \u043f\u043e \u041b\u0430\u043f\u043b\u0430\u0441\u0443<\/a> (\u043e\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0432 <a href=\"http:\/\/habrahabr.ru\/post\/184574\/\">\u043d\u0430\u0438\u0432\u043d\u043e\u043c \u0431\u0430\u0439\u0435\u0441\u043e\u0432\u0441\u043a\u043e\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0435<\/a>). \u041d\u0430\u043f\u043e\u043c\u043d\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443, \u0432 \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. \u0415\u0441\u043b\u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u0438 <b>f<\/b> \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0431\u0430\u0437\u0435 <b>n<\/b> \u0440\u0430\u0437, \u043f\u0440\u0438 \u0442\u043e\u043c \u0447\u0442\u043e \u0432\u0441\u0435\u0433\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u0432 \u0431\u0430\u0437\u0435 <b>m<\/b>, \u0430 \u0442\u0438\u043f\u043e\u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u0438 <b>t<\/b> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u0437\u0430\u043c\u0435\u043d\u044b, \u043d\u0435 \u0442\u043e \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u043c\u0435\u043d\u0430 &quot;<i>a<\/i> \u043d\u0430 <i>b<\/i>&quot;, \u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u0435\u0433\u043e \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0430\u0440 &quot;* \u043d\u0430 *&quot;), \u0442\u043e \u0440\u0430\u0437\u043c\u044b\u0442\u0430\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0433\u0434\u0435 <b>k<\/b> \u2014 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0440\u0430\u0437\u043c\u044b\u0442\u0438\u044f:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/1ce\/536\/093\/1ce536093741ce9c13a3b665d4263cb9.gif\"\/><\/p>\n<p>  \u0422\u043e\u0433\u0434\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0438 \u0440\u0430\u0437\u0443 \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b\u0430\u0441\u044c \u0432 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0435\u0439 \u0431\u0430\u0437\u0435 (<b>n = 0<\/b>) \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/42f\/afc\/bf7\/42fafcbf7e229fde5bf6c99efc6cee76.gif\"\/><\/p>\n<h4>\u0421\u043a\u043e\u0440\u043e\u0441\u0442\u044c<\/h4>\n<p>  \u0412\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441, \u0430 \u043a\u0430\u043a \u0431\u044b\u0442\u044c \u0441\u043e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c\u044e \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0432\u0435\u0434\u044c \u043d\u0430\u043c \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0442\u044c \u043f\u043e \u0432\u0441\u0435\u0439 \u0431\u0430\u0437\u0435 \u0441\u043b\u043e\u0432, \u0430 \u044d\u0442\u043e \u0441\u043e\u0442\u043d\u0438 \u0442\u044b\u0441\u044f\u0447 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u0441 backtrace&#8217;\u043e\u043c, \u0430 \u0442\u0430\u043a \u0436\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u043b\u043e\u0432 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u043e\u0448\u0438\u0431\u043a\u0438 (\u0441\u0443\u043c\u043c\u0430 \u0447\u0438\u0441\u0435\u043b, \u0435\u0441\u043b\u0438 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0431\u0430\u0437\u0435 \u043f\u0440\u0435\u0434\u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u044b). \u0422\u0443\u0442 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u043d\u0430 \u043f\u043e\u043c\u043e\u0449\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0444\u0430\u043a\u0442:<\/p>\n<ul>\n<li> 80% \u0432\u0441\u0435\u0445 \u043f\u0435\u0447\u0430\u0442\u043d\u044b\u0445 \u043e\u0448\u0438\u0431\u043e\u043a \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 1 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0442.\u0435. \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u0440\u0430\u0432\u043d\u044b\u043c \u0435\u0434\u0438\u043d\u0438\u0446\u0435<\/li>\n<li> \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435 \u043f\u0435\u0447\u0430\u0442\u043d\u044b\u0435 \u043e\u0448\u0438\u0431\u043a\u0438 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 2 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/li>\n<\/ul>\n<p>  \u041d\u0443 \u0430 \u0434\u0430\u043b\u0435\u0435 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u044b\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0442\u0440\u044e\u043a\u0438. \u042f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u0439 \u0438 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043c\u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0432\u0430 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0432 t \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0441\u043b\u043e\u0432\u0430, \u0442\u043e \u0438\u0445 \u0434\u043b\u0438\u043d\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u043d\u0430 t. \u041f\u0440\u0438 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0430, \u044f \u0441\u043e\u0437\u0434\u0430\u044e \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u0438\u043d\u044b \u0441\u043b\u043e\u0432, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u2014 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u043b\u043e\u0432 \u044d\u0442\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430.<\/p>\n<h4>\u041a\u043e\u0434<\/h4>\n<p>  \u041f\u0440\u0438\u0432\u0435\u0434\u0443 \u043a\u043e\u0434 \u043a\u043b\u0430\u0441\u0441\u0430 NoisyChannel \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443 \u043c\u0435\u043d\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f:<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">NoisyChannel<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cs\">public class NoisyChannel {      #region vars      private string[] _words = null;     private double[] _wLogPriors = null;             private IDictionary&lt;int, IList&lt;int&gt;&gt; _wordLengthDictionary = null; \/\/length of word - word indices      private IDictionary&lt;int, IDictionary&lt;string, double&gt;&gt; _mistakeLogProbs = null;     private double _lf = 1d;     private IDictionary&lt;int, int&gt; _mNorms = null;      #endregion      #region ctor      public NoisyChannel(string[] words, long[] wordFrequency,                          IDictionary&lt;int, IDictionary&lt;string, int&gt;&gt; mistakeFrequency,                          int mistakeProbSmoothing = 1)     {         _words = words;         _wLogPriors = new double[_words.Length];         _wordLengthDictionary = new SortedDictionary&lt;int, IList&lt;int&gt;&gt;();         double wNorm = wordFrequency.Sum();         for (int i = 0; i &lt; _words.Length; i++)         {             _wLogPriors[i] = Math.Log((wordFrequency[i] + 0d)\/wNorm);              int wl = _words[i].Length;             if (!_wordLengthDictionary.ContainsKey(wl))             {                 _wordLengthDictionary.Add(wl, new List&lt;int&gt;());             }             _wordLengthDictionary[wl].Add(i);         }          _lf = mistakeProbSmoothing;         _mistakeLogProbs = new Dictionary&lt;int, IDictionary&lt;string, double&gt;&gt;();         _mNorms = new Dictionary&lt;int, int&gt;();         foreach (int mType in mistakeFrequency.Keys)         {             int mNorm = mistakeFrequency[mType].Sum(m =&gt; m.Value);             _mNorms.Add(mType, mNorm);             int mUnique = mistakeFrequency[mType].Count;             _mistakeLogProbs.Add(mType, new Dictionary&lt;string, double&gt;());             foreach (string m in mistakeFrequency[mType].Keys)             {                 _mistakeLogProbs[mType].Add(m,                         Math.Log((mistakeFrequency[mType][m] + _lf)\/                                     (mNorm + _lf*mUnique))                     );             }         }     }      #endregion      #region correction      public IDictionary&lt;string, double&gt; GetCandidates(string s, int maxEditDistance = 2)     {         IDictionary&lt;string, double&gt; candidates = new Dictionary&lt;string, double&gt;();         IList&lt;int&gt; dists = new List&lt;int&gt;();         for (int i = s.Length - maxEditDistance; i &lt;= s.Length + maxEditDistance; i++)         {             if (i &gt;= 0)             {                 dists.Add(i);             }         }         foreach (int dist in dists)         {             foreach (int tIdx in _wordLengthDictionary[dist])             {                 string t = _words[tIdx];                 Tuple&lt;int, IList&lt;Tuple&lt;int, string&gt;&gt;&gt; d = LevenshteinDistanceWithBacktrace(s, t);                 if (d.Item1 &gt; maxEditDistance)                 {                     continue;                 }                  double p = _wLogPriors[tIdx];                 foreach (Tuple&lt;int, string&gt; m in d.Item2)                 {                     if (!_mistakeLogProbs[m.Item1].ContainsKey(m.Item2))                     {                         p += _lf\/(_mNorms[m.Item1] + _lf*_mistakeLogProbs[m.Item1].Count);                     }                     else                     {                         p += _mistakeLogProbs[m.Item1][m.Item2];                     }                 }                 candidates.Add(_words[tIdx], p);             }         }         candidates = candidates.OrderByDescending(c =&gt; c.Value).ToDictionary(c =&gt; c.Key, c =&gt; c.Value);         return candidates;     }      #endregion      #region static helper      \/\/del - 0, ins - 1, sub - 2      public static Tuple&lt;int, IList&lt;Tuple&lt;int, string&gt;&gt;&gt; LevenshteinDistanceWithBacktrace(string s, string t)     {         int[,] d = new int[s.Length + 1, t.Length + 1];         int[,] b = new int[s.Length + 1, t.Length + 1];         for (int i = 0; i &lt; s.Length + 1; i++)         {             d[i, 0] = i;         }         for (int j = 1; j &lt; t.Length + 1; j++)         {             d[0, j] = j;             b[0, j] = 1;         }          for (int i = 1; i &lt;= s.Length; i++)         {             for (int j = 1; j &lt;= t.Length; j++)             {                 IList&lt;int&gt; vals = new List&lt;int&gt;()                 {                     d[i - 1, j] + 1, \/\/ del                     d[i, j - 1] + 1, \/\/ ins                     d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub                 };                 d[i, j] = vals.Min();                 int idx = vals.IndexOf(d[i, j]);                 b[i, j] = idx;             }         }          List&lt;Tuple&lt;int, string&gt;&gt; bt = new List&lt;Tuple&lt;int, string&gt;&gt;();         int x = s.Length;         int y = t.Length;         while (bt.Count != d[s.Length, t.Length])         {             switch (b[x, y])             {                 case 0:                     x--;                     bt.Add(new Tuple&lt;int, string&gt;(0, s[x].ToString()));                     break;                 case 1:                     y--;                     bt.Add(new Tuple&lt;int, string&gt;(1, t[y].ToString()));                     break;                 case 2:                     x--;                     y--;                     if (s[x] != t[y])                     {                         bt.Add(new Tuple&lt;int, string&gt;(2, s[x] + &quot;&quot; + t[y]));                     }                     break;             }         }         bt.Reverse();          return new Tuple&lt;int, IList&lt;Tuple&lt;int, string&gt;&gt;&gt;(d[s.Length, t.Length], bt);     }          public static int LevenshteinDistance(string s, string t)         {             int[,] d = new int[s.Length + 1, t.Length + 1];             for (int i = 0; i &lt; s.Length + 1; i++)             {                 d[i, 0] = i;             }             for (int j = 1; j &lt; t.Length + 1; j++)             {                 d[0, j] = j;             }              for (int i = 1; i &lt;= s.Length; i++)             {                 for (int j = 1; j &lt;= t.Length; j++)                 {                     d[i, j] = (new int[]                     {                         d[i - 1, j] + 1, \/\/ del                         d[i, j - 1] + 1, \/\/ ins                         d[i - 1, j - 1] + (s[i - 1] == t[j - 1] ? 0 : 1) \/\/ sub                     }).Min();                 }             }             return d[s.Length, t.Length];         }      #endregion  } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043a\u043b\u0430\u0441\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438:  <\/p>\n<ul>\n<li> <i>string[] words<\/i> \u2014 \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043b\u043e\u0432 \u044f\u0437\u044b\u043a\u0430;<\/li>\n<li> <i>long[] wordFrequency<\/i> \u2014 \u0447\u0430\u0441\u0442\u043e\u0442\u0430 \u0441\u043b\u043e\u0432;<\/li>\n<li> <i>IDictionary&lt;int, IDictionary&lt;string, int&gt;&gt; mistakeFrequency<\/i><\/li>\n<li> <i>int mistakeProbSmoothing = 1<\/i> \u2014 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0440\u0430\u0437\u043c\u044b\u0442\u0438\u044f \u0447\u0430\u0441\u0442\u043e\u0442\u044b \u043e\u0448\u0438\u0431\u043e\u043a<\/li>\n<\/ul>\n<h4>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h4>\n<p>  \u0414\u043b\u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c <a href=\"http:\/\/norvig.com\/ngrams\/\">\u0431\u0430\u0437\u0443 \u041f\u0438\u0442\u0435\u0440\u0430 \u041d\u043e\u0440\u0432\u0438\u0433\u0430<\/a>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f 333333 \u0441\u043b\u043e\u0432 \u0441 \u0447\u0430\u0441\u0442\u043e\u0442\u0430\u043c\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 7481 \u0441\u043b\u043e\u0432\u043e \u0441 \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u044b\u043c\u0438 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f\u043c\u0438. \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u0438\u043d\u0438\u043d\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0430 NoisyChannel:<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0447\u0442\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cs\">string[] words = null; long[] wordFrequency = null;  #region read priors  if (!File.Exists(&quot;..\/..\/..\/Data\/words.bin&quot;) || !File.Exists(&quot;..\/..\/..\/Data\/wordFrequency.bin&quot;)) {     IDictionary&lt;string, long&gt; wf = new Dictionary&lt;string, long&gt;();     Console.Write(&quot;Reading data:&quot;);     using (StreamReader sr = new StreamReader(&quot;..\/..\/..\/Data\/count_1w.txt&quot;))     {         string line = sr.ReadLine();         while (line != null)         {             string[] parts = line.Split('\\t');             wf.Add(parts[0].Trim(), Convert.ToInt64(parts[1]));             line = sr.ReadLine();             Console.Write(&quot;.&quot;);         }         sr.Close();     }     Console.WriteLine(&quot;Done!&quot;);     words = wf.Keys.ToArray();     wordFrequency = wf.Values.ToArray();      using (FileStream fs = File.Create(&quot;..\/..\/..\/Data\/words.bin&quot;))     {         BinaryFormatter bf = new BinaryFormatter();         bf.Serialize(fs, words);         fs.Flush();         fs.Close();     }      using (FileStream fs = File.Create(&quot;..\/..\/..\/Data\/wordFrequency.bin&quot;))     {         BinaryFormatter bf = new BinaryFormatter();         bf.Serialize(fs, wordFrequency);         fs.Flush();         fs.Close();     } } else {     using (FileStream fs = File.OpenRead(&quot;..\/..\/..\/Data\/words.bin&quot;))     {         BinaryFormatter bf = new BinaryFormatter();         words = bf.Deserialize(fs) as string[];         fs.Close();     }      using (FileStream fs = File.OpenRead(&quot;..\/..\/..\/Data\/wordFrequency.bin&quot;))     {         BinaryFormatter bf = new BinaryFormatter();         wordFrequency = bf.Deserialize(fs) as long[];         fs.Close();     } }  #endregion   \/\/del - 0, ins - 1, sub - 2  IDictionary&lt;int, IDictionary&lt;string, int&gt;&gt; mistakeFrequency = new Dictionary&lt;int, IDictionary&lt;string, int&gt;&gt;();  #region read mistakes  IDictionary&lt;string, IList&lt;string&gt;&gt; misspelledWords = new SortedDictionary&lt;string, IList&lt;string&gt;&gt;(); using (StreamReader sr = new StreamReader(&quot;..\/..\/..\/Data\/spell-errors.txt&quot;)) {     string line = sr.ReadLine();     while (line != null)     {         string[] parts = line.Split(':');         string wt = parts[0].Trim();         misspelledWords.Add(wt, parts[1].Split(',').Select(w =&gt; w.Trim()).ToList());         line = sr.ReadLine();     }     sr.Close(); }              mistakeFrequency.Add(0, new Dictionary&lt;string, int&gt;()); mistakeFrequency.Add(1, new Dictionary&lt;string, int&gt;()); mistakeFrequency.Add(2, new Dictionary&lt;string, int&gt;()); foreach (string s in misspelledWords.Keys) {     foreach (string t in misspelledWords[s])     {         var d = NoisyChannel.LevenshteinDistanceWithBacktrace(s, t);         foreach (Tuple&lt;int, string&gt; ml in d.Item2)         {             if (!mistakeFrequency[ml.Item1].ContainsKey(ml.Item2))             {                 mistakeFrequency[ml.Item1].Add(ml.Item2, 0);             }             mistakeFrequency[ml.Item1][ml.Item2]++;         }     } }  #endregion <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u043c\u043e\u0434\u0435\u043b\u044c \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432 \u0434\u043b\u044f \u0441\u043b\u043e\u0432\u0430 &quot;<b>he;;o<\/b>&quot; (\u043a\u043e\u043d\u0435\u0447\u043d\u043e \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442\u0441\u044f <b>hello<\/b>, \u0442\u043e\u0447\u043a\u0430-\u0441-\u0437\u0430\u043f\u044f\u0442\u043e\u0439 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0441\u043f\u0440\u0430\u0432\u0430 \u043e\u0442 l \u0438 \u043b\u0435\u0433\u043a\u043e \u0431\u044b\u043b\u043e \u043e\u0448\u0438\u0431\u0438\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u043f\u0435\u0447\u0430\u0442\u0438, \u0432 \u0431\u0430\u0437\u0435 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u044b\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u043b\u043e\u0432\u0430 <b>hello <\/b>\u043d\u0435\u0442 \u0441\u043b\u043e\u0432\u0430 <b>he;;o<\/b>) \u043d\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 2, \u0441 \u0437\u0430\u0441\u0435\u0447\u0435\u043d\u0438\u0435\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0438:<\/p>\n<pre><code class=\"cs\">NoisyChannel nc = new NoisyChannel(words, wordFrequency, mistakeFrequency, 1);  Stopwatch timer = new Stopwatch(); timer.Start(); IDictionary&lt;string, double&gt; c = nc.GetCandidates(&quot;he;;o&quot;, 2); timer.Stop(); TimeSpan ts = timer.Elapsed; Console.WriteLine(ts.ToString()); <\/code><\/pre>\n<p>  \u0423 \u043c\u0435\u043d\u044f \u0442\u0430\u043a\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0447\u0443\u0442\u044c \u043c\u0435\u043d\u0435\u0435 1 \u0441\u0435\u043a\u0443\u043d\u0434\u044b, \u0445\u043e\u0442\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0435 \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438, \u0430 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442, \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u043d\u0438\u0445. \u0412\u0437\u0433\u043b\u044f\u043d\u0435\u043c \u043d\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0437\u0430\u043c\u0435\u043d\u044b \u0438 \u0438\u0445 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438: <\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/7c9\/78d\/f90\/7c978df90fbcf8a40845ce49569961ed.png\"\/><\/p>\n<h4>\u0421\u0441\u044b\u043b\u043a\u0438<\/h4>\n<p>  <\/p>\n<ul>\n<li> <a href=\"https:\/\/class.coursera.org\/nlp\/class\">\u043a\u0443\u0440\u0441 Natural Language Processing \u043d\u0430 \u043a\u0443\u0440\u0441\u0435\u0440\u0435<\/a><\/li>\n<li> <a href=\"http:\/\/norvig.com\/ngrams\/\">Natural Language Corpus Data: Beautiful Data<\/a><\/li>\n<li> <a href=\"http:\/\/habrahabr.ru\/post\/114997\/\">\u0433\u043e\u0434\u043d\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u0438 \u0414\u043e\u043c\u0435\u0440\u0430\u0443-\u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430<\/a><\/li>\n<\/ul>\n<p>  <a href=\"https:\/\/drive.google.com\/file\/d\/0B4bl7YMqDnViQ2FJeUZJdnFZVms\/edit?usp=sharing\">\u0410\u0440\u0445\u0438\u0432 \u0441 \u043a\u043e\u0434\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0441\u043b\u0438\u0442\u044c \u043e\u0442 \u0441\u044e\u0434\u0430<\/a>.    \t<\/p>\n<div class=\"clear\"><\/div>\n<\/p><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/202908\/\"> http:\/\/habrahabr.ru\/post\/202908\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"content html_format\">   \t<img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/8c6\/7d0\/cc1\/8c67d0cc19860840fc2f3a60635f98d7.jpg\" align=\"right\"\/> \u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a. \u041d\u0430 \u0434\u043d\u044f\u0445 \u0443 \u043c\u0435\u043d\u044f \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0441\u0442-\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043e\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0441\u0442\u0430. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043d\u0435 \u043f\u043b\u043e\u0445\u043e \u043f\u043e\u0434\u043e\u0448\u043b\u0430 \u043e\u0434\u043d\u0430 \u0438\u0437 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435, \u0445\u043e\u0442\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0441\u043b\u0435\u0433\u043a\u0430 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u043e\u0434 \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442 \u0437\u0430\u0434\u0430\u0447\u0438. \u042d\u0442\u043e\u0442 \u043f\u043e\u0441\u0442 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d <a href=\"http:\/\/en.wikipedia.org\/wiki\/Noisy_channel_model\">\u043c\u043e\u0434\u0435\u043b\u0438 Noisy Channel<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u043c\u044b \u0438\u0437\u0443\u0447\u0438\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c, \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043d\u0430 c# \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430, \u043e\u0431\u0443\u0447\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c <a href=\"http:\/\/norvig.com\/ngrams\/\">\u043d\u0430 \u0431\u0430\u0437\u0435 \u041f\u0438\u0442\u0435\u0440\u0430 \u041d\u043e\u0440\u0432\u0438\u0433\u0430<\/a>, \u0438 \u043f\u043e\u0434 \u043a\u043e\u043d\u0435\u0446 \u043f\u0440\u043e\u0442\u0435\u0441\u0442\u0438\u0440\u0443\u0435\u043c \u0442\u043e \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-202908","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/202908","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=202908"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/202908\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=202908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=202908"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=202908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}