5 ms·
We, humankind managed to get a good optimisation for this problem by using spaces between words. When trying these algorithms for searching a word in a string o
by rugina 2y ago
We, humankind managed to get a good optimisation for this problem by using spaces between words.
When trying these algorithms for searching a word in a string of text, I was surprised how little they could improve vs just skipping to the next word.
- jrpelkonen 2y agoBy “improving” you mean changing the problem definition: Word search is a completely different problem.
- dwallin 2y agoI think you would be surprised about how much of a performance hit that would be over existing state of the art. The thing you are missing is that the human visual system evaluates existence of spaces in parallel, a single threaded algorithm would need to check every character to see if it's a space, in addition to checking the letters of the search string. Also that fails to generalize to languages without spaces, search strings with spaces, etc. Also if you look at algorithms like Boyer-Moore, they effectively DO skip spaces, but do so in a manner that is language / content agnostic. (https://www-igm.univ-mlv.fr/~lecroq/string/node14.html https://www-igm.univ-mlv.fr/~lecroq/string/node14.html)