Improved online algorithms for jumbled matching

Sukhpal Singh Ghuman; Jorma Tarhio; Tamanna Chhabra

doi:10.1016/j.dam.2018.05.028

Improved online algorithms for jumbled matching

Sukhpal Singh Ghuman
, Jorma Tarhio^*
, Tamanna Chhabra

^*Corresponding author for this work

Department of Computer Science

Sheridan College
Seneca College

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

Abstract

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.

Original language	English
Pages (from-to)	54-66
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	274
DOIs	https://doi.org/10.1016/j.dam.2018.05.028
Publication status	Published - 15 Mar 2020
MoE publication type	A1 Journal article-refereed

Keywords

Abelian matching
Algorithm engineering
Approximate string matching
Comparison of algorithms
Jumbled matching
SIMD computation

Access to Document

10.1016/j.dam.2018.05.028

Cite this

@article{418696d095cb454a8658bc5ba9a7a234,

title = "Improved online algorithms for jumbled matching",

abstract = "We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.",

keywords = "Abelian matching, Algorithm engineering, Approximate string matching, Comparison of algorithms, Jumbled matching, SIMD computation",

author = "Ghuman, \{Sukhpal Singh\} and Jorma Tarhio and Tamanna Chhabra",

year = "2020",

month = mar,

day = "15",

doi = "10.1016/j.dam.2018.05.028",

language = "English",

volume = "274",

pages = "54--66",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Improved online algorithms for jumbled matching

AU - Ghuman, Sukhpal Singh

AU - Tarhio, Jorma

AU - Chhabra, Tamanna

PY - 2020/3/15

Y1 - 2020/3/15

N2 - We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.

AB - We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.

KW - Abelian matching

KW - Algorithm engineering

KW - Approximate string matching

KW - Comparison of algorithms

KW - Jumbled matching

KW - SIMD computation

UR - https://www.scopus.com/pages/publications/85048557903

U2 - 10.1016/j.dam.2018.05.028

DO - 10.1016/j.dam.2018.05.028

M3 - Article

AN - SCOPUS:85048557903

SN - 0166-218X

VL - 274

SP - 54

EP - 66

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Improved online algorithms for jumbled matching

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this