Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search

Details Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search

2003-06-11

arxiv.org/abs/cs/0306046v1

Computer Science

Data Structures and Algorithms

Scientific paper

We propose a very simple randomised data structure that stores an approximation from above of a lattice-valued function. Computing the function value requires a constant number of steps, and the error probability can be balanced with space usage, much like in Bloom filters. The structure is particularly well suited for functions that are bottom on most of their domain. We then show how to use our methods to store in a compact way the bad-character shift function for variants of the Boyer-Moore text search algorithms. As a result, we obtain practical implementations of these algorithms that can be used with large alphabets, such as Unicode collation elements, with a small setup time. The ideas described in this paper have been implemented as free software under the GNU General Public License within the MG4J project (http://mg4j.dsi.unimi.it/).

Affiliated with

Also associated with

No associations

Rating

Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-458342