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.

Category: COMPUTING Country: POLAND Year: 2021

 

Jakub Krzysztof Bachurski