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

Further Improvement in Approximating the Maximum Duo-Preservation string Mapping Problem 1

16th International Workshop on algorithms in Bioinformatics (WABI)

作者： Brubach, Brian Univ Maryland Dept Comp Sci College Pk MD 20742 USA

ISBN: (数字)9783319436814

ISBN: (纸本)9783319436814;9783319436807

We present an improved approximation for the Maximum Duo-Preservation string Mapping Problem (MPSM). This problem was introduced in [7] as the complement to the well-studied Minimum Common string Partition problem (MCSP). Prior work also considers the k-MPSM and k-MCSP variants in which each letter occurs at most k times. The authors of [7] showed a k(2)-appoximation for k >= 3 and 2-approximation for k = 2. A 4-approximation independent of k was shown in [4]. In [4], they also showed that k-MPSM is APX-Hard and achieved approximation ratios of 8/5 for k = 2 and 3 for k = 3. In this paper, we show an algorithm which achieves a 13/4-approximation for the general MPSM problem using a new combinatorial triplet matching approach. During publication of this paper, [3] presented a local search algorithm yielding 7/2, which falls in between the previous best and this paper. The remainder of the paper has not been altered to reflect this.

关键词： string algorithms Polynomial-time approximation Max Duo-Preservation string Mapping Problem Min Common string Partition Problem

来源：评论

学校读者我要写书评

暂无评论

Differentially Private string Sanitization for Frequency-Based Mining Tasks 21

Differentially Private String Sanitization for Frequency-Bas...

引用

21st IEEE International Conference on Data Mining (IEEE ICDM)

作者： Chen, Huiping Dong, Changyu Fan, Liyue Loukides, Grigorios Pissis, Solon P. Stougie, Leen Kings Coll London London England Newcastle Univ Newcastle Upon Tyne Tyne & Wear England Univ North Carolina Charlotte Charlotte NC USA ERABLE Team Villeurbanne France CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands

ISBN: (纸本)9781665423984

strings are used to model genomic, natural language, and web activity data, and are thus often shared broadly. However, string data sharing has raised privacy concerns stemming from the fact that knowledge of length-k substrings of a string and their frequencies (multiplicities) may be sufficient to uniquely reconstruct the string;and from that the inference of such substrings may leak confidential information. We thus introduce the problem of protecting length-k substrings of a single string S by applying Differential Privacy (DP) while maximizing data utility for frequency-based mining tasks. Our theoretical and empirical evidence suggests that classic DP mechanisms are not suitable to address the problem. In response, we employ the order-k de Bruijn graph G of S and propose a sampling-based mechanism for enforcing DP on G. We consider the task of enforcing DP on G using our mechanism while preserving the normalized edge multiplicities in G. We define an optimization problem on integer edge weights that is central to this task and develop an algorithm based on dynamic programming to solve it exactly. We also consider two variants of this problem with real edge weights. By relaxing the constraint of integer edge weights, we are able to develop linear-time exact algorithms for these variants, which we use as stepping stones towards effective heuristics. An extensive experimental evaluation using real-world large-scale strings (in the order of billions of letters) shows that our heuristics are efficient and produce near-optimal solutions which preserve data utility for frequency-based mining tasks.

关键词： differential privacy data sanitization string algorithms frequent pattern mining

来源：评论

学校读者我要写书评

暂无评论

Semi-local string Comparison: Algorithmic Techniques and Applications

引用

MATHEMATICS IN COMPUTER SCIENCE 2008年第4期1卷 571-603页

作者： Tiskin, Alexander Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

Given two strings, the longest common subsequence (LCS) problem consists in computing the length of the longest string that is a subsequence of both input strings. Its generalisation, the all semi-local LCS problem, requires computing the LCS length for each string against all substrings of the other string, and for all prefixes of each string against all suffixes of the other string. We survey a number of algorithmic techniques related to the all semi-local LCS problem. We then present a number of algorithmic applications of these techniques, both existing and new. In particular, we obtain a new all semilocal LCS algorithm, with asymptotic running time matching (in the case of an unbounded alphabet) the fastest known global LCS algorithm by Masek and Paterson. We conclude that semi-local string comparison turns out to be a useful algorithmic plug-in, which unifies, and often improves on, a number of previous approaches to various substring-and subsequence-related problems.

关键词： string algorithms longest common subsequence semi-local string comparison

来源：评论

学校读者我要写书评

暂无评论

I/O-efficient data structures for non-overlapping indexing

引用

THEORETICAL COMPUTER SCIENCE 2021年 857卷 1-7页

作者： Hooshmand, Sahar Abedin, Paniz Kulekci, M. Oguzhan Thankachan, Sharma V. Univ Cent Florida Dept Comp Sci Orlando FL 32816 USA Istanbul Tech Univ Informat Inst Istanbul Turkey

The non-overlapping indexing problem is defined as follows: pre-process a given text T[1, n] of length n into a data structure such that whenever a pattern P [1, m] comes as an input, we can efficiently report the largest set of non-overlapping occurrences of P in T. The best-known solution is by Cohen and Porat [ISAAC 2009]. The size of their structure is O (n) words and the query time is optimal O (m + nocc), where nocc is the output size. Later, Ganguly et al. [CPM 2015 and Algorithmica 2020] proposed a compressed space solution. We study this problem in the cache-oblivious model and present a new data structure of size O (n log n) words. It can answer queries in optimal O (m/B + log(B) n + nocc/B) I/O operations, where B is the block size. The space can be improved to O (n log(M/B) n) in the cache-aware model, where M is the size of main memory. Additionally, we study a generalization of this problem with an additional range [s, e] constraint. Here the task is to report the largest set of non-overlapping occurrences of P in T, that are within the range [s, e]. We present an O (n log(2) n) space data structure in the cache-aware model that can answer queries in optimal O (m/B + log(B) n + nocc([s,e]) B ) I/O operations, where nocc([s,e]) is the output size. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Suffix trees Data structure string algorithms

来源：评论

学校读者我要写书评

暂无评论

Hide and Mine in strings: Hardness, algorithms, and Experiments

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第6期35卷 5948-5963页

作者： Bernardini, Giulia Conte, Alessio Gourdel, Garance Grossi, Roberto Loukides, Grigorios Pisanti, Nadia Pissis, Solon P. Punzi, Giulia Stougie, Leen Sweering, Michelle Univ Trieste Trieste I-34127 Italy CWI NL-1098 XG Amsterdam Netherlands Univ Pisa I-56126 Pisa Italy Inria Rennes ENS Ecole Normale Super Gif Sur Yvette F-91190 France Univ Pisa Comp Sci I-91190 Pisa Italy ERABLE Team F-38330 Montbonnot SaintMartin France Kings Coll London London WCR 2LS England Vrije Univ NL-1081 HV Amsterdam Netherlands Vrije Univ Operat Res NL-1081 HV Amsterdam Netherlands

Data sanitization and frequent pattern mining are two well-studied topics in data mining. Data sanitization is the process of disguising (hiding) confidential information in a given dataset. Typically, this process incurs some utility loss that should be minimized. Frequent pattern mining is the process of obtaining all patterns occurring frequently enough in a given dataset. Our work initiates a study on the fundamental relation between data sanitization and frequent pattern mining in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns. This, however, may lead to spurious patterns that harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is as follows. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under realistic assumptions on the input parameters. We also complement the integer linear programming algorithms with a greedy heuristic. Third, we present an extensive experimental study, using both synthetic and real-world datasets, that demonstrates the effectiveness and efficiency of our methods. Beyond sanitization, the process of missing value replacement may also lead to spurious patterns. Interestingly, our results apply in this context as well. We show that, unlike popular approaches, our methods can fill missing values in genomic sequences, while preserving the accuracy of frequent pattern mining.

关键词： Data mining Bioinformatics Genomics DNA Data integrity Privacy Resists Data privacy data sanitization knowledge hiding frequent pattern mining string algorithms

来源：评论

学校读者我要写书评

暂无评论

A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length

引用

ALGORITHMICA 2022年第9期84卷 2581-2596页

作者： Sakai, Yoshifumi Inenaga, Shunsuke Tohoku Univ Grad Sch Agr Sci Sendai Miyagi Japan Kyushu Univ Dept Informat Fukuoka Japan Japan Sci & Technol Agcy PRESTO Kawaguchi Saitama Japan

The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of length n such that the dissimilarity between any elements is an integer between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is O(cn(2)), which can be translated to O(n(2)) for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(like) measures are directly applicable to analysis of time series via our reduction of DTWto LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.

关键词： string algorithms Dynamic time warping distance Longest increasing subsequence Semi-local sequence comparison

来源：评论

学校读者我要写书评

暂无评论

Succinct Non-overlapping Indexing

引用

ALGORITHMICA 2020年第1期82卷 107-117页

作者： Ganguly, Arnab Shah, Rahul Thankachan, Sharma V. Univ Wisconsin Dept Comp Sci Whitewater WI 53190 USA Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Univ Cent Florida Dept Comp Sci Orlando FL 32816 USA

Text indexing is a fundamental problem in computer science. The objective is to preprocess a text T, so that, given a pattern P, we can find all starting positions (or simply, occurrences) of P in T efficiently. In some cases, additional restrictions are imposed. We consider two variants, namely the non-overlapping indexing problem, and the range non-overlapping indexing problem. Given a text T having n characters, the non-overlapping indexing problem is defined as follows: pre-process T into a data structure, such that for any pattern P, containing |P| characters, we can report a set containing the maximum number of non-overlapping occurrences of P in T. Cohen and Porat (in: algorithms and computation, 20th international symposium, ISAAC 2009, Honolulu, Hawaii. Proceedings, 2009) showed that by maintaining a linear space index in which the suffix tree of T is augmented with an O(n) word data structure, a query P can be answered in optimal time O(|P|+nocc), where nocc is the number of occurrences reported. We present the following new result. Let CSA (not necessarily a compressed suffix array) be an index of T that can compute (i) the suffix range of P in search(P) time, and (ii) a suffix array or an inverse suffix array value in tSA time. By using CSAalone, we can answer a query P in search(P)+sort(nocc)+O(nocc center dot tSA) time. The function sort(k) denotes the time for sorting k numbers in {1,2,MIDLINE HORIZONTAL ELLIPSIS,n}. In the range non-overlapping indexing problem, along with the pattern P, two integers a and b, b >= a, are provided as input. The task is to report a set containing the maximum number of non-overlapping occurrences of P that lie within the range [a, b]. For any arbitrarily small positive constant epsilon, we present an O(nlog epsilon n) word index with O(|P|+nocca,b) query time, where nocca,b is the number of occurrences reported. Our index improves upon the result of Cohen and Porat [6].

关键词： Succinct data structures Range queries Suffix trees string algorithms

来源：评论

学校读者我要写书评

暂无评论

On Approximate Jumbled Pattern Matching in strings

引用

THEORY OF COMPUTING SYSTEMS 2012年第1期50卷 35-51页

作者： Burcsi, Peter Cicalese, Ferdinando Fici, Gabriele Liptak, Zsuzsanna Univ Salerno Dipartimento Informat & Applicaz I-84100 Salerno Italy Eotvos Lorand Univ Dept Comp Algebra Budapest Hungary Univ Nice Sophia Antipolis France CNRS I3S UMR6070 Antipolis France Univ Bielefeld Tech Fak AG Genominformat D-33615 Bielefeld Germany

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t) = q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u, v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u <= q <= v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem in sub-linear expected time using a wavelet tree of s, which can be computed in time O(n) in a preprocessing phase. We then discuss a Scrabble-like variation of the problem, in which a weight function on the letters of s is given and one has to find all occurrences in s of a substring t with maximum weight having Parikh vector p(t) <= v. For the case of a binary alphabet, we present an algorithm which solves the decision version of the Approximate Jumbled Pattern Matching problem in constant time, by indexing the string in subquadratic time.

关键词： string algorithms Pattern matching Parikh vectors Average case analysis Approximate search Permuted strings

来源：评论

学校读者我要写书评

暂无评论

On optimal parsing for LZ78-like compressors

引用

THEORETICAL COMPUTER SCIENCE 2018年 710卷 19-28页

作者： Aronica, Salvatore Langiu, Alessio Marzi, Francesca Mazzola, Salvatore Mignosi, Filippo CNR IAMC Natl Res Council Unit Capo Granitola Trapani Italy CNR ICAR Natl Res Council Unit Palermo Palermo Italy Kings Coll London Dept Informat London England Univ LAquila DISIM Dept Laquila Italy

Flexible parsing algorithm, a two-steps-greedy parsing algorithm for text factorisation, has been proved to be an optimal parsing for LZ78-like compressors in the case of constant cost phrases [1,2]. Whilst in early implementations of LZ78-like compressors the phrases have constant cost, in common modern implementations the cost of the k-th phrase is [log(2) k + C] where C is a real constant [3,4]. Indeed we show examples where Flexible parsing is not optimal under the above more realistic setting. In this paper we prove that, under the assumption that the cost of a phrase is block-wise constant and non-decreasing, the Flexible parsing is almost optimal. For almost optimal we mean that, for any text T, the difference between the sizes of the compressed text obtained by using a Flexible parsing and an optimal parsing is bounded by the maximal cost of a phrase in T, i.e. it is logarithmic in practical cases. Furthermore we investigate how an optimal parsing, and hence an almost optimal parsing, affects the rate of convergence to the entropy of LZ78-like compressors. We discuss some experimental results considering the ratio between the speed of convergence to the entropy of compressors with and without an optimal parsing. This ratio presents a kind of wave effect that increases as the entropy of a memoryless source decreases but it seems always to slowly converge to one. According to the theory, this wave can be a tsunami for some families of highly compressible strings and, although the optimal (and the almost optimal) parsing does not improve the asymptotical speed of convergence to the entropy, it can improve compression ratio, and hence the decoding speed, in many practical cases. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Lempel-Ziv compression algorithms Parsing algorithms Text factorisation Text compression Text entropy string algorithms

来源：评论

学校读者我要写书评

暂无评论

THE "RUNS" THEOREM

引用

SIAM JOURNAL ON COMPUTING 2017年第5期46卷 1501-1514页

作者： Bannai, Hideo Tomohiro, I Inenaga, Shunsuke Nakashima, Yuto Takeda, Masayuki Tsuruta, Kazuya Kyushu Univ Dept Informat Nishi Ku Fukkuoka 8190395 Japan TU Dortmund Dept Comp Sci D-44221 Dortmund Germany Kyushu Inst Technol Dept Artificial Intelligence Fukkuoka Japan

We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture [R. M. Kolpakov and G. Kucherov, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1999, pp. 596-604]), which states that the maximum number of runs rho(n) in a string of length n is less than n. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of 3n for the maximum sum of exponents sigma(n) of runs in a string of length n, improving on the best known bound of 4.1n by Crochemore et al. [J. Discrete algorithms, 14 (2012), pp. 29-36], as well as other improved bounds on related problems. The characterization also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-period query problem that was recently solved by Kociumaka et al.

关键词： maximal repetitions Lyndon words combinatorics on words string algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：