A Tree-Matching Algorithm Based on Node Splitting and Merging

IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 March 1984

S. Y. Lu

DOI10.1109/tpami.1984.4767511

Source URL

Citations45

SJR quartileQ1

SJR score3.91

SNIP5.99

Abstract

An algorithm that computes the best matching of two trees is described. The degree of mismatch, i.e., the distance, is measured in terms of the number of node splitting and merging operations required. The proposed tree distance is a more appropriate measurement of structural defonnation than the tree distance measure in terms of the number of insertions, deletions, and substitutions of tree nodes, as defined in previous studies. An algorithm that uses a divide-and-conquer strategy is presented. The analysis shows that the time complexity is O(NM2) where N and Al are the number of nodes of the two trees, respectively. The algorithm has been implemented on a VAX 11/780.

Keywords

Computer Science

The Design and Analysis of Computer Algorithms

9,456 Citations1974Alfred V. Aho, John E. Hopcroft

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.

Journal of the ACMThe String-to-String Correction Problem

3,063 Citations1974Robert A. Wagner, Michael J. Fischer

An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.

View PDF

Nuclear Science and EngineeringThe Art of Computer Programming

2,298 Citations1968W.J. Worlton

Journal of the ACMThe Tree-to-Tree Correction Problem

856 Citations1979Kuo‐Chung Tai

An algorithm is presented which solves the problem of determining the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T'.

View PDF

IEEE Transactions on Systems Man and CyberneticsA Sentence-to-Sentence Clustering Procedure for Pattern Analysis

233 Citations1978Shin-Yee Lu, King Sun Fu

A weighted distance between two strings is defined and its probabilistic interpretation given and a clustering procedure on a sentence-to-sentence basis is proposed.

IEEE Transactions on Information TheoryDecoding for channels with insertions, deletions, and substitutions with applications to speech recognition

194 Citations1975L.R. Bahl, F. Jelinek

A model for channels in which an input sequence can produce output sequences of varying length is described and a stack decoding algorithm for decoding on such channels is presented.

IEEE Transactions on Pattern Analysis and Machine IntelligenceA Tree-to-Tree Distance and Its Application to Cluster Analysis

121 Citations1979Shin-Yee Lu

An algorithm that generates the distance for any two trees is presented and cluster analysis for patterns represented by tree structures is discussed, using a tree-to-tree distance to measure the similarity between patterns.

Communications of the ACMA syntactic algorithm for peak detection in waveforms with applications to cardiography

96 Citations1975Steven L. Horowitz

Peaks in a digitized waveform are detected by an algorithm incorporating piecewise linear approximation and tabular parsing techniques, of sufficient speed to allow on-line real-time processing.

View PDF

IEEE Transactions on ComputersRepresentation of Random Waveforms by Relational Trees

74 Citations1976Ehrich, Foith

In a number of applications of image processing, much information about objects or textures in the image can be obtained by sequential analysis of individual scan lines.

Pattern RecognitionA subgraph isomorphism algorithm using resolution

24 Citations1981J. K. Cheng, Thomas S. Huang

An efficient algorithm for subgraph isomorphism that combines tree search with relaxation by using resolution is presented and can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements.