Quantum leap pattern matching

B.W. Watson, D.G. Kourie, L. Cleophas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

Quantum leap matching is introduced as a generic pattern matching strategy for the single keyword exact pattern matching problem, that can be used on top of existing Boyer-Moore-style string matching algorithms. The cost of the technique is minimal: an additional shift table (of one dimension, for shifts in the opposite direction to the parent algorithm’s shifts), and the replacement of a simple table lookup assignment statement in the original algorithm with a similar conditional assignment. Together with each of the conventional shift table lookups, the additional shift table is typically also indexed on the text character that is at a distance of z away from the current sliding window. Under conditions that are identified, the returned values from the two shift tables allow a “quantum leap” of distance more than the length of the keyword for the next matching attempt. If the conditions are not met, then there is a fall back is to the traditional shift. Quick Search (by Sunday) is used as a case study to illustrate the technique. The performance of the derived “Quantum Leap Quick Search” algorithm is compared against Quick Search. When searching for shorter patterns over natural language and genomic texts, the technique improves on Quick Search’s time for most values of z. Improvements are also sometimes seen for various values of z on larger patterns. Most interestingly, under best case conditions it performs, on average, at about three times faster than Quick Search.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015
EditorsJ. Holub, J. Žďárek
Place of PublicationPrague
PublisherPrague Stringology Club
Pages104-117
Number of pages14
ISBN (Print)978-80-01-05787-2
Publication statusPublished - 2015
EventPrague Stringology Conference 2015 - Department of Theoretical Computer Science, Prague, Czech Republic
Duration: 24 Aug 201526 Aug 2015

Conference

ConferencePrague Stringology Conference 2015
CountryCzech Republic
CityPrague
Period24/08/1526/08/15

Fingerprint

Pattern matching
String searching algorithms
Table lookup
Costs

Cite this

Watson, B. W., Kourie, D. G., & Cleophas, L. (2015). Quantum leap pattern matching. In J. Holub, & J. Žďárek (Eds.), Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015 (pp. 104-117). Prague: Prague Stringology Club.
Watson, B.W. ; Kourie, D.G. ; Cleophas, L. / Quantum leap pattern matching. Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015. editor / J. Holub ; J. Žďárek. Prague : Prague Stringology Club, 2015. pp. 104-117
@inproceedings{aa4ba38a5a8b405f832fda27ed69a8a9,
title = "Quantum leap pattern matching",
abstract = "Quantum leap matching is introduced as a generic pattern matching strategy for the single keyword exact pattern matching problem, that can be used on top of existing Boyer-Moore-style string matching algorithms. The cost of the technique is minimal: an additional shift table (of one dimension, for shifts in the opposite direction to the parent algorithm’s shifts), and the replacement of a simple table lookup assignment statement in the original algorithm with a similar conditional assignment. Together with each of the conventional shift table lookups, the additional shift table is typically also indexed on the text character that is at a distance of z away from the current sliding window. Under conditions that are identified, the returned values from the two shift tables allow a “quantum leap” of distance more than the length of the keyword for the next matching attempt. If the conditions are not met, then there is a fall back is to the traditional shift. Quick Search (by Sunday) is used as a case study to illustrate the technique. The performance of the derived “Quantum Leap Quick Search” algorithm is compared against Quick Search. When searching for shorter patterns over natural language and genomic texts, the technique improves on Quick Search’s time for most values of z. Improvements are also sometimes seen for various values of z on larger patterns. Most interestingly, under best case conditions it performs, on average, at about three times faster than Quick Search.",
author = "B.W. Watson and D.G. Kourie and L. Cleophas",
year = "2015",
language = "English",
isbn = "978-80-01-05787-2",
pages = "104--117",
editor = "J. Holub and J. Žď{\'a}rek",
booktitle = "Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015",
publisher = "Prague Stringology Club",

}

Watson, BW, Kourie, DG & Cleophas, L 2015, Quantum leap pattern matching. in J Holub & J Žďárek (eds), Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015. Prague Stringology Club, Prague, pp. 104-117, Prague Stringology Conference 2015, Prague, Czech Republic, 24/08/15.

Quantum leap pattern matching. / Watson, B.W.; Kourie, D.G.; Cleophas, L.

Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015. ed. / J. Holub; J. Žďárek. Prague : Prague Stringology Club, 2015. p. 104-117.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Quantum leap pattern matching

AU - Watson, B.W.

AU - Kourie, D.G.

AU - Cleophas, L.

PY - 2015

Y1 - 2015

N2 - Quantum leap matching is introduced as a generic pattern matching strategy for the single keyword exact pattern matching problem, that can be used on top of existing Boyer-Moore-style string matching algorithms. The cost of the technique is minimal: an additional shift table (of one dimension, for shifts in the opposite direction to the parent algorithm’s shifts), and the replacement of a simple table lookup assignment statement in the original algorithm with a similar conditional assignment. Together with each of the conventional shift table lookups, the additional shift table is typically also indexed on the text character that is at a distance of z away from the current sliding window. Under conditions that are identified, the returned values from the two shift tables allow a “quantum leap” of distance more than the length of the keyword for the next matching attempt. If the conditions are not met, then there is a fall back is to the traditional shift. Quick Search (by Sunday) is used as a case study to illustrate the technique. The performance of the derived “Quantum Leap Quick Search” algorithm is compared against Quick Search. When searching for shorter patterns over natural language and genomic texts, the technique improves on Quick Search’s time for most values of z. Improvements are also sometimes seen for various values of z on larger patterns. Most interestingly, under best case conditions it performs, on average, at about three times faster than Quick Search.

AB - Quantum leap matching is introduced as a generic pattern matching strategy for the single keyword exact pattern matching problem, that can be used on top of existing Boyer-Moore-style string matching algorithms. The cost of the technique is minimal: an additional shift table (of one dimension, for shifts in the opposite direction to the parent algorithm’s shifts), and the replacement of a simple table lookup assignment statement in the original algorithm with a similar conditional assignment. Together with each of the conventional shift table lookups, the additional shift table is typically also indexed on the text character that is at a distance of z away from the current sliding window. Under conditions that are identified, the returned values from the two shift tables allow a “quantum leap” of distance more than the length of the keyword for the next matching attempt. If the conditions are not met, then there is a fall back is to the traditional shift. Quick Search (by Sunday) is used as a case study to illustrate the technique. The performance of the derived “Quantum Leap Quick Search” algorithm is compared against Quick Search. When searching for shorter patterns over natural language and genomic texts, the technique improves on Quick Search’s time for most values of z. Improvements are also sometimes seen for various values of z on larger patterns. Most interestingly, under best case conditions it performs, on average, at about three times faster than Quick Search.

M3 - Conference contribution

SN - 978-80-01-05787-2

SP - 104

EP - 117

BT - Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015

A2 - Holub, J.

A2 - Žďárek, J.

PB - Prague Stringology Club

CY - Prague

ER -

Watson BW, Kourie DG, Cleophas L. Quantum leap pattern matching. In Holub J, Žďárek J, editors, Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015. Prague: Prague Stringology Club. 2015. p. 104-117