1

I have a given byte array in C and I need to match it against several byte arrays and return true if there is any match.

I can make various memcmp's but I feel that it is very inefficient.

Do you know a better way?

Improve this question
2
  • 2
    That depends on what your requirements profile is. Do you have a fixed set of patterns against which you must match many incoming sequences? Or do you have a fixed sequence on which you will have to perform many matches over time? In either case you can optimize your data structures so that the amortized cost goes down, but it's easier to do for one of these use cases than for both.
    – Kilian Foth
    Commented Jul 20, 2015 at 14:52
  • Thank you for your fast response, Kilian! I have a small embedded system and the matching with the fixed database must occur while the other patterns are arriving from the network. Thanks again, Rui
    – Rui Pedro Caldeira
    Commented Jul 20, 2015 at 14:56

2 Answers 2

Reset to default
4

prefix trie:

It's a degenerate DFA without cycles. For implementation you have a int state and a int nextState[256] for each state.

For Matching states you would make the state number for it negative so you know when it's reached.

Improve this answer
2

In principle a search Trie is what you want, but you'd have to profile your actual data to find out when that actually performs better (it might always be worse unless you can find a cache-friendly layout).

Edit based on comments:

  1. Are you matching a stream or discrete packets?

    If the former, and you need to handle matches spanning the boundary between consecutive byte-arrays, you definitely want ratchet freak's DFA.

    If the latter, your tradeoff depends on:

  2. Hardware characteristics

    The cache effects I originally mentioned are very platform dependent.

    If you have a reasonably-sized fast cache (ie your substrings fit in it), then direct memcmp may be faster. Profile. You can speed this up by sorting your substrings and using the return value of memcmp to perform binary search on them.

    Especially for an embedded system, if the cache is small or the penalty for missing not that large, or your substrings don't fit in cache anyway, then chasing Trie nodes around is fine

    tl;dr - Trie is asymptotically optimal but cache effects may dominate. Measure it!

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.