کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875676 | 1441979 | 2018 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Encoding nearest larger values
ترجمه فارسی عنوان
رمزگذاری نزدیکترین مقادیر بزرگتر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ساختارهای داده، ساختار داده رمزگذاری، ساختارهای اطلاعات جزیی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j1,j2 such that A[j1]>A[i] and A[j2]>A[i] and |j1âi|=|j2âi|, then which index should be returned? For the tiebreaking rule where the rightmost (i.e., largest) index is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1.89997n+o(n) bits, and can answer queries in O(1) time. An alternative approach, based on forbidden patterns, achieves a very similar space bound for two tiebreaking rules (including the one where ties are broken to the right), and (for a more flexible tiebreaking rule) achieves 1.81211n+o(n) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1.62309nâÎ(1) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 97-115
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 97-115
نویسندگان
Michael Hoffmann, John Iacono, Patrick K. Nicholson, Rajeev Raman,