Divisez le texte de manière uniforme en un certain nombre de lignes

Il existe un algorithme de temps linéaire pour diviser le texte uniformément en lignes de largeur maximale. Il utilise SMAWK (ou Knuth & Plass) et signifie "uniformément": http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Existe-t-il un algorithme ou une fonction de coût concave pour l'algorithme ci-dessus qui prendrait en compte le nombre de lignes dans lesquelles je souhaiterais que le texte pénètre, au lieu de la largeur de ligne maximale? Toujours en temps linéaire?

En d'autres termes, je recherche un algorithme de coupure de ligne (ou de formation de paragraphe ou d'habillage de mot) où l'entrée est le nombre de lignes souhaité, pas la largeur de ligne souhaitée.

Juste pour décrire une approche pratiquement inutilisable: il y a N mots et N-1 espaces entre chaque paire de mots, M est le nombre de lignes souhaité (M <= N). Après chaque espace, il peut y avoir au plus un (éventuellement zéro) saut de ligne. Maintenant, l'algorithme essaierait de placer les ruptures dans chaque combinaison possible, en calculant le "raggedness" et en retournant la meilleure. Comment le faire beaucoup plus rapidement?

De plus, un tel problème a-t-il un nom? À quelle «famille» de problèmes appartient-elle? (Par exemple "bin bin") Si je n'avais pas besoin de la solution parfaitement optimale, juste une très bonne, est-il possible de la résoudre beaucoup plus rapidement? (une certaine forme d'heuristique pourrait être utilisable si, pour une entrée donnée, il y avait toujours la même solution, éventuellement sous-optimale).

Mise à jour

Chandra Chekuri a suggéré ci-dessous "un problème dans le chapitre de Kleinberg et Tardos sur la programmation dynamique". C'était une bonne lecture, mais elle traite du saut de ligne en fonction de la largeur plutôt que du nombre de lignes. Il pourrait être adaptable à ce problème, ce que j'essaie de comprendre maintenant. Voici un bon lien vers la solution, ils prétendent même la résoudre en temps linéaire: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

En outre, il y a un chapitre "8.5 Le problème de partition" dans le manuel de conception d'algorithmes de Skiena qui semble être exactement sur le sujet, je le lis toujours, dur. (Malheureusement, d'après ce que j'ai compris, il a une complexité temporelle quadratique)

ds.algorithms Ecir Hana
la source

Joli problème de programmation dynamique! Je pourrais l'utiliser comme devoirs dans ma classe au semestre prochain.

Jeffε

@ Jɛ ﬀ E si vous voulez l'utiliser pour un problème de devoirs, mieux vaut fermer la question avant que la réponse ne soit publiée sur le web.

Joe

@Joe: en tant que personne vraiment intéressée par la réponse, je préférerais que la question soit répondue plutôt que fermée.

Ecir Hana

@Joe: ce n'est pas un devoir, je n'étudie même pas CS. En ce qui concerne le "niveau des devoirs", je trouve très intéressant que certaines personnes ne puissent même pas imaginer comment résoudre un problème, tandis que d'autres le considèrent "au niveau des devoirs". Cela dit, la réponse pourrait être effacée en une semaine ou envoyée à mon email par exemple. Et je serais également reconnaissant de ne pas avoir eu une "réponse aussi complète".

Ecir Hana

Il y a un problème dans le chapitre de Kleinberg et Tardos sur la programmation dynamique qui est de formater de manière à minimiser la somme des temps morts dans les lignes.

Chandra Chekuri

Réponses:

$M$ $O(N \log U)$ $U$ $N 2^{O(\sqrt{\log M \log \log N})}$ $M = \Omega(\log N)$

$M$ $M$

Jouni Sirén
la source

Je suis vraiment désolé mais je ne pense pas que je suive. Le «poids des bords» est-il la longueur d'un mot? À quoi ressemble le «graphique»? Est-ce juste un graphe linéaire où les nœuds sont les points d'arrêt et les bords sont les longueurs des mots? Et ce "chemin M-link" le décompose de sorte que les segments résultants aient une somme minimale de bords? Mais le plus important, dans la toute première phrase - je ne suis pas sûr de pouvoir calculer indépendamment les irrégularités. C'est à peu près la différence entre la ligne la plus longue et la ligne réelle, donc j'ai besoin de savoir quelque chose sur les autres lignes, non? Plus encore pour la dernière ligne, veuillez voir le 15ème commentaire ci-dessus.

Ecir Hana

M

$M$

1

$1$

N + 1

$N+1$

(i, j)

$(i,j)$

i

$i$

j - 1

$j-1$

@Ecir: Essentiellement, tous les algorithmes basés sur la programmation dynamique nécessitent que vous puissiez calculer indépendamment le caractère irrégulier d'une ligne. Si ce n'est pas le cas, vous voudrez peut-être utiliser quelque chose comme ma deuxième idée: deviner une largeur de ligne, calculer une solution en fonction de cette largeur et itérer pour trouver de meilleures solutions.

Jouni Sirén

Merci pour l'explication. S'il vous plaît, j'ai deux autres questions: lors de l'utilisation de l'option "recherche binaire", puis-je faire quelque chose pour garantir le nombre M de lignes? Si j'ajoute un petit epsilon aléatoire à chaque largeur de ligne pour qu'il n'y ait pas de lignes avec la même largeur, je pourrais gagner plus de résolution sur le placement des pauses.

Ecir Hana

Et dans le cas de "M-link path", les deux articles mentionnent qu '"il est facile de montrer que le minimum de K-link path peut être calculé en temps O (nK)" - savez-vous peut-être ce que cela signifie? Je n'ai pas pu trouver plus d'informations à ce sujet. Le problème est que ces papiers sont un peu trop compliqués pour ma petite tête donc j'essaye de trouver plus d'informations, une implémentation peut-être, ...

Ecir Hana

-3

Je ne sais pas si cela aide, mais vers la fin de ce commentaire, quelqu'un implémente ce que vous voulez en PHP; vous pouvez peut-être comprendre l'algorithme.

adrianp
la source

Dans le commentaire, ils ont juste coupé les lignes restantes après le nombre de lignes souhaité. Ils utilisent PHP wordwrap(), qui à son tour utilise l'algorithme gourmand (c'est-à-dire pas "uniformément") pour l'emballage. Même alors, la question reste de savoir comment "deviner" l' $widthargument de wordwrap(). Mais merci pour la réponse, de toute façon!

Ecir Hana