タグで囲むアルゴリズムが知りたい。

.
　　char, bold, italic, ruby
　　あ, False, False, False
　　い, True, False, False
　　う, True, False, False
　　え, True, True, False
　　お, True, False, False
　　か, False, True, False
　　き, False, True, False
　　く, True, False, True
　　け, True, False, False
　　こ, False, True, False

　以上のようなデータを以下のようにタグで囲むようなアルゴリズムを教えてください。

　　あ<b>いう<i>え</i>お</b><i>かき</i><b><r>く</r>け</b><i>こ</i>

　まったく同じ部分をタグで囲む時に、外側にくる優先順位は、b,i,rの順です。(別にこの順序でなくてもいいんですが、優先順位があるというだけです。)
　ただし、大きく囲った方がタグが少なくなる場合は、上の外側にくる優先順位に従いません。
　あと、この例ではcharは1文字ですが実際は２文字以上入ってる可能性があります。

　自分でいろいろと考えてやっているんですがどうも上手くいきません。

　１つの列だけを考慮するなら置換で問題なく出来るんですが、複数の列を考慮すると上手くいきませんでした。
　for文で繰り返し中に各列の値で場合わけをして、それに合わせてcharを分類して後でタグで囲む方法も試しました。
　しかし、大きく囲えるものを外側にするかどうかを考慮すると、<b>が<i>の外側に来る場合とその逆で<i>が<b>の外側に来る場合があり、さらに他のタグ同士の組み合わせもあるので、物凄い量のケースを考慮しなければならず、うまくできません。


　HTMLやXMLなどのタグ付けに関連するに似たプログラムがたくさんあるので、何かしら有効なロジックがあると思うのですが、Googleで検索しても、「タグ」という言葉でブログやＳＮＳの使い方、HTMLの作り方などばかりがヒットして見つけることができませんでした。

そこで、アルゴリズム自体、説明しているサイト、またはコード(Pythonなら分かる)を教えてください。
また、Python3で使えそうなライブラリがもしあればそれもお願いします。
（BeautifulSoupのタグ補完は試しましたが、使い方が悪いのか望んだような結果にはなりませんでした。）

よろしくお願いします。

No.2 回答者： himajin100000 回答日時： 2017/10/25 05:35

よく知られるアルゴリズムありそうだけど、単純に自力で解く算数問題として面白そうだったのでチャレンジしてみた。

VBAで考えてたんですが、デバッグで疲れたので使い慣れないPythonに移植するだけの気力が残りませんでした。

以下、自分なりの解答(正しいかどうかは自分で検証してね)

基本は現在の行と前行が異なる項目についてfalse→trueなら開始タグ、true→falseなら終了タグを置く。
まず必要な終了タグ(下位から)を全部出力してから必要な開始タグ(上位から)をすべて出力し、最後に文字列を足す。

ただし。
問題になるケースは、隣り合わせの2行について、下位のフィールドが両方trueなのに上位のフィールドが異なっていた場合である。
"", false , false, false #番兵
"あ", true,false, true
"い", true,true, true
"", false,false,false #番兵

誤: <b><r>あ<i>い</r></i></b> ←単純に前行と比較
正: <b><r>あ</r><i><r>い</r></i></b> ← rが一旦閉じてまた開く

そこで間に仮データを挟む

"", false , false, false #番兵
"あ", true,false, true
"",true, false, false #←問題となっているtrue同士の間にfalseを挟む。他のフィールドは前行を踏襲
"い", true,true, true
"", false,false,false #番兵

同様のことは真ん中でも起こる

"", false , false, false #番兵
"あ", false, true,false
"い",true ,true,false # italicはこの行と前行の両方がtrueだけど、それより上位のboldは異なる
"", false,false,false #番兵
<i>あ<b>い</i></b>

同様に

"", false , false, false #番兵
"あ", false, true,false
"", false, false, false
"い",true ,true,false
"", false,false,false #番兵

<i>あ</i><b><i>い</i></b>

3つの項目なら3位のデータについて扱ったあと、2位のデータについて扱うなど連鎖することもあるだろう。そこらへんをループでなんとか最後までやりきる。
====================以下VBA===========================-
'Sheet1

Option Explicit

Const FieldCount As Integer = 4 ' 属性と文字列両方合わせて4列
Const EndDetector As Integer = 2 ' 2列目のデータが空だったらストップ(別に条件はなんでもいい)
Const AttributeStart As Integer = 2 'フォントの各属性(太字,イタリック,ルビ)が存在するのは2列目

Sub Main()
Call Adjust
Call Work
End Sub

'気力がなくて用意されたシートに番兵などを追加してデータを変更している

Sub Adjust()
Dim i As Integer
Dim j As Integer
Dim k As Integer

Dim process As Boolean

'Cells等は原則として1オリジンである

'ヘッダは入力してません。いきなりデータから始めてます

'最初の番兵
Rows(1).Insert
'一行目は空(文字列)
For j = AttributeStart To FieldCount
Cells(1, j).Value = False
Next j

i = 2
Do While Cells(i, EndDetector).Value <> ""
For j = FieldCount To (AttributeStart + 1) Step -1
process = False
If isSameAsPreviousRecord(i, j) And Cells(i, j).Value Then
For k = j - 1 To 2 Step -1
If Not isSameAsPreviousRecord(i, k) Then
process = True
Exit For
End If
Next k
End If
If process Then
Rows(i).Insert
Rows(i - 1).Copy (Rows(i))
Cells(i, j).Value = False
Cells(i, 1).Value = ""
i = i + 1
End If
Next j

i = i + 1
Loop ' DoからLoopまで(説明相手が他言語経験者だから)

'どうせ空行なので行は挿入しない

'最後の番兵
For j = AttributeStart To FieldCount
Cells(i, j).Value = False
Next j
End Sub

Sub Work()
Dim i As Integer
Dim j As Integer
Dim x As String
Dim tagnames(2) As String
tagnames(0) = "b"
tagnames(1) = "i"
tagnames(2) = "r"
x = ""
i = 2
Do While Cells(i, EndDetector).Value <> ""
For j = FieldCount To AttributeStart Step -1
If (Cells(i - 1, j).Value = True) And (Cells(i, j).Value = False) Then
' 本当は要素名として適切かどうかのチェックができるように考えたいが…面倒なので
x = x & "</" & tagnames(j - AttributeStart) & ">"
End If

Next j
For j = AttributeStart To FieldCount
If (Cells(i - 1, j).Value = False) And (Cells(i, j).Value = True) Then
' 同上
x = x & "<" & tagnames(j - AttributeStart) & ">"
End If


Next j
x = x & Cells(i, 1).Value
i = i + 1
Loop
Debug.Print (x)
End Sub

Function isSameAsPreviousRecord(i As Integer, j As Integer) As Boolean
isSameAsPreviousRecord = Cells(i, j).Value = Cells(i - 1, j).Value '他言語で言うReturn
End Function

===========CSVデータ============
あ,FALSE,FALSE,TRUE
い,TRUE,TRUE,TRUE

No.1 回答者： Ogre7077 回答日時： 2017/10/23 17:13

ご提示の課題解決のためには、コンパイル技術の一つである構文解析が必要です。

https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87 …

今回の様に独自のルールで解析させるためには、既存のライブラリは使えないので、自分でロジックをくみ上げましょう。
一般的には再帰下降構文解析を行って、構造木を作成するのですが、
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0 …

この程度の課題なら、以下の様なロジック程度で十分かと思います。

* データ各行をテキスト要素として、配列へ格納
例: [ あ, い, う, え, お, か, き, く, け, こ ]

* bold の開始位置と終了位置を探す
開始位置の条件: 要素が bold=True かつ 前要素がテキスト要素で bold=False
終了位置の条件: 要素が bold=True かつ 次要素がテキスト要素で bold=False
注意: 配列の範囲外へのアクセスは、空要素として処理
例: い=開始, お=終了, く=開始, け=終了

* 配列の開始位置の直前にタグ要素 <b> を挿入
* 配列の終了位置の直後にタグ要素 </b> を挿入
例: [ あ, <b>, い, う, え, お, </b>, か, き, <b>, く, け, </b>, こ ]

* 同様に italic を探して <i> と </i> を挿入
例: え=開始/終了, か=開始, き=終了, こ=開始/終了
例: [ あ, <b>, い, う, <i>, え, </i>, お, </b>, <i>, か, き, </i>, <b>, く, け, </b>, <i>, こ, </i> ]

* 同様に ruby を探して <r> と </r> を挿入
例: く=開始/終了
例: [ あ, <b>, い, う, <i>, え, </i>, お, </b>, <i>, か, き, </i>, <b>, <r>, く, </r>, け, </b>, <i>, こ, </i> ]

* 配列を結合して表示
例: あ<b>いう<i>え</i>お</b><i>かき</i><b><r>く</r>け</b><i>こ</i>