Meilleur algorithme d'habillage de mots?

Question

Retour automatique à la ligne est l'un des must-have de fonctionnalités modernes éditeur de texte.

Savez-vous comment gérer le retour à la ligne? Quel est le meilleur algorithme pour word-wrap?

mise à jour: Si le texte est de plusieurs millions de lignes, comment puis-je faire word-wrap très rapide?

mise à jour: Pourquoi j'ai besoin de la solution? Parce que mes projets doivent dessiner du texte avec différents niveaux de zoom et en même temps belle apparence.

mise à jour: environnement d'Exécution est les appareils Windows Mobile. Maximum 600 mhz vitesse avec une très petite taille de la mémoire.

mise à jour: Comment dois-je gérer de l'information en ligne? Supposons données d'origine a trois lignes.

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

Après coupure de mot texte sera affiché comme ceci:

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

Dois-je allouer 3 lignes plus? Ou d'autres suggestions?

Answer 1

Voici un word-wrap algorithme que j'ai écrit en C#. Il devrait être assez facile à traduire dans d'autres langues (sauf peut-être pour 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;
    }
}

C'est assez primitif - il des fentes sur les espaces, les tabulations et les tirets. Il ne assurez-vous que les tirets en tenir à la parole avant elle (donc vous ne finirez pas avec pile\n-débordement), bien qu'il ne favorise pas le déplacement de petits mots à mots pour un retour à la ligne plutôt que de les diviser. Il ne séparent des mots s'ils sont trop longs pour une ligne.

Il est aussi assez culturellement spécifiques, comme je ne sais pas beaucoup au sujet de la parole de l'habillage de règles dans d'autres cultures.

Answer 2

Donald E. Knuth fait beaucoup de travail sur la ligne de rupture de l'algorithme dans son TeX système de composition. C'est sans doute l'un des meilleurs algorithmes pour la ligne de rupture "meilleur" en termes d'apparence visuelle de résultat.

Son algorithme d'éviter les problèmes de gourmande de la ligne de remplissage où vous pouvez vous retrouver avec un tissu très dense de la ligne suivie par un très lâche de la ligne.

Un algorithme efficace qui peut être exécuté en utilisant la programmation dynamique.

Un papier sur le TeX de coupure de ligne.

Answer 3

Je ne sais pas si quelqu'un va lire ce voir comment vieux cette question, mais j'ai eu l'occasion d'écrire un mot envelopper fonction récemment, et je veux partager ce que je suis venu avec. J'ai utilisé une approche TDD presque aussi strict que celui de l' Aller de l'exemple. J'ai commencé avec le test que l'habillage de la chaîne "Hello, world!" à 80 largeur devrait revenir "Bonjour, Monde!" Clairement, la chose la plus simple qui fonctionne est le retour de la chaîne d'entrée intacte. A partir de là, j'ai fait de plus en plus complexe des tests et a terminé avec une solution récursive (au moins pour ma part) très gère efficacement la tâche.

Pseudo-code de la solution récursive:

La fonction WordWrap (inputString, largeur)
 La garniture de la chaîne d'entrée d'attaque et de fuite des espaces.

 Si la chaîne ajustée à la longueur de l'est <= à la largeur,
 De retour de la chaîne ajustée.
Autre chose,
 Trouver l'index de la dernière de l'espace dans la chaîne ajustée, en commençant à la largeur

 Si il n'y a pas d'espaces, l'utilisation de la largeur de l'indice.

 Diviser la chaîne ajustée en deux morceaux à l'index.

 Garniture espaces à partir de la partie avant de l'index,
 et les principaux espaces de la partie après l'indice.

 Concaténer et retour:
 le garni partie avant de l'index,
 un saut de ligne,
 et le résultat de l'appel WordWrap sur le garni partie après
 l'index (avec la même largeur que l'appel d'origine).

Cela ne enveloppements à des espaces, et si vous voulez enchaîner une chaîne de caractères qui contient déjà des sauts de ligne, vous avez besoin de le diviser en les sauts de ligne, d'envoyer chaque pièce de cette fonction, puis remonter la chaîne. Même si, dans VB.NET en cours d'exécution sur une machine rapide, ce qui peut gérer environ 20 mo/sec.

Answer 4

Concernant votre question de mise à jour et de vitesse, pensez à l'optimiser ultérieurement. Tout d'abord, écrivez votre algorithme d'habillage de mots. Exécutez-le sur un million de lignes si du texte. Si et seulement s'il est trop lent pour vos besoins, alors optimisez.

Answer 5

Je ne sais pas du tout des algorithmes spécifiques, mais ne serait pas la suite être une ébauche de la façon dont il devrait fonctionner:

1. Pour le courant de la taille du texte, police, taille de l'écran, la taille de la fenêtre, les marges, etc, déterminer le nombre de caractères peuvent tenir sur une ligne (si type fixe), ou le nombre de pixels qui peuvent tenir sur une ligne (si ce n'est de type fixe).
2. Aller à travers la ligne de caractère par caractère, calculer le nombre de caractères ou de pixels ont été enregistrés depuis le début de la ligne.
3. Quand vous allez au max de caractères/pixels de la ligne, de revenir à la dernière de l'espace/les signes de ponctuation, déplacer tout le texte à la ligne suivante.
4. Répétez jusqu'à ce que vous allez à travers tout le texte dans le document.

Question: Dans .net, mot d'habillage fonctionnalité est intégrée dans les contrôles de zone de texte. Je suis sûr que même construit dans la fonctionnalité existe pour d'autres langues. Est-il une raison pourquoi vous ne voulez pas utiliser un pré-construit solution? Cela semble le long de la lignes de réinventer la roue.