Heuristic Algorithm for Generalized Function Matching

Abstract

The problem of generalized function matching can be defined as follows: given a pattern $p=p_1\cdots p_m$ and a text $t=t_1\cdots t_n$, find a mapping $f:{\Sigma }_p\to {\Sigma }_t^{\ast }$ and all text locations $i$ such that $f(p_1)f(p_2)\cdots f(p_m)=t_i\cdots t_j$, a substring of $t$. By modifying the restrictions of the matching function $f$, one can obtain different matching problems, many of which have important applications. When $f:{\Sigma }_p\to {\Sigma }_t$ we are faced with problems found in the well-established field of combinatorial pattern matching. If the single character constraint is lifted and $f:{\Sigma }_p\to {\Sigma }_t^{\ast }$, we obtain generalized function matching as introduced by Amir and Nor (JDA 2007). If we further constrain $f$ to be injective, then we arrive at generalized parametrized matching as defined by Clifford et al. (SPIRE 2009). There are a number of important applications for pattern matching in computational biology, text editors and data compression, to name a few. Therefore, many efficient algorithms have been developed for a wide variety of specific problems including finding tandem repeats in DNA sequences, optimizing embedded systems by reusing code etc. In this work we present a heuristic algorithm illustrating a practical approach to tackling a variant of generalized function matching where $f:{\Sigma }_p\to {\Sigma }_t^{+}$ and demonstrate its performance on human-produced text as well as random strings.

The paper was accepted for publication in the proceedings of KES 2019 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems