Спирина, М.С. Дискретная математика

0 1 2 3 4 5 6 7 8 9 Л ° [OOOO 0001 0010 ООП 0100 0101 0110 0111 1000 1001 Это двоично-десятичное кодирование, оно является взаимно-од­ нозначным и потому допускает декодирование. Однако схема а = ( 0 о 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 ^ 1001 не является взаимно-однозначной. Например, кортеж из шести единиц 111111 может соответствовать как слову 333, так и 77, 111111, а также 137, 3311 или 7111 плюс любая перестановка. Кодирование с минимальной избыточностью. Оптимальным я в ­ ляется кодирование, при котором сообщение имеет наименьшую из возможных длину. Но для выявления наилучшего из вариантов необходима дополнительная информация. Например, для сооб­ щений, представленных на естественном языке, такой дополни­ тельной информацией может быть распределение вероятности появления букв в некотором тексте. Тогда задача построения оп ­ тимального кода приобретает точную математическую формули­ ровку и строгое решение. Пусть задана некоторая схема алфавитного кодирования о = а , Р« а л . Тогда любая схема а' = 0-1 К а„ К где кортеж (Pi'...P^) есть перестановка кортежа <(3t...|3Я), также будет задавать некое кодирование. В таком случае, если длины элементарных к о ­ дов равны, то их перестановка в схеме не влияет на длину закоди­ рованного сообщения. В том случае, если длины элементарных кодов различны, то длина кода сообщения напрямую зависит и от того, какие элементарные коды каким буквам поставлены в соответ­ ствие, и от того, каков состав букв в сообщении. Поэтому для определения алгоритма назначения элементар­ ных кодов, дающих минимальную длину фиксированного сооб­ щения S при фиксированной схеме а , необходимо: отсортировать буквы в порядке убывания количества вхождений; отсортировать элементарные коды в порядке возрастания длины; поставить коды в соответствие буквам в установленном порядке. Назовем схему о префиксной, если элементарный код одной буквы не является префиксом кода другой буквы. Схема а называется разделимой, если любое слово, составлен­ ное из элементарных кодов, разлагается на элементарные коды единственным образом, т.е. VP = (Р,р2...р„), Р, е В 3! разбиение р = <Ь,1 ...Ь? ...Ь{ ...Ь?) = (b\b2...bk), где bj е В*, а Ь{ е В , причем b[ bfr Vbj е В* 3! а, е А* : aj - a~l(bj). Полученное слово можно разбить на к подслов длины л,: Ь{ = рь ..., Ь?' = Р„„ Ъ\ = р„1+1, ..., Ьк"> = Р„, 311