algorithm - When would you use KMP over BOYER-MOORE -


i learning pattern matching algorithms , have come across these 2 algorithms. have following general ideas:

kmp

  • compares text left-to-right
  • uses failure array shift intelligently
  • takes o(m), m length of pattern, compute failure array
  • takes o(m), space
  • takes o(n), time search string

bm

  • compares pattern last character
  • uses bad character jumps , suffix jumps
  • takes o(m + size of alphabet) compute tables
  • takes o(m + size of alphabet), space
  • takes o(n), better search

i came across following question triggered question(true or false):

the knuth-morris-pratt (kmp) algorithm choice if want search same pattern repeatedly in many different texts.

so believe answer true because assumption every time run algorithm on different text preprocessing o(n) bm o(n + size of alphabet). however, not sure if making correct assumption every time algorithm rerun new table recomputed. because text falls in alphabet of english. need compute table once , reuse table. @ end of day, answer question dependent on fact algorithms being run on text contained in same alphabet or there other factor may affect it?

in theory, both algorithms have "similar" performance; kmp 2n comparisons in searching phase , boyer-moore 3n comparisons in searching phase in worst case. in neither case need repeat preprocessing when new text.

but real answer shouldn't use either 1 in practice.

the linear auxiliary storage needed both algorithms leads considerably...rougher performance on modern architectures because of of memory accesses.

however, ideas behind boyer-moore , kmp underpin fast string matching algorithms. kmp's "failure function" idea used every practically effective string matching algorithm know of; turns out can compute suboptimal "failure function" pattern on-the-fly still gives linear time matching while needing constant additional space. boyer-moore faster linear in "average case" of matching fixed pattern against random noise, , bears out in many practical situations.


Comments

Post a Comment

Popular posts from this blog

Why does Ruby on Rails generate add a blank line to the end of a file? -

running rails generate controller foo home results in: class foocontroller < application controller def home end end (there's nothing on line in actual file, blank line) is there purpose blank line? it's common use newline indicate end of line, last line. many editors (like vi, use) add in newline silently. consensus text files (especially in unix world) should end in newline, , there have been problems historically if wasn't present. why should text files end newline? the tool used count lines in file "wc" counts newlines in file, without trailing newline show 3 instead of 4. it improves readability of templates used in generator. consider: https://github.com/rails/rails/blob/master/railties/lib/rails/generators/rails/controller/templates/controller.rb to remove trailing newline, template have last line of: end<% end -%> instead of: end <% end -%> that seems less readable me. the discussion below refers ...
Read more

keyboard - Smiles and long press feature in Android -

i've created android keyboard. how add features inserting smilies, , using long keypresses display symbols? to create long-press behavior allows select several options pop-up menu, follow guide (specifically pop-up menu section): http://developer.android.com/guide/topics/ui/menus.html smileys (also known emoticons) combination of keys, understood programs , parsed same way. have do, when clicks smiley face on keyboard, simulate pressing of key combination matching emoticon. example, when clicks smiley, should simulate key presses ':' , ')' :). here's list of emoticons: http://en.wikipedia.org/wiki/list_of_emoticons
Read more

node.js - Bad Request - node js ajax post -

i'm using express 3.0 , node v0.11.0. have button submits form , i'm using ajax post data json object node server. client code is: $('#contact').submit(function(e) { console.log('submit called'); var formdata = json.stringify($('form').serializeobject()); console.log(formdata); $.ajax({ url: "http://localhost:3000/savedata/", type: "post", datatype: 'json', data: {objectdata: formdata}, contenttype: "application/json", complete: function() { console.log('process complete'); }, success: function(data) { console.log('process sucess'); }, error: function() { console.log('process error'); }, }); return false; }); then on server: var express = require('express'); var app = express(); app.set('views', __dirname + '/views'); app.set('view engine', 'jade'); app.use(express.bodyparser());...
Read more