# Klein

75 %
25 %
Education

Published on January 9, 2008

Author: Donato

Source: authorstream.com

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 !

 User name: Comment:

July 21, 2017

August 23, 2017

July 26, 2017

August 23, 2017

August 23, 2017

August 23, 2017

## Related pages

### eBay Kleinanzeigen | Kostenlos. Einfach. Lokal. Anzeigen ...

Kostenlose Anzeigen aufgeben mit eBay Kleinanzeigen. Gebraucht oder Neu, Privat oder Gewerbe - Jetzt gratis inserieren auf Deutschlands meistbesuchtem ...

### klein – Wiktionary

Dieser Eintrag oder Abschnitt bedarf einer Erweiterung. Wenn du Lust hast, beteilige dich daran und entferne diesen Baustein, sobald du den Eintrag ...

### Klein – Wikipedia

klein steht für: Kleine Kategorie, ein Begriff der Kategorientheorie; Siehe auch: Cline; Felix Klein Prize; Klein-Gordon-Gleichung (Oskar Klein) Klein ...

### Duden | klein | Rechtschreibung, Bedeutung, Definition ...

Definition, Rechtschreibung, Synonyme und Grammatik von 'klein' auf Duden online nachschlagen. Wörterbuch der deutschen Sprache.

### Klein (Familienname) – Wikipedia

Der Familienname Klein entstand als Übername (Eigenschaftsname) wahrscheinlich nach der Körpergröße oder auch nach Eigenschaften, die von der früheren ...

### Login - Anmelden bei eBay Kleinanzeigen

Nutzen Sie diese Seite für den Login bei eBay Kleinanzeigen. eBay Kleinanzeigen. Kostenlos. Einfach. Lokal.

### Konrad Kleiner GmbH & Co. KG - KLEINER, Fachgrosshandel in ...

Herzlich Willkommen bei der Firma Kleiner Ihr Fachgroßhandel in Mindelheim, Kempten, Kaufbeuren, Ehingen und Ulm

### dict.cc | klein | Wörterbuch Englisch-Deutsch

Übersetzung für klein im Englisch-Deutsch-Wörterbuch dict.cc.