Методы эффективного кодирования естественно-языковых текстов

Наиболее распространенным и эффективным является адаптивный алгоритм, который в литературе называется также алгоритмом Зива (по имени его разработчика) или алгоритмом с указателями назад (или вперед).

В соответствии с этим алгоритмом в исходном тексте ищутся повторяющиеся фрагменты, каждый последующий из которых заменяется указателем на такой же фрагмент, который встречался ранее в начале (указатель назад) или в конце (указатель вперед) текста. В первом случае текст просматривается от начала к концу, во втором – от конца к началу.

Как строится:

а) с указателями назад. Текст просматривается от начала к концу и специальный механизм определяет, что повторно встречается указанный выше фрагмент. Алгоритм строит адресный указатель взамен этого фрагмента со структурой: количество символов, которые надо отсчитать в обратном направлении к началу первого вхождения фрагмента, и длина фрагмента.

б) с указателями вперед. Аналогично, но текст просматривается от конца к началу.

11. Помехозащитное кодирование

В качестве базового кода, который подвергается помехозащитному кодированию, используется двоичный код постоянной длины. Такой исходный (базовый) код называется первичным, поскольку подвергается модификации.

Искажение кодовых комбинаций

Для понимания сущности вопроса рассмотрим сначала, как происходит искажение кодовых комбинаций при наличии помех в каналах связи.

При передаче по каналу связи на передаваемый код накладывается помеха, которая формально представляется вектором ошибки - кодовой комбинацией с числом разрядов, равным числу разрядов передаваемого кода, причем эта кодовая комбинация содержит 1 в искажаемых разрядах. С помехой связано понятие ее кратности q – это число искажаемых разрядов, т.е. число единиц в векторе ошибки.

Искажение рассматривается как сложение по модулю 2 исходной кодовой комбинации и вектора ошибки

Кодовое расстояние и корректирующая способность кода

Под корректирующей способностью кода понимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстоянием d_ij между кодовыми комбинациями i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

Кодовым расстоянием d для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е. d=min{d_ij}.

Увеличить кодовое расстояние можно, введя в кодовые комбинации дополнительный разряд (или разряды). Тогда начальные разряды называют информационными, а дополнительный (или дополнительные) – проверочным (проверочными).

Значение одного проверочного разряда в простейшем случае определяется как результат суммирования по модулю 2 информационных разрядов.

Разрешенными кодовыми комбинациями называются те, которые соответствуют символам исходного алфавита. Их количество равно числу исходных символов (m). Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2^r – m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать:

d  q + 1.