Информационное множество

Информационное множество (Data set) — динамически изменяемое множество информационных объектов, возможным элементам которого ставятся во взаимно однозначное соответствие так называемые ключи — информационные элементы без внутренней структуры. Замена прямого поиска информационного объекта поиском его по ключу, имеющему более простую природу и связанному определенными отношениями с другими ключами, позволяет сделать поиск (и другие операции над динамическим множеством) более эффективным. Другая причина введения такого понятия, как ключ состоит в том, что содержательная трактовка элементов информационного множества (в силу сложной их природы) может зависеть от характера работы с информационным множеством, и иногда возникает необходимость в зависимости от трактовки сопоставлять с одними и теми же элементами различные системы ключей. Как правило, ключи в информационном множестве вводятся таким образом, что имеется простая процедура порождения ключа по информационному элементу (например, в качестве ключей могут рассматриваться некоторые определенные части информационных объектов).

Поиск по ключу иногда называют ассоциативным поиском, а информационное множество с введенной системой ключей — информационным массивом или словарем.

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

Литература

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
• Касьянов В.Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003