...

ne serait-ce pas un algorithme du même style ? À vue de nez ça ressemble un peu à ce que doit faire LaTeX quand il choisit correctement les espaces entre les mots pour obtenir le fameux "gris typographique", et il le fait en une seule passe (!).

sinon peut-être regarder du côté de l'algorithme de Viterbi, mais celui-ci n'est pas efficace pour de grandes quantités de données...