Алгоритм Rete

Rete — эффективный алгоритм сопоставления с образцом для , экспертных систем и баз знаний, созданный из Университета Карнеги — Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 года и в статье 1982 года (см. ). Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar. При наивной реализации экспертная система проверяет применимость каждого правила вывода к каждому факту базы знаний, при необходимости выполняет его и переходит к следующему правилу, возвращаясь в начало при исчерпании всех правил. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность. При использовании Rete экспертная система строит специальный граф или префиксное дерево, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции. В процессе работы каждый узел хранит список фактов, соответствующих условию. При добавлении или модификации факта он прогоняется по сети, при этом отмечаются узлы, условиям которых данный факт соответствует. При выполнении полного условия правила, когда система достигает листа графа, правило выполняется. Алгоритм Rete жертвует объёмом памяти ради скорости. В большинстве случаев скорость возрастает на порядки (так как эффективность теоретически не зависит от числа правил в системе). В экспертных системах с большим числом правил классический Rete требует слишком много памяти, но появились новые алгоритмы, в том числе основанные на Rete, ограничивающиеся разумным объёмом памяти, см. .