algorithm - para - distancia de levenshtein sql
Mejor algoritmo de ajuste de palabras (12)
Word wrap es una de las características imprescindibles del editor de texto moderno.
¿Sabes cómo manejar el ajuste de palabras? ¿Cuál es el mejor algoritmo para el ajuste de palabras?
actualizado: si el texto es de 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.
actualizado: el entorno en ejecución es dispositivos de Windows Mobile. 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 del texto de salto de 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?
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 y solo si es demasiado lento para sus necesidades, entonces optimícelo.
No conozco ningún algoritmo específico, pero el siguiente no sería un bosquejo de cómo debería funcionar:
- Para el tamaño de texto actual, fuente, tamaño de visualización, tamaño de ventana, 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).
- Ir a través de la línea carácter por carácter, calculando cuántos caracteres o píxeles se han registrado desde el comienzo de la línea.
- Cuando revise los caracteres / caracteres máximos para la línea, vuelva al último espacio / signo de puntuación, mueva todo el texto a la siguiente línea.
- Repita hasta que revise todo el texto del documento.
Pregunta: En .net, la función de ajuste de palabras 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.
Me preguntaba lo mismo para mi propio proyecto de editor. Mi solución fue un proceso de dos pasos:
- Encuentre la línea y guárdela en una matriz.
- Para líneas muy largas, encuentre los puntos de ruptura 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, encuentre 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 usar 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.
De forma 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.
con o sin separación silábica?
sin es 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 silábica necesita reglas de separación por sílabas en un formato común como: hy-phen-a-tion
Luego es el mismo que el anterior, excepto que necesita dividir la última palabra que ha causado el desbordamiento.
Un buen ejemplo y tutorial de cómo estructurar su código para un excelente textector se encuentra en el libro Pandillas de cuatro patrones de diseño. Es uno de la muestra principal en la que muestran los patrones.
No sé si alguien leerá esto viendo cuántos años tiene 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 ejemplo Go . 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 para 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 solo se ajusta a espacios, y si desea envolver una cadena que ya contiene saltos de línea, debe dividirla en los saltos de línea, enviar cada pieza a esta función y luego volver a ensamblar la cadena. Aun así, en VB.NET ejecutándose en una máquina rápida, esto puede manejar aproximadamente 20 mb / seg.
@ICR, gracias por compartir el ejemplo C #. No tuve éxito en usarlo, pero se me ocurrió otra solución. Si hay algún interés en esto, siéntase libre de usar esto: http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/
He incluido pruebas unitarias / muestras.
¡Gracias!
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;
}
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.
Un algoritmo eficiente puede ser implementado usando programación dinámica.
Aquí hay un algoritmo de redacción de palabras que he escrito en C #. Debería ser bastante fácil de traducir a otros idiomas (excepto tal vez 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.
No puedo reclamar la ausencia de errores de esto, pero necesitaba una palabra que cumpliera y obedeciera los límites de la sangría. No afirmo 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);
}
}
}
También puedo intervenir con una solución perl que hice, porque los fold -s gnu estaban dejando espacios al final y otros malos comportamientos. 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 texto con no más de un espacio en una fila (y sin CR) no cambia wc -c (porque reemplaza el espacio con LF en lugar de insertar 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);
}
Aquí está el mío en el que estaba trabajando para divertirme en C:
Aquí están mis consideraciones:
1) No copia de caracteres, solo imprime en stdout. 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
convertirse
This line breaks
here
así que cambiar los caracteres a ''/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.
Entonces 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;
}
Entonces, básicamente, tengo start y lastChar que quiero establecer como el inicio de una línea y el último carácter de una línea. Cuando se configuran, obtengo una salida para excluir a todos los caracteres de principio a fin, luego genero ''/n'' y continúo con la siguiente línea.
Inicialmente todo apunta al comienzo, luego while(!isDelim(*current)) ++current,++chars; palabras con el while(!isDelim(*current)) ++current,++chars; . Mientras hago eso, recuerdo el último personaje que estaba antes de los 80 caracteres ( lastChar ).
Si, al final de una palabra, he pasado mi número de caracteres (80), entonces salgo del bloque while(chars <= wrapLength) . lastChar todos los caracteres entre start y lastChar y una newline .
Luego configuro current to lastChar+1 y lastChar+1 delimitadores (y si eso me lleva al final de la cadena, hemos terminado, return 0 ). Establezca start , lastChar y current al comienzo de la siguiente línea.
los
if(*current == ''/0''){
puts(start);
return 0;
}
parte es para cuerdas que son demasiado cortas para ser envueltas, incluso una 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 wraplength?" Bueno, no funciona. Entonces agregué el
if( lastChar == start )
lastChar = current-1;
antes de la printLine() (si lastChar no se ha movido, entonces tenemos una palabra que es demasiado larga para una sola línea, así que solo tenemos que poner todo en la línea de todos modos).
Retiré los comentarios del código desde que escribo esto, pero realmente siento que debe haber una manera mejor de hacer esto que la que tengo que no necesitaría comentarios.
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.