3
$\begingroup$

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as "howareyoutoday," what is the most efficient way to determine that the segmentation is "how are you today" (i.e. quality(how)+quality(are)+quality(you)+quality(today) is the maximum quality possible)?

I was thinking that we could have something like the following:

A[0] = h, A[1] = o, ..., A[n] = y 
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n])

Now to determine the segmentation, we find max{Q[0], .., Q[n]} which will return some Q[i] (the first space is after this). Then, we find max{Q[i+1], .. Q[n]} which returns another Q[i] (second space is after this), etc. until max returns Q[n].

I have some questions though: is this method even correct, and does it use dynamic programming? It seems to me that it does, since we build the initial Q with subproblems to the original problem. Also, is this an optimal solution? To my understanding, the worst case would be O(n^2), which would be when max returns Q[0], then Q[1], then Q[2], etc.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Without information on quality it's not clear that such an approach can work. Basically, the "Bellman optimality criterion" requires that there's some operation $\circ$ so that $\operatorname{quality}(s) = \operatorname{quality}(s_1 .. s_k) \circ \operatorname{quality}(s_{k+1})$ for some $k$. $\endgroup$
    – Raphael
    Oct 4, 2014 at 12:56
  • $\begingroup$ You should be consider all partitions of the word, not necessary $s_{0,j}$, and next identify the same question, in the subproblems $s_{i_1, i_2}$. Because the string could have characters without sense before appears a real word, and after as well. I think that it's correct vote up for dynamic problem. What's about arxiv.org/pdf/1105.6162.pdf ? $\endgroup$
    – Jonathan Prieto-Cubides
    Oct 4, 2014 at 23:53

2 Answers 2

Reset to default
2
$\begingroup$

I'm assuming your quality function measures something similar to the likelihood of the string being a word. The problem with your algorithm is that it makes a hard decision about where the first space should go before considering where the other spaces go. If you make a suboptimal decision for where the first space goes it will mess you up later on.

The dynamic programming algorithm for this problem is called the Viterbi algorithm. https://en.wikipedia.org/wiki/Viterbi_algorithm You have to keep a table of the highest quality segmentations seen so far as you process the string from left to right. When the algorithm finishes you will be left with a ranked list of the highest quality segmentations.

Improve this answer
$\endgroup$
0
$\begingroup$

No that doesn't work, without harsh qualifications on 'that' or 'work'. What if the presence vs. absence of space after a letter represents a binary encoding of some hard problem into the string, where quality(x) returns 1 if your segmentation is a solution to the hard problem and 0 if it is not a solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.