{"id":301986,"date":"2020-04-16T15:00:39","date_gmt":"2020-04-16T15:00:39","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=301986"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=301986","title":{"rendered":"\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/497566\/\"><i><b>\u0412 \u043f\u0440\u0435\u0434\u0434\u0432\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u043a\u0443\u0440\u0441\u0430 <a href=\"https:\/\/otus.pw\/Hkvk\/\">\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u043e\u0432\u00bb<\/a> \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0438 \u0434\u043b\u044f \u0432\u0430\u0441 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u0435\u0449\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430.<\/b><\/i><\/p>\n<hr>\n<p>  \u041a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430 \u2013 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0441\u0436\u0430\u0442\u0438\u044f \u0444\u0430\u0439\u043b\u043e\u0432. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u043a\u043e\u0434\u0430\u0445, \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u0445 \u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430.<\/p>\n<p>  \u041c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u0437 0 \u0438 1 \u0438 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 8 \u0431\u0438\u0442. \u042d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f.<a name=\"habracut\"><\/a><\/p>\n<p>  <i>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0434\u0430\u043d \u0442\u0435\u043a\u0441\u0442. \u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u0435\u0441\u0442\u0430, \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u043e\u0433\u043e \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430?<\/i><\/p>\n<p>  \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0447\u0430\u0449\u0435, \u0447\u0435\u043c \u0434\u0440\u0443\u0433\u0438\u0435 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Letter_frequency\">\u0441\u043c. \u0437\u0434\u0435\u0441\u044c<\/a>), \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0442\u0443 \u0436\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043c\u0435\u043d\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0431\u0438\u0442\u043e\u0432. \u041f\u0440\u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043c\u044b \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0447\u0430\u0441\u0442\u043e\u0442\u044b \u0438\u0445 \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0442\u0435\u043a\u0441\u0442\u0435. \u0412 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0438\u0442\u043e\u0433\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u043c\u043e\u0433\u0443\u0442 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c \u0432\u0441\u0435\u0433\u043e 1 \u0431\u0438\u0442, \u0430 \u0434\u0440\u0443\u0433\u0438\u0435 2 \u0431\u0438\u0442\u0430, 3 \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0435. \u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043b\u0438\u0448\u044c \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>  <i>\u041a\u0430\u043a, \u0437\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u0438\u0442\u043e\u0432, \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0435\u0435 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e?<\/i><\/p>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0442\u0440\u043e\u043a\u0443 <i>\u00abaabacdab\u00bb<\/i>. \u0412 \u043d\u0435\u0439 8 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0438 \u043f\u0440\u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0434\u043b\u044f \u0435\u0435 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f 64 \u0431\u0438\u0442\u0430. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0447\u0430\u0441\u0442\u043e\u0442\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 <i>\u00aba\u00bb, \u00abb\u00bb, \u00abc\u00bb<\/i> \u0438 <i>\u00abd\u00bb<\/i> \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f 4, 2, 1, 1 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c <i>\u00abaabacdab\u00bb<\/i> \u043c\u0435\u043d\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0431\u0438\u0442\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e <i>\u00aba\u00bb<\/i> \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0447\u0430\u0449\u0435, \u0447\u0435\u043c <i>\u00abb\u00bb<\/i>, \u0430 <i>\u00abb\u00bb<\/i> \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0447\u0430\u0449\u0435, \u0447\u0435\u043c <i>\u00abc\u00bb<\/i> \u0438 <i>\u00abd\u00bb<\/i>. \u041d\u0430\u0447\u043d\u0435\u043c \u043c\u044b \u0441 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c <i>\u00aba\u00bb<\/i> \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u0430, \u0440\u0430\u0432\u043d\u043e\u0433\u043e 0, <i>\u00abb\u00bb<\/i> \u043c\u044b \u043f\u0440\u0438\u0441\u0432\u043e\u0438\u043c \u0434\u0432\u0443\u0445\u0431\u0438\u0442\u043d\u044b\u0439 \u043a\u043e\u0434 11, \u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0440\u0435\u0445 \u0431\u0438\u0442\u043e\u0432 100 \u0438 011 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c <i>\u00abc\u00bb<\/i> \u0438 <i>\u00abd\u00bb<\/i>.<\/p>\n<p>  \u0412 \u0438\u0442\u043e\u0433\u0435 \u0443 \u043d\u0430\u0441 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f:<\/p>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td>a<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>b<\/td>\n<td>11<\/td>\n<\/tr>\n<tr>\n<td>c<\/td>\n<td>100<\/td>\n<\/tr>\n<tr>\n<td>d<\/td>\n<td>011<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>  \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u0442\u0440\u043e\u043a\u0443 <i>\u00abaabacdab\u00bb<\/i> \u043c\u044b \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c \u043a\u0430\u043a <i>00110100011011 (0|0|11|0|100|011|0|11)<\/i>, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043a\u043e\u0434\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0448\u0435. \u041e\u0434\u043d\u0430\u043a\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438. \u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0440\u043e\u043a\u0443 <i>00110100011011<\/i>, \u0443 \u043d\u0430\u0441 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043d\u0435\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0430\u043a:<\/p>\n<p>  <code>0|011|0|100|011|0|11 adacdab<br \/>  0|0|11|0|100|0|11|011 aabacabd<br \/>  0|011|0|100|0|11|0|11 adacabab <br \/>  <\/code><br \/>  \u2026<br \/>  \u0438 \u0442.\u0434.<\/p>\n<p>  \u0427\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u044d\u0442\u043e\u0439 \u043d\u0435\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e\u0441\u0442\u0438, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e \u043d\u0430\u0448\u0435 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0442\u0430\u043a\u043e\u043c\u0443 \u043f\u043e\u043d\u044f\u0442\u0438\u044e, \u043a\u0430\u043a <i>\u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e<\/i>, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u043a\u043e\u0434\u044b \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u043d\u0438\u043c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c. \u041f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442, \u0447\u0442\u043e \u043d\u0438 \u043e\u0434\u0438\u043d \u043a\u043e\u0434 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u043c \u0434\u0440\u0443\u0433\u043e\u0433\u043e. \u041f\u043e\u0434 \u043a\u043e\u0434\u043e\u043c \u043c\u044b \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u043c \u0431\u0438\u0442\u044b, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430. \u0412 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u043c \u0432\u044b\u0448\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 <i>0<\/i> \u2013 \u044d\u0442\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441 <i>011<\/i>, \u0447\u0442\u043e \u043d\u0430\u0440\u0443\u0448\u0430\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e. \u0418\u0442\u0430\u043a, \u0435\u0441\u043b\u0438 \u043d\u0430\u0448\u0438 \u043a\u043e\u0434\u044b \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0443, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 (\u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442). <\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u044b\u0448\u0435. \u041d\u0430 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u043c\u044b \u043d\u0430\u0437\u043d\u0430\u0447\u0438\u043c \u0434\u043b\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 <i>\u00aba\u00bb, \u00abb\u00bb, \u00abc\u00bb<\/i> \u0438 <i>\u00abd\u00bb<\/i> \u043a\u043e\u0434\u044b, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0435 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0443.<\/p>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td>a<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>b<\/td>\n<td>10<\/td>\n<\/tr>\n<tr>\n<td>c<\/td>\n<td>110<\/td>\n<\/tr>\n<tr>\n<td>d<\/td>\n<td>111<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>  \u0421 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0442\u0430\u043a\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0441\u0442\u0440\u043e\u043a\u0430 <i>\u00abaabacdab\u00bb<\/i> \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0430 \u043a\u0430\u043a <i>00100100011010 (0|0|10|0|100|011|0|10)<\/i>. \u0410 \u0432\u043e\u0442 <i>00100100011010<\/i> \u043c\u044b \u0443\u0436\u0435 \u0441\u043c\u043e\u0436\u0435\u043c \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c\u0441\u044f \u043a \u043d\u0430\u0448\u0435\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 <i>\u00abaabacdab\u00bb<\/i>.<\/p>\n<h3>\u041a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430<\/h3>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c \u0441 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0438 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u043c \u043f\u0440\u0430\u0432\u0438\u043b\u043e\u043c, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430.<\/p>\n<p>  \u041c\u0435\u0442\u043e\u0434 \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0412 \u043d\u0435\u043c \u0443\u0437\u0435\u043b \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043b\u0438\u0431\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c, \u043b\u0438\u0431\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u043c. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441\u0447\u0438\u0442\u0430\u044e\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438 (\u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c\u0438), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u0430\u043c \u0441\u0438\u043c\u0432\u043e\u043b \u0438 \u0435\u0433\u043e \u0432\u0435\u0441 (\u0442\u043e \u0435\u0441\u0442\u044c \u0447\u0430\u0441\u0442\u043e\u0442\u0443 \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f). \u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u0443\u0437\u043b\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0432\u0435\u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u0441\u0441\u044b\u043b\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u0443\u0437\u043b\u0430-\u043d\u0430\u0441\u043b\u0435\u0434\u043d\u0438\u043a\u0430. \u041f\u043e \u043e\u0431\u0449\u0435\u043c\u0443 \u0441\u043e\u0433\u043b\u0430\u0448\u0435\u043d\u0438\u044e, \u0431\u0438\u0442 <i>\u00ab0\u00bb<\/i> \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0442\u0432\u0438, \u0430 <i>\u00ab1\u00bb<\/i> \u2014 \u043f\u043e \u043f\u0440\u0430\u0432\u043e\u0439. \u0412 \u043f\u043e\u043b\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 <i>N<\/i> \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0438 <i>N-1<\/i> \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432. \u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430 \u043e\u0442\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u043b\u0438\u0441\u044c \u043d\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u043a\u043e\u0434\u043e\u0432 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b.<\/p>\n<p>  \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430, \u0433\u0434\u0435 \u0443\u0437\u043b\u0443 \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0447\u0430\u0441\u0442\u043e\u0442\u043e\u0439 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u0441\u0432\u043e\u0435\u043d \u0432\u044b\u0441\u0448\u0438\u0439 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442. \u041d\u0438\u0436\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u0448\u0430\u0433\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f:<\/p>\n<ol>\n<li>\u0421\u043e\u0437\u0434\u0430\u0439\u0442\u0435 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u0434\u043e\u0431\u0430\u0432\u044c\u0442\u0435 \u0438\u0445 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438.<\/li>\n<li>\u041f\u043e\u043a\u0430 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043b\u0438\u0441\u0442\u0430 \u0434\u0435\u043b\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435:<br \/> \n<ul>\n<li>\u0423\u0434\u0430\u043b\u0438\u0442\u0435 \u0434\u0432\u0430 \u0443\u0437\u043b\u0430 \u0441 \u043d\u0430\u0438\u0432\u044b\u0441\u0448\u0438\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c (\u0441 \u0441\u0430\u043c\u043e\u0439 \u043d\u0438\u0437\u043a\u043e\u0439 \u0447\u0430\u0441\u0442\u043e\u0442\u043e\u0439) \u0438\u0437 \u043e\u0447\u0435\u0440\u0435\u0434\u0438;<\/li>\n<li>\u0421\u043e\u0437\u0434\u0430\u0439\u0442\u0435 \u043d\u043e\u0432\u044b\u0439 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0439 \u0443\u0437\u0435\u043b, \u0433\u0434\u0435 \u044d\u0442\u0438 \u0434\u0432\u0430 \u0443\u0437\u043b\u0430 \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0441\u043b\u0435\u0434\u043d\u0438\u043a\u0430\u043c\u0438, \u0430 \u0447\u0430\u0441\u0442\u043e\u0442\u0430 \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430 \u0441\u0443\u043c\u043c\u0435 \u0447\u0430\u0441\u0442\u043e\u0442 \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432.<\/li>\n<li>\u0414\u043e\u0431\u0430\u0432\u044c\u0442\u0435 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u0432.<\/li>\n<\/ul>\n<\/li>\n<li>\u0415\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0439\u0441\u044f \u0443\u0437\u0435\u043b \u0431\u0443\u0434\u0435\u0442 \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c, \u043d\u0430 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u0441\u044f.<\/li>\n<\/ol>\n<p>  \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0435\u043a\u0441\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0438\u0437 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 <i>\u00aba\u00bb, \u00abb\u00bb, \u00abc\u00bb, \u00abd\u00bb<\/i> \u0438 <i>\u00abe\u00bb<\/i>, \u0430 \u0447\u0430\u0441\u0442\u043e\u0442\u044b \u0438\u0445 \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0432\u043d\u044b 15, 7, 6, 6 \u0438 5 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041d\u0438\u0436\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0442\u0440\u0430\u0436\u0430\u044e\u0442 \u0448\u0430\u0433\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/08\/nz\/g9\/08nzg9y-qguo05argcfhzg7dfbo.png\"><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/1t\/fb\/5l\/1tfb5lnkadshv9ckwwbq2w8jm0k.png\"><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/dh\/uo\/be\/dhuobemww5m4uoxswnpndawrfok.png\"><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/i-\/9a\/we\/i-9awedtfaylpuh834b3xwby0pu.png\"><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/vu\/1z\/us\/vu1zusm2bv_1z0qunv7okiv8s5k.png\"><\/p>\n<p>  \u041f\u0443\u0442\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u043b\u044e\u0431\u043e\u0433\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u0439 \u043a\u043e\u0434 (\u0442\u0430\u043a\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439, \u043a\u0430\u043a \u043a\u043e\u0434 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430), \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b\u0443, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0441 \u044d\u0442\u0438\u043c \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c \u0443\u0437\u043b\u043e\u043c.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/cc\/vy\/qm\/ccvyqm21nyslsu41zf-f-ppl9go.png\"><br \/>  <i>\u0414\u0435\u0440\u0435\u0432\u043e \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430<\/i><\/p>\n<p>  \u041d\u0438\u0436\u0435 \u0432\u044b \u043d\u0430\u0439\u0434\u0435\u0442\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430 \u043d\u0430 \u044f\u0437\u044b\u043a\u0430\u0445 C++ \u0438 Java:<\/p>\n<pre><code class=\"cpp\">#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;queue&gt; #include &lt;unordered_map&gt; using namespace std;  \/\/ A Tree node struct Node { \tchar ch; \tint freq; \tNode *left, *right; };  \/\/ Function to allocate a new tree node Node* getNode(char ch, int freq, Node* left, Node* right) { \tNode* node = new Node();  \tnode-&gt;ch = ch; \tnode-&gt;freq = freq; \tnode-&gt;left = left; \tnode-&gt;right = right;  \treturn node; }  \/\/ Comparison object to be used to order the heap struct comp { \tbool operator()(Node* l, Node* r) \t{ \t\t\/\/ highest priority item has lowest frequency \t\treturn l-&gt;freq &gt; r-&gt;freq; \t} };  \/\/ traverse the Huffman Tree and store Huffman Codes \/\/ in a map. void encode(Node* root, string str, \t\t\tunordered_map&lt;char, string&gt; &amp;huffmanCode) { \tif (root == nullptr) \t\treturn;  \t\/\/ found a leaf node \tif (!root-&gt;left &amp;&amp; !root-&gt;right) { \t\thuffmanCode[root-&gt;ch] = str; \t}  \tencode(root-&gt;left, str + &quot;0&quot;, huffmanCode); \tencode(root-&gt;right, str + &quot;1&quot;, huffmanCode); }  \/\/ traverse the Huffman Tree and decode the encoded string void decode(Node* root, int &amp;index, string str) { \tif (root == nullptr) { \t\treturn; \t}  \t\/\/ found a leaf node \tif (!root-&gt;left &amp;&amp; !root-&gt;right) \t{ \t\tcout &lt;&lt; root-&gt;ch; \t\treturn; \t}  \tindex++;  \tif (str[index] =='0') \t\tdecode(root-&gt;left, index, str); \telse \t\tdecode(root-&gt;right, index, str); }  \/\/ Builds Huffman Tree and decode given input text void buildHuffmanTree(string text) { \t\/\/ count frequency of appearance of each character \t\/\/ and store it in a map \tunordered_map&lt;char, int&gt; freq; \tfor (char ch: text) { \t\tfreq[ch]++; \t}  \t\/\/ Create a priority queue to store live nodes of \t\/\/ Huffman tree; \tpriority_queue&lt;Node*, vector&lt;Node*&gt;, comp&gt; pq;  \t\/\/ Create a leaf node for each character\u00a0and add it \t\/\/ to the priority queue. \tfor (auto pair: freq) { \t\tpq.push(getNode(pair.first, pair.second, nullptr, nullptr)); \t}  \t\/\/ do till there is more than one node in the queue \twhile (pq.size() != 1) \t{ \t\t\/\/ Remove the two nodes of highest priority \t\t\/\/ (lowest frequency) from the queue \t\tNode *left = pq.top(); pq.pop(); \t\tNode *right = pq.top();\tpq.pop();  \t\t\/\/ Create a new internal node with these two nodes \t\t\/\/ as children and with frequency equal to the sum \t\t\/\/ of the two nodes' frequencies. Add the new node \t\t\/\/ to the priority queue. \t\tint sum = left-&gt;freq + right-&gt;freq; \t\tpq.push(getNode('\\0', sum, left, right)); \t}  \t\/\/ root stores pointer to root of Huffman Tree \tNode* root = pq.top();  \t\/\/ traverse the Huffman Tree and store Huffman Codes \t\/\/ in a map. Also prints them \tunordered_map&lt;char, string&gt; huffmanCode; \tencode(root, &quot;&quot;, huffmanCode);  \tcout &lt;&lt; &quot;Huffman Codes are :\\n&quot; &lt;&lt; '\\n'; \tfor (auto pair: huffmanCode) { \t\tcout &lt;&lt; pair.first &lt;&lt; &quot; &quot; &lt;&lt; pair.second &lt;&lt; '\\n'; \t}  \tcout &lt;&lt; &quot;\\nOriginal string was :\\n&quot; &lt;&lt; text &lt;&lt; '\\n';  \t\/\/ print encoded string \tstring str = &quot;&quot;; \tfor (char ch: text) { \t\tstr += huffmanCode[ch]; \t}  \tcout &lt;&lt; &quot;\\nEncoded string is :\\n&quot; &lt;&lt; str &lt;&lt; '\\n';  \t\/\/ traverse the Huffman Tree again and this time \t\/\/ decode the encoded string \tint index = -1; \tcout &lt;&lt; &quot;\\nDecoded string is: \\n&quot;; \twhile (index &lt; (int)str.size() - 2) { \t\tdecode(root, index, str); \t} }  \/\/ Huffman coding algorithm int main() { \tstring text = &quot;Huffman coding is a data compression algorithm.&quot;;  \tbuildHuffmanTree(text);  \treturn 0; }<\/code><\/pre>\n<pre><code class=\"java\">import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue;  \/\/ A Tree node class Node { \tchar ch; \tint freq; \tNode left = null, right = null;  \tNode(char ch, int freq) \t{ \t\tthis.ch = ch; \t\tthis.freq = freq; \t}  \tpublic Node(char ch, int freq, Node left, Node right) { \t\tthis.ch = ch; \t\tthis.freq = freq; \t\tthis.left = left; \t\tthis.right = right; \t} };  class Huffman { \t\/\/ traverse the Huffman Tree and store Huffman Codes \t\/\/ in a map. \tpublic static void encode(Node root, String str, \t\t\t\t\t\t\t  Map&lt;Character, String&gt; huffmanCode) \t{ \t\tif (root == null) \t\t\treturn;  \t\t\/\/ found a leaf node \t\tif (root.left == null &amp;&amp; root.right == null) { \t\t\thuffmanCode.put(root.ch, str); \t\t}   \t\tencode(root.left, str + &quot;0&quot;, huffmanCode); \t\tencode(root.right, str + &quot;1&quot;, huffmanCode); \t}  \t\/\/ traverse the Huffman Tree and decode the encoded string \tpublic static int decode(Node root, int index, StringBuilder sb) \t{ \t\tif (root == null) \t\t\treturn index;  \t\t\/\/ found a leaf node \t\tif (root.left == null &amp;&amp; root.right == null) \t\t{ \t\t\tSystem.out.print(root.ch); \t\t\treturn index; \t\t}  \t\tindex++;  \t\tif (sb.charAt(index) == '0') \t\t\tindex = decode(root.left, index, sb); \t\telse \t\t\tindex = decode(root.right, index, sb);  \t\treturn index; \t}  \t\/\/ Builds Huffman Tree and huffmanCode and decode given input text \tpublic static void buildHuffmanTree(String text) \t{ \t\t\/\/ count frequency of appearance of each character \t\t\/\/ and store it in a map \t\tMap&lt;Character, Integer&gt; freq = new HashMap&lt;&gt;(); \t\tfor (int i = 0 ; i &lt; text.length(); i++) { \t\t\tif (!freq.containsKey(text.charAt(i))) { \t\t\t\tfreq.put(text.charAt(i), 0); \t\t\t} \t\t\tfreq.put(text.charAt(i), freq.get(text.charAt(i)) + 1); \t\t}  \t\t\/\/ Create a priority queue to store live nodes of Huffman tree \t\t\/\/ Notice that highest priority item has lowest frequency \t\tPriorityQueue&lt;Node&gt; pq = new PriorityQueue&lt;&gt;( \t\t\t\t\t\t\t\t\t\t(l, r) -&gt; l.freq - r.freq);  \t\t\/\/ Create a leaf node for each character\u00a0and add it \t\t\/\/ to the priority queue. \t\tfor (Map.Entry&lt;Character, Integer&gt; entry : freq.entrySet()) { \t\t\tpq.add(new Node(entry.getKey(), entry.getValue())); \t\t}  \t\t\/\/ do till there is more than one node in the queue \t\twhile (pq.size() != 1) \t\t{ \t\t\t\/\/ Remove the two nodes of highest priority \t\t\t\/\/ (lowest frequency) from the queue \t\t\tNode left = pq.poll(); \t\t\tNode right = pq.poll();  \t\t\t\/\/ Create a new internal node with these two nodes as children  \t\t\t\/\/ and with frequency equal to the sum of the two nodes \t\t\t\/\/ frequencies. Add the new node to the priority queue. \t\t\tint sum = left.freq + right.freq; \t\t\tpq.add(new Node('\\0', sum, left, right)); \t\t}  \t\t\/\/ root stores pointer to root of Huffman Tree \t\tNode root = pq.peek();  \t\t\/\/ traverse the Huffman tree and store the Huffman codes in a map \t\tMap&lt;Character, String&gt; huffmanCode = new HashMap&lt;&gt;(); \t\tencode(root, &quot;&quot;, huffmanCode);  \t\t\/\/ print the Huffman codes \t\tSystem.out.println(&quot;Huffman Codes are :\\n&quot;); \t\tfor (Map.Entry&lt;Character, String&gt; entry : huffmanCode.entrySet()) { \t\t\tSystem.out.println(entry.getKey() + &quot; &quot; + entry.getValue()); \t\t}  \t\tSystem.out.println(&quot;\\nOriginal string was :\\n&quot; + text);  \t\t\/\/ print encoded string \t\tStringBuilder sb = new StringBuilder(); \t\tfor (int i = 0 ; i &lt; text.length(); i++) { \t\t\tsb.append(huffmanCode.get(text.charAt(i))); \t\t}  \t\tSystem.out.println(&quot;\\nEncoded string is :\\n&quot; + sb);  \t\t\/\/ traverse the Huffman Tree again and this time \t\t\/\/ decode the encoded string \t\tint index = -1; \t\tSystem.out.println(&quot;\\nDecoded string is: \\n&quot;); \t\twhile (index &lt; sb.length() - 2) { \t\t\tindex = decode(root, index, sb); \t\t} \t}  \tpublic static void main(String[] args) \t{ \t\tString text = &quot;Huffman coding is a data compression algorithm.&quot;;  \t\tbuildHuffmanTree(text); \t} }<\/code><\/pre>\n<p>  <i>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435:<\/i> \u043f\u0430\u043c\u044f\u0442\u044c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0430\u044f \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u043e\u0439, \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 47 * 8 = 376 \u0431\u0438\u0442, \u0430 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0441\u0435\u0433\u043e 194 \u0431\u0438\u0442\u0430, \u0442.\u0435. \u0434\u0430\u043d\u043d\u044b\u0435 \u0441\u0436\u0438\u043c\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043d\u0430 48%. \u0412 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u043d\u0430 \u0421++ \u0432\u044b\u0448\u0435 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043a\u043b\u0430\u0441\u0441 string \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438, \u0447\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0447\u0438\u0442\u0430\u0435\u043c\u043e\u0439. <\/p>\n<p>  \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u0432 \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u043d\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0443 <i>O(log(N))<\/i> \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0430 \u0432 \u043f\u043e\u043b\u043d\u043e\u043c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u0441 <i>N<\/i> \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 <i>2N-1<\/i> \u0443\u0437\u043b\u043e\u0432, \u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430 \u2013 \u044d\u0442\u043e \u043f\u043e\u043b\u043d\u043e\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0437\u0430 <i>O(Nlog(N))<\/i> \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0433\u0434\u0435 <i>N <\/i>\u2013 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<h3>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438:<\/h3>\n<p>  <a href=\"https:\/\/en.wikipedia.org\/wiki\/Huffman_coding\">en.wikipedia.org\/wiki\/Huffman_coding<\/a><br \/>  <a href=\"https:\/\/en.wikipedia.org\/wiki\/Variable-length_code\">en.wikipedia.org\/wiki\/Variable-length_code<\/a><br \/>  <a href=\"https:\/\/www.youtube.com\/watch?v=5wRPin4oxCo\">www.youtube.com\/watch?v=5wRPin4oxCo<\/a> <\/p>\n<hr>\n<p>  <a href=\"https:\/\/otus.pw\/Hkvk\/\">\u0423\u0437\u043d\u0430\u0442\u044c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043e \u043a\u0443\u0440\u0441\u0435.<br \/>  <\/a>  <\/p>\n<hr>\n<\/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=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/497566\/\"> https:\/\/habr.com\/ru\/company\/otus\/blog\/497566\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/497566\/\"><i><b>\u0412 \u043f\u0440\u0435\u0434\u0434\u0432\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u043a\u0443\u0440\u0441\u0430 <a href=\"https:\/\/otus.pw\/Hkvk\/\">\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u043e\u0432\u00bb<\/a> \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0438 \u0434\u043b\u044f \u0432\u0430\u0441 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u0435\u0449\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430.<\/b><\/i><\/p>\n<hr>\n<p>  \u041a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430 \u2013 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0441\u0436\u0430\u0442\u0438\u044f \u0444\u0430\u0439\u043b\u043e\u0432. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u043a\u043e\u0434\u0430\u0445, \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u0445 \u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430.<\/p>\n<p>  \u041c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u0437 0 \u0438 1 \u0438 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 8 \u0431\u0438\u0442. \u042d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\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-301986","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/301986","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=301986"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/301986\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=301986"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=301986"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=301986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}