logging in or signing up Klein Donato Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 375 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 09, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Boyer Moore Searches on Binary Texts: Boyer Moore Searches on Binary Texts Shmuel Tomi Klein Miri Kopel Ben-Nissan Bar Ilan University, ISRAEL AcceleratingSlide2: Outline Background and motivation Boyer Moore algorithm New binary variant Analysis Experiments SummarySlide3: Important application of Automata: PATTERN MATCHING KMP BDM BM Boyer & Moore this-is-a-sample-text--- pattern Match Backwards ! !Slide4: Mismatch – case 1: delta1 u b u a b does not occur in x x y Boyer – Moore AlgorithmSlide5: u b u a x y b occurs in x Mismatch – case 2: delta1 Boyer – Moore AlgorithmSlide6: u b u a x y Mismatch – case 3: delta2 u reoccurs in x preceded by c ≠ a Boyer – Moore AlgorithmSlide7: u b u a x y v Mismatch – case 4: delta2 Only a suffix v of u reoccurs in x Boyer – Moore AlgorithmSlide8: Boyer – Moore ExampleSlide9: Problems of Binary Boyer & Moore delta1 useless most work by delta1Slide10: Need for Binary Boyer & Moore Compressed Matching Given E(T) and P look for E(P) in E(T) rather than P in D(E(T)) Suggested Solution: BBBMM Blocked Binary Boyer Moore MatchingSlide11: BBBMMSlide12: ffghabdgttiocb sbgghj 01100010 01101010 BBBMM More information in binary case ASCII BINARYSlide13: BBBMM extended delta1 Slide14: BBBMM Total size of delta1 tables: If too large, use limit value Size of delta1 tables reduced toSlide15: BBBMM Original delta1 : increase of text pointer BBBMM delta1 : shift size Mismatch not in last block Correct[sh,j] Slide16: BBBMM delta2Slide17: Analysis Assumption : random input Reasonable for compressed text Expected # comparisons till mismatch: Bit-wise: Blocked: Slide18: Analysis Expected # bits shifted after mismatch: Bit-wise: M Blocked: M’Slide19: Experiments English Bible (2.5MB) World Factbook (1.5MB) Text: Huffman encoded Patterns: Random substrings of lengths 10 to 500 k = 8Slide20: Experiments: Average # comparisons between shifts Slide21: Experiments: Average size of shifts Bit-wiseSlide22: Experiments: Average # comparisons for 1000 bits Slide23: Experiments: Time to locate first occurrence (ms) Slide24: Summary Blocked variant of BM Faster than alternatives, Overhead 1-10 K Extensions: ASCII, words instead of charactersSlide25: Thank you ! You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Klein Donato Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 375 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 09, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Boyer Moore Searches on Binary Texts: Boyer Moore Searches on Binary Texts Shmuel Tomi Klein Miri Kopel Ben-Nissan Bar Ilan University, ISRAEL AcceleratingSlide2: Outline Background and motivation Boyer Moore algorithm New binary variant Analysis Experiments SummarySlide3: Important application of Automata: PATTERN MATCHING KMP BDM BM Boyer & Moore this-is-a-sample-text--- pattern Match Backwards ! !Slide4: Mismatch – case 1: delta1 u b u a b does not occur in x x y Boyer – Moore AlgorithmSlide5: u b u a x y b occurs in x Mismatch – case 2: delta1 Boyer – Moore AlgorithmSlide6: u b u a x y Mismatch – case 3: delta2 u reoccurs in x preceded by c ≠ a Boyer – Moore AlgorithmSlide7: u b u a x y v Mismatch – case 4: delta2 Only a suffix v of u reoccurs in x Boyer – Moore AlgorithmSlide8: Boyer – Moore ExampleSlide9: Problems of Binary Boyer & Moore delta1 useless most work by delta1Slide10: Need for Binary Boyer & Moore Compressed Matching Given E(T) and P look for E(P) in E(T) rather than P in D(E(T)) Suggested Solution: BBBMM Blocked Binary Boyer Moore MatchingSlide11: BBBMMSlide12: ffghabdgttiocb sbgghj 01100010 01101010 BBBMM More information in binary case ASCII BINARYSlide13: BBBMM extended delta1 Slide14: BBBMM Total size of delta1 tables: If too large, use limit value Size of delta1 tables reduced toSlide15: BBBMM Original delta1 : increase of text pointer BBBMM delta1 : shift size Mismatch not in last block Correct[sh,j] Slide16: BBBMM delta2Slide17: Analysis Assumption : random input Reasonable for compressed text Expected # comparisons till mismatch: Bit-wise: Blocked: Slide18: Analysis Expected # bits shifted after mismatch: Bit-wise: M Blocked: M’Slide19: Experiments English Bible (2.5MB) World Factbook (1.5MB) Text: Huffman encoded Patterns: Random substrings of lengths 10 to 500 k = 8Slide20: Experiments: Average # comparisons between shifts Slide21: Experiments: Average size of shifts Bit-wiseSlide22: Experiments: Average # comparisons for 1000 bits Slide23: Experiments: Time to locate first occurrence (ms) Slide24: Summary Blocked variant of BM Faster than alternatives, Overhead 1-10 K Extensions: ASCII, words instead of charactersSlide25: Thank you !