ساختارهای داده ای I / O کارآمد برای نمایه سازی غیر همپوشانی
خلاصه
کلید واژه ها
1. مقدمه و کارهای مرتبط
2. مقدمات و ساختارهای اساسی
3. نمایه سازی غیر همپوشانی - حافظه پنهان به طور کامل فراموش می شود
4- محدوده نمایه سازی غیر همپوشانی در مدل آگاه از حافظه پنهان
اعلامیه منافع رقابتی
تصدیق
منابع
Abstract
Keywords
1. Introduction and related work
2. Preliminaries and basic structures
3. Non-overlapping indexing - cache obliviously
4. Range non-overlapping indexing in cache-aware model
Declaration of Competing Interest
Acknowledgement
References
1. Introduction and Related Work
Text indexing is fundamental to many areas in Computer Science such as Information Retrieval, Bioinformatics, etc. The primary goal here is to preprocess a long text T[1, n] (given in advance), such that whenever a shorter pattern P[1, m] comes as query, all occ occurrences (or simply, starting positions) of P in T can be reported efficiently. Such queries can be answered in optimal O(m + occ) time using the classic Suffix tree data structure [1, 2]. It takes O(n) words of space. In this paper, we focus on a variation of the text indexing problem, known as the non-overlapping indexing, which is central to data compression [3, 4].
Problem 1 (Non-overlapping Indexing). Preprocess a text T[1, n] into a data structure that supports the following query: given a pattern P[1, m], report a largest set of occurrences of P in T (denote its size by nocc), such that any two (distinct) text positions in the output are separated by at least m characters.