Алгоритм переупаковки жесткого текста?

Question

Допустим, я написал специальное приложение для управления электронной почтой для компании, в которой я работаю. Он считывает электронные письма из учетной записи службы поддержки компании и сохраняет в базе данных очищенные текстовые версии в чистом виде, выполняя другие аккуратные вещи, например, связывая их с учетными записями клиентов и заказами. Когда сотрудник отвечает на сообщение, моя программа генерирует электронное письмо, которое отправляется клиенту с отформатированной версией ветки обсуждения. Если клиент отвечает, приложение ищет уникальный номер в строке темы, чтобы прочитать входящее сообщение, вычеркнуть предыдущее обсуждение и добавить его в качестве нового элемента в ветке. Например:

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

В общем, все это прекрасно работает, но есть одна область, которую я как бы откладываю на некоторое время, и она связана с переносом текста. Чтобы создать красивый формат электронной почты, подобный приведенному выше, мне нужно повторно обернуть текст, который изначально отправил клиент.

Я написал алгоритм, который делает это (хотя, глядя на код, я не совсем уверен, как он работает - он может использовать некоторый рефакторинг). Но он не может отличить жесткую новую строку, новую строку в конце абзаца и семантическую новую строку. Например, новая электронная почта - это та, которую почтовый клиент вставляется в абзац, чтобы обернуть длинную строку текста, скажем, в 79 столбцов. Новая строка в конце абзаца - это та, которую пользователь добавил после последнего предложения в абзаце. И семантическая новая строка будет выглядеть как тег br, например, адрес, который Фред напечатал выше.

Мой алгоритм вместо этого видит только две строки в строке, указывающие на новый абзац, поэтому электронная почта клиента будет отформатирована примерно так:

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

Всякий раз, когда я пытаюсь написать версию, в которой этот текст будет перефразирован по назначению, я в основном сталкиваюсь со стеной, в которой мне нужно знать семантику текста, разницу между «новой строкой» и « Я действительно имел в виду это как новую строку типа br ", например, в адресе клиента. (Я использую две новые строки подряд, чтобы определить, когда начинать новый абзац, что совпадает с тем, как большинство людей на самом деле набирают электронные письма.)

У кого-нибудь есть алгоритм, который может перематывать текст, как задумано? Или эта реализация "достаточно хороша" при оценке сложности любого конкретного решения?

Спасибо.

Answer 1

Вы можете попытаться проверить, была ли вставлена ​​новая строка, чтобы длина строки не превышала максимальную величину (иначе говоря, жесткую переноску): просто проверьте самую длинную строку в тексте. Затем для любой данной строки вы добавляете к ней первое слово следующей строки. Если результирующая строка превышает максимальную длину, разрыв строки, вероятно, был жестким переносом.

Еще проще, вы можете просто рассматривать все разрывы в (maxlength - 15) <= length <= maxlength как обертки (при этом 15 - просто догадка). Это, безусловно, отфильтровывает преднамеренные разрывы, как в адресах и прочем, и любой пропущенный разрыв в этом диапазоне не слишком сильно повлияет на результат.

Answer 2

Следуя совету Оле выше, я переработал свою реализацию, чтобы посмотреть на порог. Похоже, что он подходит для большинства сценариев, которые я использую достаточно хорошо, без необходимости сходить с ума и писать код, который действительно понимает английский язык.

Обычно я сначала сканирую входную строку и записываю самую длинную строку в переменную inputMaxLineLength. Затем, когда я переворачиваюсь, если я сталкиваюсь с символом новой строки, индекс которого составляет от inputMaxLineLength до 85% от inputMaxLineLength, то я заменяю этот символ новой строки пробелом, потому что я думаю, что это перевод строки, заключенный в жесткую переноску, если только он не последовал другой новой строкой, потому что тогда я предполагаю, что это просто однострочный абзац, который просто происходит в этом диапазоне. Это может произойти, если кто-то напечатает короткий маркированный список, например.

Конечно, не идеально, но «достаточно хорошо» для моего сценария, учитывая, что текст обычно наполовину искажен предыдущим почтовым клиентом.

Вот некоторый код, моя реализация, продолжавшаяся несколько часов, которая, вероятно, все еще не полностью реализована в некоторых крайних случаях (с использованием C #). Это намного менее сложно, чем мое предыдущее решение, и это приятно.

Исходный код

А вот некоторые модульные тесты, которые осуществляют этот код (используя MSTest):

Тестовый код

Если у кого-то есть лучшая реализация (и, несомненно, лучшая реализация существует), я буду рад прочитать ваши мысли! Спасибо.

Answer 3

У меня есть два предложения, как показано ниже.

• Обратите внимание на знаки препинания: это поможет вам различить новую строку с "жесткой переноской" и новую строку "конец абзаца" (потому что, если строка заканчивается полной остановкой, более вероятно, что пользователь хотел, чтобы это был конец абзаца.

• Обратите внимание на то, что строка намного короче максимальной длины строки: в приведенном выше примере у вас может быть текст, который «жестко упакован» в 79 символов, плюс у вас есть адресные строки, которые составляют всего 30 длинные символы; поскольку 30 намного меньше 79, вы знаете, что адресные строки были разбиты пользователем, а не алгоритмом переноса текста.

Кроме того, обратите внимание на отступы: строки, которые имеют отступ слева от пробела, могут быть новыми абзацами, оторванными от предыдущих строк, как они есть на этом форуме.