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

AOBA: An Online Benchmark tool for algorithms in stringology 46

AOBA: An Online Benchmark tool for Algorithms in stringology

46th International Conference on Current Trends in Theory and Practice of Computer Science Doctoral Student Research Forum, SOFSEM-SRF 2020

作者： Wakimoto, Ryu Kobayashi, Satoshi Igarashi, Yuki Jargalsaikhan, Davaajav Hendrian, Diptarama Yoshinaka, Ryo Shinohara, Ayumi Graduate School of Information Sciences Tohoku University Japan

Experimental performance of an algorithm often has a big gap from its theoretical complexity analysis. It is necessary to understand the characteristics of the experimental performances of different algorithms for the same problem to select an appropriate algorithm depending on available computing resources and properties of input data. In this paper, we present AOBA, an integrated online platform for testing, evaluating, analyzing and comparing different algorithms for various types of string processing problems. New algorithms can be submitted to AOBA and will be evaluated with many test data. All experiments work on the web: everyone can use AOBA without any local environment for experiments. AOBA also includes a powerful in-browser visualizer for analyzing and comparing performances of algorithms. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Counting lyndon subsequences

arXiv

引用

arXiv 2021年

作者： Hirakawa, Ryo Nakashima, Yuto Inenaga, Shunsuke Takeda, Masayuki Department of Information Science and Technology Kyushu University Fukuoka Japan Department of Informatics Kyushu University Fukuoka Japan PRESTO Japan Science and Technology Agency Kawaguchi Japan

Counting substrings/subsequences that preserve some property (e.g., palindromes, squares) is an important mathematical interest in stringology. Recently, Glen et al. studied the number of Lyndon factors in a string. A string w = uv is called a Lyndon word if it is the lexicographically smallest among all of its conjugates vu. In this paper, we consider a more general problem "counting Lyndon subsequences". We show (1) the maximum total number of Lyndon subsequences in a string, (2) the expected total number of Lyndon subsequences in a string, (3) the expected number of distinct Lyndon subsequences in a string. Copyright © 2021, The Authors. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Absent Subsequences in Words

arXiv

引用

arXiv 2021年

作者： Kosche, Maria Koß, Tore Manea, Florin Siemer, Stefan Institute for Computer Science Georg-August University Göttingen Germany

An absent factor of a string w is a string u which does not occur as a contiguous sub-string (a.k.a. factor) inside w. We extend this well-studied notion and define absent subsequences: a string u is an absent subsequence of a string w if u does not occur as subsequence (a.k.a. scattered factor) inside w. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets;we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind;also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed. © 2021, CC BY.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and linear-time string matching algorithms based on the distances of q-gram occurrences

arXiv

引用

arXiv 2020年

作者： Kobayashi, Satoshi Hendrian, Diptarama Yoshinaka, Ryo Shinohara, Ayumi Graduate School of Information Sciences Tohoku University Japan

Given a text T of length n and a pattern P of length m, the string matching problem is a task to find all occurrences of P in T. In this study, we propose an algorithm that solves this problem in O((n + m)q) time considering the distance between two adjacent occurrences of the same q-gram contained in P. We also propose a theoretical improvement of it which runs in O(n+m) time, though it is not necessarily faster in practice. We compare the execution times of our and existing algorithms on various kinds of real and artificial datasets such as an English text, a genome sequence and a Fibonacci string. The experimental results show that our algorithm is as fast as the state-of-the-art algorithms in many cases, particularly when a pattern frequently appears in a text. Copyright © 2020, The Authors. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

An Efficient, Hybrid, Double-Hash string-Matching Algorithm

An Efficient, Hybrid, Double-Hash String-Matching Algorithm

引用

2019 IEEE Long Island Systems, Applications and Technology Conference, LISAT 2019

作者： Bicer, Mehmet Zhang, Xiaowen Department of Computer Science Graduate Center City University of New York 365 Fifth Avenue New YorkNY10016 United States Department of Computer Science College of Staten Island City University of New York 2800 Victory Blvd Staten IslandNY10314 United States

ISBN: (纸本)9781728121000

In this paper we show that combining some of the good features of the existing popular algorithms can be even more efficient. This new algorithm is hybrid as it employs features from Boyer-Moore-Horspool, Rabin-Karp and Raita algorithms. We compare the right most character as well as use two independent hash functions and no character by character checking - hence leaving a very small probability for a false positive result if there is any. The proposed algorithm particularly does well when the pattern is very long as it will skip checking character by character comparison. © 2019 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel BMH string matching algorithm based on OpenMP 21

A parallel BMH string matching algorithm based on OpenMP

引用

21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

作者： Qi, Xiao Liu, Bin Li, Yuancheng Du, Yanning Li, Yuxiang Niu, Dangdang College of Information Engineering Northwest A AND F University Yangling China School of Computer Science and Technology Xi'An University of Science and Technology Xi'an China

ISBN: (纸本)9781728120584

BMH(Boyer-Moore-Horspool) string matching algorithms have played an important role in the field of biological sequence alignment, text processing, spell checking, and computer virus signature matching. However, with the explosive growth of the data, the serial string matching algorithm is too slow to finish the matching task within an acceptable time. This paper proposed a parallel BMH string matching algorithm based on OpenMP. The parallelism of the BMH algorithm is first identified by theoretical analysis. Then, the sequential algorithm is designed as a parallel algorithm in a data-parallel form and the larger string matching task is divided into multiple sub-string matching tasks by partitioning strategy. Furthermore, using the thread-level parallel technique, each thread carries out string matching operations on different sub-string blocks in parallel. Compared with the serial BMH algorithm, the parallel BMH matching algorithm with 8 threads can achieve up to 3.53 times speedup. On the OpenMP platform, experimental results show that the proposed parallel algorithm can acquire a significant increase in speedup. Under the accuracy of ensuring the string matching, the optimal number of threads and the most optimal block segmentation scheme are obtained through experimental tests. It indicates that the OpenMP-based parallel BMH algorithm has excellent acceleration performance, and an advantageous application prospect in various field. © 2019 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Fuzzy string matching algorithm for spam detection in twitter 1

引用

2nd ISEA International Conference on Security and Privacy, ISEA-ISAP 2018

作者： Kumar, Alok Singh, Maninder Pais, Alwyn Roshan Information Security Research Lab Department of Computer Science and Engineering National Institute of Technology Karnataka SurathkalKarnataka India Department of Computer Science and Engineering Thapar University PatialaPunjab India

ISBN: (数字)9789811375613

ISBN: (纸本)9789811375606

In recent times one of the most popular Internet activity around the world is visiting online social websites. The number of users and time spent by users on these social networks is increasing exponentially. Moreover, users tend to rely on the trustworthiness of data present on these networks. But in wrong hands this trustworthiness can easily be exploited and used to spread spams. Users can easily be harassed by spam messages which waste time and can fool users to click on malicious links. Spam effects many different type of electronic communications including instant messaging, email and social networks. But due to open nature, huge user base and reliance on users for data, social networks are worst hit because of spams. To detect spams from the social networks it is desirable to find new unsupervised techniques which can save the training cost which is required in supervised techniques. In this article we present an unsupervised, distributed and decentralized technique to detect and remove spams from social networks. We present a new technique which uses fuzzy based method to detect spams, which can detect spams even from a single message stream. To handle huge data in networks, we implement our technique to work on MapReduce platform. © Springer Nature Singapore Pte Ltd. 2019.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Implementation of string Matching Algorithm in Customer Data PT. PLN (Persero) Krueng Geukueh District 1

Implementation of String Matching Algorithm in Customer Data...

引用

1st Workshop on Environmental Science, Society, and Technology, WESTECH 2018

作者： Sulaiman, Oris Krianto Waridha, Aldy Hendrawan, Dian Ekalestari, Susi Purwarno Suhendi, Andang Wulan, Sri Pardi Pratiwy, Devi Sahri, Zulfan Hariani, Safitri Siregar, Amrin Suhadi, Muhammad Fatih Siwi, Purwanto Asnani Manugeren, M. Pawiro, Muhammad Ali Nuzwaty Jamaluddin, Yanhar Syofyan Tarigan, Nur M Ridha Lukito, Alamsyah Susanti, Meri Sembiring, Metrilitna Br Matondang, Asnawati Habibullah Faculty of Engineering Universitas Islam Sumatera Utara Medan Indonesia Faculty of Agriculture Universitas Islam Sumatera Utara Medan Indonesia Faculty of Literature Universitas Islam Sumatera Utara Medan Indonesia Faculty of Social and Political Science Universitas Islam Sumatera Utara Medan Indonesia Faculty of Economics Universitas Islam Sumatera Utara Medan Indonesia Faculty of Medicine Universitas Islam Sumatera Utara Medan Indonesia Faculty of Teacher Training and Education Universitas Islam Sumatera Utara Medan Indonesia Faculty of Islamic Religion Universitas Islam Sumatera Utara Medan Indonesia

According with the development of information technology and the expand of the internet in the community, the need for computers is very important to support the increasingly high utilization of information technology. Processing data and information requires speed and accuracy of data, to achieve it, it is requires an information technology that can support work so the work becomes more effective and efficient. PT. PLN (Persero) Krueng Geukueh District is a company that runs in the area of electricity and provides services to the community in the provision of services related to electricity, which has a large number of customers. The process of managing customer data at PT. PLN (Persero) Krueng Geukueh District has used a customer data system, but still has a disadvantage of requiring more time in searching customer data, to solving this problem, the author designed the development of the system using the string matching algorithm method, which is one of the most important parts in various processes related to data and text types, one of which is the search for words in customer data. The performance of the string matching algorithm is to match a letters per letter with the keywords given by the staff. The results of this study indicate that by using this method, searching for customer data can be easier. With the development of this system, it is expected that staff or admin in the company can do the work more effectively and efficiently. © Published under licence by IOP Publishing Ltd.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel string Matching with Linear Array, Butterfly and Divide and Conquer Models

引用

Annals of Data Science 2018年第2期5卷 181-207页

作者： Raju, S. Viswanadha Reddy, K.K.V.V.S. Rao, Chinta Someswara Department of CSE JNTUHCEJ JNT University Hyderabad HyderabadTelangana India Rayalasheema University KurnoolAndhra Pradesh India Department of CSE SRKR Engineering College BhimavaramAndhra Pradesh India

string Matching is a technique of searching a pattern in a text. It is the basic concept to extract the fruitful information from large volume of text, which is used in different applications like text processing, information retrieval, text mining, pattern recognition, DNA sequencing and data cleaning etc.,. Though it is stated some of the simple mechanisms perform very well in practice, plenty of research has been published on the subject and research is still active in this area and there are ample opportunities to develop new techniques. For this purpose, this paper has proposed linear array based string matching, string matching with butterfly model and string matching with divide and conquer models for sequential and parallel environments. To assess the efficiency of the proposed models, the genome sequences of different sizes (10–100 Mb) are taken as input data set. The experimental results have shown that the proposed string matching algorithms performs very well compared to those of Brute force, KMP and Boyer moore string matching algorithms. © 2017, Springer-Verlag GmbH Germany.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms to compute the lyndon array revisited 23

Algorithms to compute the lyndon array revisited

引用

23rd Prague stringology Conference, PSC 2019

作者： Franek, Frantisek Liut, Michael Department of Computing and Software McMaster University Hamilton Canada

ISBN: (纸本)9788001066188

The motivation for having an efficient algorithm for identifying all maximal Lyndon substrings of a string comes from the work of Bannai et al. on the Runs Conjecture. In 2015, they resolved the conjecture by considering Lyndon roots of runs and they also presented a unique linear algorithm for computing all runs. The uniqueness of the algorithm lies in the fact that it relies on the knowledge of all maximal Lyndon substrings, while all other linear algorithms for runs rely on Lempel-Ziv factorization of the input string. A Lyndon array is a data structure that encodes the information of all maximal Lyndon substrings of a string. In a 2016 Prague stringology Conference paper, Franek et al. discussed various known algorithms for computing the Lyndon array. In 2015, in his Masters' thesis, Baier designed a linear algorithm for suffix sorting. Inspired by Phase II of Baier's algorithm, in a 2017 Prague stringology Conference paper, Franek et al. discussed the linear co-equivalency of sorting suffixes and sorting maximal Lyndon substrings. As noticed by C. Diegelmann, the first phase of Baier's algorithm identifies and sorts all maximal Lyndon substrings of the input string. Based on Phase I of Baier's algorithm, in a 2018 Prague stringology Conference paper, Franek et. al presented an elementary (in the sense of not relying on a pre-processed global data structure) linear algorithm for identifying and sorting all maximal Lyndon substrings. This paper revisits the subject of algorithms for the Lyndon array and closes off the series of our Prague stringology Conference contributions on the topic - it provides a simple overview of all currently known algorithms including the new development since 2016. In particular, it presents a detailed analysis of a new algorithm TRLA, and comparative measurements of three of the algorithms. © Proceedings of the Prague stringology Conference, PSC 2019. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：