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

3rd International Conference on Man-Machine Interactions (ICMMI)

作者： Susik, Robert Grabowski, Szymon Deorowicz, Sebastian Lodz Univ Technol Inst Appl Comp Sci Al Politech 11 Lodz Poland Silesian Tech Univ Inst Informat PL-44100 Gliwice Poland

ISBN: (纸本)9783319023090

The problem of circular pattern matching is to find all rotations of a given pattern P in text T, both over a common alphabet. The pattern and any of its rotations are also called conjugates in the literature. For the online version of this problem we present a new general approach and use several matching techniques as components, based on bit-parallelism and filtering. The experimental results show the effectiveness of the method, with matching speeds reaching 7-8GB/s for long patterns and natural language or protein data.

关键词： combinatorial problems string algorithms circular pattern matching

来源：评论

学校读者我要写书评

暂无评论

Multiple pattern matching revisited 18

Multiple pattern matching revisited

引用

18th Prague stringology Conference, PSC 2014

作者： Susik, Robert Grabowski, Szymon Fredriksson, Kimmo Lodz University of Technology Institute of Applied Computer Science Al. Politechniki 11 Lódź90-924 Poland School of Computing University of Eastern Finland P.O.B. 1627 KuopioFI-70211 Finland

ISBN: (纸本)9788001055472

We consider the classical exact multiple string matching problem. Our solution is based on q-grams combined with pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of the various alternatives of how to achieve best combination. Our method is closely related to previous work by (Salmela et al., 2006). The experimental results show that our method performs well on different alphabet sizes and that they scale to large pattern sets. © Czech Technical University in Prague, Czech Republic.

关键词： Combinatorial problems Q-grams string algorithms Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

Computing Abelian covers and Abelian runs 18

Computing Abelian covers and Abelian runs

引用

18th Prague stringology Conference, PSC 2014

作者： Matsuda, Shohei Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Department of Informatics Kyushu University Japan

ISBN: (纸本)9788001055472

Two strings u and v are said to be Abelian equivalent if u is a permutation of the characters of v. We introduce two new regularities on strings w.r.t. Abelian equivalence, called Abelian covers and Abelian runs, which are generalizations of covers and runs of strings, respectively. We show how to determine in O(n) time whether or not a given string w of length n has an Abelian cover. Also, we show how to compute an O(n2)-size representation of (possibly exponentially many) Abelian covers of w in O(n2) time. Moreover, we present how to compute all Abelian runs in w in O(n2) time, and state that the maximum number of all Abelian runs in a string of length n is Ω(n2). © Czech Technical University in Prague, Czech Republic.

关键词： Abelian equivalence on strings Abelian repetitions Covers of strings Parikh vectors string algorithms

来源：评论

学校读者我要写书评

暂无评论

On approximating string selection problems with outliers

引用

THEORETICAL COMPUTER SCIENCE 2013年 498卷 107-114页

作者： Boucher, Christina Landau, Gad M. Levy, Avivit Pritchard, David Weimann, Oren Univ Calif San Diego Dept Comp Sci San Diego CA 92103 USA Univ Haifa Dept Comp Sci IL-31905 Haifa Israel NYU Polytech Inst Brooklyn NY 11201 USA Shenkar Coll Engn & Design IL-52526 Ramat Gan Israel Univ Haifa CRI IL-31905 Haifa Israel Univ Waterloo CEMC Waterloo ON N2L 3G1 Canada

Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most strings problem is, given a set S of the same-length strings, and a parameter d, find a string x that maximizes the number of "non-outliers" within Hamming distance d of x. We prove that this problem has no polynomial-time approximation scheme (PTAS) unless NP has randomized polynomial-time algorithms, correcting a decade-old erroneous proof made previously in the literature. The Most strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k;we show it has no PTAS unless P = NP. We also observe Closest to k strings has no efficient PTAS (EPTAS) unless a parameterized complexity hierarchy collapses. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult. (C) 2013 Elsevier B.V. All rights reserved.

关键词： string selection string algorithms

来源：评论

学校读者我要写书评

暂无评论

A subquadratic algorithm for minimum palindromic factorization

引用

JOURNAL OF DISCRETE algorithms 2014年第0期28卷 41-48页

作者： Fici, Gabriele Gagie, Travis Karkkainen, Juha Kempa, Dominik Univ Palermo Dipartimento Matemat & Informat Palermo Italy Univ Helsinki Dept Comp Sci Helsinki Finland

We give an O(nlogn)-time, O(n)-space algorithm for factoring a string into the minimum number of palindromic substrings. Thatis, given a string S[1..n], in O(nlogn) time our algorithm returns the minimum number of palindromes S-1,..., S-l such that S = S-1 ,...,S-l Wealso show that the time complexity is O(n) on average and Omega(n logn) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words. (C) 2014 Published by Elsevier B.V.

关键词： string algorithms Palindromes Factorization

来源：评论

学校读者我要写书评

暂无评论

Binary jumbled string matching for highly run-length compressible texts

引用

INFORMATION PROCESSING LETTERS 2013年第17期113卷 604-608页

作者： Badkobeh, Golnaz Fici, Gabriele Kroon, Steve Liptak, Zsuzsanna Kings Coll London Dept Informat London England Univ Palermo Dipartimento Matemat & Informat I-90133 Palermo Italy Univ Stellenbosch Div Comp Sci ZA-7600 Stellenbosch South Africa Univ Verona Dipartimento Informat I-37100 Verona Italy

The Binary Jumbled string Matching Problem is defined as follows: Given a string s over {a, b} of length n and a query (x, y), with x, y non-negative integers, decide whether s has a substring t with exactly x a's and y b's. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time O(n(2)/logn) (Burcsi et al., 2010 [1];Moosa and Rahman, 2010 [7]), or O(n(2)/log(2) n) in the word-RAM model (Moosa and Rahman, 2012 [8]). We propose an index constructed directly from the run-length encoding of s. The construction time of our index is O(n + rho(2) log rho), where O(n) is the time for computing the run-length encoding of s and rho is the length of this encoding-this is no worse than previous solutions if rho = O(n/logn) and better if rho = O(n/ logn). Our index L can be queried in O(log rho) time. While vertical bar L vertical bar = O(min(n, rho(2))) in the worst case, preliminary investigations have indicated that vertical bar L vertical bar may often be close to rho. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of s introduced in Fici and Liptak (2011) [6]. (C) 2013 Elsevier B.V. All rights reserved.

关键词： string algorithms Data structures Jumbled pattern matching Parikh vectors Prefix normal form Run-length encoding

来源：评论

学校读者我要写书评

暂无评论

Finding shuffle words that represent optimal scheduling of shared memory access

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2013年第6期90卷 1292-1309页

作者： Reidenbach, Daniel Schmid, Markus L. Univ Loughborough Dept Comp Sci Loughborough LE11 3TU Leics England

In the present paper, we introduce and study the problem of computing, for any given finite set of words, a shuffle word with a minimum so-called scope coincidence degree. The scope coincidence degree is the maximum number of different symbols that parenthesize any position in the shuffle word. This problem is motivated by an application of a new automaton model and can be regarded as the problem of scheduling shared memory accesses of some parallel processes in a way that minimizes the number of memory cells required. We investigate the complexity of this problem and show that it can be solved in polynomial time.

关键词： string algorithms shuffle memory access scheduling

来源：评论

学校读者我要写书评

暂无评论

Approximate pattern matching with k-mismatches in packed text

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 693-697页

作者： Giaquinta, Emanuele Grabowski, Szymon Fredriksson, Kimmo Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Tech Univ Lodz Inst Appl Comp Sci PL-90924 Lodz Poland Univ Eastern Finland Sch Comp FI-70211 Kuopio Finland

Given strings P of length m and T of length n over an alphabet of size sigma, the string matching with k-mismatches problem is to find the positions of all the substrings in T that are at Hamming distance at most k from P. If T can be read only one character at the time the best known bounds are O (n root klogk) and O(n + n root k/w logk) in the word-RAM model with word length w. In the RAM models (including AC(0) and word-RAM) it is possible to read up to left perpendicularw/log sigma right perpendicular characters in constant time if the characters of T are encoded using inverted right perpendicularlog sigma inverted left perpendicular bits. The only solution for k-mismatches in packed text works in O ((n log sigma/log n) inverted right perpendicularm log(k + logn/log sigma)/winverted left perpendicular + n(epsilon)) time, for any epsilon > 0. We present an algorithm that runs in time O(n/left perpendicularw/(m log sigma)right perpendicular (1 + log min(k, sigma)log m/log sigma)) in the AC(0) model if m = O (w/log sigma) and T is given packed. We also describe a simpler variant that runs in time O(n/left perpendicular/(m log sigma)right perpendicular log min(m, log w/log sigma)) in the word-RAM model. The algorithms improve the existing bound for w = Omega(log(1+epsilon) n), for any epsilon > 0. Based on the introduced technique, we present algorithms for several other approximate matching problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems string algorithms k-mismatches Hamming distance Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

PATTERN MATCHING UNDER POLYNOMIAL TRANSFORMATION

引用

SIAM JOURNAL ON COMPUTING 2013年第2期42卷 611-633页

作者： Butman, Ayelet Clifford, Peter Clifford, Raphael Jalsenius, Markus Lewenstein, Noa Porat, Benny Porat, Ely Sach, Benjamin Holon Inst Technol Dept Comp Sci Holon Israel Univ Oxford Dept Stat Oxford OX1 3TG England Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England Netanya Acad Coll Dept Comp Sci IL-42365 Netanya Israel Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

We consider a class of pattern matching problems where a normalizing polynomial transformation can be applied at every alignment of the pattern and text. Normalized pattern matching plays a key role in fields as diverse as image processing and musical information processing, where application specific transformations are often applied to the input. By considering a wide range of such transformations, we provide fast algorithms and the first lower bounds for both new and old problems. Given a pattern of length m and a longer text of length n, where both are assumed to contain integer values only, we first show O(n log m) time algorithms for pattern matching under linear transformations even when wildcard symbols can occur in the input. We then show how to extend the technique to polynomial transformations of arbitrary degree. Next we consider the problem of finding the minimum Hamming distance under polynomial transformation. We show that, for any epsilon > 0, there cannot exist an O(nm(1-epsilon)) time algorithm for additive and linear transformations conditional on the hardness of the classic 3SUM problem. Finally, we consider a version of the Hamming distance problem under additive transformations with a bound k on the maximum distance that needs to be reported. We give a deterministic O(nk log k) time solution, which we then improve by careful use of randomization to O(n root k log k log n) time for sufficiently small k. Our randomized solution outputs the correct answer at every position with high probability.

关键词： string algorithms pattern matching normalization 3SUM-hardness

来源：评论

学校读者我要写书评

暂无评论

New algorithms for binary jumbled pattern matching

引用

INFORMATION PROCESSING LETTERS 2013年第14-16期113卷 538-542页

作者： Giaquinta, Emanuele Grabowski, Szymon Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Lodz Univ Technol Inst Appl Comp Sci PL-90924 Lodz Poland

Given a pattern P and a text T, both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of P occurs in T. The indexed version of this problem, i.e., preprocessing a string to efficiently answer such permutation queries, is hard and has been studied in the last few years. Currently the best bounds for this problem are 0 (n(2)/log(2) n) (with O(n) space and O(1) query time) (Moosa and Rahman (2012) [1]) and O(r(2)logr) (with O(vertical bar L vertical bar space and O(log vertical bar L vertical bar) query time) (Badkobeh et al. (2012) [2]), where r is the length of the run-length encoding of T and vertical bar L vertical bar = O(n) is the size of the index. In this paper we present new results for this problem. Our first result is an alternative construction of the index by Badkobeh et al. (2012) [2] that obtains a trade-off between the space and the time complexity. It has O (r(2) logk + n/k) complexity to build the index, O(logk) query time, and uses O(n/k + vertical bar L vertical bar) space, where k is a parameter. The second result is an O(n(2) log(2) w/w) algorithm (with O(n) space and O(1) query time), based on word-level parallelism where w is the word size in bits. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems string algorithms Jumbled pattern matching Parikh vectors Run-length encoding Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：