4 ms·

I'd probably store cached results for Dictinary<int, HashSet<string>> allowed, notAllowed; where int == length of the user agent. This should probably be blazin

by NKCSS 9y ago

I'd probably store cached results for Dictinary<int, HashSet<string>> allowed, notAllowed; where int == length of the user agent. This should probably be blazing fast as well instead of keep doing those lookups.

alexandrnikitin 9y ago
I doubt that exactly that will work. There are tens of thousands of different UAs (maybe 100K). Perhaps some kind of tiny (few CPU cache lines) cache for most popular UAs could help. But again: measure, measure, measure :)
- NKCSS 9y ago
  Publish your test set and I can look at it :)
  - alexandrnikitin 9y ago
    I'm afraid I can't do that because of proprietary data. I think I can come up with analogous tests using open data. I'll let you know ;)
andrewgrowles 9y ago
A FST seems like a good fit for this problem. I believe it will be much more compact than the Aho-Corasick algorithm trie structure. Depends on the size of the dictionary.
- alexandrnikitin 9y ago
  I have that feeling too. But I found it harder to implement, especially with fallback failure references.
  - andrewgrowles 9y ago
    I'd look for a library and not write one from scratch. Lucene [1] and OpenFST [2] are great implementations. I haven't used C#, so I don't know if bindings exist or not. Also you may find this talk useful [3] (Particularly slide 11). Great write up by the way. Really thorough on the benchmarking! [1] https://lucene.apache.org/core/4_1_0/core/org/apache/lucene/util/fst/package-summary.html https://lucene.apache.org/core/4_1_0/core/org/apache/lucene/... [2] http://www.openfst.org/twiki/bin/view/FST/WebHome http://www.openfst.org/twiki/bin/view/FST/WebHome [3] https://www.slideshare.net/lucenerevolution/text-tagging-with-finite-state-transducers https://www.slideshare.net/lucenerevolution/text-tagging-wit...
    - alexandrnikitin 9y ago
      Awesome! The talk is great! It would be really interesting to try it. Thanks for sharing.
    - animal531 9y ago
      One can find Lucene.NET here: https://lucenenet.apache.org/ https://lucenenet.apache.org/

by NKCSS 9y ago

alexandrnikitin 9y ago

I doubt that exactly that will work. There are tens of thousands of different UAs (maybe 100K). Perhaps some kind of tiny (few CPU cache lines) cache for most popular UAs could help. But again: measure, measure, measure :)

NKCSS 9y ago
Publish your test set and I can look at it :)
- alexandrnikitin 9y ago
  I'm afraid I can't do that because of proprietary data. I think I can come up with analogous tests using open data. I'll let you know ;)

andrewgrowles 9y ago

A FST seems like a good fit for this problem. I believe it will be much more compact than the Aho-Corasick algorithm trie structure. Depends on the size of the dictionary.

alexandrnikitin 9y ago
I have that feeling too. But I found it harder to implement, especially with fallback failure references.
- andrewgrowles 9y ago
  I'd look for a library and not write one from scratch. Lucene [1] and OpenFST [2] are great implementations. I haven't used C#, so I don't know if bindings exist or not. Also you may find this talk useful [3] (Particularly slide 11). Great write up by the way. Really thorough on the benchmarking! [1] https://lucene.apache.org/core/4_1_0/core/org/apache/lucene/util/fst/package-summary.html https://lucene.apache.org/core/4_1_0/core/org/apache/lucene/... [2] http://www.openfst.org/twiki/bin/view/FST/WebHome http://www.openfst.org/twiki/bin/view/FST/WebHome [3] https://www.slideshare.net/lucenerevolution/text-tagging-with-finite-state-transducers https://www.slideshare.net/lucenerevolution/text-tagging-wit...
  - alexandrnikitin 9y ago
    Awesome! The talk is great! It would be really interesting to try it. Thanks for sharing.
  - animal531 9y ago
    One can find Lucene.NET here: https://lucenenet.apache.org/ https://lucenenet.apache.org/