Фано информатика это — условие Фано в теории кодирования, которое является достаточным условием для построения самоопределяющегося кода (по-другому, префиксного кода).
Введение
При кодировании символов, которое всегда выполняется при работе с текстовыми данными на компьютере, как правило, предполагается, что любому символу соответствует одно и то же число разрядов. К примеру, кодирование в ASCII сопоставляет любому знаку информационный байт, который хранит номер символьного знака в данной таблице. Эта методика кодировки символов не сложная, но всё же не может считаться пределом оптимальности. Существенная часть символьных знаков задействует далеко не все двоичные разряды из предназначенных им байтов, биты старших разрядов просто нулевые. Если в текстовом файле задействованы не все знаки, имеющиеся табличной кодировке (например, сообщение состоит только из прописных русских символов), тем не менее, применяется то же самое восьми битное кодирование.
Однако, существует более гибкий и менее объёмный метод кодирования, который называется неравномерным. В таком коде число битов, которые отводятся для кодировки знаков, зависит от числа применяемых в данном конкретном случае разных знаков, иначе говоря, от алфавитной мощности. При этом кодирование разных знаков, имеет различную длину в двоичном формате. Это кодирование возможно оптимизировать путём учёта частоты повторяемости разных знаков и давать постоянно применяемым символам наиболее маленькие коды. Основное правило при неравномерном кодировании заключается в обеспечении возможности однозначного и правильного декодирования закодированной таким образом информации. Это декодирование должно выполняться путём поочерёдного выделения и распознавания из непрерывной цепи нулей и единиц кодов отдельного символа. Для обеспечения однозначного декодирования текстовой информации, закодированной с применением неравномерного кодирования, такие коды следует присваивать знакам согласно условиям Фано.
Принцип Фано
Прямое условие Фано формулируется следующим образом: неравномерный код возможно однозначно декодировать, если код любого символа не имеет совпадений с начальными знаками (префиксом) любого другого кода, имеющего больший размер. Подобный код имеет название «префиксный». Обратное условие Фано формулируется так: неравномерный код возможно однозначно декодировать, при условии, что нет кодов, которые имеют совпадения с окончанием (постфиксом) любого другого кода, имеющего большую длину. Этот код носит название «постфиксный».
Для однозначного декодирования кодовой последовательности, необходимо и достаточно соблюдение по меньшей мере любого вышеназванного условия Фано. Причём если выполняется прямое условие Фано, то кодовую последовательность возможно однозначно декодировать с начала. Если же выполняется обратное условие Фано, то последовательность кодов возможно однозначно декодировать с конца.
Когда необходимо решить проблему с неравномерным кодированием и декодированием, то вначале требуется выполнить анализ кодов, заданных по условию задачи. Если исходные коды соответствуют прямому условию Фано, то его и следует применять при поиске решения. В случае не выполнения прямого условия Фано, необходимо проанализировать коды на соответствие обратному условию Фано и, в случае его выполнения, применять именно его. Затем, учитывая какое условие Фано соблюдено для данного кодового набора, нужно выбрать соответствующее направление декодирования этого кода. А именно, если для данной кодовой последовательности соблюдается прямое условие Фано, тогда процесс декодирования нужно производить с начала (слева направо). Если же для данной кодовой последовательности соблюдается обратное условие Фано, тогда процесс декодирования следует выполнять с конца (справа налево). В случае выполнения обеих условий Фано, процесс декодирования возможно производить в любом направлении. Итог должен быть один и тот же.
Проверка условий Фано
Для проверки выполнения прямого условия Фано, необходимо поочерёдно выполнять сравнение всех пар кодов, соблюдая такие условия:
Когда пара кодов, подлежащих сравнению, имеет одинаковый размер, то хватит проверки на совпадение.
Если пара кодов, подлежащих сравнению, имеет разный размер, то следует проверить на совпадение более короткого кода с начальными знаками более длинного кода (так проверяется выполнение прямого условия Фано) или с окончанием более длинного кода (так проверятся выполнение обратного условия Фано).
Для последнего случая проверка кодов может выполняться таким образом. Вначале записывается более длинный код. Далее снизу под ним располагается более короткий код так, чтобы было совпадение по расположению знаков. Причём, если проверяется прямое условие Фано, то по левой позиции знаков, а если обратное условие Фано, то по правой позиции знаков.
Пример проверки
Имеем заданные коды символов: A – 10, B – 11, C – 011. Необходимо проверить выполнение условий Фано для такого кодового набора.
Алгоритм решения можно представить в следующем виде:
Выполняем сравнение кодов символов A и B. По длине коды одинаковые (у обеих длина два бита), но сами коды разные. Отсюда следует вывод, что выполнено и прямое и обратное условие Фано для пары символов A и B.
Выполняем сравнение символов A и C. Они имеют коды различной длины.
- Выполняем проверку соответствия прямому условию Фано:
C: 0 1 1
A: 1 0
Кодирование символа A (оно короче) не совпадает с начальными кодами символа C (который длиннее). Это означает, что для данной пары символов выполнено прямое условие Фано.
- Выполняем проверку обратного условия Фано:
C: 0 1 1
A: 1 0
Кодирование символа A (оно короче) не совпадает с окончанием кода символа (его код длиннее). Делаем вывод о выполнении обратного условия Фано для этих символов.
Выполняем сравнение кодов символов B и C. По длине их коды так же отличаются.
- Выполняем проверку на выполнение прямого условия Фано:
C: 0 1 1
B: 1 1
Код символа B (он короче) не совпадает с начальными знаками кода символа C (его код длиннее). Делаем вывод, что прямое условие Фано для этих символов выполнено.
- Выполняем проверку исполнения обратного условия Фано:
C: 0 1 1
B: 1 1
Код символа B (он короче) совпадает с окончанием кода символа C (его код длиннее). То есть обратное условие Фано для этих символов не выполнено.
Формирование итогов. Прямое условие Фано исполнено для всех пар символов, обратное условие не исполнено для одной пары, то есть не может применяться и для всего набора символов.
