A set of strings, called a string dictionary, is a basic string data structure. The most primitive query, where one seeks the existence of a pattern in the dictionary, is called a lookup query. Approximate lookup queries, i.e., to lookup the existence of a pattern with a bounded number of errors, is a fundamental string problem. Several data structures have been proposed to do so efficiently. Almost all solutions consider a single error, as will this result. Lately, Belazzougui and Venturini (CPM 2013) raised the question whether one can construct efficient indexes that support lookup queries with one error in optimal query time, that is, O(|p|/ω + occ), where p is the query, ω the machine word-size, and occ the number of occurrences. Specifically, for the problem of one mismatch and constant alphabet size, we obtain optimal query time. For a dictionary of d strings our proposed index uses O(ωd log~(1+∈) d) additional bit space (beyond the space required to access the dictionary data, which can be maintained in compressed form). Our results are parameterized for a space-time tradeoff. We propose more results for the case of lookup queries with one insertion/deletion on dictionaries over a constant sized alphabet. These results are especially effective for large patterns.
展开▼
机译：一组字符串（称为字符串字典）是基本的字符串数据结构。一种最原始的查询，即查找字典中某个模式是否存在的查询，称为查找查询。近似查找查询，即查找存在一定数量错误的模式，是一个基本的字符串问题。已经提出了几种数据结构来有效地做到这一点。几乎所有解决方案都将考虑单个错误，结果也会如此。最近，Belazzougui和Venturini（CPM，2013年）提出了一个问题，即是否可以构建有效的索引来支持在最佳查询时间内出现一个错误的查找查询，即O（| p | /ω+ occ），其中p是查询， ω机器字长，并且occ出现次数。具体地，对于一个不匹配和恒定的字母大小的问题，我们获得最佳的查询时间。对于d字符串字典，我们建议的索引使用O（ωdlog〜（1 +∈）d）附加位空间（除了访问字典数据所需的空间之外，可以以压缩形式对其进行维护）。我们的结果被参数化为时空权衡。对于在恒定大小的字母上对字典进行一次插入/删除的查找查询，我们提出了更多结果。这些结果对于大型图案特别有效。
展开▼
