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

Inverse Lyndon words and inverse Lyndon factorizations of words

ADVANCES IN APPLIED MATHEMATICS 2018年 101卷 281-319页

作者： Bonizzoni, Paola De Felice, Clelia Zaccagnino, Rocco Zizza, Rosalba Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Viale Sarca 336 I-20126 Milan Italy Univ Salerno Dipartimento Informat Via Giovanni Paolo II 132 I-84084 Fisciano SA Italy

X Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is unique but w may have several inverse Lyndon factorizations. We prove that any nonempty word w admits a canonical inverse Lyndon factorization, named ICFL(w), that maintains the main properties of the Lyndon factorization of w: it can be computed in linear time, it is uniquely determined, and it preserves a compatibility property for sorting suffixes. In particular, the compatibility property of ICFL(w) is a consequence of another result: any factor in ICFL(w) is a concatenation of consecutive factors of the Lyndon factorization of w with respect to the inverse lexicographic order. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Lyndon words Lyndon factorization combinatorial algorithms on words DNA sequences

来源：评论

学校读者我要写书评

暂无评论

Pattern matching in hypertext

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第1期35卷 82-99页

作者： Amir, A Lewenstein, M Lewenstein, N Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel

The importance of hypertext has been steadily growing over the past decade. The Internet and other information systems use hypertext formal, with data organized associatively rather than sequentially or relationally. A myriad of textual problems have been considered in the pattern matching field with many nontrivial results. Nevertheless, surprisingly little work has been done on the natural combination ol pattern matching and hypertext. Ln contrast to regular text, hypertext has a nonlinear structure and the techniques of pattern matching for text cannot be directly applied to hypertext. Manber and Wu (1992, "IAPR Workshop on Structural and Syntactic Pattern Recognition, Bern, Switzerland) pioneered the study of pattern matching in hypertext and defined a hypertext model for pattern matching. Akutsu (1993, "Procedures of the 4th Symposium on combinatorial Pattern Matching Podova, Italy," pp. 1-10) developed an algorithm that can be used for exact pattern matching in a tree-structured hypertext. Park and I(im (1995, "6th Symposium on combinatorial Pattern Matching;Helsinki, Finland") considered regular pattern matching in hypertext. They developed a complex algorithm that works for hypertext with an underlying structure of a DAG. In this paper we present a much simpler algorithm achieving the same complexity which runs on any hypertext graph. We then extend the problem to approximate pattern matching in hypertext, first considering hamming distance and then edit distance. We show that in contrast to regular text, it dos make a difference whether Che;errors occur in the hypertext or the pattern The approximate pattern matching problem in hypertext with errors in the hypertext turns out to be NP-complete anti the approximate pattern matching problem in hypertext: with errors in the pattern has a polynomial time solution, (C) 2000 Academic Press.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching hypertext pattern matching on hypertext.

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for string matching with k mismatches

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2004年第2期50卷 257-275页

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length in and every length in substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil-Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O (nk). The Abrahamson algorithm finds the number of mismatches at every location in time O (nrootm log m). We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time O(nrootk log k). We also show an algorithm that solves the above problem in time O ((n + (nk(3))/m) log k). (C) 2003 Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Real scaled matching

引用

INFORMATION PROCESSING LETTERS 1999年第4期70卷 185-190页

作者： Amir, A Butman, A Lewenstein, M Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

Scaled matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary integral scale, appears. Scaled matching is an important problem that was originally inspired by problems in Vision. However, in real life, a more natural model of scaled matching is the real scaled matching model. Real scaled matching is an extended version of the scaled matching problem allowing arbitrary real-sized scales, approximated by some function, e.g., truncation. It has been shown that the scaled matching problem can be solved in linear time. However, even though there has been follow-up work on the problem, it remained an open question whether real scaled matching could be solved faster than the simple solution of O(nm) time, where n is the text size and m is the pattern size. Using a new approach we show how to solve the real scaled matching problem in linear time. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： design of algorithm analysis of algorithms combinatorial algorithms on words pattern matching scaled pattern matching approximate pattern matching generalized pattern matching

来源：评论

学校读者我要写书评

暂无评论

Character sets of strings

引用

JOURNAL OF DISCRETE algorithms 2007年第2期5卷 330-340页

作者： Didier, Gilles Schmidt, Thomas Stoye, Jens Tsur, Dekel CNRS Ctr Modelamiento Matemat UMR 2071 Santiago Chile Univ Bielefeld Ctr Biotechnol Int NRW Grad Sch Bioinformat & Genome Res D-33594 Bielefeld Germany Univ Bielefeld Tech Fak D-33594 Bielefeld Germany Ben Gurion Univ Negev Comp Sci Dept Beer Sheva Israel

Given a string S over a finite alphabet S, the character set (also called the fingerprint) of a substring S' of S is the subset C subset of Sigma of the symbols occurring in S'. The study of the character sets of all the substrings of a given string (or a given collection of strings) appears in several domains such as rule induction for natural language processing or comparative genomics. Several computational problems concerning the character sets of a string arise from these applications, especially: (1) Output all the maximal locations of substrings having a given character set. (2) Output for each character set C occurring in a given string (or a given collection of strings) all the maximal locations of C. Denoting by n the total length of the considered string or collection of strings, we solve the first problem in Theta(n) time using Theta(n) space. We present two algorithms solving the second problem. The first one runs in Theta(n(2)) time using Theta(n) space. The second algorithm has Theta(n vertical bar Sigma vertical bar log vertical bar Sigma vertical bar) time and Theta(n) space complexity and is an adaptation of an algorithm by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete algorithms 26 (2003) 1-13]. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Character sets Fingerprints combinatorial algorithms on words Comparative genomics Natural language processing

来源：评论

学校读者我要写书评

暂无评论

PATTERN MATCHING WITH SWAPS IN PRACTICE

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2012年第2期23卷 323-342页

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Scuola Super Catania I-95123 Catania Italy Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we devise two general algorithms for both Standard and Approximate Pattern Matching with Swaps, named CROSS-SAMPLING and BACKWARD-CROSS-SAMPLING, with a O(nm) and O(nm(2)) worst-case time complexity, respectively. Then we provide efficient implementations of them, based on bit-parallelism, which achieve O(n) and O(nm) worst-case time complexity, with patterns v-hose length is comparable to the word-size of the target machine. From an extensive comparison with. some of the most Live algorithms for the matching problem, it turns out that our algorithms a) very flexible and achieve very good results in practice.

关键词： Approximate pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Approximate Pattern Matching with Swaps

An Efficient Algorithm for Approximate Pattern Matching with...

引用

14th Prague Stringology Conference (PSC)

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Scuola Super Catania I-95123 Catania Italy

ISBN: (纸本)9788001044032

The Pattern Matching problern with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks to compute, for every text location with a swapped match of P the number of swaps necessary to obtain a match at the location. in this paper, we present new efficient algorithms for the Approximatc, Swap Matching problem. In particular, we first present a O(nm(2)) algorithm, where fn is the length of the pattern and n is the length of the text, which is a variation of the BACKWARD-CROSSSAMPLING algorithm, a recent solution to the swap matching problem. Subsequently, we propose an efficient implementation of our algorithm, based on the bit-parallelism technique. The latter solution achieves a O(mn)-time and O(sigma)-space complexity, where a is the dimension of the alphabet. From an extensive comparison with some of the most recent and effective algorithms for the approximate swap matching problem, it turns out that our algorithms are very flexible and achieve very good results in practice.

关键词： approximate pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching 20th

引用

20th Conference on Foundations of Software Technology and Theoretical Computer Science

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel

ISBN: (纸本)3540414134

Let a text string T of n symbols and a pattern string P of rn symbols from alphabet Sigma be given. A swapped version P' of P is a length m string derived from P by a series of local swaps, (i.e. p'(l) <-- p(l+1) and p'(l+1) <-- p(l)) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i of T for which there exists a swapped version P' of P with an exact matching of P' in location i of T. Recently, some efficient algorithms were developed for this problem. Their time complexity is better than the best known algorithms for pattern matching with mismatches. However, the Approximate Pattern Matching with Swaps problem was not known to be solved faster than the pattern matching with mismatches problem. In the Approximate Pattern Matching with Swaps problem the output is, for every text location i where there is a swapped match of P, the number of swaps necessary to create the swapped version that matches location i. The fastest known method to-date is that of counting mismatches and dividing by two. The time complexity of this method is O(n rootm log m) for a general alphabet Sigma. In this paper we show an algorithm that counts the number of swaps at every location where there is a swapped matching in time O(n log m log sigma), where sigma = min(m, \Sigma\). Consequently, the total time for solving the approximate pattern matching with swaps problem is O(f(n, m) + n log m log a), where f (n, m) is the time necessary for solving the pattern matching with swaps problem.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps nonstandard pattern matching approximate pattern matching.

来源：评论

学校读者我要写书评

暂无评论

A faster query algorithm for the text fingerprinting problem

A faster query algorithm for the text fingerprinting problem

引用

15th Annual European Symposium on algorithms (ESA 2007)

作者： Chan, Chi-Yuan Yu, Hung-, I Hon, Wing-Kai Wang, Biing-Feng Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan

ISBN: (纸本)9783540755197

Let S be a string over a finite, ordered alphabet E. For any substring S' of S, the set of distinct characters contained in S' is called its fingerprint. The text fingerprinting problem consists of constructing a data structure for the string S in advance, so that on given any input set C C E of characters, we can answer the following queries efficiently: (1) determine if C represents a fingerprint of some substrings in S;(2) find all maximal substrings of S whose fingerprint is equal to C. The best results known so far solved these two queries in Theta(\Sigma\) and Theta(\Sigma\ + K) time, respectively, where K is the number of maximal substrings. In this paper, we propose a new data structure that improves the time complexities of the two queries to O(\C\ log(\Sigma\/\C\)) and O(\C\ log(\Sigma\/\C\) + K) time, respectively, where the term \C\ log(\Sigma\/\C\) is always bounded by Theta(\Sigma\). This result answers the open problem proposed by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete algorithms 1 (2003) 409-421]. In addition, our data structure uses less storage than the existing solutions.

关键词： fingerprints combinatorial algorithms on words text indexing patricia trie

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for string matching with k mismatches

Faster algorithms for string matching with <i>k</i> mismatch...

引用

11th Annual ACM/SIAM Symposium on Discrete algorithms

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

ISBN: (纸本)0898714532

关键词： design and analysis of algorithms combinatorial algorithms on words approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：