Flexible Text Searching
Seiten
2009
Nova Science Publishers Inc (Verlag)
978-1-60692-261-3 (ISBN)
Nova Science Publishers Inc (Verlag)
978-1-60692-261-3 (ISBN)
Presents a short survey for well known sequential exact and approximate string searching algorithms. This title proposes a hybrid parallel implementation that combines the advantages of static and dynamic parallel methods in order to reduce the load imbalance and communication overhead.
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.
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.
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.
| Erscheint lt. Verlag | 18.3.2009 |
|---|---|
| Zusatzinfo | Illustrations |
| Verlagsort | New York |
| Sprache | englisch |
| Maße | 260 x 180 mm |
| Gewicht | 204 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| ISBN-10 | 1-60692-261-0 / 1606922610 |
| ISBN-13 | 978-1-60692-261-3 / 9781606922613 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2024)
Lehmanns Media (Verlag)
CHF 55,95
IT zum Anfassen für alle von 9 bis 99 – vom Navi bis Social Media
Buch | Softcover (2021)
Springer (Verlag)
CHF 41,95
Interlingua zur Gewährleistung semantischer Interoperabilität in der …
Buch | Softcover (2023)
Springer Fachmedien (Verlag)
CHF 46,15
