Anyone know an example algorithm for word segmentation using dynamic programming?

Question

If you search google for word segmentation there really are no very good descriptions of it and I'm just trying to fully understand the process a dynamic programming algorithm takes to find a segmentation of a string into individual words. Does anyone know a place where there is a good description of a word segmentation problem or can anyone describe it?

Word Segmentation is basically just taking a string of characters and deciding where to split it up into words if you didn't know and using dynamic programming it would take into account some amount of subproblems. This is pretty simple to do using recursion but I haven't been able to find anywhere online to find even just a description of an iterative algorithm for this online, so if anyone has any examples or can give an algorithm that would be great.

Thanks for any help.

Answer 1

I'm going to assume that we're not talking about the trivial case here (i.e. not just splitting a string around spaces, since that'd just be a basic tokenizer problem) - but instead, we're talking about something were there isn't a clear word delimiter character, and thus we're having to "guess" what the best match for string->words would be - for instance, the case of a set of concatenated words w/o spaces, such as transforming this:

lotsofwordstogether

into this:

lots, of, words, together

In this case, the dynamic programming approach would probably be to calculate out a table where one dimension corresponds to the Mth word in the sequence, and the other dimension corresponds to each Nth character in the input string. Then the value that you fill in for each square of the table is "the best match score we can get if we end (or instead, begin) the Mth word at position N.

Answer 2

Introduction to Algorithms, Second Edition

Answer 3

take a look at Text mining handbook