Организация доски объявлений в системе GBB

18.4.1. Организация доски объявлений в системе GBB

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

В ранних системах для повышения производительности операций с доской объявлений использовалось разбиение ее на уровни или "панели", что позволяло сократить пространство поиска, поскольку определенный источник знаний требовал просмотра только части всей структуры данных.

Ниже мы несколько подробнее рассмотрим современную систему, названную создателями GBB (Generic Blackboard Builder). Ее можно рассматривать как типичного представителя нового поколения систем с такой архитектурой.

Разделы доски объявлений в GBB называются пространствами (spaces), причем они, в свою очередь, разделены на размерности (dimensions), для доступа к которым используется специальный атрибут индексации. Элементы структуры данных доски объявлений "живут" в этих пространствах, причем оснащены собственными атрибутами индексации, позволяющими реализовать множество различных методов быстрого обращения к ним. Если пользоваться терминологией баз данных, то эти индексы являются, по существу, ключами, хотя и довольно сложными.

Размерности, используемые для дальнейшей структуризации пространств, могут быть упорядоченными (ordered) или перечислимыми (enumerated). Индексы могут быть скалярными, т.е. состоять из единственного элемента данных, или составными, состоящими из множества компонентов. Скалярные индексы упорядоченных размерностей представляют собой числа из некоторого диапазона, а составные индексы могут быть либо набором меток, либо последовательностью, упорядоченной в соответствии с какой-либо другой размерностью, например по времени.

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

(1) Первичное извлечение. Выбирается множество всех элементов данного пространства доски объявлений, которые "претендуют" на сопоставление с шаблоном. Каждое пространство имеет карту элементов, с помощью которой можно определить, как элементы хранятся в этом пространстве. Можно, конечно, хранить их и в виде последовательного списка, но такой способ недостаточно эффективен. Элементы в упорядоченных размерностях со скалярными индексами можно хранить в виде "пакетов", т.е. наборов, имеющих индексы в определенном диапазоне, а элементы перечислимых размерностей, имеющие составные индексы, — в виде хешированных таблиц.

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

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

(4) Постфильтрация. К каждому отобранному элементу доски объявлений применяются дополнительные процедуры проверки. Этот этап необязателен, как, впрочем, и этап предварительной фильтрации. В результате множество элементов-претендентов еще более сужается.

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