Algorithme de réemballage du texte enveloppé?

Question

Supposons que j'ai écrit une application de gestion de messagerie personnalisée pour l'entreprise pour laquelle je travaille. Il lit les e-mails du compte de support de la société et en stocke des versions en texte brut nettoyées dans une base de données, en effectuant d'autres tâches intéressantes, comme l'associer à des comptes clients et des commandes. Lorsqu'un employé répond à un message, mon programme génère un courrier électronique qui est envoyé au client avec une version formatée du fil de discussion. Si le client répond, l'application cherche un numéro unique dans la ligne d'objet pour lire le message entrant, élimine la discussion précédente et l'ajoute comme nouvel élément du fil de discussion. Par exemple:

This is a message from Contoso customer service.

Recently, you requested customer support. Below is a summary of your 
request and our reply.

--------------------------------------------------------------------
Contoso (Fred) on Tuesday, December 30, 2008 at 9:04 a.m.
--------------------------------------------------------------------
John:

I've modified your address. You can confirm my work by logging into
"Your Account" on our Web site. Your order should ship out today.

Thanks for shopping at Contoso.

--------------------------------------------------------------------
You on Tuesday, December 30, 2008 at 8:03 a.m.
--------------------------------------------------------------------
Oops, I entered my address incorrectly. Can you change it to

Fred Smith
123 Main St
Anytown, VA 12345

Thanks!

--
Fred Smith
Contoso Product Lover

En général, tout cela fonctionne très bien, mais il y a un domaine que je retarde depuis un certain temps, à savoir nettoyer le texte. Afin de générer le joli format de courrier électronique comme celui ci-dessus, je dois ré-emballer le texte que le client a envoyé à l'origine.

J'ai écrit un algorithme qui fait cela (bien que, regardant le code, je ne suis plus tout à fait sûr de savoir comment ça marche, il pourrait utiliser du refactoring). Mais il ne peut pas faire la distinction entre une nouvelle ligne, une & "; fin de paragraphe &"; nouvelle ligne et un " sémantique " newline. Par exemple, un saut de ligne rigide est celui que le client de messagerie électronique a inséré dans un paragraphe pour envelopper une longue ligne de texte, par exemple, sur 79 colonnes. Une nouvelle ligne de fin de paragraphe est une nouvelle ligne ajoutée par l'utilisateur après la dernière phrase d'un paragraphe. Et un retour à la ligne sémantique ressemblerait à la balise br, telle que l'adresse saisie par Fred ci-dessus.

Au lieu de cela, mon algorithme ne voit que deux nouvelles lignes à la suite indiquant un nouveau paragraphe, de sorte que le courrier électronique du client sera formaté de la manière suivante:

Oops, I entered my address incorrectly. Can you change it to

Fred Smith 123 Main St Anytown, VA 12345

Thanks!

-- Fred Smith Contoso Product Lover

Chaque fois que j'essaie d'écrire une version qui ré-enveloppe le texte comme prévu, je me heurte essentiellement à un mur car je dois connaître la sémantique du texte, la différence entre un & "hard-wrap < !> quot; nouvelle ligne et un & "; je le pensais vraiment comme une nouvelle ligne de type <=> &", telle que l'adresse du client. (J'utilise deux nouvelles lignes à la suite pour déterminer quand commencer un nouveau paragraphe, ce qui coïncide avec la façon dont la majorité des gens semblent taper des courriers électroniques.)

Quelqu'un a-t-il un algorithme capable de reformater le texte comme prévu? Ou bien cette implémentation & Est-elle suffisante?! lors de l'évaluation de la complexité d'une solution donnée?

Merci.

Answer 1

Vous pouvez essayer de vérifier si une nouvelle ligne a été insérée pour garder la longueur de ligne inférieure à un maximum (c'est-à-dire un retour rapide à la ligne): il suffit de rechercher la plus longue ligne du texte. Ensuite, pour toute ligne donnée, vous lui ajoutez le premier mot de la ligne suivante. Si la ligne résultante dépasse la longueur maximale, la rupture de ligne a probablement été dure.

Encore plus simple, vous pourriez simplement considérer toutes les pauses dans (maxlength - 15) <= length <= maxlength comme étant des blocages (15 étant une supposition éclairée). Cela filtrerait certainement les coupures intentionnelles, comme dans les adresses, etc., et toute coupure manquée dans cette plage n'influencerait pas trop le résultat.

Answer 2

J'ai deux suggestions, comme suit.

• Faites attention à la ponctuation: cela vous aidera à faire la distinction entre un & "hard-wrap &"; nouvelle ligne et une & fin de paragraphe " newline (car, si la ligne se termine par un point final, il est plus probable que l'utilisateur ait voulu en faire une fin de paragraphe.

• Faites attention si une ligne est beaucoup plus courte que la longueur maximale de la ligne: dans l'exemple ci-dessus, vous pourriez avoir du texte & "; enveloppé &"; à 79 caractères, plus vous avez des lignes d'adresse qui ne sont que 30 caractères; Comme 30 correspond à beaucoup moins que 79, vous savez que les lignes d'adresse ont été cassées par l'utilisateur et non par son algorithme de retour à la ligne.

Faites également attention aux retraits: les lignes qui sont en retrait avec des espaces à gauche peuvent être supposées être de nouveaux paragraphes, séparés des lignes précédentes, comme ils le sont sur ce forum.

Answer 3

Suivant les conseils d’Ole ci-dessus, j’ai retravaillé mon implémentation pour examiner un seuil. Il semble pouvoir gérer la plupart des scénarios que je présente assez bien sans que je sois obligé de devenir fou et d'écrire un code qui comprenne réellement la langue anglaise.

Fondamentalement, je balaye d'abord la chaîne d'entrée et enregistre la plus grande longueur de ligne dans la variable inputMaxLineLength. Ensuite, lors de la réemballage, si je rencontre une nouvelle ligne ayant un index compris entre <=> et 85% de <=>, je remplace cette nouvelle ligne par un espace, car je pense que c'est une nouvelle ligne très dure - sauf si elle est immédiatement suivie. par une autre nouvelle ligne, car alors je suppose que c’est juste un paragraphe d’une ligne qui se trouve dans cette plage. Cela peut arriver si quelqu'un tape une courte liste à puces, par exemple.

Certainement pas parfait, mais & "Assez bien &"; pour mon scénario, considérant que le texte est généralement à moitié mutilé par un client de messagerie précédent, pour commencer.

Voici un peu de code, mon implémentation vieille de quelques heures, qui continue probablement de mal fonctionner dans quelques cas extrêmes (en utilisant C #). C'est beaucoup moins compliqué que ma solution précédente, ce qui est bien.

code source

Et voici quelques tests unitaires qui exercent ce code (à l'aide de MSTest):

Code de test

Si quelqu'un a une meilleure implémentation (et une meilleure implémentation existe sans aucun doute), je serai heureux de lire vos pensées! Merci.