Буч Г. - Объектно-ориентированный анализ и проектирование с примерами приложений на C++ - 2001
.pdfИзложенный подход известен как метод информационной доски. Он впервые был предложен Ньюэллом в 1962 году, а позднее был использован Редди и Ерманом в проектах Hearsay и Hearsay II по распознаванию речи [4]. Эффективность метода подтвердилась, и он был использован в других областях, включая интерпретацию сигналов, трехмерное моделирование молекулярных структур, распознавание образов и планирование [5]. Метод показал хорошие результаты в представлении описательных знаний; он более эффективен с точки зрения памяти и времени по сравнению с другими подходами [б].
Информационная доска вполне подходит на роль среды разработки (см. главу 9). Попробуем теперь зафиксировать архитектуру этого метода в виде системы классов и механизмов их взаимодействия.
Архитектура метафоры информационной доски
Энглемор и Морган для пояснения модели информационной доски использовали следующую аналогию с группой людей, собирающей фрагменты головоломки в нужную фигуру:
Вообразим себе комнату с большой доской, рядом с которой находится группа людей, держащих в руках фрагменты изображения. Процесс начинают добровольцы, которые размещают на доске наиболее "вероятные" фрагменты изображения (предположим, что они прилепляются к доске). Далее каждый участник группы смотрит на оставшиеся у него фрагменты и решает, есть ли такие, которые подходят к уже находящимся на доске. Участник, нашедший соответствие, подходит к доске и прилепляет свой кусок. В результате фрагмент за фрагментом занимают нужное место. При этом не существенно, что один из участников может иметь больше фрагментов, чем другой. Все изображение будет полностью собрано без всякого обмена информацией между членами группы. Каждый участник активизируется самостоятельно и знает, когда ему нужно включиться в процесс. Никакого порядка подхода к доске заранее не устанавливается. Совместное поведение регулируется только информацией на доске. Наблюдение за процессом демонстрирует его последовательность (по одному фрагменту за подход) и произвольность (когда возникает возможность, фрагмент устанавливается). Это существенно отличается от строгой систематичности, например, от прохождения с левого верхнего угла и перебора каждого фрагмента[7].
Из рис. 11-1 видно, что основу метода составляют три элемента: информаци-онная доска, совокупность источников знаний и управляющий этими источниками контроллер [8]. Отметим, что следующее определение прямо соответствует принципам объектного подхода. Согласно Ни: "Информационная доска нужна для того чтобы хранить данные о ходе и состоянии решаемой задачи, используемые и формируемые источниками знаний. Доска содержит объекты из пространства решений. Эти объекты иерархически группируются по уровням анализа и вместе со своими атрибутами образуют словарь пространства решений" [9].
Энглемор и Морган уточняют: "необходимые для решения задачи знания о предметной области разделены на несколько независимых источников. Каждый источник знаний старается предложить информацию, полезную для решения за дачи. Текущая информация из каждого источника помещается на доске и модифи-
Рис. 11-1. Информационная доска
цируется в соответствии с содержанием знаний. Формой представления источников знаний являются процедуры, наборы правил или логические заключения" [10].
Источники знаний зависят от предметной области. В системах распознавания речи нас могут интересовать агенты, поставляющие знания о фонемах, словах и предложениях. В системах распознавания образов ими могут быть сведения об элементарных структурах изображения, таких, как стыки линий, участки одинаковой плотности, и, на более высоком уровне абстракции, объекты, относящиеся к конкретной сцене (дома, дороги, поля, автомобили и люди).
В общем случае источники знаний соответствуют иерархической структуре объектов, размещаемых на информационной доске. Более того, каждый источник использует объекты одного уровня иерархии в качестве входных данных, а в качестве выхода генерирует или изменяет объекты на другом уровне. Например, в системе распознавания речи источник знаний о словах наблюдает за потоком фонем (низкий уровень абстракции), чтобы обнаружить слово (более высокий уровень абстракции). Источник знаний о предложениях может предположить, что здесь нужен глагол (высокий уровень абстракции) и проверить это предположение, перебрав список возможных слов (низкий уровень абстракции),
Эти два подхода к поиску решения называются соответственно прямой и обратной последовательностью рассуждений. Прямая последовательность рассуждений позволяет перейти от более частных предположений к более общим, а обратная последовательность, отталкиваясь от некоторой гипотезы, позволяет проверить ее, сравнив с известными предпосылками. Вот почему управление информационной доской мы охарактеризовали как произвольное: в зависимости от обстоятельств, источники знаний могут активизировать либо прямые, либо обратные последовательности рассуждений.
Источники знаний, как правило, состоят из двух компонент: предусловия и действия. Предусловием называется такое состояние информационной доски, которое представляет "интерес" для конкретного источника знаний (потенциально способно его активизировать). Например, в распознавании образов предусловием может быть наличие прямой линии (которая может означать дорогу). Выполнение предусловий заставляет источник знаний сфокусировать внимание на конкретном участке информационной доски, а затем привести в действие соответствующие правила или процедурные знания.
В этих условиях очередность активизации не имеет значения: если источник знаний обнаруживает данные, полезные для решения задачи, он сигнализирует об этом контроллеру доски, фигурально выражаясь, он как бы поднимает руку, показывая, что желает сделать что-то полезное. Из нескольких источников, делающих такой жест, контроллер вызывает того, кто ему представляется наиболее перспективным.
Анализ источников знаний
Вернемся теперь к поставленной задаче и рассмотрим источники знаний, полезные для ее решения. При построении большинства приложений, основанных на знаниях, лучше всего сесть рядом с экспертом в предметной области и фиксировать те эвристики, которые он использует. В нашем случае придется попытаться расшифровать некоторое количество криптограмм и отметить особенности процесса поиска решений.
Действуя таким образом мы выявили тринадцать источников знаний, относящихся к нашей проблеме:
• Префиксы
• Суффиксы
• Согласные
• Непосредственно известные подстановки
• Двойные буквы
• Частота букв
• Правильные строки
• Сравнение с шаблоном
• Структура фраз
• Короткие слова
• Решение
• Гласные
• Структура слова
Исходя из объектно-ориентированного подхода, все эти источники знаний являются потенциальными кандидатами на роль классов, на основе которых создаются объекты, обладающие состоянием (знания), поведением (источник знаний о суффиксах может среагировать на слово с характерным окончанием) и индивидуальностью (знания о коротких словах не зависят от умения сравнивать с шаблоном).
Перечисленные источники знаний можно организовать в иерархию. В частности, существуют группы источников знаний о предложениях, о словах, о группах букв и об отдельных буквах. Такая иерархия соответствует объектам на информационной доске: предложениям, словам, частям слов и буквам.
11.2. Проектирование
Архитектура информационной доски
Теперь у нас есть все, чтобы приступить к решению поставленной задачи с использованием метафоры информационной доски. Это классический пример повторного использования "в большом": мы повторно применяем испытанный архитектурный шаблон как основу проекта. Метод информационной доски предполагает следующие объекты верхнего уровня: информационная доска, несколько источников знаний и контроллер. Остается только определить классы и объекты предметной области, которые специализируют эти общие абстракции.
Объекты информационной доски. Объекты на доске образуют иерархию, отражающую иерархичность различных уровней абстракции источников знаний. Таким образом, у нас есть три следующих класса:
•Sentence |
|
Полная криптограмма |
•Word |
Отдельное слово в криптограмме |
|
•CipherLetter |
Отдельная буква в слове |
|
Источники знаний должны пользоваться общей информацией о сделанных в процессе решения предположениях, поэтому в число объектов информационной доски включается следующий класс:
•Assumption Предположение, сделанное источником знаний
Наконец, источники знания делают предположения о связи между буквами реального и шифровального алфавитов, так что мы вводим следующий класс:
•Alphabet |
Алфавит исходного текста, алфавит |
криптограммы и |
|
соответствие между ними Есть ли между этими пятью классами что-либо общее? Ответ
однозначно утвердительный: все они соответствуют объектам информационной доски и этим существенно отличаются от других объектов, например, источников знаний и контроллера. Поэтому вводится следующий суперкласс для всех ранее перечисленных объектов:
class BlackboardObject ...
С точки зрения внешнего поведения определим для этого класса две
операции: |
|
•register |
Добавить объект на доску |
•resign |
Удалить объект с доски |
Почему мы определили эти две операции над объектами класса BlackboardObject, а не над самой доской? Это похоже на ситуацию, когда объект должен сам нарисовать себя в некотором окне. "Лакмусовый" тест в таких случаях, это вопрос: "Имеет ли сам объект достаточно знаний и умений, чтобы выполнять такие операции?". Объекты информационной доски как раз лучше всех понимают, как им правильно появляться на доске или удаляться с нее (конечно, они нуждаются при этом в помощи самой доски). Мы уже установили ранее, что объекты, взаимодействующие с доской, по своей сути должны самостоятельно включаться в процесс решения задачи.
Зависимости и подтверждения. Предложения, слова и буквы также связаны определенной общностью: для всех них есть соответствующие источники знаний. Конкретный источник знаний, со своей стороны, может проявлять интерес к одному или нескольким таким объектам (зависеть от них) и поэтому фраза, слово и символ шифра должны поддерживать связь с источником знаний, чтобы при появлении предположения относительно объекта уведомлялись соответствующие источники знаний. Это напоминает
механизм зависимостей языка Smalltalk, упомянутый в главе 4. Для реализации этого механизма введем следующий класс-примесь: class Dependent {
public:
Dependent(); Dependent(const Dependent&); virtual ~Dependent();
...
protected
UnboundedCollection<KnowledgeSource*> references;
};
Мы забежали несколько вперед и намекнули на возможную реализацию класса, чтобы показать связь с библиотекой фундаментальных классов, описанной в главе 9. В классе определен один внутренний элемент - коллекция указателей на источники знаний. 39
Определим для этого класса следующие операции:
•add |
Добавить ссылку на источник знаний |
|
•remove |
|
Удалить ссылку на источник знаний |
•numberOfDependents |
Возвратить число зависящих объектов |
|
•notify |
|
Известить каждого зависимого |
Последняя операция является пассивным итератором: при ее вызове передается как параметр действие, которое надо выполнить над всеми зависящими объектами в коллекции.
Зависимость может примешиваться к другим классам. Например, буква шифра - это объект информационной доски, от которого зависят другие, так что мы можем скомбинировать две этих абстракции для получения нужного поведения. Такое применение примесей поощряет повторное использование и разделение понятий в нашей архитектуре.
Символы шифра и алфавиты имеют еще одно общее свойство: относительно объектов этих классов могут делаться предположения. Вспомните, что предположение (Assumption) является одним из объектов на доске (BlackboardObject). Так, некоторый источник знаний может допустить, что буква K в шифре соответствует букве Р исходного текста. По мере решения задачи может абсолютно точно выясниться, что G означает J. Поэтому введен еще один класс:
class Affirmation . . .
Этот класс отвечает за высказывания (предположения или утверждения) относительно связанного с ним объекта. Мы используем этот класс не как примесь, а для агрегации. Буква, например, не является предположением, но может иметь предположение о себе.
В нашей системе предположения допускаются только в отношении отдельных букв и алфавитов. Можно, например, предположить, что какаялибо буква шифра соответствует некоторой букве алфавита. Алфавит состоит из набора букв, относительно которых делаются предположения. Определяя Affirmation как независимый класс, мы выражаем в нем сходное поведение этих двух классов, несвязанных наследованием.
Определим следующий набор операций для экземпляров этого класса:
•make |
Сделать высказывание |
•retract |
Отменить высказывание |
•chiphertext |
Вернуть шифрованный эквивалент для заданной |
буквы исходного текста |
|
•plaintext |
Вернуть исходный текстовый эквивалент для |
заданной буквы шифра
Из предыдущего обсуждения видно, что надо ясно различать две роли высказываний: временные предположения о соответствиях между буквами шифра и текста и окончательно доказанные соответствия - утверждена. По мере расшифровки криптограммы может делаться множество различных предположений о соответствии букв шифра и текста, но в конце концов находятся окончательные соответствия для всего алфавита. Чтобы отразить эти роли, уточним ранее выявленный класс Assumption в подклассе Assertion (утверждение). Экземпляры обоих классов управляются объектами класса Affirmation и могут помещаться на доску. Для поддержки введенных ранее операций make и retract нам необходимо определить следующие селекторы:
•isPlainLetterAsserted определена ли эта буква текста достоверно?
•isCipherLetterAsserted |
определена ли эта буква шифра |
достоверно? |
|
•plainLetterHasAssumptlon |
есть ли предположение об этой |
букве текста? |
|
•cipherLetterHasAssumption |
есть ли предположение об этой |
букве шифра? |
|
Теперь мы можем определить класс Assumption. Поскольку данная абстракция носит исключительно структурный характер, се состояние можно сделать открытым:
class Assumption : public BlackboardObject { public:
…
BlackboardObject* target; KnowledgeSource* creator; String<char> reason; char plainLetter;
char chipherLetter;
};
Отметим, что мы повторно использовали еще один класс среды, описанной в главе 9, а именно, параметризуемый класс String.
Класс Assumption является объектом информационной доски, поскольку информация о сделанных предположениях используется всеми источниками знаний. Отдельные члены класса выражают следующие его свойства:
•target Объект доски, о котором делается предположение
•creator |
Источник знаний, который сделал |
предположение |
|
•reason |
Основание для сделанного предположения |
•cipherLetter |
Предполагаемое значение буквы исходного |
текста |
|
Необходимость каждого из перечисленных свойств в значительной степени объясняется природой предположений: источник знании формирует предполагаемое соответствие "буква исходного текста - буква шифра" на основании каких-то причин (обычно, некоторого правила). Назначение первого свойства target менее очевидно. Оно нужно для отката. Если сделанное предположение не подтвердится, то нужно восстановить состояние объектов на доске, которые воспользовались предположением, а они должны известить источники знаний, что их смысл изменился.
Далее определим подкласс Assertion:
class Assertion : public Assumption ...
Общим для классов Assumption и Assertion является следующий селектор:
•isRetractaole Является ли соответствие потенциально неверным?
Для всех высказанных предположений значение предиката isRetractable является истинным, а для утверждений - ложным. Сделанное утверждение уже нельзя ни изменить ни отвергнуть.
Рис. 11-2. Классы зависимостей и высказываний
На рис. 11-2 приведена диаграмма, поясняющая связь классов зависимостей и высказываний. Обратите особое внимание на роли, которые играют упомянутые абстракции в различных ассоциациях. Например, класс KnowledgeSource в одном аспекте является создателем (creator) предположения, а в другом - ссылается (referencer) на букву шифра. Из различия ролей естественным образом вытекают различия протоколов взаимодействия.
Проектирование объектов информационной доски. Завершим проектирование, добавив кроме класса алфавита классы для предложения (Sentence), слова (Word) и буквы шифра (cipherLetter). Предложение представляет собой просто объект доски (от которого зависят другие объекты), содержащий список слов, Исходя из этого, запишем:
class Sentence : public BlackboardObject, virtual public Dependent {
public:
…
protected:
List<Word*>. words;
};
Суперкласс Dependent определен виртуальным, поскольку мы ожидаем, что будут подклассы от sentence, которые захотят наследовать также и от Dependent. При этом для всех таких подклассов члены класса Dependent будут общими.
В дополнение к операциям register и resign (определенным в суперклассе BlackboardObject) и четырем операциям, унаследованным от класса Dependent, мы добавляем еще две специфические операции для предложения:
•value |
Текущее значение предложения. |
•isSolved |
Истинно, если о всех словах в предложении |
сделаны утверждения.
Первоначальное значение value совпадает с текстом криптограммы. Когда isSolved станет истиной, value вернет исходный расшифрованный текст.
Слово является объектом доски и источником зависимости. Оно состоит из букв. Для удобства источников знаний в класс слова введены указатели на все предложение, а также на предыдущее и следующее слова в предложении. Описание класса Word выглядит так:
class Word : public BlackboardObject, virtual public Dependent {
public:
…
Sentence& sentence() const; Word* previous 0 const; Word* next() const;
protected:
List<CipherLetter*> letters;
};
Так же как для предложения, в класс слова введены две дополнительные операции:
•value Текущее значение слова.
•isSolved Истинно, если о всех буквах слова сделаны утверждения.
Теперь можно определить класс cipherLetter (буква шифра). Буквы шифра являются объектами информационной доски и порождают зависимости. Кроме того, они имеют значение (буква, как она записывается в шифровке, например, н) и коллекцию возможных предположений и утверждений о соотнесении ее с буквами исходного текста. Для организации коллекции мы используем класс Affirmation. Опишем класс буквы следующим образом:
class CipherLetter : public BlackboardObject, virtual public Dependent {
public:
…
char value() const;
int isSolvedO const; ...
protected:
char letter;
Affirmation affirmations;
};
Отметим, что и в этот класс добавлена та же пара селекторов по аналогии с классами слова и предложения. Для клиентов этого объекта нужно предусмотреть защищенные операции доступа к предположениям и утверждениям.
Объект affirmations, включенный в этот класс, содержит коллекцию предположений и утверждений в порядке их выдвижения. Последний элемент коллекции содержит текущее предположение или утверждение. Смысл хранения последовательности решения задачи состоит в возможности обучения источников знании на собственных ошибках. Поэтому в класс Affirmation введены два дополнительных селектора:
•moatRecent возвращает последнее предположение или утверждение
•statementAt возвращает n-ое высказывание (предположение или утверждение)
Уточнив поведение класса, мы можем принять правильные решения о его реализации. В частности, нам потребуется ввести в класс следующий защищенный объект:
UnboundedOrderedCollection<Assumption*> statements;
Этот объект также позаимствован нами из библиотеки фундаментальных классов главы 9.
Теперь обратимся к классу Alphabet (алфавит). Он содержит данные об алфавитах исходного текста и шифра, а также о соответствии между ними. Эта информация необходима для того, чтобы источники знаний могли узнать о выявленных соответствиях между буквами шифра и текста и тех, которые еще предстоит найти. Например, если уже доказано, что буква с а шифре соответствует букве и исходного текста, то это соответствие фиксируется в алфавите и источники знаний уже не будут делать других предположений в отношении буквы м исходного текста. Для эффективности обработки полезно получать данные о соответствии букв шифра и текста двумя способами: по букве шифра и по букве исходного текста. Определим класс Alphabet следующим образом:
class Alphabet : public BlackboardObject { public:
char plaintext (char) const; char ciphertext(char) const; int isBound(char) const;
};
Так же, как и в класс CipherLetter, в класс Alphabet необходимо включить защищенный объект affirmations и определить операции доступа к его состоянию.
Наконец, определим класс Blackboard, который является коллекцией экземпляров класса Blackboardobject и его подклассов:
class Blackboard : public DynamicCollection<BlackboardObject*>
...
Поскольку доска есть разновидность коллекции (тест на наследование), мы предпочитаем образовать этот класс методом наследования, а не с помощью включения экземпляра класса DynamicCollectlon. Операции включения в коллекцию и исключения из нее наследуются от класса Collection, а следующие пять операций, специфичных для информационной доски, вводятся нами:
•reset |
Очистить доску |
•assertProblem |
Поместить на доске начальные условия задачи |
•connect |
Подключить к доске источник знании |
•issolved |
Истинно, если предложение расшифровано |
•retriaveSolution Значение расшифрованного текста
Вторая операция устанавливает зависимость между доской и источником знании. На рис. 11-3 приведена итоговая диаграмма классов, связанных с Blackboard. Она в первую очередь отражает отношения наследования. Отношения использования (например, между Assumption и информационной доской) для простоты опушены.
Рис. 11-3. Диаграмма классов информационной доски
Обратите внимание на то, что класс Blackboard одновременно и инстанциру-ет от шаблона DynamicCollection, и наследует от него. Кроме того, становится понятным использование класса Dependent в качестве примеси. Не привязывая этот класс жестко к иерархии Blackboard, мы повышаем шансы на его последующее повторное использование.
Проектирование источников знаний
В предыдущем разделе мы выделили тринадцать источников знаний, относящихся к решаемой задаче. Теперь можно приступить к проектированию структур классов для них (как это было сделано для информационной доски) и обобщению их в более абстрактные классы.
Проектирование специализированных источников знаний.
Предположим, что существует абстрактный класс KnowledgeSource (по аналогии с классом BlackboardObject). Прежде чем определять все тринадцать источников в качестве подклассов одного общего суперкласса, нужно посмотреть, не группируются ли они каким-нибудь образом. Действительно, такие группы находятся: некоторые источники знаний оперируют целым предложением, другие - словами, фрагментами слов или отдельными буквами. Отразим этот факт в следующих определениях: class SentenceKnowledgeSource : public KnowledgeSource ...
class WordKnowledgeSource : public KnowledgeSource ...
class LetterKnowledgeSource : public KnowledgeSource ...
Для каждого из этих абстрактных классов в дальнейшем мы определим специализированные подклассы. Для класса SentenceKnowledgeSource они будут выглядеть следующим образом:
class SentenceStructureKnowledgeSource : public SentenceKnowledgeSource ...
class SolvedKnowledgeSource : public SentenceKnowledgeSource ...