检索结果-内蒙古大学图书馆

2012 International Conference on Future Information Technology and Management Science & Engineering(FITMSE 2012)

作者： Qiaoxia Zhang 1, Zhijie Wu 2, Yongkang Xu 2, Xin Mao 3, Ran Yu 3 and Songfeng Lu 4 1 Wuhan Power Supply Design Institute Limited Company, Wuhan 430032, China 2 Institute of Computer Application Technology, China Academy of Engineering Physics, Mianyang, Sichuan 621900, China 3 Wuhan Qiaokou Power Supply Company, Wuhan 430034, China 4 School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

String matching is an important class of string algorithms that try to find a place where one or several patterns are found within a larger string or text. Fast search algorithms are based on preprocessing of the text. After building a substring index, the occurrences of a pattern can be found quickly. The existing index methods need either larger space occupancy or more running time. In this paper, by using Burrows-Wheeler Transform, a new string matching algorithm based on compressed suffix array is presented. The experiment results show that the space occupancy of the proposed method is optimal, while the searching time is also desirable.

关键词： String Matching Compressed suffix array Burrows-Wheeler Transform suffix array

来源：评论

学校读者我要写书评

暂无评论

A Complete suffix array-based String Match Search Algorithm of Sliding Windows

A Complete Suffix Array-based String Match Search Algorithm ...

引用

2012 Fifth International Symposium on Computational Intelligence and Design [第五届计算智能与设计国际会议 ISCID 2012]

作者： Lu Wang Kun Huang Jian Zhang Jin Yao China ship development and design center 268 Zhang Zhidong Road Wuchang District Wuhan 430064 China

String match has been widely used in such diverse areas as data compression, search engine, information retrieval. Due to its simplicity and high-efficient space, suffix array is used to improve the efficiency of string match. However, the existing suffix arraybased algorithms will rebuild suffix array after window slides every time. According to the properties of sliding window, the concept of completed suffix array and a new sliding window search algorithm for string matching using the orderly construction of suffix arrays are proposed. Thus, it is unnecessary that suffix array is rebuilt every time. Both theoretical analysis and experimental results show the improved efficiency of the proposed algorithm.

关键词： string match suffix array sliding window completed suffix array

来源：评论

学校读者我要写书评

暂无评论

Fast parallel skew and prefix-doubling suffix array construction on the GPU

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2016年第12期28卷 3466-3484页

作者： Wang, Leyuan Baxter, Sean Owens, John D. Univ Calif Davis Davis CA 95616 USA DE Shaw Res New York NY USA

suffix arrays are fundamental full-text index data structures of importance to a broad spectrum of applications in such fields as bioinformatics, Burrows-Wheeler transform-based lossless data compression, and information retrieval. In this work, we propose and implement two massively parallel approaches on the graphics processing unit (GPU) based on two classes of suffix array construction algorithms. The first, parallel skew, makes algorithmic improvements to the previous work of Deo and Keely to achieve a speedup of 1.45x over their work. The second, a hybrid skew and prefix-doubling implementation, is the first of its kind on the GPU and achieves a speedup of 2.3-4.4x over Osipov's prefix-doubling and 2.4-7.9x over our skew implementation on large datasets. Our implementations rely on two efficient parallel primitives, a merge and a segmented sort. We theoretically analyze the two formulations of suffix array construction algorithms and show performance comparisons on a large variety of practical inputs. We conclude that, with the novel use of our efficient segmented sort, prefix-doubling is more competitive than skew on the GPU. We also demonstrate the effectiveness of our methods in our implementations of the Burrows-Wheeler transform and in a parallel full-text, minute-space-index for pattern searching. Copyright (C) 2016 John Wiley & Sons, Ltd.

关键词： suffix array parallel GPU skew prefix-doubling segmented sort

来源：评论

学校读者我要写书评

暂无评论

A Qualitative Performance Comparison and Analysis of suffix array,FM-index and Compressed suffix array

A Qualitative Performance Comparison and Analysis of Suffix ...

引用

2012 International Conference on Future Information Technology and Management Science & Engineering(FITMSE 2012)

作者： Jichuan Wu 1, Xin Mao 2, and Songfeng Lu 3, 1 Department of Mechanical Engineering, National University of Singapore,Singapore 2 Wuhan Qiaokou Power Supply Company, Wuhan 430034, China 3 School of Computer Science, Huazhong University of Science&Technology, Wuhan 430074, China

suffix array is an index structure widely used in string matching and data compression which has the advantages of fast data retrieval and high compatibility in many areas of applications. Nevertheless, the memory space consumption for the execution of the algorithm is inefficient compare with conventional methods. To overcome this problem, FM-index and Compressed suffix array (CSA) were proposed. In this paper, the constructor methods of the three index structures are comprehensively described in order to evaluate their specific characteristics in the corresponding applicable field. Performances of these index structures are analyzed through the designed experiments, and qualitative conclusions are drawn based on the measured results.

关键词： String Matching Compressed suffix array FM-index suffix array

来源：评论

学校读者我要写书评

暂无评论

Sparse suffix and LCP array: Simple, Direct, Small, and Fast 16th

Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Ayad, Lorraine A. K. Loukides, Grigorios Pissis, Solon P. Verbeek, Hilde Brunel Univ London London England Kings Coll London London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands

ISBN: (纸本)9783031555978;9783031555985

Sparse suffix sorting is the problem of sorting b = o(n) suffixes of a string of length n. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures;direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure;fast in the sense that they run in O( n log b) time, in the worst case, or in O( n) time, when the total number of suffixes with an LCP value greater than 2(left perpendicularlog n/bright perpendicular+1) - 1 is in O(b/ log b), matching the time of optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017;Birenzwige et al., SODA 2020];and small in the sense that they can be implemented using only 8b + o(b) machine words. We also show that our second algorithm can be trivially amended to work in O(n) time for any uniformly random string. Our algorithms are non-trivial space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in O(n log b) time [STACS 2014].

关键词： suffix array LCP array suffix sorting sparse suffix sorting

来源：评论

学校读者我要写书评

暂无评论

Linear Time Reconstruction of Parameterized Strings from Parameterized suffix and LCP arrays for Constant-Sized Alphabets 31st

Linear Time Reconstruction of Parameterized Strings from Par...

引用

31st International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Amir, Amihood Kondratovsky, Eitan Marcus, Shoshana Sokol, Dina Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Georgia Inst Technol Coll Comp 801 Atlantic Dr Atlanta GA 30318 USA Open Univ Dept Math & Comp Sci Raanana Israel CUNY Kingsborough Community Coll Dept Math & Comp Sci 2001 Oriental Blvd Brooklyn NY 11210 USA Broklyn Coll Dept Comp & Informat Sci Brooklyn NY USA CUNY Grad Ctr Dept Comp Sci New York NY USA

ISBN: (纸本)9783031721991;9783031722004

A parameterized string (p-string) is a string that can contain two kinds of characters, static symbols and parameter characters. Parameterized pattern matching is a form of pattern matching that allows parameters to be renamed by applying a one-to-one function. The parameterized suffix array is a data structure that is useful in efficient parameterized pattern matching when accompanied by the parameterized longest common prefix (LCP) array. Reconstructing input from a given instance of a data structure is the task of determining whether the instance is valid or not, and if valid, producing a plausible set of data that it can represent. In this paper we consider parameterized suffix and LCP arrays and reconstruct a corresponding p-string that they can represent. In previous work, an algorithm can determine in O(n(2)) time whether a p-string can be constructed to correspond to the input parameterized suffix and LCP arrays of size n. In this work, we develop an algorithm that accomplishes this in O(n) time for constant-sized alphabets, and O(n log n) time for general alphabets. Furthermore, when reconstruction is possible, we demonstrate that a p-string can be reconstructed over the minimal alphabet in O(n(2)) time.

关键词： Strings Parameterized Strings suffix array Longest Common Prefix array Reverse Engineering

来源：评论

学校读者我要写书评

暂无评论

Optimal suffix sorting and LCP array construction for constant alphabets

引用

INFORMATION PROCESSING LETTERS 2017年 118卷 30-34页

作者： Louza, Felipe A. Gog, Simon Telles, Guilherme P. Univ Estadual Campinas Inst Comp Campinas SP Brazil Karlsruhe Inst Technol Inst Theoret Informat D-76021 Karlsruhe Germany

We show how the longest common prefix (LCP) array can be generated as a by-product of the suffix array construction algorithm SACA-K (Nong, 2013). Our algorithm builds on Fischer's proposal (Fischer, WADS'11), and also runs in linear time, but uses only constant extra memory for constant alphabets. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Data structures suffix array LCP array Linear time Constant space

来源：评论

学校读者我要写书评

暂无评论

A quick tour on suffix arrays and compressed suffix arrays

引用

THEORETICAL COMPUTER SCIENCE 2011年第27期412卷 2964-2973页

作者： Grossi, Roberto Univ Pisa Dipartimento Informat I-56100 Pisa Italy

suffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in {1, 2, ..., n), encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Pattern matching suffix array suffix tree Text indexing Data compression Space efficiency Implicitness and succinctness

来源：评论

学校读者我要写书评

暂无评论

Inducing enhanced suffix arrays for string collections

引用

THEORETICAL COMPUTER SCIENCE 2017年 678卷 22-39页

作者： Louza, Felipe A. Gog, Simon Telles, Guilherme P. Univ Estadual Campinas Inst Comp Campinas SP Brazil Karlsruhe Inst Technol Inst Theoret Informat D-76021 Karlsruhe Germany

Constructing the suffix array for a string collection is an important task that may be performed by sorting the concatenation of all strings. In this article we present algorithms gSAIS and gSACA-K, which extend SAIS (Nong et al., 2011) [8] and SACA-IC (Nong, 2013) [10] to construct the suffix array for a string collection maintaining their theoretical bounds, respecting the order among all suffixes, and improving their practical performance. gSACA-K is an optimal suffix array construction algorithm for string collections from constant alphabets. Moreover, we show how to modify gSAIS and gSACA-K to also compute the longest common prefix array and the document array as a byproduct of suffix sorting, with the same theoretical bounds. We performed experiments that showed that our algorithms have an outstanding practical performance. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Data structures suffix array LCP array Document array String collections

来源：评论

学校读者我要写书评

暂无评论

On the combinatorics of suffix arrays

引用

INFORMATION PROCESSING LETTERS 2013年第22-24期113卷 915-920页

作者： Kucherov, Gregory Tothmeresz, Lilla Vialette, Stephane Univ Paris Est Marne La Vallee France CNRS Lab Informat Gaspard Monge Marne La Vallee France Eotvos Lorand Univ H-1117 Budapest Hungary

We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows-Wheeler arrays given in [1]. We show that previous characterizations [2-4], or their analogs, can be obtained in a simple and elegant way using this relationship, To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows-Wheeler permutations. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Permutations suffix array Burrows-Wheeler transform

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：