3 ms·

String searching is interesting in that the naive algorithm is quadratic-ish: imagine searching for “aaaab” in the string “aaaaaaaaaaaa” by comparing the charac

by joppy 5y ago

String searching is interesting in that the naive algorithm is quadratic-ish: imagine searching for “aaaab” in the string “aaaaaaaaaaaa” by comparing the characters 1-5, then 2-6, and so on. So at least some kind of clever insight needs to be used so as to not hit quadratic behaviour - some mechanical way of deciding that a chunk of the input can be skipped after being read. The value of extra skips (not examining some of the input) is debatable, but these algorithms are still very much relevant when wanting to avoid accidentally-quadratic behaviour.

lofi_lory 5y ago
Naive BM goes quadratic at T: aaaaaaaaaaaa P: xaaaaa Not easy to come up with an improvement, there will always be that exception you didn't think of XD I wonder, if you could derive meta information about the DNA "lyrical" composition by observing the BM put through. After all the algorithm assumes random text.
- taeric 5y ago
  I thought it was implicit that you build a jump table based on the string. That is, BM isn't just "search from the end." It includes the push down automata.
  - lofi_lory 5y ago
    Yes, I am not contesting or anything, but my example shows how the original BC and GS rules don't protect you from quadratic worst case complexity either. That's my point, it's not easy to do sub-quadratic worst case search. I haven't recently looked into the sub-quadratic worst case improved version of BM, but IIRC it's far from trivial and not what most people think of for this algorithm. I assume it's also slower IRL, for cache misses, or for expensive operations like modulo in the main loop, and prolly has a space penalty. BM just has a better average case than naive string search.
    - taeric 5y ago
      Burntsushi has plenty of data showing it isn't the best nowadays. Pretty sure any version that goes quadratic is bite BM, though. Not that you are wrong, but just highlighting that most folks don't think of BM when they think they are, though.
- joppy 5y ago
  Straightforward Boyer-Moore is worst case O(nm), but (I believe) there are modifications that make it linear time. There are other string searching algorithms like Knuth-Morris-Pratt which are linear in the size of the two inputs. My point was that non-naive string searching algorithms absolutely do matter, and that no amount of cache-efficiency is going to save an implementation from hitting the quadratic behaviour intrinsic to a naive algorithm.

by joppy 5y ago

lofi_lory 5y ago

Naive BM goes quadratic at T: aaaaaaaaaaaa P: xaaaaa Not easy to come up with an improvement, there will always be that exception you didn't think of XD I wonder, if you could derive meta information about the DNA "lyrical" composition by observing the BM put through. After all the algorithm assumes random text.

taeric 5y ago
I thought it was implicit that you build a jump table based on the string. That is, BM isn't just "search from the end." It includes the push down automata.
- lofi_lory 5y ago
  Yes, I am not contesting or anything, but my example shows how the original BC and GS rules don't protect you from quadratic worst case complexity either. That's my point, it's not easy to do sub-quadratic worst case search. I haven't recently looked into the sub-quadratic worst case improved version of BM, but IIRC it's far from trivial and not what most people think of for this algorithm. I assume it's also slower IRL, for cache misses, or for expensive operations like modulo in the main loop, and prolly has a space penalty. BM just has a better average case than naive string search.
  - taeric 5y ago
    Burntsushi has plenty of data showing it isn't the best nowadays. Pretty sure any version that goes quadratic is bite BM, though. Not that you are wrong, but just highlighting that most folks don't think of BM when they think they are, though.
joppy 5y ago
Straightforward Boyer-Moore is worst case O(nm), but (I believe) there are modifications that make it linear time. There are other string searching algorithms like Knuth-Morris-Pratt which are linear in the size of the two inputs. My point was that non-naive string searching algorithms absolutely do matter, and that no amount of cache-efficiency is going to save an implementation from hitting the quadratic behaviour intrinsic to a naive algorithm.