  Accelerating inexact string matching procedures is of utmost importance when
dealing with practical applications where huge amount of data must be processed
in real time, as usual in bioinformatics or cybersecurity. Inexact matching
procedures can yield multiple shadow hits, which must be filtered, according to
some criterion, to obtain a concise and meaningful list of occurrences. The
filtering procedures are often computationally demanding and are performed
offline in a post-processing phase. This paper introduces a novel algorithm for
Online Approximate String Matching (OASM) able to filter shadow hits on the
fly, according to general purpose priority rules that greedily assign
priorities to overlapping hits. An FPGA hardware implementation of OASM is
proposed and compared with a serial software version. Even when implemented on
entry level FPGAs, the proposed procedure can reach a high degree of
parallelism and superior performance in time compared to the software
implementation, while keeping low the usage of logic elements. This makes the
developed architecture very competitive in terms of both performance and cost
of the overall computing system.
