Flexible Text Searching

Exact and approximate string matching problem is a common and often repeated task in information retrieval and bioinformatics. As current free textual databases are growing almost exponentially with the time, the string matching problem is becoming more expensive in terms computational times. The authors believe that recent advances in parallel and distributed processing techniques are currently mature enough and can provide powerful computing means convenient for overcoming this string matching problem. In this book the authors present a short survey for well known sequential exact and approximate string searching algorithms. Further, the authors propose four text searching implementations onto general purpose parallel computer like a cluster of heterogeneous workstations using MPI message passing library. The first three parallel implementations are based on the static and dynamic master-worker methods. Further, the authors propose a hybrid parallel implementation that combines the advantages of static and dynamic parallel methods in order to reduce the load imbalance and communication overhead. Moreover, the authors present linear processor array architectures for flexible exact and approximate string matching. These architectures are based on parallel realisation of dynamic programming and non-deterministic finite automaton algorithms. The algorithms consist of two phases, i.e. pre-processing and searching. Then, starting from the data dependence graphs of the searching phase, parallel algorithms are derived, which can be realised directly onto special purpose processor array architectures for approximate string matching. Further, the pre-processing phase is also accommodated onto the same processor array designs. In addition, the proposed architectures support flexible patterns i.e. patterns with a "don't care" symbol, patterns with a complement symbol and patterns with a class symbol. Finally, this book proposes a generic design of a programmable array processor architecture for a wide variety of approximate string matching algorithms to gain high performance at low cost. Further, the authors describe the architecture of the array and the architecture of the cell in more detail in order to efficiently implement for both the pre-processing and searching phases of most string matching algorithms.

Table of Contents:
Preface; Introduction; Exact String Matching Algorithms; Approximate String Matching Algorithms; Parallel and Distributed Computing; MPI Implementations of Exact and Approximate String Matching; Description of Algorithms for Implementation; Data Dependence Graphs for Approximate String Matching Algorithms; Mapping Approximate String Matching Algorithms onto Processor Arrays; A Unified Array Processor Architecture; Comparison with Previous Hardware; Conclusion; Index.