A comparison of BWT approaches to string pattern matching

    Authors

    A. Firth; T. Bell; A. Mukherjee;D. Adjeroh

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Softw.-Pract. Exp.

    Keywords

    compressed pattern matching; suffix arrays; binary search; q-grams; FM-index; BWT; LENGTH CODED STRINGS; ALGORITHM; Computer Science, Software Engineering

    Abstract

    Recently a number of algorithms have been developed to search files compressed with the Burrows-Wheeler Transform (BWT) without the need for full decompression first. This allows the storage requirement of data to be reduced through the exceptionally good compression offered by BWT, while allowing fast access to the information for searching by taking advantage of the sorted nature of BWT files. We provide a detailed description of five of these algorithms: BWT-based Boyer-Moore, Binary Search, Suffix Arrays, q-grams and the FM-index, and also present results from a set of extensive experiments that were performed to evaluate and compare the algorithms. Furthermore, we introduce a technique to improve the search times of Binary Search, Suffix Arrays and q-grams by 22% on average, as well as reduce the memory requirement of the latter two by 40% and 31%, respectively. Our results indicate that, while the compressed files of the FM-index are larger than those of the other approaches, it is able to perform searches with considerably less memory. Additionally, when only counting the occurrences of a pattern, or when locating the positions of a small number of matches, it is the fastest algorithm. For larger searches, Binary Search provides the fastest results. Comparative results with non-BWT based search methods are also included. Copyright (c) 2005 John Wiley & Sons, Ltd.

    Journal Title

    Software-Practice & Experience

    Volume

    35

    Issue/Number

    13

    Publication Date

    1-1-2005

    Document Type

    Article

    Language

    English

    First Page

    1217

    Last Page

    1258

    WOS Identifier

    WOS:000232927300001

    ISSN

    0038-0644

    Share

    COinS