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

21st Prague stringology Conference, PSC 2017

作者： Grabowski, Szymon Kowalski, Tomasz Lodz University of Technology Institute of Applied Computer Science Al. Politechniki 11 Lódź90–924 Poland

ISBN: (纸本)9788001061930

Range Minimum Query (RMQ) is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, there are scenarios in which the number of queries, q, is rather small and given beforehand, which encourages to use a simpler approach. A recent work by Alzamel et al. starts with contracting the input array to a much shorter one, with its size proportional to q. In this work, we build upon their solution, speeding up handling small batches of queries by a factor of 3.8–7.8 (the gap grows with q). The key idea that helped us achieve this advantage is adapting the well-known Sparse Table technique to work on blocks, with speculative block minima comparisons. We also propose an even much faster (but possibly using more space) variant without the array contraction. © Czech Technical University in Prague, Czech Republic.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

DFC: Accelerating string Pattern Matching for Network Applications 13

DFC: Accelerating String Pattern Matching for Network Applic...

引用

13th USENIX Symposium on Networked Systems Design and Implementation (NSDI)

作者： Choi, Byungkwon Chae, Jongwook Jamshed, Muhammad Park, KyoungSoo Han, Dongsu Korea Adv Inst Sci & Technol Daejeon South Korea

ISBN: (纸本)9781931971294

Middlebox services that inspect packet payloads have become commonplace. Today, anyone can sign up for cloud-based Web application firewall with a single click. These services typically look for known patterns that might appear anywhere in the payload. The key challenge is that existing solutions for pattern matching have become a bottleneck because software packet processing technologies have advanced. The popularization of cloud-based services has made the problem even more critical. This paper presents an efficient multi-pattern string matching algorithm, called DFC. DFC significantly reduces the number of memory accesses and cache misses by using small and cache-friendly data structures and avoids instruction pipeline stalls by minimizing sequential data dependency. Our evaluation shows that DFC improves performance by 2.0 to 3.6 times compared to state-of-the-art on real traffic workload obtained from a commercial network. It also outperforms other algorithms even in the worst case. When applied to middlebox applications, such as network intrusion detection, anti-virus, and Web application firewalls, DFC delivers 57-160% improvement in performance.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel GPU-based hybrid string matching algorithm 2nd

Parallel GPU-based hybrid string matching algorithm

引用

2nd International Conference on Communication and Computer Engineering, ICOCOE 2015

作者： Kadhim, Hakim Adil Rashid, Nuraini Abdul Univerisity of Kufa Najaf Iraq Pusat Pengajian Sains Komputer Universiti Sains Malaysia Minden Pulau Pinang11800 Malaysia

ISBN: (纸本)9783319245829

string or pattern matching is an essential part of most computer applications that are widely used in text processors, Internet-based search engines and computer security. A key concept of string matching is identifying the existence of a pattern with m characters in a much longer text string. string matching operations are basic to many algorithms such as indexing algorithms, search algorithms and bioinformatics algorithms that are used in molecular biology, adopted pattern matching concept in their programming structure. Although the mathematical and algorithmic calculations of pattern matching algorithms are simple, they are still the main reason of a large ratio of the computational load in many applications This research proposes to parallelize a hybrid string matching algorithm called Maximum-Shift algorithm, by using CUDA device (GPU) to increase its speed up during the matching process. The parallel Maximum-Shift algorithm shows slight improvement over the sequential version in terms of running time, speed up rate and percentage of performance gain. © Springer International Publishing Switzerland 2016.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A novel multi pattern string matching algorithm with while shift 16

A novel multi pattern string matching algorithm with while s...

引用

2nd International Conference on Information and Communication Technology for Competitive Strategies, ICTCS 2016

作者： Rao, Chinta Someswara Viswanadha Raju, S. Department of CSE SRKR Engineering College China Amiram Bhimavaram Andhra Pradesh India Department of CSE JNTUHCEJ JNTUniversity HyderabadTelangana India

ISBN: (纸本)9781450339629

string matching plays a dominant role in digital computer world, because it is made up of huge digital information. Digital computer world users often face a problem to extract the relevant information from these huge digital data to their queries. Hence it requires efficient retrieval algorithms for retrieving relevant data from huge digital data. To retrieve relevant data, in this paper we proposed two retrieval algorithms called single pattern and multi pattern string matching algorithms with while shift. © 2016 ACM.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster batched range minimum queries

arXiv

引用

arXiv 2017年

作者： Grabowski, Szymon Kowalski, Tomasz Lodz University of Technology Institute of Applied Computer Science Al. Politechniki 11 Lodz90-924 Poland

Range Minimum Query (RMQ) is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, there are scenarios in which the number of queries, q, is rather small and given beforehand, which encourages to use a simpler approach. A recent work by Alzamel et al. starts with contracting the input array to a much shorter one, with its size proportional to q. In this work, we build upon their solution, speeding up handling small batches of queries by a factor of 3.8-7.8 (the gap grows with q). The key idea that helped us achieve this advantage is adapting the wellknown Sparse Table technique to work on blocks, with speculative block minima comparisons. We also propose an even much faster (but possibly using more space) variant without the array *** Codes 68W32 Copyright © 2017, The Authors. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries 1

引用

23rd International Symposium on string Processing and Information Retrieval (SPIRE)

作者： Crochemore, Maxime Iliopoulos, Costas S. Kociumaka, Tomasz Kundu, Ritu Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Walen, Tomasz Kings Coll London Dept Informat London England Univ Warsaw Fac Math Informat & Mech Warsaw Poland

ISBN: (数字)9783319460499

ISBN: (纸本)9783319460499;9783319460482

Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE queries have been known for over a decade. However, these algorithms assume a linearly-sortable integer alphabet. A recent breakthrough paper by Bannai et al. (SODA 2015) showed a link between the two notions: all the runs in a string can be computed via a linear number of LCE queries. The first to consider these problems over a general ordered alphabet was Kosolobov (Inf. Process. Lett., 2016), who presented an O(n(log n)(2/3))-time algorithm for answering O(n) LCE queries. This result was improved by Gawrychowski et al. (CPM 2016) to O(n log log n) time. In this work we note a special non-crossing property of LCE queries asked in the runs computation. We show that any n such non-crossing queries can be answered on-line in O(n alpha(n)) time, where alpha(n) is the inverse Ackermann function, which yields an O(n alpha(n))-time algorithm for computing runs.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Evaluation and improvement of fast algorithms for exact matching on genome sequences 3rd

Evaluation and improvement of fast algorithms for exact matc...

引用

3rd International Conference on algorithms for Computational Biology, AlCoB 2016

作者： Faro, Simone Dipartimento di Matematica e Informatica Universitá di Catania Viale A. Doria n.6 Catania95125 Italy

ISBN: (纸本)9783319388267

With the availability of large amounts of dna data, exact matching of nucleotide sequences has become an important application in modern computational biology and in meta-genomics. In the last decade several efficient solutions for the exact string matching problem have been developed and most of them are very fast in practical cases. However when the length of the pattern is short or the alphabet size is small (as in the case of dna sequences) the problem becomes more difficult to be solved efficiently. In this paper we review and compare the most efficient solutions for the online exact matching problem appeared in the latest years when applied for searching on genome sequences. In addition we also propose some new variants of an efficient string matching algorithm. From our experimental results it turns out that the newly presented variants are very fast in most practical cases. © Springer International Publishing Switzerland 2016.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the all-pairs suffix-prefix problem

An improved algorithm for the all-pairs suffix-prefix proble...

引用

作者： Tustumi, William H.A. Gog, Simon Telles, Guilherme P. Louza, Felipe A. Institute of Computing University of Campinas Campinas SP Brazil Institute of Theoretical Informatics Karlsruhe Institute of Technology Germany

Finding all longest suffix-prefix matches for a collection of strings is known as the all pairs suffix-prefix match problem and its main application is de novo genome assembly. This problem is well studied in stringology and has been solved optimally in 1992 by Gusfield et al. [8] using suffix trees. In 2010, Ohlebusch and Gog [13] proposed an alternative solution based on enhanced suffix arrays which has also optimal time complexity but is faster in practice. In this article, we present another optimal algorithm based on enhanced suffix arrays which further improves the practical running time. Our new solution solves the problem locally for each string, scanning the enhanced suffix array backwards to avoid the processing of suffixes that are no suffix-prefix matching candidates. In an empirical evaluation we observed that the new algorithm is over two times faster and more space-efficient than the method proposed by Ohlebusch and Gog. When compared to Readjoiner [5], a good practical solution, our algorithm is faster for small overlap lengths, in pace with theoretical optimality. © 2016 Elsevier B.V.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Open-domain question answering framework using wikipedia 29th

引用

29th Australasian Joint Conference on Artificial Intelligence, AI 2016

作者： Ameen, Saleem Chung, Hyunsuk Han, Soyeon Caren Kang, Byeong Ho School of Engineering and ICT TAS7005 Australia

ISBN: (纸本)9783319501260

This paper explores the feasibility of implementing a model for an open domain, automated question and answering framework that leverages Wikipedia’s knowledgebase. While Wikipedia implicitly comprises answers to common questions, the disambiguation of natural language and the difficulty of developing an information retrieval process that produces answers with specificity present pertinent challenges. However, observational analysis suggests that it is possible to discount the syntactical and lexical structure of a sentence in contexts where questions contain a specific target entity (words that identify a person, location or organisation) and that correspondingly query a property related to it. To investigate this, we implemented an algorithmic process that extracted the target entity from the question using CRF based named entity recognition (NER) and utilised all remaining words as potential properties. Using DBPedia, an ontological database of Wikipedia’s knowledge, we searched for the closest matching property that would produce an answer by applying standardised string matching algorithms including the Levenshtein distance, similar text and Dice’s coefficient. Our experimental results illustrate that using Wikipedia as a knowledgebase produces high precision for questions that contain a singular unambiguous entity as the subject, but lowered accuracy for questions where the entity exists as part of the object. © Springer International Publishing AG 2016.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A syntactic approach for detecting viral polymorphic malware variants 11th

A syntactic approach for detecting viral polymorphic malware...

引用

11th Pacific Asia Workshop on Intelligence and Security Informatics, PAISI 2016

作者： Naidu, Vijay Narayanan, Ajit School of Computer and Mathematical Sciences Auckland University of Technology Auckland New Zealand

ISBN: (纸本)9783319318622

Polymorphic malware is currently difficult to identify. Such malware is able to mutate into functionally equivalent variants of themselves. Modern detection techniques are not adequate against this rapidly-mutating polymorphic malware. The age-old approach of signature-based detection is the only one that has the highest detection rate in real time and is used by almost all antivirus software products. The process of current signature extraction has so far been by manual evaluation. Even the most advanced malware detection process which employs heuristic-based approaches requires progressive evaluation and modification by humans to keep up with new malware variants. The aim of the research reported here is to investigate efficient and effective techniques of string matching algorithm for the automatic identification of some or all new polymorphic malware. We demonstrate how our proposed syntactic-based approach using the well-known string matching Smith-Waterman algorithm can successfully detect the known polymorphic variants of *** virus. Our string-matching approach may revolutionize our understanding of polymorphic variant generation and may lead to a new phase of syntactic-based anti-viral software. © Springer International Publishing Switzerland 2016.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：