标题: | 一个简单型的树结构模组比对演算法 A Simple Tree Pattern-Matching Algorithm |
作者: | 吕晓慈 Hsiao-Tzu Lu 杨武 Wuu Yang 资讯科学与工程研究所 |
关键字: | 演算法;模组比对;树结构模组比对;树取代系统;algorithm;pattern matching;tree pattern matching;tree replacement system |
公开日期: | 1999 |
摘要: | 树结构模组比对在很多程式任务里都扮演着一个极重要的步骤,它也经常发生在树取代系统的内容中。我们提出了一个新的演算法来解决树结构模组比对的问题。这个演算法可视为是 Knuth-Morris-Pratt 字串比对演算法延伸至树结构模组比对的问题。在这个新的演算法中,主题树中的每个点所需要被拜访的次数被其阶级所限定。因此我们的演算法在比对时间上的时间复杂度为O(n log n),其中 n 为主题树的点的数目。最糟的情形会发生在,当主题树中的点的内容有很大的部分都和模组的根内容相等时。另外我们也需要一个额外的模组事前处理步骤,其时间复杂度为O(m log m),其中 m 为模组的点的数目。在空间上,我们利用间接法来达到解省空间的目的,使得我们的时间复杂度可以降至O(n+m)。 Tree pattern matching occurs as a crucial step in a number of programming tasks. It occurs frequently in the context of tree replacement systems. And the tree replacement approach is very convenient for producing interpreters for existing languages such as LISP and LUCID or for implementing experimental languages. We propose a new algorithm to solve the tree pattern-matching problem. The algorithm may be viewed as an extension of the Knuth-Morris-Pratt string-matching algorithm to the tree pattern-matching problem. In the new algorithm, the times of each node in the subject tree needs to be traversed is bounded by their level. Therefore, the time complexity of the simple tree pattern-matching is bounded by O(n×log n), where n is the number of nodes in the subject tree. The worst case occurs when the frequency of the same content of the pattern's root in the subject tree is high. But we need an extra preprocessing time of the pattern. The time complexity of the pattern preprocessing is bounded by O(m×log m), where m is the number of nodes in the pattern. The worst case occurs similarly when the frequency of the same content of the root in the pattern is high. By using indirection, the space complexity will be down to O(n+m). |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT880394077 http://hdl.handle.net/11536/65577 |
显示于类别: | Thesis |