Sökning: id:"swepub:oai:DiVA.org:umu-206269" >
Quantum leap patter...
Quantum leap pattern matching : a new high performance quick search-style algorithm
-
- Watson, Bruce W. (författare)
- FASTAR Research Group, Department of Information Science, Stellenbosch University, Matieland, South Africa; Centre for Artificial Intelligence Research, CSIR Meraka Institute, South Africa
-
- Kourie, Derrick G. (författare)
- FASTAR Research Group, Department of Information Science, Stellenbosch University, Matieland, South Africa; Centre for Artificial Intelligence Research, CSIR Meraka Institute, South Africa
-
- Cleophas, Loek (författare)
- Umeå universitet,Institutionen för datavetenskap,FASTAR Research Group, Department of Information Science, Stellenbosch University, Matieland, South Africa
-
(creator_code:org_t)
- Prague Stringology Club, 2015
- 2015
- Engelska.
-
Ingår i: Proceedings of the Prague Stringology Conference 2015, PSC 2015. - : Prague Stringology Club. - 9788001057872 ; , s. 104-117
- Relaterad länk:
-
https://dblp.org/db/...
-
visa fler...
-
http://www.stringolo...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Boyer-moore algorithms
- Faster pattern matching
- High-speed pattern matching single keyword matching
- Sunday's algorithm
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas