Справочники

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

Рассмотрим линейную последовательность пар ключ-значение. Преимущества использования для их представления неполной структуры данных очевидны. Программа 15,8 определяет отношение lookup(Key,Diсt,Value), которое истинно, если запись с ключом Key в справочнике Dict имеет значение Value. Словарь представляется как неполный список пар вида (Key, Value).

lookup (Key, Dictionary, Value) ¬

Dictionary содержит значение Value, индексированное ключом Key.

Dictionary представляется списком пар (Key, Value).

lookup(Key, [(Key, Value) | Dictionary], Value).

lookup(Key,[Keyl, Value!) | Dictionary], Value) ¬

Key ¹ Key1,lookup(Key, Dictionary, Value),

Программа 15.8. Поиск в словаре, представленном списком кортежей.

Рассмотрим пример справочника, используемого для хранения номеров телефонов, фамилии владельцев которых играют роль ключей. Предположим, что справочник Diсt первоначально представлен списком [(арнольд, 8881), (барри, 4513), (кэти, 5950)|Xs]. Тогда на вопрос lookup (арнольд, Dict,N)?, используемый для поиска номера телефона человека по имени Арнольд, будет получен ответ N = 8881. Вопрос lookup (барри ,Dict,4513), используемый для проверки номера телефона Барри, имеет утвердительный ответ.

Ввод новых ключей и значений рассмотрим на примере вопроса lookup (Дэвид, Dict, 1199)?. Синтаксически этот вопрос кажется проверкой номера телефона Дэвида. Но он приводит к иному результату. Этот вопрос успешно решается: справочник Dict будет теперь представлен списком [(арнольд,8881), (барри,4513), (кэти,5950), (дэвид, 1199) |Хs1]. Таким образом, с помощью процедуры lookup вводится новое значение.

Что произойдет, если проверить номер телефона Кэти с помощью вопроса lookup (кэти,Dict,5951)?, в котором номер задан неправильно? Вторая запись в справочник номера телефона Кэти сделана не будет: вследствие проверки Key ¹ Keyl решение вопроса будет безуспешным.

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

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

Бинарные деревья, описанные в разд. 3.4, преобразуются в четырехместную структуру dict(Key, Value, Left, Right), где Left и Right – левый и правый подсправочники соответственно, a Key и Value – как и прежде, ключ и значение. Функтор did напоминает, что речь идет о справочнике.

Поиск по дереву-справочнику имеет очень элегантное определение, напоминающее по духу определение процедуры поиска в программе 15.8.Он выполняется рекурсивно по двоичным деревьям, а не по спискам и основан на унификации для конкретизации переменных в структурах справочника. В программе 15.9 определена процедура lookup (Key. Dictionary, Value), которая, как и прежде, обеспечивает поиск значения по заданному ключу и вводит новые значения.

На каждом шаге поиска ключ сравнивается с ключом, записанным в текущем узле. Если ключ поиска меньше ключа в текущем узле, то рекурсивно продолжается поиск по левой ветви, если больше, то выбирается правая ветвь. Если ключ не числовой, то предикаты < и > необходимо обобщить. В программе 15.9 в отличие от программы 15.8 следует использовать отсечение. Это обусловлено «нелогическим» характером действий операторов сравнения, которые будут приводить к ошибкам, если ключи не конкретизированы.

lookup (Key,Dictionary, Value) ¬

Dictionary содержит значение Value, индексированное ключом Key.

Dictionary представляется упорядоченным, бинарным деревом.

lookup(Key,dict,(Kev,X, Left, Right), Value) ¬

!, X = Value.

lookup(Key,dict(Key1,X,Left,Right), Value) ¬

Key < Keyl,lookup(Key, Left, Value).

lookup(Key,dict(Keyl,X, Left, Right), Value) ¬

Key > Keyl, lookup(Key, Right, Value).

Программа 15.9. Поиск в словаре, составленном в виде бинарного дерева.

Если имеется ряд пар ключей и значений, то справочник их определяет не единственным образом. Форма справочника зависит от порядка, в котором поступали вопросы.

Справочник может использоваться и для размораживания терма, который был заморожен с помощью программы 13.2 для предиката numbervars. С этой целью может использоваться программа 15.10. Каждая размороженная переменная вводится в справочник так, чтобы значения были присвоены соответствующим общим переменным.

freeze(A,B) ¬

Заморажнвание терма А в терме В.

freeze (А, В) ¬

сору(А.В), numbervars(B,0,N).

Melt_new(А,В) ¬

Освобождение (размораживание) терма А в терме В.

melt_new(A,B) ¬

melt (А, В, Dictionary),!.

melt ('$VAR'(N),X, Dictionary) ¬

lookup(N, Dictionary, X).

mell(X,Y, Dictionary) ¬

conslant(X).

melt(X,Y, Dictionary) ¬

compound(X),

functor(X,F,N),

funclor(Y,F,N),

melt(N,X,Y,Dictionary).

melt(N,X,Y, Dictionary) ¬

N >0.

arg(N,X,ArgX),

melt(ArgX,ArgY, Dictionary),

arg(N,Y,ArgY),

N1:= N- 1,

melt(N1,Х,У, Dictionary).

melt(0,X,Y, Dictionary).

copy(A.B) ¬ assert('$foo'(A)),retract('$foo'(B)).

numbervars(Term,Nl,N2) ¬ См. программу 13.2.

lookup(Key. Dictionary, Value) ¬ См. программу 15.9.

Программа 15.10. Размораживание терма.

Дата добавления: 2014-01-07