Удаление общих подвыражений

#алгоритм #cpp

Доброго времени суток!
Столкнулся с такой задачей: есть n уравнений, записанных в символьном виде, необходимо
оптимизировать количество операций для их вычисления (пока для простоты подразумевается
только сложение). Вот пример:
Исходная система уравнений:
x1 = a + b + c
x2 = a + d + c
x3 = a + e + c

В результате должно получиться следующее:
r1 = a + c
x1 = r1 + b
x2 = r1 + d
x3 = r1 + e

Здесь r1 - это замена повторяющейся операции a + b. Легко видеть, что количество
сложений уменьшилось с 6 до 4. Все это хорошо, но с маленькими уравнениями, а вот когда
количество переменных переваливает за несколько сотен - надо писать программу.
Реализовывать алгоритм мне необходимо на C/C++. 
После длительного гугления, я выяснил что это называется common subexpression elimination
(или удаление общих подвыражений). Однако, как написать программу или каким именно
методом такое можно реализовать я так и не понял. И поэтому придумал свой велоспед. 
Суть велосипеда в следующем:
Входными данными является набор строк. Каждая строка представляет собой одно уравнение,
например: abc - это x1 = a + b + c
Алгоритм действий следующий:
1) упорядочиваем все переменные всех уравнений (ибо он могут быть записаны не по порядку)
2) создаем для каждого уравнения битовый вектор
3) Используя побитовый AND складываем все уравнения и ищем вектор с максимальным
количеством установленных бит
4) Добавляем новое уравнение составленное из бит полученных на предыдущем шаге
5) Повторяем все шаги пока не получим нулевой вектор
Я сильно сомневаюсь, что иду правильным путем.
Подскажите, пожалуйста, может кто-то сталкивался с подобными алгоритмами, или натолкнете
на идею/книгу/библиотеку?
P.S. Сорри если сумбурно, я уже совсем замучался((    

Ответы

Ответ 1

Смотрите, это делается, например, так.

Для начала, для преобразований кода вам нужно распарсить его в syntax tree, или в
ещё более удобное представление (например, semantic tree). (Это самая лёгкая часть,
вам всё равно это понадобится.)
Суммы переведите из бинарных в n-арные операции. Если одно из слагаемых — сумма,
уберите его и добавьте его подслагаемые. То же с разностями. Установите канонический
порядок на слагаемых, чтобы не различать x + 3 и 3 + x.
Составляете список всех подвыражений в дереве путём его рекурсивного обхода.
Далее вам нужно ввести порядок на выражениях. Например, вы можете написать хэш-функцию
такую, чтобы одинаковые подвыражения обязательно получали одинаковое значение. (Если
вы определите хэш-функцию рекурсивно, будет как раз то, что надо.)
Вычислите значения хэша на каждом подвыражении (опять-таки рекурсивно). Отсортируйте
список по хэшу.
Рассматривайте (относительно маленькие) группы с одинаковым хэшем. Определите рекурсивно
равенство выражений:
высоты деревьев не равны => подвыражения не равны
типы корней не совпадают => подвыражения не равны
поддеревья не совпадают => подвыражения не равны
иначе равны


Таким образом, получите список одинаковых подвыражений.
Поскольку суммы можно разделить на части по-разному, вычисляйте хэши также для частичных
сумм. Достаточно отсортировать слагаемые, и вычислить 2^n вариантов (включая/не включая
каждое из слагаемых). Эти частичные суммы тоже добавляйте в список подвыражений (со
ссылкой на оригинальное выражение). При разумном числе слагаемых получится не так уж
и много вариантов.

Дерзайте, у вас прекрасное задание!