US 2012/0233185 A1Published application

String matching in hardware using the fm-index

AssigneeThe Regents of the University of California

InventorsWalid A. Najjar, Edward Bryann C. Fernandez, Stefano Lonardi

Life of this patent

Estimating the term…

Loading patent…

Abstract

String matching is a ubiquitous problem that arises in a wide range of applications in computer science, e.g., packet routing, intrusion detection, web querying, and genome analysis. Due to its importance, dozens of algorithms and several data structures have been developed over the years. A recent breakthrough in this field is the FM-index, a data structure that synergistically combines the Burrows-Wheeler transform and the suffix array. In software, the FM-index allows searching (exact and approximate) in times comparable to the fastest known indices for large texts (suffix trees and suffix arrays), but has the additional advantage to be much more space-efficient than those indices. This disclosure discusses an FPGA-based hardware implementation of the FM-index for exact and approximate pattern matching.

Claims17

Dependent claims

A method using circuitry for processing a substring with respect to a text string, comprising:

storing in memory information for characters in a sorted BWT of a text string indicating a position of a first occurrence of each of those characters in the sorted Burrows-Wheeler transform (BWT) of the text string;
storing in memory, for characters of an allowable alphabet, an ordered set of values indicating the number of occurrences of that character in preceding characters of a BWT of the text string, with the order of the values in the order of the characters of the BWT of the text string;
initializing a signal indicating a first index to indicate a first position of the ordered set of values and initializing a signal indicating a second index to indicate a second position of the ordered set of values, the second position being different than the first position;
iteratively receiving a signal indicative of a new character of a specified substring, setting, by the circuitry, the signal indicating the first index to indicate a first new position, the first new position being based on a sum of a) the value of the ordered set of values currently indicated by the position of the first index for the new character and b) the information indicating the first occurrence of the new character in the sorted BWT of the text string, and setting, by the circuitry, the signal indicating the second index to indicate a second new position, the second new position being based on a sum of c) the value of the ordered set of values currently indicated by the position of the second index for the new character and d) the information indicating the first occurrence of the new character in the sorted BWT of the text string;
and
providing, by the circuitry, a signal indicating that the specified substring does not appear in the text string if, for any characters of the specified substring, the position of the first index relative to the position of the second index within the ordered set of values is reversed compared to the initial position of the first index relative to the initial position of the second index within the ordered sets of value or if the position of the first index and the position of the second index within the ordered sets of values is the same position.

3 more elements

Circuitry for processing a substring with respect to a text string, comprising:

a shift register configured to receive a information of a substring and sequentially provide as an output information of characters of the substring;
a memory block configured to store information of an I-table for a text string;
a plurality of memory blocks configured to store information of a C-table for an allowable alphabet for the text string;
a top multiplexer configured to select, using the output of the shift register, as an output one of first memory locations from each of the plurality of memory blocks storing information of the C-table;
a bottom multiplexer configured to select, using the output of the shift register, as an output one of second memory locations from each of the plurality of memory blocks storing information of the C-table;
a top summer configured to sum the output of the top multiplexer and a selected, using the output of the shift register, a memory location of the memory block storing information of the I-table, an output of the top summer indicating the first memory locations of the plurality of memory blocks storing information of the C-table;
and
a bottom summer configured to sum the output of the bottom multiplexer and the selected memory location of the memory block storing information of the I-table, an output of the bottom summer indicating the second memory locations of the plurality of memory blocks storing information of the C-table.

5 more elements

Circuitry for processing a substring with respect to a text string, comprising:

memory for storing information for characters in a sorted BWT of a text string indicating a position of a first occurrence of each of those characters in the sorted Burrows-Wheeler transform (BWT) of the text string;
memory for storing characters of an allowable alphabet, an ordered set of values indicating the number of occurrences of that character in preceding characters of a BWT of the text string, with the order of the values in the order of the characters of the BWT of the text string:
means for initializing a first index to indicate a first position of the ordered set of values and means for initializing a second index to indicate a second position of the ordered set of values, the second position being different than the first position;
means for iteratively receiving a signal indicative of a new character of a specified substring;
means for setting the first index to indicate a first new position, the first new position being based on a sum of the value of the ordered set of values currently indicated by the position of the first index for the new character and the information indicating the first occurrence of the new character in the sorted BWT of the text string;
and
means for setting the second index to indicate a second new position, the second new position being based on a sum of the value of the ordered set of values currently indicated by the position of the second index for the new character and the information indicating the first occurrence of the new character in the sorted BWT of the text string.

4 more elements

Dependencies are inferred from the claim text.