一個簡單型的樹結構模組比對演算法

Abstract

樹結構模組比對在很多程式任務裡都扮演著一個極重要的步驟，它也經常發生在樹取代系統的內容中。我們提出了一個新的演算法來解決樹結構模組比對的問題。這個演算法可視為是 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).