Flexible text searching /

作     者：Michailidis Panagiotis D.Panagiotis D. Michailidis and Konstantinos G. Margaritis. Margaritis Konstantinos G. 

I S B N：(纸本) 9781606922613 

出 版 社：Nova Science Publishers 

出 版 年：2008年

页      数：viii, 72 p. :页

主 题 词：Computer algorithms..Database searching..Electronic data processing.Parallel processing (Electronic computers) 

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

摘      要：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 ***, 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 ***, 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