Miglior algoritmo di word wrap?

Il wrap di parole è una delle caratteristiche indispensabili nel moderno editor di testo.

Sai come gestire il wrap di parole? Qual è il miglior algoritmo per il word-wrap?

aggiornato: se il testo è di diverse milioni di righe, come posso eseguire il word-wrap molto velocemente?

aggiornato: Perché ho bisogno della soluzione? Perché i miei progetti devono disegnare il testo con vari livelli di zoom e contemporaneamente un aspetto bellissimo.

aggiornato: l’ambiente di esecuzione è dispositivi Windows Mobile. Velocità massima di 600 MHz con dimensioni di memoria molto ridotte.

aggiornato: come devo gestire le informazioni sulla linea? Supponiamo che i dati originali abbiano tre linee.

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

Il testo dopo l’interruzione della parola verrà mostrato in questo modo:

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

Devo allocare 3 linee in più? O qualche altro suggerimento?

Ecco un algoritmo di word-wrap che ho scritto in C #. Dovrebbe essere abbastanza facile da tradurre in altre lingue (tranne forse per 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 parts = new List(); 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; } } 

È piuttosto primitivo – si divide su spazi, tabulazioni e trattini. Fa in modo che i trattini restino fedeli alla parola che precede (quindi non si finisce con lo stack \ n-overflow) sebbene non favorisca lo spostamento di piccole parole con trattino in una nuova riga invece di dividerle. Separa le parole se sono troppo lunghe per una linea.

È anche abbastanza culturalmente specifico, dato che non conosco molto le regole di avvolgimento di parole di altre culture.

Donald E. Knuth ha lavorato molto sull’algoritmo di rottura riga nel suo sistema di composizione tipografica TeX. Questo è probabilmente uno dei migliori algoritmi per l’interruzione di riga – “migliore” in termini di aspetto visivo del risultato.

Il suo algoritmo evita i problemi di riempimento di linee avide in cui si può finire con una linea molto densa seguita da una linea molto allentata.

Un algoritmo efficiente può essere implementato utilizzando la programmazione dynamic.

Un articolo sulla rottura della linea di TeX .

Non so se qualcuno leggerà mai questo vedere quanti anni ha questa domanda, ma ho avuto l’occasione di scrivere una funzione di wrap di parole di recente, e voglio condividere ciò che mi è venuto in mente. Ho usato un approccio TDD quasi rigoroso come quello dell’esempio Go . Ho iniziato con il test che avvolge la stringa “Ciao, mondo!” a 80 larghezza dovrebbe restituire “Hello, World!” Chiaramente, la cosa più semplice che funziona è restituire intatta la stringa di input. A partire da quello, ho fatto test sempre più complessi e ho trovato una soluzione ricorsiva che (almeno per i miei scopi) gestiva in modo abbastanza efficiente l’attività.

Pseudocodice per la soluzione ricorsiva:

 Funzione WordWrap (inputString, larghezza)
     Taglia la stringa di input degli spazi iniziali e finali.

     Se la lunghezza della corda tagliata è <= la larghezza,
         Restituisce la corda tagliata.
     Altro,
         Trova l'indice dell'ultimo spazio nella stringa tagliata, a partire dalla larghezza

         Se non ci sono spazi, usa la larghezza come indice.

         Dividi la stringa tagliata in due pezzi all'indice.

         Taglia gli spazi finali dalla parte prima dell'indice,
         e conducendo spazi dalla parte dopo l'indice.

         Concatena e restituisce:
           la parte tagliata prima dell'indice,
           una interruzione di riga,
           e il risultato di chiamare WordWrap sulla parte ritagliata dopo
             l'indice (con la stessa larghezza della chiamata originale).

Questo si limita agli spazi e, se vuoi racchiudere una stringa che contiene già interruzioni di riga, devi dividerla nelle interruzioni di riga, inviare ciascun pezzo a questa funzione e quindi riassemblare la stringa. Anche così, in VB.NET in esecuzione su una macchina veloce, questo può gestire circa 20 mb / sec.

Per quanto riguarda la tua domanda di aggiornamento e velocità, ricorda di ottimizzare in seguito. Innanzitutto, scrivi l’algoritmo di avvolgimento delle parole. Eseguilo su un milione di righe se il testo. Se e solo se è troppo lento per le tue esigenze, allora ottimizza.

Non conosco algoritmi specifici, ma il seguente non dovrebbe essere un abbozzo di come dovrebbe funzionare:

  1. Per dimensioni del testo, font, dimensioni di visualizzazione, dimensioni della finestra, margini, ecc., Determinare quanti caratteri possono essere contenuti su una linea (se di tipo fisso) o quanti pixel possono essere contenuti su una linea (se non di tipo fisso).
  2. Passa attraverso la riga carattere per carattere, calcolando quanti caratteri o pixel sono stati registrati dall’inizio della riga.
  3. Quando superi i caratteri / pixel massimi per la linea, torna all’ultimo segno di punteggiatura, sposta tutto il testo sulla riga successiva.
  4. Ripeti fino a quando non passi tutto il testo nel documento.

Domanda: In .net, la funzionalità di word wrapping è incorporata in controlli come TextBox. Sono sicuro che funzionalità incorporate simili esistono anche per altre lingue. C’è una ragione per cui non vuoi usare una soluzione pre-costruita? Questo sembra sulla falsariga di reinventare la ruota.

con o senza sillabazione?

senza la sua facile Basta incapsulare il testo come parolaobject per parola e dare loro un metodo getWidth () quindi iniziare dalla prima parola sumndo la lunghezza della riga finché non è maggiore dello spazio disponibile. in tal caso, avvolgere l’ultima parola e ricominciare a contare per la riga successiva che inizia con questa ecetera.

Con la sillabazione sono necessarie regole di sillabazione in un formato comune come: hy-phen-a-tion

Quindi è lo stesso di sopra tranne che è necessario dividere l’ultima parola che ha causato l’overflow.

Un buon esempio e un tutorial su come strutturare il codice per un eccellente texteditor è fornito nel libro Gang of Four Design Patterns. È uno dei campioni principali su cui mostrano i pattern.

Mi sono chiesto la stessa cosa per il mio progetto editoriale. La mia soluzione era un processo in due fasi:

  1. Trova le estremità della linea e memorizzale in un array.
  2. Per linee molto lunghe, trova i punti di rottura adatti a intervalli di circa 1K e salvali anche nell’array line. Questo per catturare il “testo da 4 MB senza interruzioni di linea”.

Quando hai bisogno di visualizzare il testo, trova le linee in questione e avvolgile al volo. Ricorda queste informazioni in una cache per un rapido ridisegno. Quando l’utente scorre un’intera pagina, svuota la cache e ripeti.

Se è ansible, caricare / analizzare l’intero testo in un thread in background. In questo modo, puoi già visualizzare la prima pagina di testo mentre il resto del documento è ancora in fase di esame. La soluzione più semplice qui è quella di tagliare i primi 16KB di testo e di eseguire l’algoritmo sulla sottostringa. Questo è molto veloce e ti permette di visualizzare immediatamente la prima pagina, anche se il tuo editor sta ancora caricando il testo.

Puoi usare un approccio simile quando il cursore è inizialmente alla fine del testo; basta leggere gli ultimi 16 KB di testo e analizzarlo. In questo caso, utilizzare due buffer di modifica e caricare tutti tranne gli ultimi 16 KB nel primo mentre l’utente è bloccato nel secondo buffer. E probabilmente vorrai ricordare quante righe ha il testo quando chiudi l’editor, quindi la barra di scorrimento non sembra strana.

Diventa peloso quando l’utente può avviare l’editor con il cursore da qualche parte nel mezzo, ma alla fine è solo un’estensione del problema finale. Solo tu devi ricordare la posizione del byte, il numero di riga corrente e il numero totale di righe dell’ultima sessione, più hai bisogno di tre buffer di modifica o hai bisogno di un buffer di modifica in cui puoi tagliare 16 KB nel mezzo.

In alternativa, bloccare la barra di scorrimento e altri elementi dell’interfaccia mentre il testo viene caricato; che consente all’utente di guardare il testo mentre si carica completamente.

Ecco il mio su cui stavo lavorando oggi per divertirmi in C:

Ecco le mie considerazioni:

1) Nessuna copia di caratteri, è sufficiente stampare su stdout. Pertanto, poiché non mi piace modificare gli argomenti argv [x], e poiché mi piace una sfida, ho voluto farlo senza modificarlo. Non ho avuto l’idea di inserire '\n' .

2) Non voglio

 This line breaks here 

diventare

 This line breaks here 

cambiare i caratteri in '\n' non è un’opzione data questo objective.

3) Se l’ampiezza di riga è impostata su 80 e l’ottantesimo carattere è nel mezzo di una parola, l’intera parola deve essere posizionata sulla riga successiva. Quindi, mentre stai scansionando, devi ricordare la posizione della fine dell’ultima parola che non ha superato gli 80 caratteri.

Quindi qui è mio, non è pulito; Mi sono rotto la testa da un’ora passata cercando di farlo funzionare, aggiungendo qualcosa qua e là. Funziona per tutti i casi limite che io conosca.

 #include  #include  #include  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; } 

Quindi, in sostanza, ho start e lastChar che voglio impostare come inizio di una riga e l'ultimo carattere di una linea. Quando questi sono impostati, esco in output per stdout tutti i caratteri dall'inizio alla fine, quindi emetto un '\n' e passiamo alla riga successiva.

Inizialmente tutto punta all'inizio, poi salta le parole con il while(!isDelim(*current)) ++current,++chars; . Mentre lo faccio, ricordo l'ultimo carattere che era prima di 80 caratteri ( lastChar ).

Se, alla fine di una parola, ho passato il mio numero di caratteri (80), allora while(chars <= wrapLength) blocco while(chars <= wrapLength) . lastChar tutti i caratteri tra start e lastChar e una newline .

Poi imposto la current a lastChar+1 e salta i delimitatori (e se questo mi porta alla fine della stringa, abbiamo finito, return 0 ). Imposta start , lastChar e current all'inizio della riga successiva.

Il

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

parte è per stringhe troppo corte per essere avvolte anche una sola volta. L'ho aggiunto prima di scrivere questo post perché ho provato una stringa breve e non ha funzionato.

Credo che questo potrebbe essere fattibile in un modo più elegante. Se qualcuno ha qualcosa da suggerire mi piacerebbe provarlo.

E mentre scrivevo questo mi sono chiesto "cosa succederà se avrò una stringa che è una parola che è più lunga della mia lunghezza". Beh, non funziona. Quindi ho aggiunto il

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

prima printLine() (se lastChar non è stato spostato, allora abbiamo una parola troppo lunga per una singola riga, quindi dobbiamo solo mettere l'intera cosa sulla linea comunque).

Ho preso i commenti dal codice da quando sto scrivendo questo, ma sento davvero che ci deve essere un modo migliore per farlo rispetto a quello che ho che non avrebbe bisogno di commenti.

Quindi questa è la storia di come ho scritto questa cosa. Spero che possa essere utile alle persone e spero anche che qualcuno sia insoddisfatto del mio codice e proponga un modo più elegante di farlo.

Va notato che funziona per tutti i casi limite: parole troppo lunghe per una linea, stringhe che sono più corte di una wrapLength e stringhe vuote.

Ecco la soluzione in C #. Ha rovesciato l’unica parola con il limite superiore e altre parole rimangono come al solito.

  ///  /// Word wraps the given text to fit within the specified width. ///  /// Text to be word wrapped /// Width, in characters, to which the text /// should be word wrapped /// The modified text 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(); } ///  /// Locates position to break the given line so as to avoid /// breaking words. ///  /// String that contains line of text /// Index where line of text starts /// Maximum line length /// The modified line length 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; } 

Non posso reclamare la mancanza di errori, ma avevo bisogno di una parola che avvolgesse e obbedisse ai confini della rientranza. Non rivendico nulla di questo codice se non quello che ha funzionato per me finora. Questo è un metodo di estensione e viola l’integrità di StringBuilder ma potrebbe essere fatto con qualsiasi input / output desiderato.

 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); } } } 

@ ICR, grazie per aver condiviso l’esempio C #. Non ci sono riuscito a usarlo ma ho trovato un’altra soluzione. Se ci sono interessi in questo, per favore sentiti libero di usare questo: http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/

Ho incluso test / campioni unitari.

Grazie!

Potrei anche cantare con una soluzione perl che ho creato, perché gnu fold -s stava lasciando spazi finali e altri cattivi comportamenti. Questa soluzione non gestisce (correttamente) il testo contenente tabulazioni o backspaces o ritorni a capo incorporato o simili, sebbene gestisca le terminazioni di riga CRLF, convertendole tutte solo in LF. Rende minimo il cambiamento del testo, in particolare non divide mai una parola (non cambia wc -w ), e per il testo con non più di un singolo spazio di fila (e nessun CR) non cambia wc -c (perché sostituisce lo spazio con LF anziché inserire 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); }