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

Efficient algorithms for the Order Preserving Pattern Matching Problem 1

11th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dept Math & Comp Sci Catania Italy Istanbul Tech Univ Inst Informat Istanbul Turkey

ISBN: (数字)9783319411682

ISBN: (纸本)9783319411682;9783319411675

Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM, which might be viewed as an approximate variant of the well known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in a lot of fields as from time series analysis, like share prices on stock markets or weather data analysis, to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods by reducing the number of false positives up to 99%. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions.

关键词： Approximate text analysis experimental algorithms Filtering algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

A Very Fast String Matching Algorithm Based on Condensed Alphabets 1

引用

11th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Faro, Simone Univ Catania Viale A Doria 6 I-95125 Catania Italy

ISBN: (数字)9783319411682

ISBN: (纸本)9783319411682;9783319411675

String matching is the problem of finding all the substrings of a text which correspond to a given pattern. It's one of the most investigated problem in computer science, mainly due to its various applications in many fields. In recent years most solutions to the problem focused on efficiency and flexibility of the searching procedure and effective techniques appeared to speed-up previous solutions. In this paper we present a simple and very efficient algorithm for string matching. It can be seen as an extension of the Skip-Search algorithm to condensed alphabets with the aim of reducing the number of verifications during the searching phase. From our experimental results it turns out that the new variant obtains in most cases the best running time when compared against the most effective algorithms in literature. This makes the new algorithm one of the most flexible solutions in practical cases.

关键词： Exact text analysis String matching experimental algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

experimental evaluation of various register-pressure-reduction heuristics

引用

SOFTWARE-PRACTICE & EXPERIENCE 2015年第11期45卷 1497-1517页

作者： Shobaki, Ghassan Sakka, Laith Abu Rmaileh, Najm Eldeen Al-Hamash, Hasan Princess Sumaya Univ Technol Amman Jordan

Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre-allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre-allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large-scale programs. In this paper, we present an experimental study that evaluates the performance of several pre-allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open-source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86-64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86-64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction-level parallelism (ILP). This result shows the importance of ILP in pre-allocation scheduling even on out-of-order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance;even the best heuristic in the study produces s

关键词： compiler optimizations instruction scheduling register pressure reduction spill code minimization performance optimization combinatorial optimization NP-complete problems experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybrid string matching algorithm with a pivot

引用

JOURNAL OF INFORMATION SCIENCE 2015年第1期41卷 82-88页

作者： Al-Ssulami, Abdulrakeeb M. King Saud Univ Riyadh 11543 Saudi Arabia

Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an efficient algorithm is an outstanding issue. In this paper, we present a simple and practical string matching algorithm. The proposed algorithm is a hybrid that combines our modification of Horspool's algorithm with two observations on string matching. The algorithm scans the text from left to right and matches the pattern from right to left. experimental results on natural language texts, genomes and human proteins demonstrate that the new algorithm is competitive with practical algorithms.

关键词： Design of algorithms experimental algorithms online string searching

来源：评论

学校读者我要写书评

暂无评论

Implicit Generation of Pattern-Avoiding Permutations by Using Permutation Decision Diagrams

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1171-1179页

作者： Inoue, Yuma Toda, Takahisa Minato, Shin-ichi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan JST ERATO MINATO Discrete Struct Manipulat Syst P Sapporo Hokkaido 0600814 Japan

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

关键词： pattern-avoiding permutations generating algorithms decision diagrams pi DD experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

An Efficient Method for Indexing All Topological Orders of a Directed Graph 25

An Efficient Method for Indexing All Topological Orders of a...

引用

25th International Symposium on algorithms and Computation (ISAAC)

作者： Inoue, Yuma Minato, Shin-ichi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido Japan JST ERATO MINATO Discrete Struct Manipulat Syst Project Sapporo Hokkaido Japan

ISBN: (纸本)9783319130750;9783319130743

Topological orders of a directed graph are an important concept of graph algorithms. The generation of topological orders is useful for designing graph algorithms and solving scheduling problems. In this paper, we generate and index all topological orders of a given graph. Since topological orders are permutations of vertices, we can use the data structure pi DD, which generates and indexes a set of permutations. In this paper, we propose Rot-pi DDs, which are a variation of pi DDs based on a different interpretation. Compression ratios of Rot-pi DDs for representing topological orders are theoretically improved from the original pi DDs. We propose an efficient method for constructing a Rot-pi DD based on dynamic programming approach. Computational experiments show the amazing efficiencies of a Rot-pi DD: a Rot-pi DD for 3.7 x 10(41) topological orders has only 2.2 x 10(7) nodes and is constructed in 36 seconds. In addition, the indexed structure of a Rot-pi DD allows us to fast post-process operations such as edge addition and random samplings.

关键词： Topological orders Linear extensions Permutations Decision diagrams Enumerating algorithms experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved and self-tuned occurrence heuristics

引用

JOURNAL OF DISCRETE algorithms 2014年第0期28卷 73-84页

作者： Cantone, Domenico Faro, Simone Univ Catania Dipartimento Matemat & Informat Catania Italy

In this note we present three efficient variations of the occurrence heuristic, adopted by many exact string matching algorithms and first introduced in the well-known Boyer-Moore algorithm. Our first heuristic, called improved-occurrence heuristic, is a simple improvement of the rule introduced by Sunday in his Quick-Search algorithm. Our second heuristic, called worst-occurrence heuristic, achieves its speed-up by selecting the relative position which yields the largest average advancement. Finally, our third heuristic, called jumping-occurrence heuristic, uses two characters for computing the next shift. Setting the distance between these two characters optimally allows one to maximize the average advancement. The worst-occurrence and jumping-occurrence heuristics tune their parameters according to the distribution of the characters in the text. experimental results show that the newly proposed heuristics achieve very good results on average, especially in the case of small alphabets. (C) 2014 Elsevier B.V. All rights reserved.

关键词： String matching experimental algorithms Text-processing Occurrence heuristics Frequency of characters Tuned-search approach

来源：评论

学校读者我要写书评

暂无评论

Fast and flexible packed string matching

引用

JOURNAL OF DISCRETE algorithms 2014年第0期28卷 61-72页

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat Catania Italy Istanbul Medipol Univ Fac Engn & Nat Sci Istanbul Turkey

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design a very fast string matching algorithm. We evaluate our solution in terms of efficiency, stability and flexibility, where we propose to use the deviation in running time of an algorithm on distinct equal length patterns as a measure of stability. From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithm becomes the clear winner on the average in many cases, when compared against the most recent and effective algorithms known in literature. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Exact string matching Text algorithms experimental algorithms Online searching Information retrieval

来源：评论

学校读者我要写书评

暂无评论

Towards a Very Fast Multiple String Matching Algorithm for Short Patterns

Towards a Very Fast Multiple String Matching Algorithm for S...

引用

8th Prague Stringology Conference (PSC)

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat I-95124 Catania Italy TUBTAK Natl Res Inst Elect & Cryptol Gebze Turkey

ISBN: (纸本)9788001053300

Multiple exact string matching is one of the fundamental problems in computer science and finds applications in many other fields, among which computational biology and intrusion detection. It turns out that short patterns appear in many instances of such problems and, in most cases, sensibly affect the performances of the algorithms. Recent solutions in the field of string matching try to exploit the power of the word RAM model to speed-up the performances of classical algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. This study presents a first preliminary attempt to develop a filter based exact multiple string matching algorithm for searching set of short patterns by taking benefit from Intel's SSE (streaming SIMD extensions) technology. Our experimental results on small, medium, and large alphabet text files show that the proposed algorithm is competitive in the case of short patterns against other efficient solutions, which are known to be among the fastest in practice.

关键词： multiple string matching experimental algorithms text-processing short patterns Streaming SIMD Extensions Technology SSE

来源：评论

学校读者我要写书评

暂无评论

Improved and Self-Tuned Occurrence Heuristics.

Improved and Self-Tuned Occurrence Heuristics.

引用

8th Prague Stringology Conference (PSC)

作者： Cantone, Domenico Faro, Simone Univ Catania Dipartimento Matemat & Informat Viale Andrea Doria 6 I-95125 Catania Italy

ISBN: (纸本)9788001053300

In this note we present three efficient variations of the occurrence heuristic, adopted by many exact string matching algorithms and firstly introduced in the well-known Boyer-Moore algorithm. Our first heuristic, called improved-occurrence heuristic, is a simple improvement of the rule introduced by Sunday in his Quick- Search algorithm. Our second heuristic, called worst-occurrence heuristic, achieves its speed-up by selecting the relative position which yields the largest average advancement. Finally, our third heuristic, called jumping-occurrence heuristic, uses two characters for computing the next shift, whose distance allows one to maximize the average advancement. The worst-occurrence and jumping-occurrence heuristics tune their parameters according to the text characters' distribution. experimental results show that the new proposed heuristics achieve very good results on average, especially in the case of small alphabets.

关键词： string matching experimental algorithms text-processing occurrence heuristics frequency of characters tuned-search approach

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：