19 Jul Approximate pattern matching with bounded absolute error
Algorithmics is about solving problems formally. My algorithm belongs to text algorithms that relate to processing sequences of data. The problem itself is a variation of a classical problem in computer science called pattern matching. Its input data consists of two real number sequences – a pattern and a text, and the goal is to find contiguous parts of the text similar to the pattern. I decided to define similarity as maximum absolute error. This is a twist to the basic version where strict equality is required. It took me many weeks to find the core idea that made my method work. But it paid off – the algorithm is simple, effective and its code is short. It has applications in plagiarism detection, numerical data processing (for experiments or simulations), and musical analysis.
Jakub Krzysztof Bachurski