finding algorithms

October 6, 2008

Dear lazyweb, I recently found myself having a set of Unicode strings (in main memory) and the desire to search all of them for a particular prefix (not substring). For bonus points, let’s say I want to do it in parallel (seems like an easily parallelizable problem, although at worst you can divide-and-conquer for a given number N of processors). The constraints are that the set of strings can change, but not very often usually. I don’t want too large of a hit to compute tables and the like though.

The real question is – how do you find papers (and implementations thereof) for computer science problems like this? My first instinct was to get an ACM subscription, which I did. Their search turns out to be mediocre, and then I discovered Wikipedia has useful pages on these kinds of things. Wikipedia also has the winning feature of linking to quality free software implementations thereof.

On this particular problem, a lot of the literature is around substring matching which isn’t what I want, at least not directly. Still looking.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: