Facebook Instagram Twitter RSS Feed PodBean Back to top on side

A hybrid algorithm for the longest common transposition-invariant subsequence problem

In: Computing and Informatics, vol. 28, no. 5
S. Deorowicz - S. Grabowski

Details:

Year, pages: 2009, 729 - 744
Keywords:
Longest common transposition-invariant subsequence (LCTS), bit- parallelism, sparse dynamic programming, string matching
About article:
The longest common transposition-invariant subsequence (LCTS) problem is a music information retrieval oriented variation of the classic LCS problem. There are basically only two known efficient approaches to calculate the length of the LCTS, one based on sparse dynamic programming and the other on bit-parallelism. In this work, we propose a hybrid algorithm picking the better of the two algorithms for individual subproblems. Experiments on music (MIDI), with 32-bit and 64-bit implementations, show that the proposed algorithm outperforms the faster of the two component algorithms by a factor of 1.4–2.0, depending on sequence lengths. Similar, if not better, improvements can be observed for random data with Gaussian distribution. Also for uniformly random data, the hybrid algorithm is the winner if the alphabet is neither too small (at least 32 symbols) nor too large (up to 128 symbols). Part of the success of our scheme is attributed to a quite robust component selection heuristic.
How to cite:
ISO 690:
Deorowicz, S., Grabowski, S. 2009. A hybrid algorithm for the longest common transposition-invariant subsequence problem. In Computing and Informatics, vol. 28, no.5, pp. 729-744. 1335-9150.

APA:
Deorowicz, S., Grabowski, S. (2009). A hybrid algorithm for the longest common transposition-invariant subsequence problem. Computing and Informatics, 28(5), 729-744. 1335-9150.