Generalized substring compression

Orgad Keller, Tsvi Kopelowitz, Shir Landau, Moshe Lewenstein

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


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) and OC log j−i C 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]
שפה מקוריתאנגלית
כותר פרסום המארחAnnual Symposium on Combinatorial Pattern Matching
מספר עמודים13
סטטוס פרסוםפורסם - 2009
אירוע20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009 - Lille, צרפת
משך הזמן: 22 יוני 200924 יוני 2009

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך5577 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Generalized substring compression'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי