Scout Algorithm For Fast Substring Matching
- URL: http://arxiv.org/abs/2011.04010v1
- Date: Sun, 8 Nov 2020 16:09:20 GMT
- Title: Scout Algorithm For Fast Substring Matching
- Authors: Anand Natrajan, Mallige Anand
- Abstract summary: Exact matching is a common task in many software applications.
We present a new algorithm, Scout, that is straightforward, quick and appropriate for all applications.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Exact substring matching is a common task in many software applications.
Despite the existence of several algorithms for finding whether or not a
pattern string is present in a target string, the most common implementation is
a na\"ive, brute force approach. Alternative approaches either do not provide
enough of a benefit for the added complexity, or are impractical for modern
character sets, e.g., Unicode. We present a new algorithm, Scout, that is
straightforward, quick and appropriate for all applications. We also compare
the performance characteristics of the Scout algorithm with several others.
Related papers
- A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings.
In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions.
Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
arXiv Detail & Related papers (2024-07-17T21:26:27Z) - string2string: A Modern Python Library for String-to-String Algorithms [24.167017445129105]
string2string is an open-source library that offers a comprehensive suite of efficient algorithms for string-to-string problems.
It includes traditional algorithmic solutions as well as recent advanced neural approaches to tackle various problems in string alignment, distance measurement, lexical and semantic search, and similarity analysis.
It is implemented in Python, easily installable via pip, and accessible through a simple API.
arXiv Detail & Related papers (2023-04-27T17:57:19Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges.
We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric.
We show that in practice, automated search can find substantial improvements to the initial program.
arXiv Detail & Related papers (2021-09-14T20:52:55Z) - Determinantal Beam Search [75.84501052642361]
Beam search is a go-to strategy for decoding neural sequence models.
In use-cases that call for multiple solutions, a diverse or representative set is often desired.
By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
arXiv Detail & Related papers (2021-06-14T13:01:46Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order.
We propose an $O(n3/4)$ quantum query algorithm for LMSR.
arXiv Detail & Related papers (2020-12-17T03:13:45Z) - Quantum Algorithms for String Processing [58.720142291102135]
We provide a quantum algorithm for the String matching problem that uses exponentially less quantum memory than existing ones.
Using the same ideas, we provide two algorithms for the String comparing problem.
The second algorithm works exponentially faster than the existing one.
arXiv Detail & Related papers (2020-12-01T09:59:06Z) - Towards Meta-Algorithm Selection [78.13985819417974]
Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates.
We show that meta-algorithm-selection can indeed prove beneficial in some cases.
arXiv Detail & Related papers (2020-11-17T17:27:33Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.