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

THEORETICAL COMPUTER SCIENCE 2025年 1041卷

作者： Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Walen, Tomasz Zuba, Wiktor Birkbeck Univ London London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands Univ Warsaw Inst Informat Warsaw Poland

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].

关键词： text algorithms Combinatorics on Covers Shuffle powers Subsequence

来源：评论

学校读者我要写书评

暂无评论

Various improvements to text fingerprinting

引用

JOURNAL OF DISCRETE algorithms 2013年 22卷 1-18页

作者： Belazzougui, Djamal Kolpakov, Roman Raffinot, Mathieu Univ Helsinki Dept Comp Sci FI-00014 Helsinki Finland Lomonosov Moscow State Univ Liapunov French Russian Inst Moscow Russia Univ Paris Diderot Paris 7 LIAFA F-75205 Paris 13 France

Let s = s(1)..s(n) be a text (or sequence) on a finite alphabet Sigma of size sigma. A fingerprint in s is the set of distinct characters appearing in one of its substrings. The problem considered here is to compute the set.F of all fingerprints of all substrings of s in order to answer efficiently certain questions on this set. A substring s(i)..s(j) is a maximal location for a fingerprint f is an element of F (denoted by (i, j)) if the alphabet of s(i)..s(j) is f and s(i+1), s(j+1), if defined, are not in f. The set of maximal locations in s is L (it is easy to see that vertical bar L vertical bar <= n sigma). Two maximal locations (i, j) and (k, l) such that s(i)..s(j) = s(k)..s(l) are named copies, and the quotient set of L according to the copy relation is denoted by L-c. We first present new exact efficient algorithms and data structures for the following three problems: (1) to compute F;(2) given f as a set of distinct characters in X, to answer if f represents a fingerprint in.F;(3) given f, to find all maximal locations of f in s. As well as in papers concerning succinct data structures, in the paper all space complexities are counted in bits. Problem 1 is solved either in 0 (n + vertical bar L-c vertical bar log sigma) worst-case time (in this paper all logarithms are intended as base two logarithms) using 0 ((n + vertical bar L-c vertical bar + vertical bar F vertical bar log sigma)log n) bits of space, or in 0 (n + vertical bar L-c vertical bar log sigma) randomized expected time using 0 ((n + vertical bar F vertical bar log sigma) logn) bits of space. Problem 2 is solved either in 0(vertical bar f vertical bar) expected time if only 0 (vertical bar f vertical bar logn) bits of working space for queries is allowed, or in worst-case 0 (vertical bar f vertical bar/epsilon) time if a working space of 0 (sigma(epsilon) log n) bits is allowed (with c a constant satisfying 0 < epsilon < 1). These algorithms use a data structure that occupies vertical bar F ver

关键词： text algorithms Indexing Naming Character sets

来源：评论

学校读者我要写书评

暂无评论

Fast computation of abelian runs

引用

THEORETICAL COMPUTER SCIENCE 2016年第PartB期656卷 256-264页

作者： Fici, Gabriele Kociumaka, Tomasz Lecroq, Thierry Lefebvre, Arnaud Prieur-Gaston, Elise Univ Palermo Dipartimento Matemat & Informat Palermo Italy Univ Warsaw Fac Math Informat & Mech Warsaw Poland Univ Rouen Normandie Univ LITIS EA4108 IRIBNormaSt CNRS FR 3638 F-76821 Mont St Aignan France

Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period P. Our main result is an online algorithm that, given a word w of length n over an alphabet of cardinality sigma and a Parikh vector P, returns all the abelian runs of period P in w in time O(n) and space O(sigma + p), where p is the norm of P, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm p in w in time O(np), for any given norm p. Finally, we give an O(n(2))-time offline randomized algorithm for computing all the abelian runs of w. Its deterministic counterpart runs in O(n(2) log sigma) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Combinatorics on words text algorithms Abelian period Abelian run

来源：评论

学校读者我要写书评

暂无评论

Indexing and querying color sets of images

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期647卷 74-84页

作者： Belazzougui, Djamal Kolpakov, Roman Raffinot, Mathieu Res Ctr Sci & Tech Informat CERIST DTISI Algiers Algeria Lomonosov Moscow State Univ Moscow Russia Univ Bordeaux 1 LaBRI F-33405 Talence France

We aim to study the set of color sets of continuous regions of an image given as a matrix of m rows over n >= m columns where each element in the matrix is an integer from [1, sigma] named a color. The set of distinct colors in a region is called fingerprint. We aim to compute, index and query the fingerprints of all rectangular regions named rectangles. The set of all such fingerprints is denoted by F. A rectangle is maximal if it is not contained in a greater rectangle with the same fingerprint. The set of all locations of maximal rectangles is denoted by L. We first explain how to determine all the vertical bar L vertical bar maximal locations with their fingerprints in expected time O (nm(2)sigma) using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic O (nm(2)sigma log(vertical bar L vertical bar/nm(2) + 2)) time. We then show how to build a data structure which occupies O(nm logn + vertical bar L vertical bar) space such that a query which asks for all the maximal locations with a given fingerprint f can be answered in time O(vertical bar f vertical bar + log logn + k), where k is the number of maximal locations with fingerprint f. If the query asks only for the presence of the fingerprint, then the space usage becomes O (nm logn + vertical bar F vertical bar) while the query time becomes O(nm log logn + vertical bar F vertical bar). We eventually consider the special case of squared regions (squares). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Image algorithms text algorithms Fingerprint Set of characters Set of colors Maximal locations

来源：评论

学校读者我要写书评

暂无评论

algorithms for computing Abelian periods of words

引用

DISCRETE APPLIED MATHEMATICS 2014年第part3期163卷 287-297页

作者： Fici, Gabriele Lecroq, Thierry Lefebvre, Arnaud Prieur-Gaston, Elise Univ Palermo Dipartimento Matemat & Informat I-90133 Palermo Italy Univ Rouen Normandie Univ LITIS EA4108 F-76821 Mont St Aignan France

Constantinescu and file [S. Constantinescu, L. Hie. Fine and Wilt's theorem for abelian periods, Bulletin of the European Association for Theoretical Computer Science 89 (2006) 167-170] introduced the notion of an Abelian period of a word. A word of length n over an alphabet of size sigma can have Theta (n(2)) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n(2) x sigma) using O(n x sigma) space. We present an offline algorithm based on a select function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present online algorithms that also enable us to compute all the Abelian periods of all the prefixes of w. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Abelian period Abelian repetition Weak repetition Design of algorithms text algorithms Combinatorics on words

来源：评论

学校读者我要写书评

暂无评论

A note on easy and efficient computation of full abelian periods of a word

引用

DISCRETE APPLIED MATHEMATICS 2016年第0期212卷 88-95页

作者： Fici, Gabriele Lecroq, Thierry Lefebvre, Arnaud Prieur-Gaston, Elise Smyth, William F. Univ Palermo Dipartimento Matemat & Informat I-90133 Palermo Italy Univ Rouen Normandie Univ Normast FR CNRS 3638 LITIS EA 4108 F-76821 Mont St Aignan France McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada Murdoch Univ Fac Engn & Informat Technol Murdoch WA 6150 Australia

Constantinescu and Elie (2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement O(n log log n)-time algorithm for computing all the full Abelian periods of a word of length n over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the O(n) algorithm proposed by Kociumaka et al. (2013) for the same problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Abelian period Abelian power Weak repetition Design of algorithms text algorithms Combinatorics on words

来源：评论

学校读者我要写书评

暂无评论

xkcd-repeats: A new taxonomy of repeats defined by their context diversity

引用

JOURNAL OF DISCRETE algorithms 2018年 48卷 1-16页

作者： Galle, Matthias Tealdi, Matias Naver Labs Europe Meylan France Amazon Com Toronto ON Canada Xerox Res Ctr Europe Grenoble France

The context in which a substring appears is an important notion to identify - for example - its semantic meaning. However, existing definitions from stringology fail to model the context explicitly. We introduce here xkcd-repeats, a new family of repeats characterized by the number of different symbols at the left and right of their occurrences. These repeats include as special extreme cases the well-known classes of maximal and super-maximal repeats. We give sufficient and necessary condition to bound their number linearly in the size of the original string, and show an optimal algorithm that computes them in linear time - given a suffix array -, independent of the size of the alphabet, as well as two other algorithms that are faster in practice. We extend this in two ways: first we show how to generalize the notion of context. Instead of reducing it to the single symbol before and after an occurrence, we propose the notion of unbounded context, while keeping linear representation and computing time. Secondly, we provide a general framework which allows to compute these (and other) repeats incrementally;opening the door to streaming application. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Repeats Stringology text algorithms Suffix array Natural-language processing

来源：评论

学校读者我要写书评

暂无评论

Improving Exact Search of Multiple Patterns From a Compressed Suffix Array

Improving Exact Search of Multiple Patterns From a Compresse...

引用

16th Prague Stringology Conference (PSC)

作者： Karhu, Kalle Aalto Univ Dept Comp Sci & Engn Helsinki Finland

ISBN: (纸本)9788001048702

Self-indexes are largely studied and widely applied structures in string matching. However, the exact matching of multiple patterns using self-indexes is a topic that has not been the subject of concentrated study although it is an area that may have direct and indirect applications and uses in fields such as bioinformatics. This paper presents a method of improving the exact search of multiple patterns from a compressed suffix array. The proposed method is able to cut down run-times for the handled patterns by as much as 71.6%. A set of 1000 patterns of length 1000 nucleotides each is found from a text of 50 MB in size 14.0% faster than by searching the patterns using the locate functionality of the compressed suffix array.

关键词： self-indexes pattern matching indexing text algorithms

来源：评论

学校读者我要写书评

暂无评论

Quasi-linear time computation of the abelian periods of a word

Quasi-linear time computation of the abelian periods of a wo...

引用

Prague Stringology Conference, PSC 2012

作者： Fici, Gabriele Lecroq, Thierry Lefebvre, Arnaud Prieur-Gaston, Élise Smyth, William F. I3S CNRS and Université Nice Sophia Antipolis France LITIS EA4108 Université de Rouen 76821 Mont-Saint-Aignan Cedex France Department of Computing and Software McMaster University Hamilton ON L8S 4K1 Canada

ISBN: (纸本)9788001050958

In the last couple of years many research papers have been devoted to Abelian complexity of words. Recently, Constantinescu and Ilie (Bulletin EATCS 89, 167-170, 2006) introduced the notion of Abelian period. In this article we present two quadratic brute force algorithms for computing Abelian periods for special cases and a quasi-linear algorithm for computing all the Abelian periods of a word. © Czech Technical University in Prague, Czech Republic.

关键词： Abelian period Abelian repetition Combinatorics on words Design of algorithms text algorithms Weak repetition

来源：评论

学校读者我要写书评

暂无评论

Podpora tokenizace pro Diff a Patch

Podpora tokenizace pro Diff a Patch

引用

作者： Antoniewicz, Arkadiusz Martin Charles University of Prague

File comparison algorithms and utilities diff, patch and diff3 are widely used in programming for the purpose of code comparison, and in many version control systems. Despite the usefulness, the differences and patches produced by the tools are strictly line-oriented, which complicates processing of differently formatted data, such as free flowing text, markup, and various other formats where line breaks are not crucial. This thesis de- scribes and implements a customizable version of these tools, which allows the user to specify an arbitrary tokenization of the input, thus allowing easy diffing, patching and change-merging of content not supported by the tradi- tional diff. Additionally, the thesis describes a newly appearing challenge of managing the whitespace in the patches, and demonstrates the functional- ity on a practical use-case that can not be performed with the current diff utilities. 1

关键词： editing distance three-way merge text algorithms version control

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：