標題: | Complete Fix-Free Codes for the Statistical Dictionary-Based String Matching Problem |
作者: | Suri, Meer Rini, Stefano 電機工程學系 Department of Electrical and Computer Engineering |
關鍵字: | Dictionary-based string matching;Small vs small algorithm;Inverted index;Complete fix-free codes |
公開日期: | 1-一月-2019 |
摘要: | In the dictionary based string matching problem, the positions in which a short sequence of symbols, query, occurs in a longer sequence, source, have to be retrieved. To improve the query search efficiency, the source can be pre-processed to build an inverted index, that is a table storing positions of occurrences of certain substrings in the text. Given an inverted index, various algorithms can be utilized to retrieve the position of the query in the source. In the literature, motivated by text retrieval and web search applications, the small v/s small (SvS) algorithm is often considered for the case in which the substrings stored are k-gram codes, i.e. all possible substrings of length k. In [9] we have proposed a novel approach to the string matching problem by letting the strings generating the inverted index be a variable length code, i.e. posting code, to be optimally design for a given performance metric. Posting codes [9] generalize classic k-gram codes and enable new query retrieval algorithms with potentially lower complexity than the SvS algorithm. In this paper, we propose a new query retrieval algorithm, the forward-backward SvS (FB-SvS) algorithm which can be applied when the posting code is a complete fix-free code. The complexity of the FB-SvS algorithm for various fix-free codes is investigated and numerical experiments using the human DNA sequence as the source are presented. |
URI: | http://hdl.handle.net/11536/155065 |
ISBN: | 978-1-7281-4300-2 |
ISSN: | 1058-6393 |
期刊: | CONFERENCE RECORD OF THE 2019 FIFTY-THIRD ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS & COMPUTERS |
起始頁: | 1389 |
結束頁: | 1393 |
顯示於類別: | 會議論文 |