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

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