CODEWITHSUNDEEP
language-agnosticparsing
jkeys
jkeys

Reputation: 3955

What is the most efficient data structure to hold keywords?

I decided to write a small parser to parse BBCode and return properly formatted HTML. I am having a hard time deciding what the most efficient way to represent the keywords would be. I could always use separate strings to hold them, but I feel like there must be some unknown data structure (to me) that would allow for efficient lookup.

I am using C++ if there is anything in the STL I can use. I don't intend to actually use it so I don't need to use anything like PHP. It will not have a GUI interface; just input a text file and it outputs a new file with the HTML parsed out.

Edit: By keywords, I mean the opening and closing tags, such as [b] and [/b].

Upvotes: 1

Views: 215

Answers (3)

Kristoffon
Kristoffon

Reputation: 642

The classic answer is a hash table. Constant time insertion/replacement.

But it's not entirely clear what you want. If it's just to keep the keywords neatly organized instead of peppered through your code a simple array would do; then use #defines to index and select them.

Upvotes: 2

Alex Martelli
Alex Martelli

Reputation: 881745

Since you know all your keywords in advance, you can take advantage of perfect hashing, e.g. via this library -- see also the wikipedia entry and the pointers from it.

Upvotes: 4

user124493
user124493

Reputation:

The classic is the Aho-Corasick keyword tree introduced in their 1973 paper.

linear time word insertion, linear time word lookup.

Upvotes: 1

Related Questions