کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434351 689720 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generalized substring compression
ترجمه فارسی عنوان
فشرده سازی زیرمجموعه عمومی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In substring compression one is given a text to preprocess so that, upon request, a compressed substring is returned. Generalized substring compression is the same with the following twist. The queries contain an additional context substring (or a collection of context substrings) and the answers are the substring in compressed format, where the context substring is used to make the compression more efficient.We focus our attention on generalized substring compression and present the first non-trivial correct algorithm for this problem. Inherent to our algorithm is a new method for finding the bounded longest common prefix of substrings, which may be of independent interest. In addition, we propose an efficient algorithm for substring compression which makes use of range successor queries.We present several tradeoffs for both problems. For compressing the substring S[i..j] (possibly with the substring S[α..β] as a context), the best query times we achieve are O(C)O(C) and O(Clog(j−iC)) for substring compression query and generalized substring compression query, respectively, where C is the number of phrases encoded.A preliminary version of this paper has been presented in [21].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 525, 13 March 2014, Pages 42–54
نویسندگان
, , , ,