Rete algorithm (original) (raw)
L'algorisme Rete és un algorisme de reconeixement de patrons eficient per implementar un sistema de producció de regles. Va ser creat pel Dr. a la Carnegie Mellon University. La seva primera referència escrita data de 1974, i va aparèixer de forma més detallada en la seva tesi doctoral (el 1979) i en un article científic de 1982. Rete és avui dia la base de molts sistemes experts molt famosos, incloent , , , i .
| Property | Value |
|---|---|
| dbo:abstract | L'algorisme Rete és un algorisme de reconeixement de patrons eficient per implementar un sistema de producció de regles. Va ser creat pel Dr. a la Carnegie Mellon University. La seva primera referència escrita data de 1974, i va aparèixer de forma més detallada en la seva tesi doctoral (el 1979) i en un article científic de 1982. Rete és avui dia la base de molts sistemes experts molt famosos, incloent , , , i . (ca) Der Rete-Algorithmus (lateinisch rete ‚Netz‘, ‚Netzwerk‘) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Er wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit an der Carnegie Mellon University entwickelt, der ihn 1979 zum Titel führen sollte. Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war. (de) El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar un . Fue creado por el Dr. en la Carnegie Mellon University. Su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral (en 1979) y en un artículo científico de 1982. Rete es hoy en día la base de muchos sistemas expertos muy famosos, incluyendo CLIPS, , Drools, y . (es) L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par Charles L. Forgy de l'université Carnegie-Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse de doctorat en 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, Drools, Ilog JRules, Soar...etc Une implémentation naïve d'un système expert pourrait vérifier chaque règle en la confrontant aux faits de la base de connaissance, éliminant les règles au fur et à mesure, puis passant à la règle suivante (et rebouclant à la première règle une fois terminé). Même pour des règles et des bases de connaissance de taille réduite, cette approche naïve est bien trop longue. L'algorithme de Rete (habituellement prononcé en Europe, « re-té » d'après la prononciation latine, du latin « rete » pour réseau) fournit la base pour une exécution plus efficace d'un système expert. Un système expert basé sur Rete établit un réseau des nœuds, où chaque nœud (excepté la racine) correspond à un modèle se produisant dans le « côté gauche » d'une règle. Le chemin du nœud racine à un nœud externe (leaf node) définit un « côté gauche » complet de règle. Chaque nœud a une mémoire des faits qui satisfont ce modèle. Cette structure est essentiellement un trie généralisé. Lorsque de nouveaux faits sont affirmés ou modifiés, ils se propagent le long du réseau, annotant les nœuds quand les faits correspondent au modèle. Quand un fait ou une combinaison des faits satisfait tous les modèles d'une règle donnée, un nœud externe (leaf node) est atteint et la règle correspondante est déclenchée. L'algorithme de Rete est conçu pour sacrifier la mémoire au profit de la vitesse. Dans la plupart des cas, l'augmentation de la vitesse par rapport à une implémentation naïve est de plusieurs ordres de grandeur (parce que l'exécution de Rete est théoriquement indépendante du nombre de règles dans le système). Dans les systèmes experts très grands, cependant, l'algorithme de Rete original tend à rencontrer des problèmes de consommation de mémoire. D'autres algorithmes ont depuis été conçus, d'une part basés sur Rete ou d'autre part complètement nouveaux, qui exigent moins de mémoire. (fr) The Rete algorithm (/ˈriːtiː/ REE-tee, /ˈreɪtiː/ RAY-tee, rarely /ˈriːt/ REET, /rɛˈteɪ/ reh-TAY) is a pattern matching algorithm for implementing rule-based systems. The algorithm was developed to efficiently apply many rules or patterns to many objects, or facts, in a knowledge base. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper. (en) L'algoritmo Rete è un efficiente algoritmo di pattern matching per l'implementazione di sistemi di produzione a regole. È stato creato da della Carnegie Mellon University. La prima pubblicazione dell'algoritmo risale al 1974 e dopo rielaborato nel 1979 per la sua tesi di dottorato. L'algoritmo Rete è alla base di alcuni tra i più popolari sistemi esperti come ad esempio: * Blaze Advisor, su fairisaac.com. URL consultato il 26 febbraio 2007 (archiviato dall'url originale il 16 febbraio 2007). * JRules, su ilog.com. * * CLIPS * Jess * LISA, su lisa.sourceforge.net. Un'implementazione 'naïve' di un sistema esperto dovrebbe verificare ogni regola rispetto ai fatti conosciuti presenti nella base di conoscenza attivando la regola necessaria e poi passando a controllare le altre regole applicabili. Questo approccio 'naïve' anche per piccoli sistemi con un numero prefissato di regole e fatti, si rivela molto inefficiente. L'algoritmo Rete fornisce una efficiente base per l'implementazione di un sistema esperto. Un sistema esperto Rete-based costruisce un network di nodi, dove ogni nodo (ad eccezione del nodo radice) corrisponde ad un pattern presente nella parte sinistra di una regola. Il cammino che collega il nodo radice al nodo foglia definisce una completa parte sinistra di una regola. Ogni nodo ha una memoria di fatti che soddisfano quel pattern. Questa struttura è genericamente riconducibile ad un Trie (it) Het rete-algoritme is een algoritme voor patroonmatching, gebruikt bij regelgebaseerde productiesystemen (expertsystemen). Het werd in 1979 ontwikkeld door Dr. Charles L. Forgy van de Carnegie-Mellon Universiteit. Het rete-algoritme wordt toegepast in veelgebruikte expertsystemen zoals , CLIPS, JESS en LISA. Een eenvoudige implementatie van een expertsysteem zou elke productieregel kunnen vergelijken met alle feiten in de feitenverzameling van het expertsysteem, en deze proberen uit te voeren wanneer aan de condities van de productieregel voldaan zijn. Zelfs voor kleine feitenverzamelingen en kennisbanken is deze benadering veel te traag. Het rete-algoritme (van het Latijnse rete, dat net, netwerk betekent) ligt aan de basis van een meer efficiënte implementatie: het algoritme bouwt een graaf op waarbij elke (behalve de ) overeenkomt met een bepaald patroon in de condities van de productieregel. Het van de wortel tot een definieert een dergelijke (conjunctie van) condities. Elke knoop houdt in het geheugen de lijst van feiten bij die aan het patroon horend bij de knoop voldoen. (nl) Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参照）。数々のエキスパートシステムの基盤として使われており、JRules、、CLIPS、Jess、Drools、Soar、LISA、Microsoft BizTalk Server におけるビジネスルールエンジン、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。 素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。 Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。 新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（RHS）が起動される。 Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。 (ja) Rete — эффективный алгоритм сопоставления с образцом для , экспертных систем и баз знаний, созданный из Университета Карнеги — Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 года и в статье 1982 года (см. ). Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar. При наивной реализации экспертная система проверяет применимость каждого правила вывода к каждому факту базы знаний, при необходимости выполняет его и переходит к следующему правилу, возвращаясь в начало при исчерпании всех правил. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность. При использовании Rete экспертная система строит специальный граф или префиксное дерево, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции. В процессе работы каждый узел хранит список фактов, соответствующих условию. При добавлении или модификации факта он прогоняется по сети, при этом отмечаются узлы, условиям которых данный факт соответствует. При выполнении полного условия правила, когда система достигает листа графа, правило выполняется. Алгоритм Rete жертвует объёмом памяти ради скорости. В большинстве случаев скорость возрастает на порядки (так как эффективность теоретически не зависит от числа правил в системе). В экспертных системах с большим числом правил классический Rete требует слишком много памяти, но появились новые алгоритмы, в том числе основанные на Rete, ограничивающиеся разумным объёмом памяти, см. . (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Rete.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cut-the-knot.org/classes/Last.shtml https://github.com/cerner/clara-rules http://drdobbs.com/184405218 http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf http://reports-archive.adm.cs.cmu.edu/anon/scan/CMU-CS-79-forgy.pdf |
| dbo:wikiPageID | 172566 (xsd:integer) |
| dbo:wikiPageLength | 36444 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1105678356 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Carnegie_Mellon_University dbr:Root_node dbr:Negation_as_failure dbr:Universal_quantification dbr:Bayesian_network dbr:Decision_trees dbr:Algorithm dbc:Pattern_matching dbr:Charles_Forgy dbr:Cycle_detection dbr:Double_negation dbr:Inference dbr:Inference_engine dbr:Quantification_(logic) dbr:Object_(computer_science) dbr:OPS5 dbr:Equality_(mathematics) dbr:Logical_conjunction dbr:Computer_memory dbr:Data_types dbr:Priority_queue dbr:Table_(database) dbr:Business_analyst dbr:Trie dbr:Tuple dbr:Fuzzy_logic dbr:Leaf_node dbr:Linked_list dbr:Logical_truth dbr:Cut-the-knot dbr:Daniel_P._Miranker dbr:Drools dbr:Forward_chaining dbr:Knowledge_base dbr:Logical_connective dbr:Projection_(relational_algebra) dbr:Rule-based_system dbr:Hash_table dbr:Attribute_(computing) dbr:Backward_chaining dbr:Directed_acyclic_graph dbc:Expert_systems dbr:Business_rules_engine dbr:Software_developer dbr:XML dbr:If-then-else dbr:Pattern_matching dbr:Rule_of_inference dbr:Selection_(relational_algebra) dbr:Soar_(cognitive_architecture) dbr:Variable_(mathematics) dbr:Vertex_(graph_theory) dbr:Expert_system dbr:Fact dbr:IBM_Operational_Decision_Management dbr:Probabilistic_logic dbr:Existential_quantification dbr:Jess_programming_language dbr:Rule_engine dbr:First_order_logic dbr:BizTalk dbr:Action_selection_mechanism dbr:Naïve_algorithm dbr:Tibco dbr:CLIPS_programming_language dbr:Truth_maintenance_systems dbr:Wikt:entity dbr:Wiktionary:Network dbr:File:Rete.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:IPAc-en dbt:More_citations_needed dbt:More_footnotes_needed dbt:Reflist dbt:Respell dbt:Short_description |
| dcterms:subject | dbc:Pattern_matching dbc:Expert_systems |
| gold:hypernym | dbr:Pattern |
| rdf:type | yago:Artifact100021939 yago:Instrumentality103575240 yago:Object100002684 yago:PhysicalEntity100001930 dbo:Disease yago:System104377057 yago:Whole100003553 yago:WikicatExpertSystems |
| rdfs:comment | L'algorisme Rete és un algorisme de reconeixement de patrons eficient per implementar un sistema de producció de regles. Va ser creat pel Dr. a la Carnegie Mellon University. La seva primera referència escrita data de 1974, i va aparèixer de forma més detallada en la seva tesi doctoral (el 1979) i en un article científic de 1982. Rete és avui dia la base de molts sistemes experts molt famosos, incloent , , , i . (ca) Der Rete-Algorithmus (lateinisch rete ‚Netz‘, ‚Netzwerk‘) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Er wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit an der Carnegie Mellon University entwickelt, der ihn 1979 zum Titel führen sollte. Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war. (de) El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar un . Fue creado por el Dr. en la Carnegie Mellon University. Su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral (en 1979) y en un artículo científico de 1982. Rete es hoy en día la base de muchos sistemas expertos muy famosos, incluyendo CLIPS, , Drools, y . (es) The Rete algorithm (/ˈriːtiː/ REE-tee, /ˈreɪtiː/ RAY-tee, rarely /ˈriːt/ REET, /rɛˈteɪ/ reh-TAY) is a pattern matching algorithm for implementing rule-based systems. The algorithm was developed to efficiently apply many rules or patterns to many objects, or facts, in a knowledge base. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper. (en) L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par Charles L. Forgy de l'université Carnegie-Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse de doctorat en 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, Drools, Ilog JRules, Soar...etc (fr) Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参照）。数々のエキスパートシステムの基盤として使われており、JRules、、CLIPS、Jess、Drools、Soar、LISA、Microsoft BizTalk Server におけるビジネスルールエンジン、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。 素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。 新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（RHS）が起動される。 (ja) L'algoritmo Rete è un efficiente algoritmo di pattern matching per l'implementazione di sistemi di produzione a regole. È stato creato da della Carnegie Mellon University. La prima pubblicazione dell'algoritmo risale al 1974 e dopo rielaborato nel 1979 per la sua tesi di dottorato. L'algoritmo Rete è alla base di alcuni tra i più popolari sistemi esperti come ad esempio: * Blaze Advisor, su fairisaac.com. URL consultato il 26 febbraio 2007 (archiviato dall'url originale il 16 febbraio 2007). * JRules, su ilog.com. * * CLIPS * Jess * LISA, su lisa.sourceforge.net. (it) Het rete-algoritme is een algoritme voor patroonmatching, gebruikt bij regelgebaseerde productiesystemen (expertsystemen). Het werd in 1979 ontwikkeld door Dr. Charles L. Forgy van de Carnegie-Mellon Universiteit. Het rete-algoritme wordt toegepast in veelgebruikte expertsystemen zoals , CLIPS, JESS en LISA. (nl) Rete — эффективный алгоритм сопоставления с образцом для , экспертных систем и баз знаний, созданный из Университета Карнеги — Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 года и в статье 1982 года (см. ). Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar. (ru) |
| rdfs:label | Algorisme Rete (ca) Rete-Algorithmus (de) Algoritmo Rete (es) Algorithme de Rete (fr) Algoritmo Rete (it) Reteアルゴリズム (ja) Rete-algoritme (nl) Rete algorithm (en) Алгоритм Rete (ru) |
| owl:sameAs | freebase:Rete algorithm yago-res:Rete algorithm wikidata:Rete algorithm dbpedia-ca:Rete algorithm dbpedia-de:Rete algorithm dbpedia-es:Rete algorithm dbpedia-fa:Rete algorithm dbpedia-fr:Rete algorithm dbpedia-it:Rete algorithm dbpedia-ja:Rete algorithm dbpedia-nl:Rete algorithm dbpedia-ru:Rete algorithm dbpedia-sr:Rete algorithm https://global.dbpedia.org/id/ufE2 |
| prov:wasDerivedFrom | wikipedia-en:Rete_algorithm?oldid=1105678356&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Rete.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Rete_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Rete |
| is dbo:wikiPageRedirects of | dbr:ReteOO dbr:Rete2 dbr:Rete_II dbr:Rete_network dbr:Rete_resolution_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Reactive_planning dbr:Charles_Forgy dbr:Inference_engine dbr:Workflow_engine dbr:Constraint_Handling_Rules dbr:MassTransit-Project dbr:OPS5 dbr:Semantic_reasoner dbr:ReteOO dbr:Glossary_of_artificial_intelligence dbr:Lisp-based_Intelligent_Software_Agents dbr:Action_selection dbr:Drools dbr:Forward_chaining dbr:List_of_Java_frameworks dbr:Production_system_(computer_science) dbr:Rete dbr:Islamic_Golden_Age dbr:Jess_(programming_language) dbr:Schematron dbr:Business_rules_approach dbr:Business_rules_engine dbr:Microsoft_BizTalk_Server dbr:WME dbr:Event_condition_action dbr:Rete2 dbr:Rete_II dbr:Rete_network dbr:Rete_resolution_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Rete_algorithm |
