Enhancing the Hunt-Szymanski Strategy for Longest Common Subsequence

improving the worst case performance of the hunt n.w
1 / 65
Embed
Share

Discover how Alberto Apostolico from Purdue University improved the worst-case performance of the Hunt-Szymanski strategy for finding the longest common subsequence of two strings. This algorithm offers enhanced efficiency and better worst-case scenarios compared to previous approaches, utilizing dominant matches and minimal candidates to optimize performance. Explore the advancements made in this algorithm and its implications for string sequence processing.

  • Algorithm
  • Performance
  • Longest Common Subsequence
  • Optimization
  • Efficiency
rayaanacharya
ant_bat Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. IMPROVING THE WORST-CASE PERFORMANCE OF THE HUNT- SZYMANSKI STRATEGY FOR THE LOGEST COMMON SUBSEQUENCE OF TWO STRINGS ALBERTO APOSTOLICO, DEPARTMENT OF COMPUTER SCIENCE, PURDUE UNIVERSITY. INFORMATION PROCESSING LETTERS 23 (1986) 63-69 REPORTER : CING-YAO CHEN DATE:2014/3/4

  2. ABSTRUCT Among the algorithms set up to date for finding the longest common subsequence of two strings, the one by Hunt and Szymanski exhibits the best known performance in favorable cases, but can be worse than any straightforward algorithm for a large variety of inputs. The new algorithm presented here pursues a schedule of primitive operations quite close to the one inherent to the Hunt-Szymanski strategy, but with substantially enhanced efficiency. In fact, the new algorithm improves on the former in two important respects. First, its worst case is never worse than linear in the product nm of the lengths of the two input strings. Second, its time bound does not always grow with the cardinality r of the set R of all pairs of matching positions of the input strings. Rather, it depends on the cardinality d of a specific subset of R, whose elements are called here dominant matches, and are elsewhere referred to as minimal candidates. This second improvement also appears of significance, since it seems that whenever r gets too close to mn, this forces d to be linear in m. The new algorithm requires standard preprocessing, and makes use of finger-trees. In a forthcoming paper, it will be shown among other things that the same performance can be achieved with simpler and handier auxiliary data structures.

  3. LCS A = abcdbb B = cbacbaaba k: [i,j] LCS Match: K-dominant: d:K-dominant l:LCS ,k<=l

  4. Algorithm HS

  5. Algorithm HS A a B THRESH m=6 b c d b b c b a c b a a b a n=9 LINK PTR MATCHLIST 1 2 3 4 5 6

  6. Algorithm HS A a B THRESH m=6 b c d b b c b a c b a a b a i=1 n=9 LINK PTR MATCHLIST 9, 7, 6, 3 1 2 3 4 5 6

  7. Algorithm HS A a B THRESH m=6 b c d b b c b a c b a a b a i=2 n=9 LINK PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 1 2 3 4 5 6

  8. Algorithm HS A a B THRESH m=6 b c d b b c b a c b a a b a i=6 n=9 LINK PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2

  9. Algorithm HS A a B THRESH 0 101010101010 m=6 b c d b b c b a c b a a b a n=9 LINK PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2

  10. Algorithm HS A a B THRESH 0 101010101010 m=6 b c d b b c b a c b a a b a i = 1 j = 9 n=9 LINK PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  11. Algorithm HS A a B THRESH 0 9 m=6 b c d b b c b a c b a a b a i = 1 j = 9 n=9 LINK 1010101010 1,9,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  12. Algorithm HS A a B THRESH 0 9 m=6 b c d b b c b a c b a a b a i = 1 j = 7 n=9 LINK 1010101010 1,9,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  13. Algorithm HS A a B THRESH 0 7 m=6 b c d b b c b a c b a a b a i = 1 j = 7 n=9 LINK 1010101010 1,7,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  14. Algorithm HS A a B THRESH 0 7 m=6 b c d b b c b a c b a a b a i = 1 j = 6 n=9 LINK 1010101010 1,7,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  15. Algorithm HS A a B THRESH 0 6 m=6 b c d b b c b a c b a a b a i = 1 j = 6 n=9 LINK 1010101010 1,6,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  16. Algorithm HS A a B THRESH 0 6 m=6 b c d b b c b a c b a a b a i = 1 j = 3 n=9 LINK 1010101010 1,6,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  17. Algorithm HS A a B THRESH 0 3 m=6 b c d b b c b a c b a a b a i = 1 j = 3 n=9 LINK 1010101010 1,3,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  18. Algorithm HS A a B THRESH 0 3 m=6 b c d b b c b a c b a a b a i = 2 j = 8 n=9 LINK 1010101010 1,3,null PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  19. Algorithm HS A a B THRESH 0 3 8 m=6 b c d b b c b a c b a a b a i = 2 j = 8 n=9 LINK 1,3,null 2,8,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  20. Algorithm HS A a B THRESH 0 3 8 m=6 b c d b b c b a c b a a b a i = 2 j = 5 n=9 LINK 1,3,null 2,8,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  21. Algorithm HS A a B THRESH 0 3 5 m=6 b c d b b c b a c b a a b a i = 2 j = 5 n=9 LINK 1,3,null 2,5,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  22. Algorithm HS A a B THRESH 0 3 5 m=6 b c d b b c b a c b a a b a i = 2 j = 2 n=9 LINK 1,3,null 2,5,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  23. Algorithm HS A a B THRESH 0 2 5 m=6 b c d b b c b a c b a a b a i = 2 j = 2 n=9 LINK 2,2,null 2,5,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  24. Algorithm HS A a B THRESH 0 2 5 m=6 b c d b b c b a c b a a b a i = 3 j = 4 n=9 LINK 2,2,null 2,5,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  25. Algorithm HS A a B THRESH 0 2 4 m=6 b c d b b c b a c b a a b a i = 3 j = 4 n=9 LINK 2,2,null 3,4,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  26. Algorithm HS A a B THRESH 0 2 4 m=6 b c d b b c b a c b a a b a i = 3 j = 1 n=9 LINK 2,2,null 3,4,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  27. Algorithm HS A a B THRESH 0 1 4 m=6 b c d b b c b a c b a a b a i = 3 j = 1 n=9 LINK 3,1,null 3,4,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=1 8, 5, 2 8, 5, 2

  28. Algorithm HS A a B THRESH 0 1 4 m=6 b c d b b c b a c b a a b a i = 5 j = 8 n=9 LINK 3,1,null 3,4,L1 10101010 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=3 8, 5, 2 8, 5, 2

  29. Algorithm HS A a B THRESH 0 1 4 8 m=6 b c d b b c b a c b a a b a i = 5 j = 8 n=9 LINK 3,1,null 3,4,L1 101010 5,8,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=3 8, 5, 2 8, 5, 2

  30. Algorithm HS A a B THRESH 0 1 4 8 m=6 b c d b b c b a c b a a b a i = 5 j = 5 n=9 LINK 3,1,null 3,4,L1 101010 5,9,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=3 8, 5, 2 8, 5, 2

  31. Algorithm HS A a B THRESH 0 1 4 5 m=6 b c d b b c b a c b a a b a i = 5 j = 5 n=9 LINK 3,1,null 3,4,L1 101010 5,5,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=3 8, 5, 2 8, 5, 2

  32. Algorithm HS A a B THRESH 0 1 4 5 m=6 b c d b b c b a c b a a b a i = 5 j = 2 n=9 LINK 3,1,null 3,4,L1 101010 5,5,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  33. Algorithm HS A a B THRESH 0 1 2 5 m=6 b c d b b c b a c b a a b a i = 5 j = 2 n=9 LINK 3,1,null 5,2,L1 101010 5,5,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  34. Algorithm HS A a B THRESH 0 1 2 5 m=6 b c d b b c b a c b a a b a i = 6 j = 8 n=9 LINK 3,1,null 5,2,L1 101010 5,5,L2 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=4 8, 5, 2 8, 5, 2

  35. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 8 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=4 8, 5, 2 8, 5, 2

  36. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 5 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=3 8, 5, 2 8, 5, 2

  37. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 k=2 8, 5, 2 8, 5, 2

  38. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2 k=4

  39. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2 k=4 b

  40. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2 k=4 b b

  41. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2 k=4 b b c

  42. Algorithm HS A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 6 j = 2 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR MATCHLIST 9, 7, 6, 3 8, 5, 2 4, 1 1 2 3 4 5 6 8, 5, 2 8, 5, 2 k=4 b b c b

  43. Worse Case A = B O(mn log n) a a a a a MATCHLIST 5, 4, 3, 2, 1 5, 4, 3, 2, 1 5, 4, 3, 2, 1 5, 4, 3, 2, 1 5, 4, 3, 2, 1 a 1 1 1 1 1 1 2 3 4 5 a 1 2 2 2 2 a 1 2 3 3 3 a 1 2 3 4 4 a 1 2 3 4 5

  44. Algorithm HS1

  45. Algorithm HS1 A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR a 7 a True (Active list) AMATCHLIST 3, 6, 7, 9 2, 5, 8 1, 4 a b c d b b c b

  46. Algorithm HS1 A a B THRESH 0 1 2 5 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR a 7 a True 5 (Active list) AMATCHLIST 3, 6, 7, 9 2, 5, 8 1, 4 a b c d b b c b

  47. Algorithm HS1 A a B THRESH 0 1 2 3 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 5,5,L2 6,8,L3 PTR a 7 3 a True 5 (Active list) AMATCHLIST 3, 6, 7, 9 2, 5, 8 1, 4 a b c d b b c b

  48. Algorithm HS1 A a B THRESH 0 1 2 3 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 7,3,L2 6,8,L3 PTR a 7 3 a True 5 (Active list) AMATCHLIST 3, 6, 7, 9 2, 5, 8 1, 4 a b c d b b c b

  49. Algorithm HS1 A a B THRESH 0 1 2 3 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 7,3,L2 6,8,L3 PTR a 7 3 a True 5 (Active list) AMATCHLIST 3, 6, 7, 9 2, 5, 8 1, 4 a b c d symb(bt) = b b b c b

  50. Algorithm HS1 A a B THRESH 0 1 2 3 8 m=6 b c d b b c b a c b a a b a i = 7 j = 3 n=9 LINK 3,1,null 5,2,L1 1010 7,3,L2 6,8,L3 PTR a 7 3 a True 5 (Active list) AMATCHLIST 6, 7, 9 2, 5, 8 1, 4 a b c d symb(bt) = b b b c b

Related


No related presentations.

More Related Content