Algorytmy rozpoznawania wzorów

Question

W przeszłości musiałem opracować program, który działał z reguły jako ewaluator. Miałeś poprzednika i kilka podstępów (działań), więc jeśli poprzednik zdeterminował prawdziwe działania, które zostały wykonane.

W tym czasie użyłem zmodyfikowanej wersji RETE algorithm (istnieją trzy wersje RETE, z których tylko pierwsza jest publiczna) w celu dopasowania wzorca poprzedzającego. Mówimy tu o wielkim systemie z milionem operacji na regułę, a niektórzy operatorzy "powtarzali" w kilku regułach.

Jest możliwe, że będę musiał zaimplementować go ponownie w innym języku i mimo, że mam doświadczenie w RETE, czy ktoś wie o innych algorytmach dopasowywania wzorców? Jakieś sugestie czy powinienem nadal używać RETE?

Answer 1

Algorytm TREAT jest podobny do RETE, ale nie rejestruje częściowych dopasowań. W rezultacie może w niektórych sytuacjach zużywać mniej pamięci niż RETE. Ponadto, jeśli zmodyfikujesz znaczną liczbę znanych faktów, TREAT może być znacznie szybszy, ponieważ nie musisz tracić czasu na wycofywanie.

Istnieje również RETE*, który równoważy wartości RETE i TREAT przez zapisanie stanu łączenia węzłów w zależności od tego, ile pamięci chcesz użyć. Nadal oszczędzasz czas asercji, ale także oszczędzasz pamięć i oszczędzasz czas, w zależności od tego, jak dostroisz swój system.

Możesz również chcieć sprawdzić LEAPS, która wykorzystuje leniwy schemat oceny i zawiera elementy zarówno RETE, jak i TREAT.

Mam tylko osobiste doświadczenie z RETE, ale wygląda na to, że RETE * lub LEAPS to lepsze, bardziej elastyczne wybory.