Simple, compact and robust approximate string dictionary

This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary D of d strings of total length n over an alphabet of size σ. Given a bound k and a pattern x of length m, a query has to return all the strings of the dictionary which are at edit distance at most k from x, where the edit distance between two strings x and y is defined as the minimum-cost sequence of edit operations that transform x into y  . 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 2≤k