An Efficient Composite-Alphabet Transform for String Matching under a Restricted Alphabet Set
|
| Title | An Efficient Composite-Alphabet Transform for String Matching under a Restricted Alphabet Set |
| Authors | |
| Abstract | String matching is a problem of finding all occurrences of a short pattern on a relatively long reference string. While a number of methods have been presented, most published implementations assume several restrictions due to some practical issues. We focus on the restriction of the alphabet size, which is usually set to be 256 in many string matching libraries. When strings must be handled over an alphabet with a size greater than the limit provided by the given implementation, each character should be represented as a composite alphabet which involves combinations of two or more characters in the restricted alphabet set. In this case, potential false positives can sometimes occur, which may cause a decline in the performance in output-sensitive string matching systems, such as the FM-index. In this paper, we empirically compare various configurations of composite alphabets using FM-index, and show how they affect the performance in terms of the number of false positives and the searching time. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2013-07-01 |
| Source | Journal of Computers Vol 8, No 7 (2013): Special Issue: Advances in Internet Technologies and Applications |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |