К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В. Более сложными являются так называемые кодирующие отображения. Под кодирующим отображением понимается соответствие, сопоставляющее каждому символу входного алфавита некоторую конечную последовательность символов в выходном алфавите, называемую кодом.
Пусть заданы алфавиты: A={p,r,s,t} – входной и B={a,b,c,d,f,g,h} – выходной. Тогда отображение символов А символами В, т.е. кодом, является примером кодирующего отображения. Для построения искомого отображения достаточно заменить все символы любого слова ai в алфавите А соответствующими кодами алфавита В. Так, если слово x=sstr, то Гx=fghfghabcceg есть код исходного слова x.
Процесс, обратный кодированию, т.е. замена в слове bj кодов алфавита В символами из А, называется декодированием и обозначается как Г-1bj=ai. Например, для слова b=fghfghabcceg в алфавите В декодирование Г-1b дает слово a=sstr.
Если при кодировании слова ai получается некоторое слово bj и декодирование дает исходное слово ai(Гai=bj, Г-1bj=ai), то имеет место обратимость кодирования. Условие обратимости кодирования иначе называется условием взаимной однозначности соответствующего кодирующего отображения. В приведенном выше примере обратимость существует. Но, если зданы A={a,b,c}, B={r,s}, Га=r, Гb=s, Гс=rs и слово aabca в алфавите А, то обратимость отсутствует, так как Гaabca=rrsrsr, а Г-1rrsrsr=aababa (либо одно из слов acaba, aabca, acca).
Для обратимости кодирования должны выполняться следующие условия:
- коды разных символов исходного алфавита А должны быть различны;
- код любого символа алфавита А не может совпадать ни с каким из начальных подслов кодов других символов этого алфавита.
Пояснение этих утверждений сводится к следующему. Пусть слово q=b1,b2, ...,bn является кодом слова p=a1,a2, ...,am в алфавите А. Тогда по коду q можно однозначно восстановить слово р. В силу второго условия только одно начальное подслово слова q будет совпадать с каким-либо символом алфавита А. Ясно, что таким подсловом является символ а1. Применяя аналогичные рассуждения к оставшемуся отрезку слова q, можно однозначно восстановить один за другим все символы слова р. Следовательно, любому данному коду может соответствовать только одно слово в А, что доказывает обратимость кодирующего отображения.
Второе условие обязательно выполняется в том случае, когда коды всех символов алфавита А имеют одинаковую длину. Кодирование, при котором все коды имеют одинаковую длину, называется нормальным.
Кодирование позволяет сводить изучение произвольных алфавитных отображений к алфавитным отображениям в некотором стандартном алфавите. Наиболее часто в качестве стандартного алфавита выбирается двоичный алфавит, состоящий из двух символов. В качестве таких символов обычно используются цифры 0 и 1, т.е. С={0,1}. Подавляющее большинство современных ЭВМ обрабатывают информацию, закодированную именно в двоичном стандартном алфавите.
Пусть А – произвольный, а С – стандартный алфавиты и n - число символов в алфавите А, а m - число символов в алфавите С. В этом случае всегда можно выбрать длину слова L, удовлетворяющую условию mL>=n и закодировать все символы в алфавите А словами длины l в алфавите С так, чтобы коды различных букв были разными (действительно, число различных слов длины L в m-символьном алфавите равно mL). Любое такое кодирование будет нормальным и порождает обратимое кодирующее отображение слов в алфавите А в слова в алфавите С (см. ниже диапазон представления чисел в машине).
|
