Browsing by Author "Ghuman, Sukhpal Singh"
Now showing 1 - 3 of 3
- Results Per Page
- Sort Options
- Improved Online Algorithms for Jumbled Matching
School of Science | Doctoral dissertation (monograph)(2017) Ghuman, Sukhpal SinghIn Computer Science, the problem of finding the occurrences of a given string is a common task. There are many different variations of the problem. We consider the problem of jumbled pattern matching (JPM) (also known as Abelian pattern matching or permutation matching) where the objective is to find all permuted occurrences of a pattern in a text. Jumbled pattern matching has numerous applications in the field of bioinformatics. For instance, jumbled matching can be used to find those genes that are closely related to one another. Besides exact jumbled matching we study approximate jumbled matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bitparallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Furthermore, we have developed a bitparallel algorithm for episode matching. This algorithm finds the maximal parallel episodes of a given sequence. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions. - Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä(2019-06) Ghuman, Sukhpal Singh; Giaquinta, Emanuele; Tarhio, JormaWe present two modifications of Duval's algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length rho, the other algorithm computes the Lyndon factorization of R in O (rho) time and in constant space. It is shown by experimental results that the new variations are faster than Duval's original algorithm in many scenarios. - String searching with mismatches using AVX2 and AVX-512 instructions
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä(2025-03) Chhabra, Tamanna; Ghuman, Sukhpal Singh; Tarhio, JormaWe present new algorithms for the k mismatches version of approximate string matching. Our algorithms utilize the SIMD (Single Instruction Multiple Data) instruction set extensions, particularly AVX2 and AVX-512 instructions. Our approach is an extension of an earlier algorithm for exact string matching with SSE2 and AVX2. In addition, we modify this exact string matching algorithm to work with AVX-512. We demonstrate the competitiveness of our solutions by practical experiments. Our algorithms outperform earlier algorithms for both exact and approximate string matching on various benchmark data sets.