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