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

16th International Workshop on combinatorial Image Analysis (IWCIA)

作者： Brimkov, Valentin E. SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA

ISBN: (纸本)9783319071480;9783319071473

In this talk we discuss on parallel computation approach to two-dimensional combinatorial pattern matching. The latter features numerous applications in pattern recognition, low level image processing, computer vision and, more recently, multimedia. After introducing some basic notions and concepts and recalling related key facts, we briefly discuss the basic steps of a parallel algorithm design, illustrating them by author's results on the problem of detecting all two-dimensional repetitions in a two-dimensional array.

关键词： combinatorial pattern matching two-dimensional array tandem parallel algorithm CRCW-PRAM divide and conquer

来源：评论

学校读者我要写书评

暂无评论

A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation

引用

THEORETICAL COMPUTER SCIENCE 2009年第51期410卷 5317-5333页

作者： Hundt, Christian Liskiewicz, Maciej Nevries, Ragnar Univ Rostock Inst Informat D-2500 Rostock 1 Germany Univ Lubeck Inst Theoret Informat Lubeck Germany

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F is to find matches of transformed versions f (P) of a pattern P in a given text T, for all f in F. In this paper, pattern matching invariant under compositions of real valued scaling and rotation are investigated. We give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. Subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. The algorithm works in time O(m(2) n(6)) for patterns of size m(2) and texts of size n(2). We conclude with an experimental section to support the practical use of our results. (C) 2009 Elsevier B.V. All rights reserved.

关键词： combinatorial pattern matching Digital image matching Discrete rotations and scalings Discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate pattern matching and transitive closure logics

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期299卷 387-412页

作者： Lemström, K Hella, L Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Univ Helsinki Dept Math FIN-00014 Helsinki Finland

A sartorial query language facilitates the formulation of queries to a (string) database. One step towards an implementation of such a query language can be taken by defining a logical formalism expressing a known solution for the particular problem at hand. The simplicity of the logic is a desired property, because the simpler the logic that the query language is based on, the more efficiently it can be implemented. We introduce a logical formalism for expressing approximate pattern matching. The formalism uses properties of the dynamic programming approach;a minimizing path of a dynamic programming table is expressed by using a formula in an extension of first order logic (FO). We consider the well-known problems of k-mismatches and k-differences. Assuming first that k is given as a part of the input, those problems are expressed by using deterministic transitive closure logic (FO(DTC)) and transitive closure logic (FO(TC)), respectively. We show how to adapt the formalisms to allow individual costs for the editing operations, and consider music information retrieval (MIR) as a case study. We believe that in the general case k-differences is not expressible in FO(DTC). However, we show that proving this is at least as hard as separating LOGSPACE from NLOGSPACE. On the other hand, we show that if k is fixed, the k-differences problem can be expressed by an FO(DTC) formula. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： logic in computing combinatorial pattern matching music information retrieval

来源：评论

学校读者我要写书评

暂无评论

pattern matching with Variables: Efficient Algorithms and Complexity Results

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2020年第1期12卷 6-6页

作者： Fernau, Henning Manea, Florin Mercas, Robert Schmid, Markus L. Univ Trier Fachbereich 4 Abt Informat Wissensch Trier Germany Univ Trier FB 4 Abt Informat D-54286 Trier Germany Gottingen Univ Inst Comp Sci Goldschmidtstr 7 D-37077 Gottingen Germany Loughborough Univ Dept Comp Sci Haslegrave Bldg Loughborough LE11 3TU Leics England Rudower Chaussee 25 D-12489 Berlin Adlershof Germany

A pattern alpha (i.e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of alpha by terminal words. The respective matching problem, i.e., deciding whether or not a given pattern matches a given word, is generally NP-complete, but can be solved in polynomial-time for restricted classes of patterns. We present efficient algorithms for the matching problem with respect to patterns with a bounded number of repeated variables and patterns with a structural restriction on the order of variables. Furthermore, we show that it is NP-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors. As an immediate consequence of this hardness result, the injective version (i.e., different variables are replaced by different words) of the matching problem is NP-complete even for very restricted classes of patterns.

关键词： combinatorial pattern matching combinatorics on words patterns with variables NP-complete string problems

来源：评论

学校读者我要写书评

暂无评论

Multi-pattern matching with bidirectional indexes

引用

JOURNAL OF DISCRETE ALGORITHMS 2014年第0期24卷 26-39页

作者： Gog, Simon Karhu, Kalle Karkkainen, Juha Makinen, Veli Valimaki, Niko Univ Melbourne Dept Comp & Informat Syst Melbourne Vic Australia Aalto Univ Dept Comp Sci & Engn Espoo Finland Univ Helsinki Dept Comp Sci Helsinki Finland

We study multi-pattern matching in a scenario where the pattern set is to be matched to several texts and hence indexing the pattern set is affordable. This kind of scenarios arise, for example, in metagenomics, where pattern set represents DNA of several species and the goal is to find out which species are represented in the sample and in which quantity. We develop a generic search method that exploits bidirectional indexes both for the pattern set and texts, and analyze the best and worst case running time of the method on worst case text. We show that finding the instance of the search method with minimum best case running time on worst case text is NP-hard. The positive result is that an instance with logarithm factor approximation to minimum best case running time can be found in polynomial time using a bidirectional index called affix tree. We further show that affix trees can be simulated, in reduced space, using bidirectional variant of compressed suffix trees. Lastly, we provide a practical implementation of this approach. We show that one can obtain 3-fold speed up against the basic scenario of searching each pattern independently with data sets typical in high-throughput DNA sequencing. (C) 2013 Elsevier B.V. All rights reserved.

关键词： combinatorial pattern matching Compressed data structures Computational genomics

来源：评论

学校读者我要写书评

暂无评论

pattern matching with Variables: Fast Algorithms and New Hardness Results 32

Pattern Matching with Variables: Fast Algorithms and New Har...

引用

32nd International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fernau, Henning Manea, Florin Mercas, Robert Schmid, Markus L. Univ Trier Fachbereich Abt Informat Wissensch 4 D-54286 Trier Germany Univ Kiel Dept Comp Sci D-24098 Kiel Germany

ISBN: (纸本)9783939897781

A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words;deciding this is NP-complete. We present efficient algorithms(1) that solve this problem for restricted classes of patterns. Furthermore, we show that it is NP-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors;this shows that the injective version (i. e., different variables are replaced by different words) of the above matching problem is NP-complete even for very restricted cases.

关键词： combinatorial pattern matching combinatorics on words patterns with variables NP-complete string problems

来源：评论

学校读者我要写书评

暂无评论

Two-dimensional pattern matching with combined scaling and rotation

引用

19th Annual Symposium on combinatorial pattern matching

作者： Hundt, Christian Liskiewicz, Maciej Univ Rostock Inst Informat D-2500 Rostock 1 Germany Univ Lubeck Inst Theoret Informat Lubeck Germany

ISBN: (纸本)9783540690665

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F is to find in text T matches of transformed versions f (P) of the pattern P, for all f in F. In this paper, pattern matching invariant under compositions of real scaling and rotation are investigated. We give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. Subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. The algorithm works in time O(m(2)n(6)) for patterns of size m(2) and texts of size n(2). Our method can also be applied to the image matching problem, the well known issue in the image processing research.

关键词： combinatorial pattern matching digital image matching discrete rotations and scalings discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Longest repeats with a block of k don't cares

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期362卷 248-254页

作者： Crochemore, Maxime Iliopoulos, Costas S. Mohamed, Manal Sagot, Marie-France Kings Coll London Dept Comp Sci London WC2R 2LS England Univ Marne la Vallee Inst Gaspard Monge F-77454 Marne La Vallee 2 France Univ Lyon 1 INRIA Rhone Alpes Lab Biometrie & Biol Evolut F-69622 Villeurbanne France

A k-repeat is a string w(k) = u* (k)v that matches more than one substring of x, where is the don't care letter and k > 0. We propose an O(n log n)-time algorithm for computing all longest k-repeats in a given string x = x[l..n]. The proposed algorithm uses suffix trees to fulfill this task and relies on the ability to answer lowest common ancestor queries in constant time. (C) 2006 Elsevier B.V. All rights reserved.

关键词： combinatorial pattern matching string repeat don't care

来源：评论

学校读者我要写书评

暂无评论

A Linear-Time Algorithm for Hamming Distance with Shifts

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期44卷 349-355页

作者： Jiang, Minghui Utah State Univ Dept Comp Sci Logan UT 84322 USA

The Hamming distance with shifts was introduced by Bookstein et al. as a generalization of the traditional Hamming distance to allow a tunable degree of fuzziness when comparing two binary sequences of the same length... 详细信息

关键词： Hamming distance Swap distance String algorithm combinatorial pattern matching

来源：评论

学校读者我要写书评

暂无评论

Unified Compression-Based Acceleration of Edit-Distance Computation

引用

ALGORITHMICA 2013年第2期65卷 339-353页

作者： Hermelin, Danny Landau, Gad M. Landau, Shir Weimann, Oren Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Haifa Dept Comp Sci IL-31999 Haifa Israel NYU Poly Dept Comp Sci & Engn New York NY USA Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic programming solution for this problem computes the edit-distance between a pair of strings of total length O(N) in O(N (2)) time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well under a particular compression scheme. The basic idea is to first compress the strings, and then to compute the edit distance between the compressed strings. As it turns out, practically all known o(N (2)) edit-distance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single edit-distance algorithm that works for strings which are compressed under any compression scheme. A rephrasing of this question is to ask whether a single algorithm can exploit the compressibility properties of strings under any compression method, even if each string is compressed using a different compression. In this paper we set out to answer this question by using straight line programs. These provide a generic platform for representing many popular compression schemes including the LZ-family, Run-Length Encoding, Byte-Pair Encoding, and dictionary methods. For two strings of total length N having straight-line program representations of total size n, we present an algorithm running in O(nNlg(N/n)) time for computing the edit-distance of these two strings under any rational scoring function, and an O(n (2/3) N (4/3)) time algorithm for arbitrary scoring functions. Our new result, while providing a speed up for compressible strings, does not surpass the quadratic time bound even in the worst case scenario.

关键词： combinatorial pattern matching Edit-distance Straight-line-programming Data compression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：