- •Теоретические основы информационных процессов введение
- •1.Кодирование сообщений
- •§1. Информационные процессы
- •§2. Передача и кодирование данных в аис
- •§3. Сжатие данных как информационный процесс
- •§4. Сжатие на основе смыслового содержания данных
- •§5. Переход от естественных обозначений к более компактным.
- •§6. Подавление повторяющихся символов
- •§7. Кодирование часто используемых данных
- •§8. Сжатие данных на основе сравнения
- •§9. Целесообразность сжатия данных
- •§10. Сжатие на основе статистических свойств данных и неравномерные коды
- •§11. Двоичное кодирование и бинарные деревья
- •§12. Кодирование сообщений словами переменной длины
- •§13. Процедура Шеннона-Фано
- •§14. Процедура Хафмана
- •§15. Кодирование последовательностей символов
- •§16. Помехоустойчивость данных
- •§17. Методы обеспечения помехоустойчивости
- •§18. Способность кодов обнаруживать и исправлять ошибки
- •2. Поиск данных
- •§1. Проблема поиска данных
- •§ 2. Виды зу
- •§3. Поиск на основе преобразования ключа в адрес
- •§4. Перемешивание
- •§5. Поиск на основе сравнения ключей
- •§6. Последовательный поиск
- •§7. Блочный поиск
- •§8. Двоичный поиск
- •§9. Поиск по бинарному дереву
- •§10. Чистый бинарный поиск
- •§11. Помехоустойчивый поиск
- •§12. B-деревья: общие сведения
- •§13. B-деревья: добавление ключей
- •§14. B-деревья: удаление ключей
§18. Способность кодов обнаруживать и исправлять ошибки
Кодовым расстоянием или расстоянием Хэмминга между двумя кодовыми словами одинаковой длины называется число несовпадающих в них символов. Например, расстояние Хэмминга между комбинациями 10010011 и 10000001 составляет d=2. Чем больше минимальное расстояние между разрешенными кодовыми комбинациями, тем больше избыточность. При безызбыточном кодировании d=1.
Ошибка кратности r приводит к тому, что искаженная комбинация отодвигается на расстояние d=r от исходной. В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую. Следовательно, способность кодов обнаруживать ошибки зависит от кодового расстояния между разрешенными кодовыми словами: чем больше расстояние, тем большей кратности требуется ошибка, переводящая одну разрешенную комбинацию в другую. Таким образом, если минимальное кодовое расстояние между разрешенными комбинациями равно dmin, то можно обнаружить ошибки кратностью r≤ dmin -1.
Способность кодов исправлять обнаруженные ошибки состоит в возможности однозначного отнесения запрещенной кодовой комбинации к некоторой единственной разрешенной комбинации. Для этого достаточно, чтобы выполнялось условие dmin ≥ 2r +1, следовательно, коды с заданным dmin обеспечивают исправление ошибок кратностью r≤ (dmin -1)/2. В рассмотренном примере коды содержат 4 информационных и 3 контрольных символа, dmin=3, поэтому они могут обнаруживать однократные и двукратные ошибки, а исправлять только однократные.
2. Поиск данных
§1. Проблема поиска данных
С проблемой кодирования данных, передаваемых по каналу связи, тесно связаны проблемы их хранения в запоминающих устройствах (ЗУ) и поиска необходимых данных по специальному запросу. Действительно, чтобы исходному сообщению поставить в соответствие определенное кодовое слово, это слово часто нужно найти в некотором ЗУ. Приняв кодовое слово, также бывает необходимо найти в ЗУ данные, соответствующие исходному сообщению. С другой стороны, сложные системы поиска (например, в СУБД) в процессе своего функционирования используют большое число процедур кодирования и декодирования информации.
При рассмотрении задач поиска будем предполагать, что данные находятся в ЗУ в виде записей, каждая из которых содержит специальное поле, называемое ключом. Обычно требуется, чтобы ключи были различными и чтобы каждый ключ однозначно определял свою запись. Совокупность записей образует таблицу или файл, размещаемый в запоминающем устройстве.
Поиск обычно начинается с получения извне аргумента поиска и состоит в отыскании записи, ключ которой совпадает с аргументом поиска или находится с ним в определенном соотношении. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил найти нужную запись, либо неудачным, т.е. показал, что записи с данным ключом в таблице отсутствуют.
Хотя целью поиска являются данные, содержащиеся в некоторой записи, их извлечение, когда запись найдена, принципиальных затруднений не вызывает. Поэтому для простоты можно считать, что записи состоят только из ключей.
Конкретные процедуры поиска и их эффективность во многом определяются теми возможностями, которые предоставляют различные виды запоминающих устройств. Поэтому изучение методов поиска целесообразно начать с рассмотрения важнейших разновидностей ЗУ.