Divide el texto uniformemente en cierto número de líneas

Existe un algoritmo de tiempo lineal para dividir el texto de manera uniforme en líneas de ancho máximo. Utiliza SMAWK (o Knuth & Plass) y "uniformemente" significa: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

¿Existe un algoritmo o una función de costo cóncava para el algoritmo anterior que tenga en cuenta la cantidad de líneas en las que me gustaría que se divida el texto, en lugar del ancho máximo de línea? También en tiempo lineal?

En otras palabras, estoy buscando un algoritmo de salto de línea (o formación de párrafo o ajuste de palabras) donde la entrada es el número deseado de líneas, no el ancho de línea deseado.

Solo para describir un enfoque prácticamente inutilizable: hay N palabras y N-1 espacios entre cada par de palabras, M es el número deseado de líneas (M <= N). Después de cada espacio puede haber como máximo un salto de línea (posiblemente cero). Ahora, el algoritmo intentaría colocar los descansos en cada combinación posible, calculando la "irregularidad" y devolviendo la mejor. ¿Cómo hacerlo mucho más rápido?

Además, ¿ese problema tiene un nombre? ¿A qué "familia" de problemas pertenece? (Por ejemplo, "embalaje de contenedores"). Si no necesitara la solución perfectamente óptima, solo una muy buena, ¿es posible resolverla mucho más rápido? (alguna forma de heurística podría ser utilizable, si para una entrada dada siempre hubiera la misma solución, posiblemente subóptima).

Actualizar

Chandra Chekuri sugirió a continuación "un problema en el capítulo de Kleinberg y Tardos sobre programación dinámica". Fue una buena lectura, pero se trata del salto de línea basado en el ancho en lugar del recuento de líneas. Podría ser adaptable a este problema, que es algo que estoy tratando de resolver ahora. Aquí hay un buen enlace a la solución, incluso afirman resolverlo en tiempo lineal: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Además, hay un capítulo "8.5 El problema de la partición" en el Manual de diseño de algoritmos de Skiena que parece estar exactamente en el tema, todavía lo estoy leyendo, difícil. (Desafortunadamente, por lo que entendí, tiene una complejidad de tiempo cuadrática)

ds.algorithms Ecir Hana
fuente

Buen problema de programación dinámica! Podría usarlo como tarea en mi clase el próximo semestre.

Jeff

@ Jɛ ﬀ E si desea usarlo para un problema de tarea, mejor cierre la pregunta antes de que la respuesta se publique en la web.

Joe

@ Joe: como alguien realmente interesado en la respuesta, preferiría que la pregunta fuera respondida, en lugar de cerrada.

Ecir Hana

@ Joe: no es tarea, ni siquiera estudio CS. En cuanto al "nivel de tarea", me parece muy interesante que algunas personas ni siquiera puedan imaginar cómo resolver un problema, mientras que otras personas lo consideran "nivel de tarea". Dicho esto, la respuesta podría borrarse en una semana o enviarse a mi correo electrónico, por ejemplo. Y estaría agradecido por no tan "respuesta completa", también.

Ecir Hana

Hay un problema en el capítulo de Kleinberg y Tardos sobre programación dinámica que consiste en formatear de manera tal que se minimice la suma de holguras en las líneas.

Chandra Chekuri

Respuestas:

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

$M$ $M$

Jouni Sirén
fuente

Lo siento mucho, pero no creo seguirlo. ¿Es "peso de borde" la longitud de una palabra? ¿Cómo se ve el "gráfico"? ¿Es solo un gráfico lineal donde los nodos son los puntos de ruptura y los bordes son las longitudes de las palabras? ¿Y esta "ruta de enlace M" la divide para que los segmentos resultantes tengan una suma mínima de bordes? Pero lo más importante, en la primera oración, no estoy seguro de si puedo calcular la irregularidad de forma independiente. Es aproximadamente la diferencia entre la línea más larga y la línea real, así que necesito saber algo sobre las otras líneas, ¿no? Más aún para la última línea, vea el comentario 15 arriba.

Ecir Hana

M

$M$

1

$1$

N + 1

$N+1$

(i, j)

$(i,j)$

i

$i$

j - 1

$j-1$

@Ecir: Esencialmente, todos los algoritmos basados en la programación dinámica requieren que pueda calcular la irregularidad de una línea de forma independiente. Si ese no es el caso, es posible que desee utilizar algo como mi segunda idea: adivinar un ancho de línea, calcular una solución basada en ese ancho e iterar para encontrar mejores soluciones.

Jouni Sirén

Gracias por la explicación. Por favor, tengo dos preguntas más: cuando uso la opción "búsqueda binaria", ¿hay algo que pueda hacer para garantizar el número M de líneas? Si agrego un pequeño épsilon aleatorio a cada ancho de línea para que no haya líneas con el mismo ancho, podría obtener más resolución sobre la colocación de saltos.

Ecir Hana

Y en el caso de la "ruta del enlace M", ambos documentos mencionan que "es fácil demostrar que la ruta mínima del enlace K se puede calcular en el tiempo O (nK)", ¿quizás saben qué significan? No pude encontrar más información al respecto. El problema es que esos documentos son demasiado complicados para mi cabecita, así que estoy tratando de encontrar más información, tal vez una implementación ...

Ecir Hana

-3

No sé si esto ayuda, pero hacia el final de este comentario alguien implementa lo que quieres en PHP; tal vez puedas descifrar el algoritmo.

adrianp
fuente

En el comentario, simplemente cortan las líneas restantes después del número deseado de líneas. Utilizan PHP wordwrap(), que a su vez utiliza el algoritmo codicioso (es decir, no "uniformemente") para envolver. Incluso entonces, la pregunta sigue siendo cómo "adivinar" el $widthargumento de wordwrap(). Pero gracias por la respuesta, de todos modos!

Ecir Hana