advertisement

Klein

75 %
25 %
advertisement
Information about Klein
Education

Published on January 9, 2008

Author: Donato

Source: authorstream.com

advertisement

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 !

Add a comment

Related presentations

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 ...
Read more

klein – Wiktionary

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

Klein – Wikipedia

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

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

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

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 ...
Read more

Login - Anmelden bei eBay Kleinanzeigen

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

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

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

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

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

Fachgroßhandel - Wilhelm Klein GmbH - Wilhelm Klein GmbH

Wilhelm Klein GmbH in Wilnsdorf. Als Fachgroßhandel für Sauberkeit, Hygiene und Frische sind wir in einer gemeinsamen Kette von effizienten Abläufen mit ...
Read more

Immobilienfinanzierung mit Beratung vor Ort

Immobilienfinanzierung einfach und verständlich: Glücklichmacher-Zinsen, Alles-klar-Rechner und immer einen Berater an Ihrer Seite - das ist Dr. Klein!
Read more