Findings string segments in a string

I have a list of segments (15000+ segments), I want to find out the occurence of segments in a given string. The segment can be single word or multiword, I can not assume space as a delimeter in string.

e.g. String "How can I download codec from internet for facebook, Professional programmer support"

[the string above may not make any sense but I am using it for illustration purpose]

segment list

• Microsoft word
• Microsoft excel
• Professional Programmer.
• Google
• Facebook
• Download codec from internet.

Ouptut :

• Download codec from internet
• facebook
• Professional programmer

Bascially i am trying to do a query reduction.

I want to achieve it less than O(list length + string length) time. As my list is more than 15000 segments, it will be time consuming to search entire list in string. The segment开发者_C百科s are prepared manully and placed in a txt file.

Regards

~Paul

You basically want a string search algorithm like Aho-Corasik string matching. It constructs a state machine for processing bodies of text to detect matches, effectively making it so that it searches for all patterns at the same time. It's runtime is on the order of the length of the text and the total length of the patterns.

In order to do efficient searches, you will need an auxiliary data structure in the form of some sort of index. Here, a great place to start would be to look at a KWIC index:

http://en.wikipedia.org/wiki/Key_Word_in_Context

http://www.cs.duke.edu/~ola/ipc/kwic.html

What your basically asking how to do is write a custom lexer/parser.

Some good background on the subject would be the Dragon Book or something on lex and yacc (flex and bison).

Take a look at this question:

Poor man's lexer for C#

Now of course, alot of people are going to say "just use regular expressions". Perhaps. The deal with using regex in this situation is that your execution time will grow linearly as a function of the number of tokens you are matching against. So, if you end up needing to "segment" more phrases, your execution time will get longer and longer.

What you need to do is have a single pass, popping words on to a stack and checking if they are valid tokens after adding each one. If they aren't, then you need to continue (disregard the token like a compiler disregards comments).

Hope this helps.