метод фано

Ответ от Јива[гуру]
Помните, как ловко расправились с шифрованными письменами герои рассказов По и Дойла ("Золотой жук" и "Пляшущие человечки")? А всё - от наблюдательности своей! Подметили тот очевидный факт, что каждая буква в тексте имеет свою частоту. Мы это и сами интуитивно чувствуем. Буква "и" в любом отвлеченном тексте, например, встречается в сотни раз чаще, чем "ъ". И если любую подстановочную криптограмму подвергнуть частотному анализу, а затем присовокупить чуток логики - расшифровке поддаётся она очень легко. Но, отвлечёмся от детективной тематики и обратим внимание на такое свойство, как ЧАСТОТА ВСТРЕЧАЕМОСТИ различных элементов. Это свойство присуще любому относительно осмысленному множеству элементов - будь то мелодия (как последовательность звуков) или - картина (как сочетание различных мазков там, завитков, штрихов и линий) . А частота встречаемости различных букв в письменной речи, так она и вовсе выражена очень чётко.
Так вот, метод кодирования Шенона-Фано стоит на принципе экономии места. То есть, - наиболее часто встречаемые символы кодируем коротко, а те символы, что встречаются пореже – длинно. Потому что если наоборот – «палучица многа цыфар, ниасилят» . А как определить – что встречается пореже, а что – почаще? Можно, конечно, и на глазок. Но на глазок в матеметике не принято. Математики – оне народ точный – даже водку на глазок не наливают, а уж цифры – так это ж вааще святое. Надо точно и четко. Как? А с помощью дихтомии (не путать с лоботомией! ) – т. е. процесса разделения на два.
Вот, взять, к примеру Ваш текст «Корнилов Алексей Олегович» и применить к нему метод Шеннона-Фано то мы все символы, встречающиеся в нём разделим на две примерно равные группы – по 11 и 12 букв. Оговоримся сразу «и» = «й» .
В первую группу попадут буквы К*2,О*4,Р, Н, И*3 (итого11букв)
Во вторую – Л*3,В*2,А, Е*3,Г, Ч (итого 12 букв)
Первую гуппу тоже разобьём на две примерно равные подгруппы по 5 и 6 букв
В первой подгруппе будут буквы К*2 и О*4 (итого 6 букв) ,
Во второй – буквы Р, Н, И*3 (итого 5 букв)
Каждую из подгрупп опять половиним.
Первая подгруппа у нас распадается на 2 подподгруппы:
-К*2
-О*4
А вторая подподгруппа распадается на
-Р, Н
-И*2…
Словом, мы занимаемся тем, что делим каждое из двух получаемых подмножеств ещё раз на два аж до упора, до состояния полной неделимости…
После этого – мы попросту записываем «адреса» каждой из букв. То есть буква «К» -1-я группа, 1-я подгруппа, 1-я подподгруппа и 1-я подподгруппа (код – 1111), «адрес» буквы «О» - 1112 (первая группа, первая подгруппа, первая подподгрупа, вторая подподгрупа) . И таким вот нехитрым способом мы записываем «адреса» каждой буквы, превращая каждую из букв в кодовый символ.
Пааанравилось? Думаю - да! Это прикоооольна! Наслаждайтесь.