ハードラップされたテキストを再ラップするためのアルゴリズム?

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

通常、これはすべてうまく機能しますが、しばらくクリーンアップを先延ばしにしていた領域が 1 つあり、それはテキストの折り返しに関するものです。上記のようなきれいな電子メール形式を生成するには、顧客が最初に送信したテキストを再ラップする必要があります。

私はこれを行うアルゴリズムを書きました (ただし、コードを見ると、それがどのように機能するかはもう完全にはわかりません。リファクタリングが必要になる可能性があります)。 しかし、ハードラップ改行、「段落の終わり」改行、および「セマンティック」改行を区別することはできません。 たとえば、ハードラップ改行は、電子メール クライアントが、たとえば 79 桁の長いテキスト行を折り返すために段落内に挿入する改行です。段落末尾の改行は、ユーザーが段落の最後の文の後に追加した改行です。そして、セマンティック改行は次のようなものになります br タグ（フレッドが上で入力したアドレスなど）。

私のアルゴリズムでは、連続する 2 つの改行のみが新しい段落を示すものとみなされるため、顧客の電子メールは次のような形式になります。

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" - 顧客の住所などに改行を入力します。(私は新しい段落をいつ開始するかを決定するために 2 つの改行を続けて使用しています。これは、大多数の人が実際に電子メールを入力する方法と一致しています。)

意図したとおりにテキストを再ラップできるアルゴリズムを持っている人はいますか?それとも、特定のソリューションの複雑さを考慮した場合、この実装は「十分に優れている」のでしょうか?

ありがとう。

Answer 1

改行が挿入されているかどうかを確認して、行の長さを最大値（ハードラップ）未満に保つことができます。テキストの最も長い行を確認してください。次に、特定の行について、次の行の最初の単語を追加します。結果の行が最大長を超える場合、改行はおそらくハードラップでした。

さらに単純な場合は、(maxlength - 15) <= length <= maxlengthのすべてのブレークをハードラップと見なすことができます（15は単なる推測に基づくものです）。これにより、アドレスやスタッフのように意図的な休憩が確実に除外され、この範囲内で休憩を逃しても結果に悪影響が及ぶことはありません。

Answer 2

次の2つの提案があります。

• 句読点に注意してください：これは、<！> quot; hard-wrap <！> quot;を区別するのに役立ちます。改行と<！> quot;段落の終わり<！> quot;改行（行がフルストップで終わる場合、ユーザーが段落の終わりを意図した可能性が高いためです。

• 行が最大行長よりはるかに短いかどうかに注意してください。上記の例では、<！> quot; hard-wrapped <！> quot; 79文字で、さらに30行だけの住所行があります。 30は79よりもはるかに少ないため、アドレス行がユーザーのテキストラップアルゴリズムではなくユーザーによって破損されたことがわかります。

また、インデントにも注意してください：左から空白でインデントされている行は、このフォーラムにあるように、前の行から分割された新しい段落であると想定される場合があります。

Answer 3

上記の Ole のアドバイスに従って、しきい値を確認するために実装をやり直しました。私が実際に英語を理解するコードを夢中になって書かなくても、私が投げたほとんどのシナリオを十分にうまく処理しているようです。

基本的には、まず入力文字列をスキャンし、最長の行の長さを変数に記録します。 inputMaxLineLength. 。次に、再ラップしているときに、次のようなインデックスを持つ改行に遭遇した場合、 inputMaxLineLength そして85% inputMaxLineLength, 次に、その改行をスペースに置き換えます。これは、ハードラップ改行であると考えられるためです。ただし、すぐに別の改行が続いていない限り、その範囲内にたまたま存在する単なる 1 行の段落であると想定されるためです。これは、たとえば誰かが短い箇条書きリストを入力した場合に発生する可能性があります。

確かに完璧ではありませんが、最初からテキストが通常、以前の電子メール クライアントによって半分破壊されていることを考慮すると、私のシナリオには「十分」です。

以下にいくつかのコードを示します。数時間前の実装ですが、おそらくいくつかの特殊なケース (C# を使用) をまだ十分に理解していません。以前のソリューションよりもはるかに複雑ではなく、優れています。

ソースコード

そして、そのコードを実行するいくつかの単体テスト (MSTest を使用) を次に示します。

テストコード

誰かがより良い実装を持っている場合 (そして、より良い実装が存在することは間違いありません)、喜んであなたの意見を読んでみたいと思います。ありがとう。