Klein

Information about Klein

Published on January 9, 2008

Author: Donato

Source: authorstream.com

Content

Boyer Moore Searches on Binary Texts:  Boyer Moore Searches on Binary Texts Shmuel Tomi Klein Miri Kopel Ben-Nissan Bar Ilan University, ISRAEL Accelerating Slide2:  Outline Background and motivation Boyer Moore algorithm New binary variant Analysis Experiments Summary Slide3:  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 Algorithm Slide5:  u b u a x y b occurs in x Mismatch – case 2: delta1 Boyer – Moore Algorithm Slide6:  u b u a x y Mismatch – case 3: delta2 u reoccurs in x preceded by c ≠ a Boyer – Moore Algorithm Slide7:  u b u a x y v Mismatch – case 4: delta2 Only a suffix v of u reoccurs in x Boyer – Moore Algorithm Slide8:  Boyer – Moore Example Slide9:  Problems of Binary Boyer & Moore delta1 useless most work by delta1 Slide10:  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 Matching Slide11:  BBBMM Slide12:  ffghabdgttiocb sbgghj 01100010 01101010 BBBMM More information in binary case ASCII BINARY Slide13:  BBBMM extended delta1 Slide14:  BBBMM Total size of delta1 tables: If too large, use limit value Size of delta1 tables reduced to Slide15:  BBBMM Original delta1 : increase of text pointer BBBMM delta1 : shift size Mismatch not in last block Correct[sh,j] Slide16:  BBBMM delta2 Slide17:  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 = 8 Slide20:  Experiments: Average # comparisons between shifts Slide21:  Experiments: Average size of shifts Bit-wise Slide22:  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 characters Slide25:  Thank you !

Related presentations


Other presentations created by Donato

The Rise of Dictators
20. 04. 2008
0 views

The Rise of Dictators

csharp
21. 02. 2008
0 views

csharp

Conference Brochure web
10. 01. 2008
0 views

Conference Brochure web

P17 Biljakovic
11. 01. 2008
0 views

P17 Biljakovic

10 02 ed406a
12. 01. 2008
0 views

10 02 ed406a

Physical descriptions Bible
13. 01. 2008
0 views

Physical descriptions Bible

4 Mining
14. 01. 2008
0 views

4 Mining

Role of Race and Ethnicity
14. 01. 2008
0 views

Role of Race and Ethnicity

main stream school as a deaf
14. 01. 2008
0 views

main stream school as a deaf

InfantWellness
15. 01. 2008
0 views

InfantWellness

434 L18 Marine Pollution 07
15. 01. 2008
0 views

434 L18 Marine Pollution 07

WinRDBI
16. 01. 2008
0 views

WinRDBI

Alexander von Humboldt fertig
17. 01. 2008
0 views

Alexander von Humboldt fertig

Mesa Teen Dating Violence65466
17. 01. 2008
0 views

Mesa Teen Dating Violence65466

water LCHS
17. 01. 2008
0 views

water LCHS

galileo new
17. 01. 2008
0 views

galileo new

Colonies Powerpoint
19. 01. 2008
0 views

Colonies Powerpoint

OSTP Lewis
21. 01. 2008
0 views

OSTP Lewis

pptEarlyBCNewspapers
21. 01. 2008
0 views

pptEarlyBCNewspapers

SumerOL
22. 01. 2008
0 views

SumerOL

Whole Show Welch 2007
23. 01. 2008
0 views

Whole Show Welch 2007

JC NIH INRIA160407ppt
05. 02. 2008
0 views

JC NIH INRIA160407ppt

Wedding Presentation email
05. 02. 2008
0 views

Wedding Presentation email

InfoSec120804 web 2
04. 02. 2008
0 views

InfoSec120804 web 2

The Civil War Era
12. 02. 2008
0 views

The Civil War Era

Psychotherapy
28. 01. 2008
0 views

Psychotherapy

energysecurity
06. 02. 2008
0 views

energysecurity

david35
07. 02. 2008
0 views

david35

Fichner Rathus CH09
11. 02. 2008
0 views

Fichner Rathus CH09

wipo smes ge 07 www 81572
12. 02. 2008
0 views

wipo smes ge 07 www 81572

rpc dae
09. 01. 2008
0 views

rpc dae

Android Idea
25. 02. 2008
0 views

Android Idea

Peds Asthma
28. 02. 2008
0 views

Peds Asthma

Cubism
03. 03. 2008
0 views

Cubism

ppt00022
04. 02. 2008
0 views

ppt00022

George Mucibabici Deloitte
07. 03. 2008
0 views

George Mucibabici Deloitte

African Culture
10. 01. 2008
0 views

African Culture

04 TransmissionMedia
24. 03. 2008
0 views

04 TransmissionMedia

Performance Driven Government
31. 03. 2008
0 views

Performance Driven Government

i20083241155
14. 04. 2008
0 views

i20083241155

Israel Paralympics
16. 04. 2008
0 views

Israel Paralympics

MDiazGELSS2003
17. 01. 2008
0 views

MDiazGELSS2003

Skarb sport reng
22. 04. 2008
0 views

Skarb sport reng

H105l
14. 01. 2008
0 views

H105l

f7
07. 02. 2008
0 views

f7

Hood Canal CD Final 25Jan08 1
24. 04. 2008
0 views

Hood Canal CD Final 25Jan08 1

US Fed Indian Policy
11. 03. 2008
0 views

US Fed Indian Policy

Introduccion al Fast Track
06. 05. 2008
0 views

Introduccion al Fast Track

CHINA ROHS SEMI CONWEST redick
07. 05. 2008
0 views

CHINA ROHS SEMI CONWEST redick

obrien
08. 05. 2008
0 views

obrien

GMO EU Bans
08. 05. 2008
0 views

GMO EU Bans

audvotpowpoint
30. 04. 2008
0 views

audvotpowpoint

Abo dar3 hav mots
07. 02. 2008
0 views

Abo dar3 hav mots

vpbusiness 2004
11. 02. 2008
0 views

vpbusiness 2004

Beauty
08. 03. 2008
0 views

Beauty

LA STEM pres5
16. 01. 2008
0 views

LA STEM pres5

Polarhide And Roof Heat Edited
25. 01. 2008
0 views

Polarhide And Roof Heat Edited

Games2
22. 01. 2008
0 views

Games2

tvp urg
17. 01. 2008
0 views

tvp urg

wombwithaview
08. 01. 2008
0 views

wombwithaview

Proposal slides
08. 04. 2008
0 views

Proposal slides

corporate partnership
22. 01. 2008
0 views

corporate partnership

POA June 2006
10. 01. 2008
0 views

POA June 2006

LifeShapes 1
29. 01. 2008
0 views

LifeShapes 1

Clavel
22. 01. 2008
0 views

Clavel