Journal
PATTERN RECOGNITION
Volume 34, Issue 1, Pages 127-137Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/S0031-3203(99)00199-5
Keywords
dynamic programming; edit distance; pattern matching; trees; computational biology
Ask authors/readers for more resources
The problem of finding this similar consensus (also known as the largest approximately common substructures) of two trees arises in many pattern recognition applications. This paper presents a dynamic programming algorithm to solve the problem based on the distance measure originated from Tanaka and Tanaka. The algorithm runs as fast as the best-known algorithm for comparing two trees using Tanaka's distance measure when the allowed distance between the common substructures is a constant independent of the input trees. In addition, we establish a hierarchy among Tanaka's distance measure and three other edit-based distance measures published in the literature. (C) 2000 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available