News for hackers. Stuff that matters.
Re:The Trie: A Neglected Data Structure by anaphor on Friday September 13, 2013 @10:54AM (#6380837)
I just used a Trie yesterday to implement some string matching that I needed to do in a tokenizer :) It's quite useful if you want to do string matching and you know ahead of time the exact list of strings you need to match with. My only issue with this article is that it explains them using Java, which I think just obscures the explanation too much, but I guess it's a Java blog.
Re:The Trie: A Neglected Data Structure by ArbitraryLimits on Friday September 13, 2013 @11:01AM (#6380892)
Some people say to use a perfect hash function in that case, IMO it's more trouble than it's worth.
Re:The Trie: A Neglected Data Structure by nly on Friday September 13, 2013 @11:23AM (#6381058)
Did you need full prefix and/or suffix string matching?
Re:The Trie: A Neglected Data Structure by anaphor on Friday September 13, 2013 @11:31AM (#6381109)
All I needed to do was match prefixes, and now that I think about it, what I actually did was closer to a ternary search tree. The problem was to match operators after matching an identifier, e.g. say the language has these operators ['+', '++', '%'], and you want to be very permissive with what's allowed to be a normal identifier, so "$$#3" is matched as an identifier, but say you have "b++45", then you want to be able to match ++ correctly. There are lots of ways I could've done it, but a trie-like data structure seemed like the easiest way to allow adding more operators easily.