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（2013年CPM）提出了一个问题，无论是可以构建有效的索引，支持在最佳查询时间内使用一个错误支持查找查询，即（| P | /ω+ OCC），其中P是查询， ω机器字大小，而OCC的出现次数。具体地，对于一个不匹配和恒定字母大小的问题，我们获得最佳查询时间。对于D字符串字典，我们所提出的索引使用O（ωdlog〜（1 +∈）d）附加位空间（超出访问所述字典数据所需的空间，可以以压缩形式维护）。我们的结果是用于时空权衡的参数化。我们为在恒定大小的字母表中的字体上的一个插入/删除有一个插入/删除的查询的情况下提出了更多结果。这些结果对于大型模式特别有效。
展开▼
