2008-08-20 12 views
31

Word wrap es una de las características imprescindibles del editor de texto moderno.¿Algún algoritmo de ajuste de palabra?

¿Sabes cómo manejar el ajuste de palabras? ¿Cuál es el mejor algoritmo para el ajuste de palabras?

actualizado: Si el texto es varios millones de líneas, ¿cómo puedo hacer un ajuste de palabras muy rápido?

actualizado: ¿Por qué necesito la solución? Debido a que mis proyectos deben dibujar texto con varios niveles de zoom y apariencia hermosa al mismo tiempo.

updated: Running environment is Windows Mobile devices. Velocidad máxima de 600MHz con un tamaño de memoria muy pequeño.

actualizado: ¿Cómo debo manejar la información de línea? Supongamos que los datos originales tienen tres líneas.

THIS IS LINE 1. 
THIS IS LINE 2. 
THIS IS LINE 3. 

Después de texto de corte palabra se mostrará así:

THIS IS 
LINE 1. 
THIS IS 
LINE 2. 
THIS IS 
LINE 3. 

¿Debo asignar 3 líneas más? ¿O alguna otra sugerencia?

+0

La pregunta no especifica explícitamente que sea para fuentes de ancho fijo, aunque los ejemplos y el uso en un "editor de texto" lo implican. Solo la respuesta de Yaakov Ellis menciona el ajuste de texto para fuentes de ancho no fijo. – Gnubie

Respuesta

4

con o sin separación silábica?

sin su fácil. Simplemente encapsule su texto como wordobjects por palabra y asígneles un método getWidth() luego comience en la primera palabra sumando la longitud de la fila hasta que sea mayor que el espacio disponible. si es así, envuelva la última palabra y comience a contar nuevamente para la siguiente fila comenzando con este ecetera.

Con la separación de sílabas se necesitan reglas de división de palabras en un formato común como: HY-fen-a-ción

Entonces es el mismo que el anterior, excepto que necesita para dividir la última palabra que ha causado el desbordamiento.

Un buen ejemplo y tutorial de cómo estructurar su código para un texto excelente se encuentra en el libro Pandillas de cuatro patrones de diseño. Es uno de la muestra principal en la que muestran los patrones.

+0

¿Por qué fue votado -1? De acuerdo, el algoritmo codicioso no es óptimo, pero ... – ShreevatsaR

+0

me gana. Me sorprendió también. –

+1

Como es incorrecto decir que es "fácil", no es trivial escribir un algoritmo eficiente para este trabajo, incluso si ignora la separación por sílabas. También es difícil crear cualquier versión que sea eficiente para fuentes de ancho fijo y ancho variable. Fácil es incorrecto, de ahí el voto a la baja. – mjaggard

5

No sé de ningún algoritmos específicos, pero ¿no la siguiente ser un esbozo de cómo debería funcionar:

  1. Para el tamaño actual del texto, la fuente, el tamaño de la pantalla, tamaño de la ventana, los márgenes , etc., determine cuántos caracteres caben en una línea (si son de tipo fijo) o cuántos píxeles caben en una línea (si no son de tipo fijo).
  2. Pase por la línea carácter por carácter, calculando cuántos caracteres o píxeles se han grabado desde el comienzo de la línea.
  3. Cuando pasa los máximos caracteres/píxeles de la línea, vuelve al último espacio/signo de puntuación, mueve todo el texto a la siguiente línea.
  4. Repita hasta que revise todo el texto del documento.

Pregunta: En .net, la función de ajuste de texto está integrada en controles como TextBox. Estoy seguro de que existe una funcionalidad integrada similar para otros idiomas también. ¿Hay alguna razón por la cual no quieras usar una solución preconstruida? Esto parece en la línea de reinventar la rueda.

11

En cuanto a su pregunta de actualización y velocidad, recuerde optimizarla más adelante. Primero, escribe tu algoritmo de ajuste de palabras. Ejecútelo en un millón de líneas si el texto. Si es y solo si es demasiado lento para sus necesidades, entonces optimícelo.

30

Aquí hay un algoritmo de ajuste de palabras que he escrito en C#. Debería ser bastante fácil de traducir a otros idiomas (excepto quizás para IndexOfAny).

static char[] splitChars = new char[] { ' ', '-', '\t' }; 

private static string WordWrap(string str, int width) 
{ 
    string[] words = Explode(str, splitChars); 

    int curLineLength = 0; 
    StringBuilder strBuilder = new StringBuilder(); 
    for(int i = 0; i < words.Length; i += 1) 
    { 
     string word = words[i]; 
     // If adding the new word to the current line would be too long, 
     // then put it on a new line (and split it up if it's too long). 
     if (curLineLength + word.Length > width) 
     { 
      // Only move down to a new line if we have text on the current line. 
      // Avoids situation where wrapped whitespace causes emptylines in text. 
      if (curLineLength > 0) 
      { 
       strBuilder.Append(Environment.NewLine); 
       curLineLength = 0; 
      } 

      // If the current word is too long to fit on a line even on it's own then 
      // split the word up. 
      while (word.Length > width) 
      { 
       strBuilder.Append(word.Substring(0, width - 1) + "-"); 
       word = word.Substring(width - 1); 

       strBuilder.Append(Environment.NewLine); 
      } 

      // Remove leading whitespace from the word so the new line starts flush to the left. 
      word = word.TrimStart(); 
     } 
     strBuilder.Append(word); 
     curLineLength += word.Length; 
    } 

    return strBuilder.ToString(); 
} 

private static string[] Explode(string str, char[] splitChars) 
{ 
    List<string> parts = new List<string>(); 
    int startIndex = 0; 
    while (true) 
    { 
     int index = str.IndexOfAny(splitChars, startIndex); 

     if (index == -1) 
     { 
      parts.Add(str.Substring(startIndex)); 
      return parts.ToArray(); 
     } 

     string word = str.Substring(startIndex, index - startIndex); 
     char nextChar = str.Substring(index, 1)[0]; 
     // Dashes and the likes should stick to the word occuring before it. Whitespace doesn't have to. 
     if (char.IsWhiteSpace(nextChar)) 
     { 
      parts.Add(word); 
      parts.Add(nextChar.ToString()); 
     } 
     else 
     { 
      parts.Add(word + nextChar); 
     } 

     startIndex = index + 1; 
    } 
} 

Es bastante primitivo: se divide en espacios, pestañas y guiones. Se asegura de que los guiones se adhieren a la palabra anterior (por lo que no terminan con stack \ n-overflow), aunque no favorece el movimiento de palabras con guiones pequeños a una nueva línea en lugar de dividirlas. Separa las palabras si son demasiado largas para una línea.

También es bastante específico culturalmente, ya que no sé mucho sobre las reglas de envoltura de palabras de otras culturas.

+0

Muy agradable y conciso. Error menor: si la cadena contiene un salto de línea, curLineLength debe establecerse en cero (lo más fácil es agregar '\ n' a los caracteres de corte, y luego probar si la palabra es igual a '\ n'). – dbkk

+0

Además, es mejor no tratar de poner un guión cuando se dividen palabras largas, solo romperlas. Los guiones finales adecuados son un problema difícil, incluso para inglés (no en inglés o inglés). – dbkk

+0

Un error en esto son los caracteres no espaciados. Por ejemplo, si su usuario ingresó la PEQUEÑA LETRA E MINÚSCULA seguida de COMBINACIÓN DE BREVE, y tiene 50 palabras de eso, va a dejar de 2/3 a 1/2 de cada línea vacía. La normalización a FormC limitaría eso cada vez que haya una variante de punto de código único de la combinación, pero en general deberá escanear y verificar cada glifo para ver si se trata de un carácter de espaciado. Pequeño problema normalmente, gran problema en algunas entradas. – dhasenan

23

Donald E. Knuth hizo mucho trabajo en el algoritmo de salto de línea en su sistema de composición tipo TeX. Podría decirse que este es uno de los mejores algoritmos para la rotura de líneas: "mejor" en términos de apariencia visual del resultado.

Su algoritmo evita los problemas del relleno de líneas codiciosas donde puede terminar con una línea muy densa seguida de una línea muy suelta.

Se puede implementar un algoritmo eficiente usando la programación dinámica.

A paper on TeX's line breaking.

19

No sé si alguien leerá esto viendo la antigüedad de esta pregunta, pero tuve la oportunidad de escribir una función de ajuste de palabras recientemente, y quiero compartir lo que se me ocurrió. Utilicé un enfoque TDD casi tan estricto como el del Go example. Empecé con la prueba que envolvía la cadena "¡Hola, mundo!" a 80 de ancho debería aparecer "Hello, World!" Claramente, lo más simple que funciona es devolver la cadena de entrada intacta. A partir de eso, hice pruebas cada vez más complejas y terminé con una solución recursiva que (al menos para mi propósito) maneja la tarea de manera bastante eficiente.

Pseudocódigo de la solución recursiva:

 
Function WordWrap (inputString, width) 
    Trim the input string of leading and trailing spaces. 

    If the trimmed string's length is <= the width, 
     Return the trimmed string. 
    Else, 
     Find the index of the last space in the trimmed string, starting at width 

     If there are no spaces, use the width as the index. 

     Split the trimmed string into two pieces at the index. 

     Trim trailing spaces from the portion before the index, 
     and leading spaces from the portion after the index. 

     Concatenate and return: 
      the trimmed portion before the index, 
      a line break, 
      and the result of calling WordWrap on the trimmed portion after 
      the index (with the same width as the original call). 

Esto sólo envuelve a los espacios, y si quieres para envolver una cadena que ya contiene saltos de línea, que necesita para dividirlo en los saltos de línea, enviar cada pieza a esta función y luego volver a montar la cadena. Aun así, en VB.NET ejecutándose en una máquina rápida, esto puede manejar aproximadamente 20 mb/seg.

3

Me preguntaba lo mismo para mi propio proyecto de editor. Mi solución fue un proceso de dos pasos:

  1. Busque los extremos de la línea y guárdelos en una matriz.
  2. Para líneas muy largas, encuentre los puntos de interrupción adecuados a intervalos de aproximadamente 1K y guárdelos en la matriz de líneas, también. Esto es para captar el "texto de 4 MB sin un salto de línea único".

Cuando necesite mostrar el texto, busque las líneas en cuestión y envuélvalas sobre la marcha. Recuerde esta información en un caché para volver a dibujar rápidamente. Cuando el usuario se desplaza por una página completa, purgue la caché y repita.

Si puede, cargue/analice todo el texto en un hilo de fondo. De esta manera, ya puede mostrar la primera página de texto mientras el resto del documento aún se está examinando. La solución más simple aquí es cortar los primeros 16 KB de texto y ejecutar el algoritmo en la subcadena. Esto es muy rápido y le permite representar la primera página al instante, incluso si su editor todavía está cargando el texto.

Puede utilizar un enfoque similar cuando el cursor está inicialmente al final del texto; solo lea los últimos 16 KB de texto y analícelos. En este caso, use dos búferes de edición y cargue todos menos los últimos 16 KB en el primero mientras el usuario está bloqueado en el segundo búfer. Y es probable que desee recordar cuántas líneas tiene el texto cuando cierra el editor, por lo que la barra de desplazamiento no se ve extraña.

Se pone peludo cuando el usuario puede iniciar el editor con el cursor en algún lugar en el medio, pero en última instancia, es solo una extensión del problema final. Solo necesita recordar la posición de bytes, el número de línea actual y el número total de líneas de la última sesión, además necesita tres búferes de edición o necesita un búfer de edición donde puede cortar 16 KB en el medio.

Como alternativa, bloquee la barra de desplazamiento y otros elementos de la interfaz mientras se carga el texto; que permite al usuario mirar el texto mientras se carga por completo.

1

Aquí está la solución en C#. Derramó la única palabra que excede el límite dado y otras palabras permanecen como de costumbre.

 /// <summary> 
     /// Word wraps the given text to fit within the specified width. 
     /// </summary> 
     /// <param name="text">Text to be word wrapped</param> 
     /// <param name="width">Width, in characters, to which the text 
     /// should be word wrapped</param> 
     /// <returns>The modified text</returns> 
     public static string WordWrap(string text, int width) 
     { 
      int pos, next; 
      StringBuilder sb = new StringBuilder(); 

      // Lucidity check 
      if (width < 1) 
       return text; 

      // Parse each line of text 
      for (pos = 0; pos < text.Length; pos = next) 
      { 
       // Find end of line 
       int eol = text.IndexOf(Environment.NewLine, pos); 
       if (eol == -1) 
        next = eol = text.Length; 
       else 
        next = eol + Environment.NewLine.Length; 

       // Copy this line of text, breaking into smaller lines as needed 
       if (eol > pos) 
       { 
        do 
        { 
         int len = eol - pos; 
         if (len > width) 
          len = BreakLine(text, pos, width); 
         sb.Append(text, pos, len); 
         sb.Append(Environment.NewLine); 

         // Trim whitespace following break 
         pos += len; 
         while (pos < eol && Char.IsWhiteSpace(text[pos])) 
          pos++; 
        } while (eol > pos); 
       } 
       else sb.Append(Environment.NewLine); // Empty line 
      } 
      return sb.ToString(); 
     } 

     /// <summary> 
     /// Locates position to break the given line so as to avoid 
     /// breaking words. 
     /// </summary> 
     /// <param name="text">String that contains line of text</param> 
     /// <param name="pos">Index where line of text starts</param> 
     /// <param name="max">Maximum line length</param> 
     /// <returns>The modified line length</returns> 
     private static int BreakLine(string text, int pos, int max) 
     { 
      // Find last whitespace in line 
      int i = max; 
      while (i >= 0 && !Char.IsWhiteSpace(text[pos + i])) 
       i--; 

      // If no whitespace found, break at maximum length 
      if (i < 0) 
       return max; 

      // Find start of whitespace 
      while (i >= 0 && Char.IsWhiteSpace(text[pos + i])) 
       i--; 

      // Return length of text before whitespace 
      return i + 1; 
     } 
1

No puedo reclamar la ausencia de errores de esto, pero necesitaba una palabra que cumpliera y cumpliera los límites de la sangría. No reclamo nada acerca de este código, aparte de que me ha funcionado hasta ahora. Este es un método de extensión y viola la integridad de StringBuilder, pero podría hacerse con las entradas/salidas que desee.

public static void WordWrap(this StringBuilder sb, int tabSize, int width) 
{ 
    string[] lines = sb.ToString().Replace("\r\n", "\n").Split('\n'); 
    sb.Clear(); 
    for (int i = 0; i < lines.Length; ++i) 
    { 
     var line = lines[i]; 
     if (line.Length < 1) 
      sb.AppendLine();//empty lines 
     else 
     { 
      int indent = line.TakeWhile(c => c == '\t').Count(); //tab indents 
      line = line.Replace("\t", new String(' ', tabSize)); //need to expand tabs here 
      string lead = new String(' ', indent * tabSize); //create the leading space 
      do 
      { 
       //get the string that fits in the window 
       string subline = line.Substring(0, Math.Min(line.Length, width)); 
       if (subline.Length < line.Length && subline.Length > 0) 
       { 
        //grab the last non white character 
        int lastword = subline.LastOrDefault() == ' ' ? -1 : subline.LastIndexOf(' ', subline.Length - 1); 
        if (lastword >= 0) 
         subline = subline.Substring(0, lastword); 
        sb.AppendLine(subline); 

        //next part 
        line = lead + line.Substring(subline.Length).TrimStart(); 
       } 
       else 
       { 
        sb.AppendLine(subline); //everything fits 
        break; 
       } 
      } 
      while (true); 
     } 
    } 
} 
0

puedo también interrumpiría con una solución del Perl que hice, porque GNU fold -s dejaba espacios finales y otro mal comportamiento. Esta solución no maneja (adecuadamente) el texto que contiene pestañas o retrocesos o retornos de carro incrustados o similares, aunque maneja terminaciones de línea CRLF, convirtiéndolos todos a solo LF. Hace un cambio mínimo en el texto, en particular, nunca divide una palabra (no cambia wc -w), y para el texto con no más de un espacio en una fila (y no CR) no cambia wc -c (porque es reemplaza el espacio con LF en lugar de insertando LF).

#!/usr/bin/perl 

use strict; 
use warnings; 

my $WIDTH = 80; 

if ($ARGV[0] =~ /^[1-9][0-9]*$/) { 
    $WIDTH = $ARGV[0]; 
    shift @ARGV; 
} 

while (<>) { 

s/\r\n$/\n/; 
chomp; 

if (length $_ <= $WIDTH) { 
    print "$_\n"; 
    next; 
} 

@_=split /(\s+)/; 

# make @_ start with a separator field and end with a content field 
unshift @_, ""; 
push @_, "" if @_%2; 

my ($sep,$cont) = splice(@_, 0, 2); 
do { 
    if (length $cont > $WIDTH) { 
    print "$cont"; 
    ($sep,$cont) = splice(@_, 0, 2); 
    } 
    elsif (length($sep) + length($cont) > $WIDTH) { 
    printf "%*s%s", $WIDTH - length $cont, "", $cont; 
    ($sep,$cont) = splice(@_, 0, 2); 
    } 
    else { 
    my $remain = $WIDTH; 
    { do { 
     print "$sep$cont"; 
     $remain -= length $sep; 
     $remain -= length $cont; 
     ($sep,$cont) = splice(@_, 0, 2) or last; 
    } 
    while (length($sep) + length($cont) <= $remain); 
    } 
    } 
    print "\n"; 
    $sep = ""; 
} 
while ($cont); 

} 
2

Aquí es mío que yo estaba trabajando en la actualidad para la diversión en C:

Éstos son mis consideraciones:

1) Prohibida la reproducción de caracteres, solo se imprime en la salida estándar. Por lo tanto, dado que no me gusta modificar los argumentos argv [x], y porque me gusta un desafío, quería hacerlo sin modificarlo.No fui por la idea de insertar '\n'.

2) No quiero

This line breaks  here 

para convertirse en

This line breaks 
    here 

por lo que cambiar a caracteres '\n' no es una opción dada este objetivo.

3) Si el ancho de línea se establece en digamos 80, y el 80º carácter está en el medio de una palabra, la palabra completa debe colocarse en la siguiente línea. Entonces, mientras escanea, debe recordar la posición del final de la última palabra que no superó los 80 caracteres.

Así que aquí está el mío, no está limpio; He estado rompiéndome la cabeza durante la última hora tratando de hacer que funcione, agregando algo aquí y allá. Funciona para todos los casos extremos que conozco.

#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 

int isDelim(char c){ 
    switch(c){ 
     case '\0': 
     case '\t': 
     case ' ' : 
     return 1; 
     break; /* As a matter of style, put the 'break' anyway even if there is a return above it.*/ 
     default: 
     return 0; 
    } 
} 

int printLine(const char * start, const char * end){ 
    const char * p = start; 
    while (p <= end) putchar(*p++); 
    putchar('\n'); 
} 

int main (int argc , char ** argv) { 

    if(argc <= 2) exit(1); 

    char * start = argv[1]; 
    char * lastChar = argv[1]; 
    char * current = argv[1]; 
    int wrapLength = atoi(argv[2]); 

    int chars = 1; 
    while(*current != '\0'){ 
     while(chars <= wrapLength){ 
     while (!isDelim(*current)) ++current, ++chars; 
     if(chars <= wrapLength){ 
      if(*current == '\0'){ 
       puts(start); 
       return 0; 
      } 
      lastChar = current-1; 
      current++,chars++; 
     } 
     } 

     if(lastChar == start) 
     lastChar = current-1; 

     printLine(start,lastChar); 
     current = lastChar + 1; 
     while(isDelim(*current)){ 
     if(*current == '\0') 
      return 0; 
     else 
      ++current; 
     } 
     start = current; 
     lastChar = current; 
     chars = 1; 
    } 

    return 0; 
} 

Así que, básicamente, no tengo start y lastChar que desea establecer como el comienzo de una línea y el último carácter de una línea. Cuando se configuran, obtengo una salida para excluir todos los caracteres de principio a fin, y luego imprimo un '\n', y continúo con la siguiente línea.

Inicialmente todo apunta al comienzo, luego omito palabras con while(!isDelim(*current)) ++current,++chars;. Mientras hago eso, recuerdo el último personaje que estaba antes de 80 caracteres (lastChar).

Si, al final de una palabra, he pasado mi número de caracteres (80), entonces salgo del bloque while(chars <= wrapLength). Salí todos los caracteres entre start y lastChar y un newline.

Entonces me puse a currentlastChar+1 y pase delimitadores (y si eso me lleva a la final de la cadena, que hemos terminado, return 0). Establezca start, lastChar y current al comienzo de la línea siguiente.

La parte

if(*current == '\0'){ 
    puts(start); 
    return 0; 
} 

es para las cadenas que son demasiado cortos para ser envuelto ni una sola vez. Lo agregué justo antes de escribir esta publicación porque probé una cadena corta y no funcionó.

Siento que esto podría ser factible de una manera más elegante. Si alguien tiene algo que sugerir, me encantaría probarlo.

Y mientras escribía esto, me preguntaba "¿qué va a pasar si tengo una cuerda que es una palabra que es más larga que mi espectro?" Bueno, no funciona. Por lo que añade el

if(lastChar == start) 
    lastChar = current-1; 

antes de la declaración printLine() (si lastChar no se ha movido, entonces tenemos una palabra que es demasiado largo para una sola línea, de modo que sólo tenemos que poner todo en la línea de todos modos) .

Retiré los comentarios del código ya que estoy escribiendo esto, pero realmente siento que debe haber una manera mejor de hacer esto que la que tengo que no necesitaría comentarios.

Así que esa es la historia de cómo escribí esto.Espero que pueda ser útil para las personas y también espero que alguien no esté satisfecho con mi código y proponga una forma más elegante de hacerlo.

Cabe señalar que funciona para todos los casos extremos: palabras demasiado largas para una línea, cadenas que son más cortas que una longitud de envolvente y cadenas vacías.

Cuestiones relacionadas