This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary @math of @math strings of total length @math over an alphabet of size @math . Given a bound @math and a pattern @math of length @math , a query has to return all the strings of the dictionary which are at edit distance at most @math from @math , where the edit distance between two strings @math and @math is defined as the minimum-cost sequence of edit operations that transform @math into @math . The cost of a sequence of operations is defined as the sum of the costs of the operations involved in the sequence. In this paper, we assume that each of these operations has unit cost and consider only three operations: deletion of one character, insertion of one character and substitution of a character by another. We present a practical implementation of the data structure we recently proposed and which works only for one error. We extend the scheme to @math . Our implementation has many desirable properties: it has a very fast and space-efficient building algorithm. The dictionary data structure is compact and has fast and robust query time. Finally our data structure is simple to implement as it only uses basic techniques from the literature, mainly hashing (linear probing and hash signatures) and succinct data structures (bitvectors supporting rank queries).
Our algorithm is in a sense similar to the FASTSS algorithm introduced in @cite_0 . In this algorithm, a hash table stores all the strings that can be obtained by deleting (at most) @math characters from any string in the dictionary. Then at query time the hash table is queried for all the strings that can be obtained by deleting (at most) @math characters from the string. Then, it can be proved that all the strings at edit distance at most @math will be contained in the resulting set and the remaining task will be to test all the candidates. A clever improvement to FASTSS was achieved in @cite_4 , where instead of storing all the strings obtained by deleting one character, the dictionary stores pointers to the strings. Following this, @cite_23 compresses the strings in a different way: instead of storing the strings, only deleted characters along with their positions are stored. Space-efficient perfect hashing methods @cite_6 are then used to store the lists of positions and characters.
@cite_0 @cite_4 @cite_6 @cite_23
2162031302 2949858479 77954401
We present experimental analysis of approximate search algorithms that involve indexing of deletion neighborhoods. These methods require huge indices whose sizes grow exponentially with respect to the maximum allowable number of errors k. Despite extraordinary space requirements, the super-linear indices are of great interest, because they provide some of the shortest retrieval times. A straightforward implementation that creates a hash index directly over residual strings (obtained by deletions from dictionary words) is not space efficient. Rather than memorizing complete residual strings, we record only deleted characters and their respective positions. These data are indexed using a perfect hash function computed for a set of residual dictionary strings [2]. We carry out an experimental evaluation of this approach against several well-known benchmarks (including FastSS, which stores residual strings directly [3]). Experiments show that our implementation has a comparable or superior performance to that of the fastest benchmarks. At the same time, our implementation requires 4-8 times less space as compared to FastSS. Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string @math of length @math under @math deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string @math ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of @math -run strings @math , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every @math , we present @math -run strings with the minimum (respectively maximum) number of subsequences under any @math deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time. Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. Over fifty years of usage have produced many variants and implementations to overcome some of their limitations. We explore new succinct representations of path-decomposed tries and experimentally evaluate the corresponding reduction in space usage and memory latency, comparing with the state of the art. We study two cases of applications: (1) a compressed dictionary for (compressed) strings, and (2) a monotone minimal perfect hash for strings that preserves their lexicographic order. For (1), we obtain data structures that outperform other state-of-the-art compressed dictionaries in space efficiency, while obtaining predictable query times that are competitive with data structures preferred by the practitioners. In (2), our tries perform several times faster than other trie-based monotone perfect hash functions, while occupying nearly the same space. The edit distance between two character strings can be defined as the minimum cost of a sequence of editing operations which transforms one string into the other. The operations we admit are deleting, inserting and replacing one symbol at a time, with possibly different costs for each of these operations. The problem of finding the longest common subsequence of two strings is a special case of the problem of computing edit distances. We describe an algorithm for computing the edit distance between two strings of length n and m, n  m, which requires O(n  max(1, mlog n)) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite. These conditions are necessary for the algorithm to achieve the time bound.