a dictionary for approximate string search and longest prefix search
In this paper we propose a dictionary data structure for string search with errors where the query string may didiffer from the expected matching string by a few edits. This data structure can also be used to find the database string with the longest common prefix with few errors. Specifically, with a database of n random strings, each of length of O ( m ), we show how to perform string search on a query string that differs from its closest match by k edits using a data structure of linear size and query time equal to  (log n 2 log n k log a 2 m over 2 m ). This means that if k < m over log a 2 m log n , then the query time is  (1). This is of significant in practice as there are several applications where k is small relative to m . Our approach converts strings into bit vectors so that similar strings can map to similar bit vectors with small hamming distance. A simple reduction can be used to obtain similar results for approximate longest prefix search.
embeddings hamming space