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

13th Prague Stringology Conference (PSC)

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

ISBN: (纸本)9788001041451

In this article we present two efficient variants of the BOM string matching algorithm which are more efficient and flexible than the original algorithm. We also present bit-parallel versions of them obtaining an efficient variant of the BNDM algorithm. Then we compare the newly presented algorithms with some of the most recent and effective string matching algorithms. It turns out that the new proposed variants are very flexible and achieve very good results, especially in the case of large alphabets.

关键词： String matching experimental algorithms text processing automaton

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fault Recovery in Wireless Networks: The Geometric Recolouring Approach

Fault Recovery in Wireless Networks: The Geometric Recolouri...

引用

9th International Symposium on experimental algorithms

作者： Meijer, Henk Nunez-Rodriguez, Yurai Rappaport, David Roosevelt Acad Middelburg Netherlands Queens Univ Kingston ON Canada

ISBN: (纸本)9783642131929

Duplication of information allows distributed systems to recover from data errors, or faults. If faults occur spontaneously, without notification, and disguised incorrect data blends in with correct data, their detection becomes non-trivial. Known solutions for fault recovery use monitoring mechanisms that compare the data in multiple nodes to infer the occurrence of faults. To this end, we propose a localized geometric approach to fault recovery in wireless networks. We compare our approach with a more traditional combinatorial approach that uses a majority rule. Our experiments show that our geometric approach is an improvement over the majority rule in some cases, whereas in the other cases a hybrid method that combines the best of both strategies is superior to each individual method.

关键词： fault recovery recolouring wireless networks computational geometry experimental algorithms localized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Space-Efficient Implementation of the Good-Suffix Heuristic

A Space-Efficient Implementation of the Good-Suffix Heuristi...

引用

Prague Stringology Conference (PSC)

作者： Cantone, Domenico Cristofaro, Salvatore Faro, Simone Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

We present an efficient variation of the good-suffix heuristic, firstly introduced in the well-known Boyer-Moore algorithm for the exact string matching problem. Our proposed variant uses only constant space, retainin... 详细信息

ISBN: (纸本)9788001045978

关键词： string matching experimental algorithms text-processing good-suffix rule costant-space algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Flexible and Efficient algorithms for Abelian Matching in Genome Sequence 7th

Flexible and Efficient Algorithms for Abelian Matching in Ge...

引用

7th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO)

作者： Faro, Simone Pavone, Arianna Univ Catania Dipartimento Matemat & Informat Viale Andrea Doria 6 I-95125 Catania Italy Univ Messina Dipartimento Sci Cognit Via Concez 6 I-98122 Messina Italy

ISBN: (纸本)9783030179380;9783030179373

Approximate matching in strings is a fundamental and challenging problem in computer science and in computational biology, and increasingly fast algorithms are highly demanded in many applications including text processing and dna sequence analysis. Recently efficient solutions to specific approximate matching problems on genomic sequences have been designed using a filtering technique, based on the general abelian matching problem, which firstly locates the set of all candidate matching positions and then perform an additional verification test on the collected positions. The abelian pattern matching problem consists in finding all substrings of a text which are permutations of a given pattern. In this paper we present a new class of algorithms based on a new efficient fingerprint computation approach, called Heap-Counting, which turns out to be fast, flexible and easy to be implemented. We prove that, when applied for searching short patterns on a dna sequence, our solutions have a linear worst case time complexity. In addition we present an experimental evaluation which shows that our newly presented algorithms are among the most efficient and flexible solutions in practice for the abelian matching problem in dna sequences.

关键词： Approximate string matching Abelian matching jumbled matching experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast-search: A new efficient variant of the Boyer-Moore string matching algorithm 1

引用

2nd International Workshop on experimental and Efficient algorithms

作者： Cantone, D Faro, S Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

ISBN: (数字)9783540448679

ISBN: (纸本)3540402055

We present a new variant of the Boyer-Moore string matching algorithm which, though not linear, is very fast in practice. We compare our algorithm with the Horspool, Quick Search, Mined Boyer-Moore, and Reverse Factor algorithms, which are among the fastest string matching algorithms for I practical uses. It turns out that our algorithm achieve very good results in terms of both time efficiency and number of character inspections, especially in the cases in which the patterns are very short.

关键词： string matching experimental algorithms text processing

来源：评论

学校读者我要写书评

暂无评论

Minimum spanning tree under explorable uncertainty in theory and experiments 16

Minimum spanning tree under explorable uncertainty in theory...

引用

16th Symposium on experimental algorithms, SEA 2017

作者： Focke, Jacob Megow, Nicole Meifiner, Julie Department of Computer Science University of Oxford Oxford United Kingdom Department of Mathematics and Computer Science University of Bremen Bremen Germany Institute of Mathematics Technical University of Berlin Berlin Germany

ISBN: (纸本)9783959770361

We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library. © Jacob Focke, Nicole Megow, and Julie Meifiner.

关键词： Competitive ratio experimental algorithms Explorable uncertainty MST

来源：评论

学校读者我要写书评

暂无评论

Improved characters distance sampling for online and offline text searching

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期946卷

作者： Faro, Simone Marino, Francesco Pio Pavone, Arianna Univ Catania Dept Math & Comp Sci Viale ADoria n6 I-95125 Catania Italy Univ Messina Dept Cognit Sci Via Concez n6 I-98121 Messina Italy

Sampled string matching is a very effective technique to reduce the search time for a pattern within a text at the cost of a small amount of additional memory, used for storing a partial index of the text. This approach has recently received some interest and has been applied to improve both online and offline string matching solutions, improving standard solutions by more than 50%. However, this improvement is currently only achievable in the case of texts on large-sized alphabets, and remains small (or absent) in the case of small-sized alphabets. In this article we propose an extension of the approach to text-sampling, known as Character Distance Sampling, to the case of small alphabets, obtaining an improvement of up to 98% compared to standard solutions in the case of online string matching. We also extend this approach to the case of offline string matching, introducing a sampled version of the suffix array, obtaining performances up to 5 times higher than the search obtained on the standard suffix array. Differently from what has been done by previous solutions, our idea is not based on the reduction of the number of indexed suffixes, but on the construction of the index directly on the sampled text. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Text processing experimental algorithms String matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：