2F3-04 Finding a Common Structure based on Approximate Tree Matching ×1 *2 *3 Tetsuji Kuboyama Kilho Shin Tetsuhiro Miyahara *1 Center for Collaborative Research, University of Tokyo *2 Research Center for Advanced Science and Technology, University of Tokyo *3 Faculty of Information Sciences, Hiroshima City University Information extraction from semistructured data such as HTML documents gains importance with the growth of the Web. This paper proposes an efficient method for discovering a common tree structure from multiple trees based on the bottom-up subtree isomorphism algorithm by Valiente.  The aim of this work is to extract Web contents from a set of HTML documents which are generated from a common template, but include a number of grammatical mistakes in HTML, redundant or missing fragments introduced by manual editing. 1. HTML HTML 2 1 Web HTML [1] Web 2 Valiente 3 4. 2 2. 2.1 2 (strict partial order) V <<
).
x < y XML HTML
v
T Web . ● 3 ), 1:     : T 1 T 2 E(T) = {(x,y) ∈ V(T) × V(T)|x < T y ∧̸≡z ∈ V (T) [ x < z < y]} x x ≤ y y x < y y x x 2 ch( x ) ch( x ) T {y|(y,x) E E(T)} p(x) T t, T(x) 3. 2 M | T | M|2 = {y|(x,y) ∈ M} T = (V, <) V'こV 2. y ∈ V’ y ≤ x V' (common ancestor) V' x (least common ancestor)ツlca(V') lca({x,y}) y M|1 = {x|(x,y) ∈ M} x ∈ V V' x ） (tree map- 2 M ∀(x 1 , x 2 ), (y 1 , y 2 ) ∈ M  [x 1 ≤ y 1 ⇔ y 1 ⇔ x 2 ≤ y 2 ] Zhang M 4 (Zhang [6]). (constrained mapping) ∀(x1, x2), (y1, y2), (z1, z2) ∈ M [z1 < x1 ～ y1 ⇔ z2 < x2 ～ y2] 2 1 ( [4]). M ∀(x1, x2), (y1, y2), (z1, z2) ∈ M [x 1 ～ y 1 ＜ x 1 ～ z 1 ⇒ y 2 ～ z 2 ＝ z 2 ～ z 2 ] .
(less-constrained)
5 (Valiente [10]). M ∀(x1,x2) ∈ M [|T(x1)| = |T(x2)|  ∧ y1 ∈ V(T1(x1)) ⇒ y2 ∈ V(T2(x2)) s.t. (y1,y2) ∈ M] Valiente [10] Valiente [10] [7] [4] 1 2 y ≤ x T 2 ping) [4] 3 ( T 1 ). V(T1) × V(T2) T 2 2. G T F F F 4 DAG F = {T1, ... , Tn} G   u u v x ∈ [u] y ∈ [ʊ] x T F y | F | DAG F F DAG 2.2 3.1 1 (DAG) [ʊ] v 2 O(| F |) F 3.2 F F 6. 1. G F v F 3 F U
F = {T1, . . . ,Tn}
DAG
procedure compact( F : trees, G : DAG, K : mapping) ( K is a mapping from nodes in F to nodes in G ) let L be an empty hash of node labels to nodes of G foreach leaf label l in F do add a new node v to G label[v] ← l; L[l] = v end foreach let Q be a queue containing all leaf nodes in F foreach node v in F do rest[v]← number of children of v end foreach while Q is empty do dequeue node v from Q if v is leaf then K [v] ← L [label[v]] else foreach node w in G from the latest added do if v and w have the same label, height, and number of children and {K[u]|u is a child of node v} = {u|u is a child of node w} then K [v] ← w else add a new node w to G K[v] ← w; label[w] ← label[v] end if end foreach end if if node v is not the root of a tree in F then rest[parent[v]]== enqueue parent[v] into Q if rest[parent[v]] = 0 end if end while DAG G for F={ T 1 , T 2 } T 1 T 2 ; 3: F = {T 1 , T 2 } Valiente 1 DAG 2: F = {T1,...,Tn} Proof. M* 3.3 XML HTML 7. T 1 M M* = T 2 {(x～y, x～y)|(x, x), (y, y) ∈ M} ∪ {(r(Ti), r(Ti)} M* Valiente Valiente [10] [1] D. C. Reis, P. B. Golgher, A. S. Silva, and A. H. F. Laender.  Automatic web news extraction using tree edit distance. In WWW2004 , pages 502–511, 2004. G : 5 3. M M* M M *口M M' ⊂ M M' M'* 6 2 
 
 T 1 T2 4. T 1 T 2 x, y ∈ V (T1) T1(x ～y)しWeb 1 2. F = {T1, . . . ,Tn} procedure mapping( F : trees, G : DAG, K : mapping, M 2 3 : mapping) for i = 1 to n do foreach node v in T i in reverse < T i -order do for j = i + 1 to n do if M i j [v] is undefined then w ← the root of T j foreach node u in T i with K [ u ] = K [ v ] do w ← u if u is the left to w end foreach if K[v] = K[w] then M ij ← M ij U {(x, y)|corresponding pair of nodes x ∈ V(T i ( v )) and y ∈ V(T i ( w ))} end if end if end for end foreach end for 4: F = {T1,...,Tn} [2] J.T.-L. Wang and K. Zhang. Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34:127–137, 2001. [3] G. Valiente. Tree edit distance and common subtrees. Technical Report LSI-02-20-R, Universitat Politecnica de Catalunya, Barcelona, Spain, 2002. [4] T. Kuboyama, S. Kilho, and T. Miyahara. A theoreti- cal analysis of tree edit distance measures. Information Processing Society of Japan, Transactions on Mathe- matical Modeling and Its Applications. to appear. [5] K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related prob- lems. SIAM Journal on Computing, 18(6):1245–1262, December 1989. [6] K. Zhang and T. Jiang.  Some max snp-hard results concerning unordered labeled trees. Information Pro- cessing Letters, 49:249–254, 1994. [7] T. Jiang, L. Wang, and K. Zhang. Alignment of trees — an alternative to tree edit.  Theoretical Computer Science, 143:137–148, 1995. [8] C. L. Lu, Z.-Y. Su, and G. Y. Tang. A new measure of edit distance between labeled trees. LNCS , 2108:pp. 338–348, 2001. COCOON 2001. [9] K. Zhang. A constrained edit distance between un- ordered labeled trees. Algorithmica , 15:205–222, 1996. [10] G. Valiente. An efficient bottom-up distance between trees. In Proc. 8th Int. Symposium on String Process- ing and Information Retrieval, pages 212–219. IEEE Computer Science Press, 2001.