3 ms·

He's arguing that you don't need to skip ahead on a miss. If you're test some UTF-8 string for membership in some other UTF-8 text, then go ahead and compare th

He's arguing that you don't need to skip ahead on a miss. If you're test some UTF-8 string for membership in some other UTF-8 text, then go ahead and compare the individual bytes even if they don't line up as characters. If you use a fast text search algorithm like Aho-Corasick, you'll still get reliable and accurate fast text search, and while you will perform unnecessary checks against invalid UTF-8 sequences, you won't have to create extra data structures or use any other operations and the algorithm can be implemented in a way that's pretty straightforward. The convenience of that outweighs the benefits you'd get of using a larger, elaborate data structure.

pjscott 16y ago
If you just need get-current-char and go-forward-n-chars operations, you can get those cheaply by having heavyweight strings implement an iterable API. (Yes, I know you also need the ability to iterate backward for Boyer-Moore, but that's also fairly straightforward.) This is not an argument against heavyweight strings, but an argument for better programming languages.
- andolanra 16y ago
  Well, the other advantage to using language-provided ropes or some variation on it, especially in functional languages with the capability for parallel execution, is that the rope structures (i.e. trees) are similar enough to Steele's conc lists (c.f. Guy Steele's "Organizing Functional Code for Parallel Execution") that searching in parallel could be achieved with little to no extra work from the programmer, which when possible would be much better than straight Aho-Corasick on a byte array.
  - pjscott 16y ago
    What if you're searching for substrings which span more than one chunk? What you'd end up needing to do is make a monoid of Aho-Corasick automaton state transition functions, and use a parallel prefix method. Steele gives examples of this sort of thing in the talk you mentioned. He and Danny Hillis go into more detail in their classic paper: http://portal.acm.org/citation.cfm?doid=7902.7903 http://portal.acm.org/citation.cfm?doid=7902.7903 If you combine this with heavyweight strings, you can get incremental and/or parallel string matching, but it's almost as easy to do on a byte array.
moultano 16y ago
Additionally, the larger elaborate data structure will almost certainly be slower.

pjscott 16y ago

If you just need get-current-char and go-forward-n-chars operations, you can get those cheaply by having heavyweight strings implement an iterable API. (Yes, I know you also need the ability to iterate backward for Boyer-Moore, but that's also fairly straightforward.) This is not an argument against heavyweight strings, but an argument for better programming languages.

andolanra 16y ago
Well, the other advantage to using language-provided ropes or some variation on it, especially in functional languages with the capability for parallel execution, is that the rope structures (i.e. trees) are similar enough to Steele's conc lists (c.f. Guy Steele's "Organizing Functional Code for Parallel Execution") that searching in parallel could be achieved with little to no extra work from the programmer, which when possible would be much better than straight Aho-Corasick on a byte array.
- pjscott 16y ago
  What if you're searching for substrings which span more than one chunk? What you'd end up needing to do is make a monoid of Aho-Corasick automaton state transition functions, and use a parallel prefix method. Steele gives examples of this sort of thing in the talk you mentioned. He and Danny Hillis go into more detail in their classic paper: http://portal.acm.org/citation.cfm?doid=7902.7903 http://portal.acm.org/citation.cfm?doid=7902.7903 If you combine this with heavyweight strings, you can get incremental and/or parallel string matching, but it's almost as easy to do on a byte array.

moultano 16y ago

Additionally, the larger elaborate data structure will almost certainly be slower.