10 ms·

The Boyer-Moore Fast String Searching Algorithm

228 points by js2 6y ago

kccqzy 6y ago
The Boyer–Moore algorithm is very well known. It's in the standard library of many languages such as C++: https://en.cppreference.com/w/cpp/utility/functional/boyer_moore_searcher https://en.cppreference.com/w/cpp/utility/functional/boyer_m... But TIL after reading this page that there's a new variation optimized for small alphabets such as DNA: https://www.cs.utexas.edu/users/moore/publications/sustik-moore.pdf https://www.cs.utexas.edu/users/moore/publications/sustik-mo...
- js2 6y ago
  I know the algorithm is well known, but I never really knew how it worked other than very hand wavy. This page also links to a demonstration of how the search works which I found easier to follow than the wiki page on the algorithm.
- MattPalmer1086 6y ago
  There's a lot of different approaches to searching small alphabets. The one you linked to maintains state during the search loop to get bigger shifts, and complexity in search loops always slows it down, sometimes to the point there is a net loss. If the needle was reasonably long, which is not uncommon for low alphabet needles, I suspect a better approach would be to use a hash based Horspool style algorithm working on n-grams, say 4. This works by calculating shifts based on ngrams, rather than individual bytes. Since there are many more permutations, you effectively increase the alphabet and hence the shifts also increase. At the cost of always having to read an entire ngram before you can shift. Edit: you also hash the ngram into a smaller hash table of course, you don't maintain a shift position for each ngram. You can tune the size of the hash table for lower memory or higher performance. This is similar to the multi pattern Wu Manber search, but applied to a single needle. Edit 2: I have found this algorithm also beats Horspool most of the time, say for an ngram size of 2 or 3, on any alphabet, not just low ones.
aparsons 6y ago
If you’d like to read a canonical, well-commented implementation, here is one from OpenJDK: http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/37a05a11f281/src/share/classes/java/util/regex/Pattern.java http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/37a05a11f281/s...
ganafagol 6y ago
To me, this is a classic and timeless piece of real computer science. Such an eye opener when I learned about it the first time! And a reminder that we really stand on the shoulder of giants.
bjoli 6y ago
I have always implemented the horspool algorithm instead. It is simpler to implement and generally performs just as good. When researching string search algorithms some time ago I came across max shift Boyer moore which seemed to be a very nice incremental improvement.
- dataflow 6y ago
  I've actually found Boost's Boyer-Moore-Horspool to be faster than its Boyer-Moore.
  - bjoli 6y ago
    For long needles it is, I agree. I am just too lazy to have a good heuristics between a naive search (which is surprisingly fast on modern hardware) and the horspool. With whatever implementations I have implemented have a sweet spot between naive and horspool wher BM is actually sliiightly faster. I think it is just that Horspool works better on modern hardware. BM isn't nearly as much of a gain over the naive search that it was 25 years ago. Edit: the max shift change I mentioned above can be done to Horspool as well!
    - dataflow 6y ago
      Oh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And yeah I should really try out the max shift change, I came across it not too long ago but never got around to implementing it.
      - MattPalmer1086 6y ago
        I find Horspool is almost always faster than Boyer Moore. For very short needles though (e.g. less than 8) it is hard to beat the SHIFT OR algorithm. Even though it is not sublinear, looking at every position, it tracks matches using a bitmask. In practice this is very fast and has very good cache hits. It easily beats BM or Horspool by quite a margin. They rely for speed in skips, and you don't get great skips with a short needle.
deivid 6y ago
Is this faster than Aho-Corasick? https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorit...
- hvdijk 6y ago
  It solves a slightly different problem, searching for one substring instead of searching for one of many, so it would not be fair to compare the two.
  - AlbertoGP 6y ago
    Yes, and if you need the best of both there is the Commentz-Walter algorithm from 1979: > Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(m·n), though the average case is often much better. > GNU grep implements a string matching algorithm very similar to Commentz-Walter. https://en.wikipedia.org/wiki/Commentz-Walter_algorithm https://en.wikipedia.org/wiki/Commentz-Walter_algorithm
    - burntsushi 6y ago
      Commentz-Walter doesn't work that well in practice. As you add more patterns, the likelihood that there is any meaningful byte skipping goes way down. So it might be useful for a small number of patterns, but at that point, there are vectorized algorithms that will do (a lot) better. (Like Teddy from Hyperscan.)
      - AlbertoGP 6y ago
        Thank you very much for this reply. I was considering implementing it for a program I’m writing, but in light of that it’s clearly not worth it.
deleted 6y ago
[deleted]
Const-me 6y ago
Interesting, but I’m not sure the algorithm aged well. Memory is a block device now. DDR delivers 8 bytes per transaction per channel, e.g. 16 bytes per transaction for dual-channel memory configuration. Skipping bytes delivers little profit in terms of memory bandwidth (but it saves other things, CPUs have very small limit how many memory load instructions can run per cycle). SIMD instructions can compare vectors for about the same cost as scalars, e.g. _mm_cmpeq_epi8 (SSE2) and vceqq_u8 (NEON) compare 16 bytes with another 16 bytes. If I wanted a super-fast substring search, I would try to leverage these things.
- beagle3 6y ago
  It has not aged well for ascii characters, especially for texts like English where the letter “e” is abundant enough to make it likely that your average jump would be 6, less than the 64-bit fetch. It can still be used to find a substring of 100 64-bit values in a much longer 64-bit string, but ... it’s a problem I never encountered (and only encountered a 16-bit version of it once in my life). Then again, if you use 32-bit for each Unicode character and have a lot of emojis, it might still be somewhat competitive with brute force.
  - lofi_lory 6y ago
    Harder to argue about character frequency in DNA/RNA sequences.
    - pmiller2 6y ago
      Naively, I'd expect all letters to occur equally frequently. Do you know if this is the case?
      - thamer 6y ago
        It's not the case. There are consequences to the proportion of some nucleotides, the most well-known being the GC-content[1], or proportion in a sequence of bases being G or C (G pairs with C and A pairs with T). There are benefits to a higher GC-content, like the sequence being more stable. From this the obvious question would be why this matters, since you obviously can't replace an A-T pair with a G-C pair just to increase this proportion. Except that there are ways to do it… kind of. If you look at the codon table[2], you'll see that there are multiple ways to represent each protein encoded by a triplet of nucleotides. [1] https://en.wikipedia.org/wiki/GC-content https://en.wikipedia.org/wiki/GC-content [2] https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables
healeycodes 6y ago
The "Boyer–Moore majority vote algorithm" is also very neat. It's the optimal solution to https://leetcode.com/problems/majority-element/ https://leetcode.com/problems/majority-element/ – as in it's required to solve the problem in linear time and in O(1) space.
- lofi_lory 6y ago
  Does it have practical applications tho? Last I read about it, I figured it was just neat. (On the other hand it pollutes the namespace as a "BMA" search term collision XD)
  - healeycodes 6y ago
    These days? Perhaps some niche area. From the paper's abstract: > the algorithm uses storage in a way that permits an efficient use of magnetic tape
- tzs 6y ago
  I don't know if this applies to that problem, but something worth noting about Leetcode O(1) space problems: the input is mutable and does not count toward your space usage. I like to use Leetcode hard or medium problems as interesting puzzles to work on in my head when I've got some time to kill, such as waiting in line for some service or lying in bed trying to fall asleep. One of those problems was given an input array of integers, find the smallest positive integer that is not in the array. They wanted this in O(N) time and O(1) space. I spent something like two months trying to solve that. I even spent a fair bit of that time trying to prove that it could not be done, hoping that maybe if I could not prove it impossible I might get some insights from why I could not do so that would help me figure out how to do it. That "try to disprove it to gain insight" approach didn't work, because my attempts to disprove it actually almost convinced me that it was in fact impossible. I say almost, because my argument using Turing machines actually seemed like it wa right, but it has been around 40 years since I last studied or used Turing machines, and so I wasn't quite sure that I wasn't missing something. I finally gave up, and took a quick glance at a published solution, trying to just see enough to get unstuck. The first thing I saw was that they were writing to the input array. As soon as I saw that you can overwrite the input, and so by O(1) space what they really mean is O(1) additional space besides this array of length N that we give you, the solution came quickly.
svat 6y ago
I remember encountering this wonderful page/website about ten years ago, and I was struck by two things: 1. How effective it was (and is). Both the demonstrations here (of Boyer-Moore algorithm, and of Knuth-Morris-Pratt) illustrate the algorithms very clearly (the same for the linear-time majority vote algorithm); the interactive (web) medium really helps (just hyperlinks and maybe the back button); and the technology is nothing more than a hand-coded HTML file (with abundant "<BR>"s), already over a decade old when I saw it. (The DOCTYPE line in the source mentioning "HTML 3.2" lets us date this to 1997 I guess, as HTML 3.2 was released in January 1997 and HTML 4 in December 1997.) 2. The page one level up from this (https://www.cs.utexas.edu/users/moore/best-ideas/index.html https://www.cs.utexas.edu/users/moore/best-ideas/index.html), titled ``My'' Best Ideas, which opens [Incidentally, this usage of `` and '' reflects ancient fonts—you can see the same usage in Emacs, TeX, etc—explained well by Markus Kuhn here: https://www.cl.cam.ac.uk/~mgk25/ucs/quotes.html https://www.cl.cam.ac.uk/~mgk25/ucs/quotes.html] with: > Here are the technical achievements of which I am most proud. I think such a list gives more insight into my research than, say, the traditional ``Honors and Awards'' section of a resume. And it lists eight ideas. Firstly, what a great idea to make such a list. And secondly, an impressive research career, and it's a successful life, to end with a portfolio of 8 ideas of which one can be proud. One doesn't need much more, and to have a handful of good ideas is something to hope for. I'm reminded of this, from Proofs from the Book (saw it here: https://sites.math.rutgers.edu/~zeilberg/Opinion82.html https://sites.math.rutgers.edu/~zeilberg/Opinion82.html ): > The essence of mathematics is proving theorems – and so, that is what mathematicians do: they prove theorems. But to tell the truth, what they really want to prove once in their lifetime, is a Lemma…
- kzrdude 6y ago
  I had great help of this website too: https://www-igm.univ-mlv.fr/~lecroq/string/ https://www-igm.univ-mlv.fr/~lecroq/string/
- twic 6y ago
  > The DOCTYPE line in the source mentioning "HTML 3.2" lets us date this to 1997 I guess, as HTML 3.2 was released in January 1997 and HTML 4 in December 1997. Not necessarily. HTML 4 was a big change from 3.2, more complicated, and stricter about separating structure from presentation. Lots of people stayed with the more familiar 3.2 for a long time.
cntlzw 6y ago
These algorithms are such a joy for me to code. Much more fun than the whole enterprise application work most of us 'developers' are stuck with.
- lofi_lory 6y ago
  Have you looked into the Z-algorithm? It's related to BM via Good Suffix rule, and I think it's very neat and handy.
raphaelj 6y ago
I few years ago, I wrote another substring search algorithm that is outperforming this one on a modern computer: https://github.com/RaphaelJ/fast_strstr/tree/master/benchmark/algorithms https://github.com/RaphaelJ/fast_strstr/tree/master/benchmar... While the algorithm is time linear (Boyer-Moore is sub linear), it ends up being significantly faster on textual content as the per character operations are significantly simplier.
- vanderZwan 6y ago
  Speaking of modern computers, have you compared it to these SIMD string find algorithms by Wojciech Muła? They're a bit more recent: http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html
- lofi_lory 6y ago
  BM taught me that cleverness doesn't pay for fast, similar iterations. Performance is all about cache misses. I hated that lesson.
  - lofi_lory 6y ago
    Also that thinking about string matching problems isn't good for my mental health. I had horrible nightmares on the road to my O(m) good suffix rule. Very hard not to go a little mad over iterating countless ideas and string matching scenarios in your head... on the train, on the pot, laying in bed trying to sleep. Btw. digital tablet with pen input is gold thinking about algorithms, as you get modifying your scenarios in place endlessly and copy and paste over paper + pencil.
  - linsomniac 6y ago
    Same. I implemented it, IIRC, on my Amiga 2000 and compared it to the Manx C library builtin. Which wiped the floor with my BM implementation. I don't remember the exact numbers, but it was so much faster that I didn't even bother trying to optimize mine, I just threw up my hands. It may have been on an HP9000s2xx machine instead of Amiga. Taught me that hand optimized assembly can beat clever algorithms.
- 6y ago
londons_explore 6y ago
Does this actually matter in the real world? I assume that even with a naieve search a modern CPU can search at the memory read speed. Without any kind of indexing beforehand it is impossible to search faster than the memory read speed. The approach shown of only checking some characters doesn't help remove memory bandwidth constraints unless the thing you are looking for is very long (because cache lines are very wide), which I suspect is not a common use case.
- ganafagol 6y ago
  The real world is larger than your desktop PC.
- superdisk 6y ago
  ROM hackers frequently use this algorithm to search binary ROMs for encoded strings.
- joppy 6y 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 6y 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 6y ago
MaxBarraclough 6y ago
Work has been done applying the Boyer-Moore principle to regex scanning. * https://doi.org/10.1016/S0167-6423(03)00013-3 https://doi.org/10.1016/S0167-6423(03)00013-3 (PDF is freely available) * https://nothings.org/computer/source/sgrep.html https://nothings.org/computer/source/sgrep.html
- MattPalmer1086 6y ago
  Interesting, thanks for the link, I wasn't aware of that one. I've been mulling how to apply fast search algorithms to regular expressions for a while. There isn't really one technique that works well for all expressions, so the more options right now the better. Eventually I'll settle on a few that offer the best overall coverage and performance.
mikewarot 6y ago
Back in the days of MS-DOS I wrote what I thought was a fairly clever search algorithm making use of the XLAT instruction. It could search for N= 1-8 characters in a block of text in a loop 7 instructions long, which I'm trying to reproduce from memory start: xor ah,ah lea bx, masktable mov cx, textlength lea si, texttosearch test_character: or ah, startbit (set bit 8-N of the ah register) lodsb (get a character into AL) xlat (AL gets [BX+AL]) and ah,al (masks off non-matching characters) shl ah,1 (AH=AH*2, carry goes into Carry Flag) jc match_found ; we found a match, break out loopnz test_character no_match_found: ; get here if there isn't a match In a 64 bit environment, you should be able to search for up to 64 characters fairly quickly, using a table that is 8*256 bytes, you can do case insensitive searches, along with a ? for any character to do some wildcarding. The nice thing is that everything is in the cache until you jump out when you have a match, and not before.
- mikewarot 6y ago
  I went through the work, and re-implemented it as an assembly language routine inside a 64bit free pascal program. It searches about 1 gigabyte of text in 2 seconds. https://github.com/mikewarot/fastsearch/blob/master/fastsearch_demo.lpr https://github.com/mikewarot/fastsearch/blob/master/fastsear...
rurban 6y ago
They make look like nothing happened in optimal strstr algorithms in the last decades. In the libc's not, indeed. They are still in the stoneage of string search. But the fastest is currently EPSM, by S. Faro and O. M. Kulekci. See https://smart-tool.github.io/smart/ https://smart-tool.github.io/smart/ "Exact Packed String Matching" optimized for SIMD SSE4.2/AVX (x86_64 and aarch64). It performs stable and best on all sizes. The site I linked to compares 199 fast string search algorithms, with the usual ones (BM, KMP, BMH) being pretty slow. EPSM outperforms all the others being mentioned here on these platforms. It's also the latest.
- MattPalmer1086 6y ago
  It is a great site, I've discovered many interesting algorithms on it. And benchmarked them with their tool, along with some of my own. And yes, EPSM outperforms the others by a mile. If you are comfortable with your search performance being bound to particular CPU architectures, and that may be entirely reasonable, then you can't beat that approach.
sarpdag 6y ago
I implemented it in Go for fun. I expected Go's standard lib will beat it but for long substring searches it perform up to 10 times faster than `strings.Index`. https://github.com/sarpdag/boyermoore https://github.com/sarpdag/boyermoore Go's strings package depends on the substring size tries different approaches like Rabin Karp algorithm, (https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)

228 points by js2 6y ago

The Boyer–Moore algorithm is very well known. It's in the standard library of many languages such as C++: https://en.cppreference.com/w/cpp/utility/functional/boyer_moore_searcher https://en.cppreference.com/w/cpp/utility/functional/boyer_m... But TIL after reading this page that there's a new variation optimized for small alphabets such as DNA: https://www.cs.utexas.edu/users/moore/publications/sustik-moore.pdf https://www.cs.utexas.edu/users/moore/publications/sustik-mo...

js2 6y ago
I know the algorithm is well known, but I never really knew how it worked other than very hand wavy. This page also links to a demonstration of how the search works which I found easier to follow than the wiki page on the algorithm.
MattPalmer1086 6y ago
There's a lot of different approaches to searching small alphabets. The one you linked to maintains state during the search loop to get bigger shifts, and complexity in search loops always slows it down, sometimes to the point there is a net loss. If the needle was reasonably long, which is not uncommon for low alphabet needles, I suspect a better approach would be to use a hash based Horspool style algorithm working on n-grams, say 4. This works by calculating shifts based on ngrams, rather than individual bytes. Since there are many more permutations, you effectively increase the alphabet and hence the shifts also increase. At the cost of always having to read an entire ngram before you can shift. Edit: you also hash the ngram into a smaller hash table of course, you don't maintain a shift position for each ngram. You can tune the size of the hash table for lower memory or higher performance. This is similar to the multi pattern Wu Manber search, but applied to a single needle. Edit 2: I have found this algorithm also beats Horspool most of the time, say for an ngram size of 2 or 3, on any alphabet, not just low ones.

aparsons 6y ago

If you’d like to read a canonical, well-commented implementation, here is one from OpenJDK: http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/37a05a11f281/src/share/classes/java/util/regex/Pattern.java http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/37a05a11f281/s...

ganafagol 6y ago

To me, this is a classic and timeless piece of real computer science. Such an eye opener when I learned about it the first time! And a reminder that we really stand on the shoulder of giants.

bjoli 6y ago

I have always implemented the horspool algorithm instead. It is simpler to implement and generally performs just as good. When researching string search algorithms some time ago I came across max shift Boyer moore which seemed to be a very nice incremental improvement.

dataflow 6y ago
I've actually found Boost's Boyer-Moore-Horspool to be faster than its Boyer-Moore.
- bjoli 6y ago
  For long needles it is, I agree. I am just too lazy to have a good heuristics between a naive search (which is surprisingly fast on modern hardware) and the horspool. With whatever implementations I have implemented have a sweet spot between naive and horspool wher BM is actually sliiightly faster. I think it is just that Horspool works better on modern hardware. BM isn't nearly as much of a gain over the naive search that it was 25 years ago. Edit: the max shift change I mentioned above can be done to Horspool as well!
  - dataflow 6y ago
    Oh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And yeah I should really try out the max shift change, I came across it not too long ago but never got around to implementing it.
    - MattPalmer1086 6y ago
      I find Horspool is almost always faster than Boyer Moore. For very short needles though (e.g. less than 8) it is hard to beat the SHIFT OR algorithm. Even though it is not sublinear, looking at every position, it tracks matches using a bitmask. In practice this is very fast and has very good cache hits. It easily beats BM or Horspool by quite a margin. They rely for speed in skips, and you don't get great skips with a short needle.

deivid 6y ago

Is this faster than Aho-Corasick? https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorit...

hvdijk 6y ago
It solves a slightly different problem, searching for one substring instead of searching for one of many, so it would not be fair to compare the two.
- AlbertoGP 6y ago
  Yes, and if you need the best of both there is the Commentz-Walter algorithm from 1979: > Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(m·n), though the average case is often much better. > GNU grep implements a string matching algorithm very similar to Commentz-Walter. https://en.wikipedia.org/wiki/Commentz-Walter_algorithm https://en.wikipedia.org/wiki/Commentz-Walter_algorithm
  - burntsushi 6y ago
    Commentz-Walter doesn't work that well in practice. As you add more patterns, the likelihood that there is any meaningful byte skipping goes way down. So it might be useful for a small number of patterns, but at that point, there are vectorized algorithms that will do (a lot) better. (Like Teddy from Hyperscan.)
    - AlbertoGP 6y ago
      Thank you very much for this reply. I was considering implementing it for a program I’m writing, but in light of that it’s clearly not worth it.

deleted 6y ago

[deleted]

Const-me 6y ago

Interesting, but I’m not sure the algorithm aged well. Memory is a block device now. DDR delivers 8 bytes per transaction per channel, e.g. 16 bytes per transaction for dual-channel memory configuration. Skipping bytes delivers little profit in terms of memory bandwidth (but it saves other things, CPUs have very small limit how many memory load instructions can run per cycle). SIMD instructions can compare vectors for about the same cost as scalars, e.g. _mm_cmpeq_epi8 (SSE2) and vceqq_u8 (NEON) compare 16 bytes with another 16 bytes. If I wanted a super-fast substring search, I would try to leverage these things.

beagle3 6y ago
It has not aged well for ascii characters, especially for texts like English where the letter “e” is abundant enough to make it likely that your average jump would be 6, less than the 64-bit fetch. It can still be used to find a substring of 100 64-bit values in a much longer 64-bit string, but ... it’s a problem I never encountered (and only encountered a 16-bit version of it once in my life). Then again, if you use 32-bit for each Unicode character and have a lot of emojis, it might still be somewhat competitive with brute force.
- lofi_lory 6y ago
  Harder to argue about character frequency in DNA/RNA sequences.
  - pmiller2 6y ago
    Naively, I'd expect all letters to occur equally frequently. Do you know if this is the case?
    - thamer 6y ago
      It's not the case. There are consequences to the proportion of some nucleotides, the most well-known being the GC-content[1], or proportion in a sequence of bases being G or C (G pairs with C and A pairs with T). There are benefits to a higher GC-content, like the sequence being more stable. From this the obvious question would be why this matters, since you obviously can't replace an A-T pair with a G-C pair just to increase this proportion. Except that there are ways to do it… kind of. If you look at the codon table[2], you'll see that there are multiple ways to represent each protein encoded by a triplet of nucleotides. [1] https://en.wikipedia.org/wiki/GC-content https://en.wikipedia.org/wiki/GC-content [2] https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables

healeycodes 6y ago

The "Boyer–Moore majority vote algorithm" is also very neat. It's the optimal solution to https://leetcode.com/problems/majority-element/ https://leetcode.com/problems/majority-element/ – as in it's required to solve the problem in linear time and in O(1) space.

lofi_lory 6y ago
Does it have practical applications tho? Last I read about it, I figured it was just neat. (On the other hand it pollutes the namespace as a "BMA" search term collision XD)
- healeycodes 6y ago
  These days? Perhaps some niche area. From the paper's abstract: > the algorithm uses storage in a way that permits an efficient use of magnetic tape
tzs 6y ago
I don't know if this applies to that problem, but something worth noting about Leetcode O(1) space problems: the input is mutable and does not count toward your space usage. I like to use Leetcode hard or medium problems as interesting puzzles to work on in my head when I've got some time to kill, such as waiting in line for some service or lying in bed trying to fall asleep. One of those problems was given an input array of integers, find the smallest positive integer that is not in the array. They wanted this in O(N) time and O(1) space. I spent something like two months trying to solve that. I even spent a fair bit of that time trying to prove that it could not be done, hoping that maybe if I could not prove it impossible I might get some insights from why I could not do so that would help me figure out how to do it. That "try to disprove it to gain insight" approach didn't work, because my attempts to disprove it actually almost convinced me that it was in fact impossible. I say almost, because my argument using Turing machines actually seemed like it wa right, but it has been around 40 years since I last studied or used Turing machines, and so I wasn't quite sure that I wasn't missing something. I finally gave up, and took a quick glance at a published solution, trying to just see enough to get unstuck. The first thing I saw was that they were writing to the input array. As soon as I saw that you can overwrite the input, and so by O(1) space what they really mean is O(1) additional space besides this array of length N that we give you, the solution came quickly.

svat 6y ago

I remember encountering this wonderful page/website about ten years ago, and I was struck by two things: 1. How effective it was (and is). Both the demonstrations here (of Boyer-Moore algorithm, and of Knuth-Morris-Pratt) illustrate the algorithms very clearly (the same for the linear-time majority vote algorithm); the interactive (web) medium really helps (just hyperlinks and maybe the back button); and the technology is nothing more than a hand-coded HTML file (with abundant "<BR>"s), already over a decade old when I saw it. (The DOCTYPE line in the source mentioning "HTML 3.2" lets us date this to 1997 I guess, as HTML 3.2 was released in January 1997 and HTML 4 in December 1997.) 2. The page one level up from this (https://www.cs.utexas.edu/users/moore/best-ideas/index.html https://www.cs.utexas.edu/users/moore/best-ideas/index.html), titled ``My'' Best Ideas, which opens [Incidentally, this usage of `` and '' reflects ancient fonts—you can see the same usage in Emacs, TeX, etc—explained well by Markus Kuhn here: https://www.cl.cam.ac.uk/~mgk25/ucs/quotes.html https://www.cl.cam.ac.uk/~mgk25/ucs/quotes.html] with: > Here are the technical achievements of which I am most proud. I think such a list gives more insight into my research than, say, the traditional ``Honors and Awards'' section of a resume. And it lists eight ideas. Firstly, what a great idea to make such a list. And secondly, an impressive research career, and it's a successful life, to end with a portfolio of 8 ideas of which one can be proud. One doesn't need much more, and to have a handful of good ideas is something to hope for. I'm reminded of this, from Proofs from the Book (saw it here: https://sites.math.rutgers.edu/~zeilberg/Opinion82.html https://sites.math.rutgers.edu/~zeilberg/Opinion82.html ): > The essence of mathematics is proving theorems – and so, that is what mathematicians do: they prove theorems. But to tell the truth, what they really want to prove once in their lifetime, is a Lemma…

kzrdude 6y ago
I had great help of this website too: https://www-igm.univ-mlv.fr/~lecroq/string/ https://www-igm.univ-mlv.fr/~lecroq/string/
twic 6y ago
> The DOCTYPE line in the source mentioning "HTML 3.2" lets us date this to 1997 I guess, as HTML 3.2 was released in January 1997 and HTML 4 in December 1997. Not necessarily. HTML 4 was a big change from 3.2, more complicated, and stricter about separating structure from presentation. Lots of people stayed with the more familiar 3.2 for a long time.

cntlzw 6y ago

These algorithms are such a joy for me to code. Much more fun than the whole enterprise application work most of us 'developers' are stuck with.

lofi_lory 6y ago
Have you looked into the Z-algorithm? It's related to BM via Good Suffix rule, and I think it's very neat and handy.

raphaelj 6y ago

I few years ago, I wrote another substring search algorithm that is outperforming this one on a modern computer: https://github.com/RaphaelJ/fast_strstr/tree/master/benchmark/algorithms https://github.com/RaphaelJ/fast_strstr/tree/master/benchmar... While the algorithm is time linear (Boyer-Moore is sub linear), it ends up being significantly faster on textual content as the per character operations are significantly simplier.

vanderZwan 6y ago
Speaking of modern computers, have you compared it to these SIMD string find algorithms by Wojciech Muła? They're a bit more recent: http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html
lofi_lory 6y ago
BM taught me that cleverness doesn't pay for fast, similar iterations. Performance is all about cache misses. I hated that lesson.
- lofi_lory 6y ago
  Also that thinking about string matching problems isn't good for my mental health. I had horrible nightmares on the road to my O(m) good suffix rule. Very hard not to go a little mad over iterating countless ideas and string matching scenarios in your head... on the train, on the pot, laying in bed trying to sleep. Btw. digital tablet with pen input is gold thinking about algorithms, as you get modifying your scenarios in place endlessly and copy and paste over paper + pencil.
- linsomniac 6y ago
  Same. I implemented it, IIRC, on my Amiga 2000 and compared it to the Manx C library builtin. Which wiped the floor with my BM implementation. I don't remember the exact numbers, but it was so much faster that I didn't even bother trying to optimize mine, I just threw up my hands. It may have been on an HP9000s2xx machine instead of Amiga. Taught me that hand optimized assembly can beat clever algorithms.
6y ago

londons_explore 6y ago

Does this actually matter in the real world? I assume that even with a naieve search a modern CPU can search at the memory read speed. Without any kind of indexing beforehand it is impossible to search faster than the memory read speed. The approach shown of only checking some characters doesn't help remove memory bandwidth constraints unless the thing you are looking for is very long (because cache lines are very wide), which I suspect is not a common use case.

ganafagol 6y ago
The real world is larger than your desktop PC.
superdisk 6y ago
ROM hackers frequently use this algorithm to search binary ROMs for encoded strings.
joppy 6y 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 6y 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 6y ago

MaxBarraclough 6y ago

Work has been done applying the Boyer-Moore principle to regex scanning. * https://doi.org/10.1016/S0167-6423(03)00013-3 https://doi.org/10.1016/S0167-6423(03)00013-3 (PDF is freely available) * https://nothings.org/computer/source/sgrep.html https://nothings.org/computer/source/sgrep.html

MattPalmer1086 6y ago
Interesting, thanks for the link, I wasn't aware of that one. I've been mulling how to apply fast search algorithms to regular expressions for a while. There isn't really one technique that works well for all expressions, so the more options right now the better. Eventually I'll settle on a few that offer the best overall coverage and performance.

mikewarot 6y ago

Back in the days of MS-DOS I wrote what I thought was a fairly clever search algorithm making use of the XLAT instruction. It could search for N= 1-8 characters in a block of text in a loop 7 instructions long, which I'm trying to reproduce from memory start: xor ah,ah lea bx, masktable mov cx, textlength lea si, texttosearch test_character: or ah, startbit (set bit 8-N of the ah register) lodsb (get a character into AL) xlat (AL gets [BX+AL]) and ah,al (masks off non-matching characters) shl ah,1 (AH=AH*2, carry goes into Carry Flag) jc match_found ; we found a match, break out loopnz test_character no_match_found: ; get here if there isn't a match In a 64 bit environment, you should be able to search for up to 64 characters fairly quickly, using a table that is 8*256 bytes, you can do case insensitive searches, along with a ? for any character to do some wildcarding. The nice thing is that everything is in the cache until you jump out when you have a match, and not before.

mikewarot 6y ago
I went through the work, and re-implemented it as an assembly language routine inside a 64bit free pascal program. It searches about 1 gigabyte of text in 2 seconds. https://github.com/mikewarot/fastsearch/blob/master/fastsearch_demo.lpr https://github.com/mikewarot/fastsearch/blob/master/fastsear...

rurban 6y ago

They make look like nothing happened in optimal strstr algorithms in the last decades. In the libc's not, indeed. They are still in the stoneage of string search. But the fastest is currently EPSM, by S. Faro and O. M. Kulekci. See https://smart-tool.github.io/smart/ https://smart-tool.github.io/smart/ "Exact Packed String Matching" optimized for SIMD SSE4.2/AVX (x86_64 and aarch64). It performs stable and best on all sizes. The site I linked to compares 199 fast string search algorithms, with the usual ones (BM, KMP, BMH) being pretty slow. EPSM outperforms all the others being mentioned here on these platforms. It's also the latest.

MattPalmer1086 6y ago
It is a great site, I've discovered many interesting algorithms on it. And benchmarked them with their tool, along with some of my own. And yes, EPSM outperforms the others by a mile. If you are comfortable with your search performance being bound to particular CPU architectures, and that may be entirely reasonable, then you can't beat that approach.

sarpdag 6y ago

I implemented it in Go for fun. I expected Go's standard lib will beat it but for long substring searches it perform up to 10 times faster than `strings.Index`. https://github.com/sarpdag/boyermoore https://github.com/sarpdag/boyermoore Go's strings package depends on the substring size tries different approaches like Rabin Karp algorithm, (https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)