Approximate Parameterize Matching的近似参数化匹配.pptVIP

2 Dimensional Parameterized Matching Carmit Hazay Moshe Lewenstein Dekel Tsur CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 CPM 2005 Parameterized Matching Input: two strings s and t, |s|=|t|, over alphabets ∑s and ∑t. s parameterize matches t: if bijection : ∑s ∑t , such that (s) = t. Parameterized Matching Input: Two strings T, P; |T|=n, |P|=m. Output: All text locations i, such that (P)=Ti …Ti+m-1. 2D Parameterized Matching Input: Text T and pattern P; |T|=n*n, |P|=m*m. Output: All text locations (i,j), such that (P)=Ti,j …Ti+m-1,j+m-1. Example- Parameterized Matching History Introduced by Brenda Baker [Baker93]. Others: [AFM94], [Bak95], [Bak97]. Two Dimensions: [AACLP03][This work]. Used in scaled matching [ABL99]. Periodicity of parameterized matching [ApostolicoGiancarlo]. Approximate parameterized matching [AEL], [HLS04]. Na?ve Algorithm For every location (i,j) of text Check if P parameterized matches at (i,j):  1. For each a ? alphabet of P, check if all a’s of P align with same character 2. For each b ? alphabet of T, check if all b’s of T align with same character Na?ve Algorithm Time Analysis: If done properly – O(n2m2) Mismatch pairs Pair of locations such that the characters disagree parameterized. Example, 1D Encoding Encode every text location by its predecessor location. 1D Encoding Two p-matching strings have the same encoded texts. 1D Encoding Hence, in order to check whether two strings p-match, enough to compare their encoded strings. Reduction to exact matching problem. 2D Mismatch Pairs Same as 1D mismatch pairs, but with 2D strings. Example: 2D Encoding First idea, Encode the linearization of text and pattern. 2D Encoding First idea, Encode the linearization of text and pattern. 2D Encoding First idea, Encode the linearization of