Проблема поиска данных

ПОИСК ДАННЫХ

Способность кодов обнаруживать и исправлять ошибки

Кодовым расстоянием или расстоянием Хэмминга между двумя кодовыми словами одинаковой длины называется число несовпадающих в них символов. Например, расстояние Хэмминга между комбинациями 10010011 и 10000001 составляет d=2. Чем больше минимальное расстояние между разрешенными кодовыми комбинациями, тем больше избыточность. При безызбыточном кодировании d=1.

Ошибка кратности r приводит к тому, что искаженная комбинация отодвигается на расстояние d=r от исходной. В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую. Следовательно, способность кодов обнаруживать ошибки зависит от кодового расстояния между разрешенными кодовыми словами: чем больше расстояние, тем большей кратности требуется ошибка, переводящая одну разрешенную комбинацию в другую. Таким образом, если минимальное кодовое расстояние между разрешенными комбинациями равно d_min, то можно обнаружить ошибки кратностью r≤ d_min -1.

Способность кодов исправлять обнаруженные ошибки состоит в возможности однозначного отнесения запрещенной кодовой комбинации к некоторой единственной разрешенной комбинации. Для этого достаточно, чтобы выполнялось условие d_min ≥ 2r +1, следовательно, коды с заданным d_min обеспечивают исправление ошибок кратностьюr≤ (d_min -1)/2. В рассмотренном примере коды содержат 4 информационных и 3 контрольных символа, d_min=3,поэтому они могут обнаруживать однократные и двукратные ошибки, а исправлять только однократные.

С проблемой кодирования данных, передаваемых по каналу связи, тесно связаны проблемы их хранения в запоминающих устройствах (ЗУ) и поиска необходимых данных по специальному запросу. Действительно, чтобы исходному сообщению поставить в соответствие определенное кодовое слово, это слово часто нужно найти в некотором ЗУ. Приняв кодовое слово, также бывает необходимо найти в ЗУ данные, соответствующие исходному сообщению. С другой стороны, сложные системы поиска (например, в СУБД) в процессе своего функционирования используют большое число процедур кодирования и декодирования информации.

При рассмотрении задач поиска будем предполагать, что данные находятся в ЗУ в виде записей, каждая из которых содержит специальное поле, называемое ключом. Обычно требуется, чтобы ключи были различными и чтобы каждый ключ однозначно определял свою запись. Совокупность записей образует таблицу или файл, размещаемый в запоминающем устройстве.

Поиск обычно начинается с получения извне аргумента поиска и состоит в отыскании записи, ключ которой совпадает с аргументом поиска или находится с ним в определенном соотношении. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил найти нужную запись, либо неудачным, т.е. показал, что записи с данным ключом в таблице отсутствуют.

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

Конкретные процедуры поиска и их эффективность во многом определяются теми возможностями, которые предоставляют различные виды запоминающих устройств. Поэтому изучение методов поиска целесообразно начать с рассмотрения важнейших разновидностей ЗУ.