5 ms·

If you need to access a utf-8 string indexed by character rather than byte you are probably doing something wrong.

• tomjen3 16y ago
  You have an issue with fast text search?
  • moultano 16y ago
    If you aren't building an index ahead of time, you're writing a state machine, in which case you're better off treating it as bytes for efficiency and simplicity. (An array of 256 pointers vs a nearly unbounded dynamic map of pointers.) If you are building an index ahead of time, just use byte offsets in your index instead of character offsets. You'll still be iterating through it from the beginning to build the index.
    • tomjen3 16y ago
      You can't treat its as bytes because you are than dependent on what the came before those bytes, which messes with your ability to skip ahead on a miss.
      • moultano 16y ago
        I'm not understanding. In which case? Aho corasick works just as well on a sequence of bytes as on a sequence of characters.
      • andolanra 16y ago
        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.