Software & Systems

В компьютерной алгебре [1] существует направление, ориентированное на системы, основанные на так называемых правилах перезаписи. Входное алгебраическое выражение в таких системах преобразовывается по типу и образцу правил перезаписи, которые представляют собой нечто близкое к обычным тождествам и формулам в математике. Из множества правил перезаписи выбирается некоторым образом одно правило, левая часть которого соответствует входному выражению, подобно тому, как выбирается применимое тождество для преобразования алгебраического выражения. Затем входное выражение заменяется на выражение, соответствующее правой части правила. Если соответствующее правило не найдено, то процесс преобразования заканчивается. К числу подобных систем, где реализован данный механизм, можно отнести следующие: PRESS [2], Алькор [3], Santra-Basic [4], Алгебра [5] и многие другие.

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

В систему Алгебра [5] включена как составная часть оригинальная база данных алгебраических выражений (БД Абдал) для манипулирования правилами перезаписи, что позволяет производить быстрый поиск применимых к входному выражению правил. Кроме того, БД Абдал может выступать и в качестве самостоятельной базы данных алгебраических выражений. В такой роли Абдал была использована при создании электронного справочника по дифференциальным уравнениям, являющимся аналогом справочника Камке “Дифференциальные уравнения”.

БД Абдал обеспечивает выполнение трех основных функций: поиск, вставку и удаление записей, являющихся алгебраическими выражениями, представленными во внутреннем виде системы Алгебра, если база данных работает в ее составе, либо записанными в виде, практически не отличающемся от обычного написания выражений в математике, если БД Абдал используется самостоятельно.

Для удобства условимся, что выражения записаны с помощью термов следующих типов:

А. Конкретные константы (0, 1, 3.14159, ...)

Б. Общие константы (a, b, C, ...)

В. Переменные (x, y, z, ...)

Г. Конкретные функции (sin, tg, ln, ...)

Д. Общие функции (f(x), g(x), ...)

А также: скобки, знаки препинания и т.п.

Определение 1. Подстановкой в выражение v называется операция, при которой выражение v переписывается с заменой терма t1, обозначающего либо общую константу, либо общую функцию, на терм t2, причем: если t1 - общая константа, то t2 - конкретная константа; если t1 - общая функция, то t2 - конкретная функция либо подвыражение.

Определение 2. Переобозначением выражения v называется операция, при которой в выражении v переименовываются переменные, общие константы и общие функции.

Определение 3. Выражение w соответствует выражению v, если из выражения w путем конечного числа подстановок и переобозначений можно получить выражение v.

Утверждение 1. Из того, что выражение w соответствует выражению v не следует, что выражение v соответствует выражению w.

Доказательство следует из нижеприведенного примера.

Пример. Пусть даны два тождества:

 w1 : (a + 1)^2 = a^2 + 2a + 1,

 w2 : (a + b)^2 = a^2 + 2ab + b^2

и выражение v : (a + 5)^2.

Видно, что левая часть тождества w2 соответствует левой части тождества w1, однако обратное неверно, что и доказывает утверждение 1.

Выражению v соответствует тождество w2, но не тождество w1. Таким образом, понятия применимости и соответствия в некотором смысле совпадают.

Заметим, что при поиске выделяются все правила перезаписи, левая часть которых соответствует запросу. Далее система Алгебра выбирает из выделенных применимое правило и преобразовывает входное выражение по образцу этого правила. Если БД Абдал используется как электронный справочник, например как справочник "Дифференциальные уравнения", то выделяются все уравнения, соответствующие запросу, причем левая часть выделенной записи является самим уравнением, а правая часть может содержать любую информацию, в том числе и решение этого уравнения.

 Данные хранятся в отдельном файле последовательно в порядке их поступления в базу данных. В основе поисковых процедур лежит модифицированный метод хеширования [6]. Использование его в "чистом" виде для нашей задачи представляется невозможным по причине специфического понятия соответствия выражений друг другу. Чтобы убедиться в этом, достаточно заметить, что вместо терма f(x) может быть записано любое подвыражение, а для определения ключевого слова необходимо иметь в записи что-нибудь устойчивое и неизменяющееся. Суть модификации состоит в том, что данные разбиваются на подмножества, в каждом из которых уже возможно определение корректного ключевого слова.

Перейдем к более подробному описанию нашего метода поиска. Известно, что любое выражение может быть представлено в виде дерева, где узлы дерева соответствуют функциям, а "сыновья" узла - аргументам функции. В дискретной математике есть способ однозначной кодировки дерева [7], суть которой заключается в следующем (для удобства мы несколько модифицировали ее определение ).

Пусть каждой функции присвоен номер. Дереву с одним ребром соответствует код 0k, где k - номер функции.

Дереву, имеющему одну корневую ветвь, сопоставим код 0xk, где k - номер корневой функции, x - код дерева, который получится, если удалить из дерева корень и объявить корнем узел, инцидентный бывшему корню.

Дереву, имеющему несколько корневых ветвей, сопоставим код x1 x2 ... xl, где xi - код дерева. Таким образом можно закодировать любое выражение.

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

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

Утверждение 2. Если выражение w соответствует выражению v, то ключевые слова w и v одинаковы.

Доказательство. Достаточно доказать, что при переобозначении переменных и общих констант, а также при подстановке конкретных констант на место общих код дерева выражения не меняется. Но при этих операциях у дерева меняются только листья. А при кодировании тип листьев не учитывается. Следовательно и код дерева не меняется.

Рассмотрим теперь любые выражения, в том числе и имеющие общие функции. Пусть M - множество выражений, среди которых идет поиск; v - любое выражение. Занумеруем уровни дерева : 0-ой уровень - корень дерева, 1-ый уровень - "сыновья" 0-го уровня и т.д.

Определение 4. Выражение v является выражением n-го уровня, если на n+1-ом уровне дерева существует узел, соответствующий общей функции, а на 0-ом, 1-ом, ..., n-ом уровнях таких узлов нет. Если в дереве вообще нет узлов, соответствующих общим функциям, то выражение, соответствующее этому дереву, назовем выражением бесконечного уровня.

Разобьем M на подмножества M0, M1, ..., Mn, где Mi - множество i-го уровня, содержащее выражения i-го уровня и только их, i=1,...,n. M0 - множество бесконечного уровня. Нам надо найти выражения, которые соответствуют запросу. Следовательно, если запрос v имеет уровень i, то нам надо искать соответствующие выражения в подмножествах

{ Mi, Mi-1, ..., M1, i != 0;

{ M0, M1, ..., Mn, i = 0; (бесконечный уровень)

 Для выражений из множества Mi, i=1,...,n, считаем ключевое слово, учитывая лишь первые i уровней. Тем самым мы как бы отрезаем нижнюю часть дерева, в которой находятся общие функции.

При поиске в каждом множестве Mi, i= 1,...,n, пересчитываем ключевое слово запроса, учитывая первые i уровней.

Утверждение 3. Если выражение w соответствует выражению v, то ключевые слова, подсчитанные до i-го уровня, одинаковы; где i=min(уровень w, уровень v).

Доказательство проводится аналогично доказательству утверждения 1.

На основе утверждений 1 и 2 можно заключить, что для каждого уровня ключевые слова соответствующих выражений являются одинаковыми, что позволяет использовать метод хеширования для быстрого поиска выражений, соответствующих запросу.

Опираясь на полученные результаты, представим общую схему алгоритма поиска. Введем следующие обозначения: Mik - подмножество множества Mi, имеющее ключевое слово k; v - запрос, yv - уровень запроса, n - максимальный уровень выражений из множества M.

1. Если запрос v бесконечного уровня,

то 1.1 вычислить ключ запроса v, пусть ключ v = kv;

1.2 выход хешированием на подмножество M0kv;

1.3 поиск перебором в M0kv.

2. Вычислить уровень yv запроса v.

3. l := min(yv,n);

4. Цикл от i := l уменьшая до 1

4.1 пересчитать ключ v до уровня i; пусть это kv;

4.1 выход хешированием на подмножество Mikv;

4.3 поиск перебором в Mikv

 Конец цикла;

 5. Конец.

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

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

Программное обеспечение написано на языке Си. Система может быть использована на ЭВМ типа IBM PC и рабочих станциях.

Список литературы

1. Абрамов С.А., Зима Е.В., Ростовцев В.А. Компьютерная алгебра // Программирование, - 1992. - № 5. - С. 4-25.

2. Bundy A., Welham B. Using meta-level inference for selective application of multiple rewrite rules in algebraic manipulation // Artificial intelligence. - 1981. - Vol. 16, - ¹ 2. - Р. 189-218.

3. Проворов Л.В. Система Алькор // Системы для аналитических преобразований в механике / Тезисы докладов Всесоюз. конф.-Горький: Изд-во ГГУ, 1984. - C. 42-43.

4. Щенков И.Б. Система Santra-Basic для символьно-аналитических преобразований // Системы для аналитических преобразований в механике / Тезисы докладов Всесоюз. конф. - Горький: Изд-во ГГУ. 1984. - C. 47-49.

5. Михайлюк М.В., Петрова И.Н., Трушина А.А. О некоторых компонентах системы компьютерной алгебры // Программные продукты и системы. -1992. - № 1.- С. 51-53.

6. Кохонен Т. Ассоциативные запоминающие устройства. // М.: Мир, 1982, -384 с.

7. Яблонский С.В. Введение в дискретную математику// М.: Наука, 1986.-384 с.