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

^*Tämän työn vastaava kirjoittaja

Tietotekniikan laitos

Sheridan College Institute of Technology and Advanced Learning
Seneca College

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

Abstrakti

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.

Alkuperäiskieli	Englanti
Sivut	54-66
Sivumäärä	13
Julkaisu	Discrete Applied Mathematics
Vuosikerta	274
DOI - pysyväislinkit	https://doi.org/10.1016/j.dam.2018.05.028
Tila	Julkaistu - 15 maalisk. 2020
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Pääsy asiakirjaan

10.1016/j.dam.2018.05.028

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

@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

Abstrakti

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä