Reverse search is a convenient method for enumerating structured objects, that can be used both to address theoretical issues and to solve data mining problems. This method has already been successfully developed to handle unordered trees. If the literature proposes solutions to enumerate singletons of trees, we study in this article a more general, higher combinatorial problem, the enumeration of sets of trees - forests. By compressing each forest into a Directed Acyclic Graph (DAG), we develop a reverse search like method to enumerate DAG compressing forests. Remarkably, we prove that these DAG are in bijection with the row-Fishburn matrices, a well-studied class of combinatorial objects. In a second step, we derive our forest enumeration to provide algorithms for tackling two related problems : (i) the enumeration of "subforests" of a forest, and (ii) the frequent "subforest" mining problem. All the methods presented in this article enumerate each item uniquely, up to isomorphism.
翻译:反向搜索是计算结构化物体的方便方法,可用于处理理论问题和数据挖掘问题。这种方法已经成功地开发出来,可以处理无序树木。如果文献提出单吨树木的计算方法,我们在本条中研究一个更一般、更高级的组合问题,即树木组群-森林。通过将每个森林压缩成一个定向环形图(DAG),我们开发了一个反向搜索方法,以罗列DAG压缩森林。值得注意的是,我们证明这些DAG与行-Fishburn矩阵是双向的,这是经过仔细研究的组合对象类别。第二步,我们从森林查点中找出方法,为处理两个相关问题提供算法:(一) 森林“子森林”的计数,和(二) 频繁的“子森林”采矿问题。本文章提出的所有方法都列出了每个独特项目,直至无形态学。