下記のように、文字列の差分を求めるアルゴリズムの確認をしたかったので、PowerShellで実装してみた。
(アドカレ用に記事を書いていたわけではないが、時期的に被ったので投稿)
元ネタ
- 差分検出アルゴリズム三種盛り
- 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～#レーベンシュタイン距離-diffコマンド
- 意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法#2-3-レーベンシュタイン距離
やりたいこと
- 素朴な動的計画法で下記を求める
- 編集距離（ただし、置換は含まず、挿入・削除の編集のみ）
- SES（Shortest Edit Script）
- 色付きの差分表示
なお、詳細な説明も、効率的なアルゴリズムの実装もしないので、気になる人は元ネタを読んでください。
動的計画法の表を求める
下記のとおり、表（２次元配列）を２つ求める。
編集距離の表
１つ目の表は編集距離を表すものである。
最左上を 0行, 0列 とすると、上記画像の 3行, 4列 の編集距離は 3 になっている。これは、kittenの先頭3文字kitからsittingの先頭4文字sittへ、挿入または削除の操作を3回実施することで変換できることを表す。具体的には、「kit -(kを削除)-> it -(sを挿入)-> sit -(tを挿入)-> sitt」である。
このように、編集距離の表はkittenの先頭からの各部分文字列と、sittingの先頭からの各部分文字列の組み合わせの編集距離すべてを表している（動的計画法なので部分問題の解が一緒に求まる）。特に、0行目は空文字からの変換を表し、0列目は空文字への変換を表している。
SESの表
２つ目のひょうはSESを表すものである。*が操作なし、+が挿入、-が削除の操作を表す。
上記画像の 3行, 4列 の操作は+になっているが、kitからsittへ変換するSESの最後の編集操作が挿入であることを表す。具体的には、「sit -(tを挿入)-> sitt」である。
細かくは説明しないが、SESの最終操作がわかるので、逆順に辿ることで、SES全体が求まる。
実装
実装は下記の通り。動的計画法はなんらかのDAG（有向非巡回グラフ）の最短経路問題を解いているが、このアルゴリズムの場合、編集グラフというDAGの最短経路問題を解いていることになる。
filter Get-EditTable
{
Param (
[string] $Reference,
[string] $Difference,
[int] $CommonCost = 0,
[int] $DeletionCost = 1,
[int] $InsertionCost = 1,
[char] $CommonChar = "*",
[char] $DeletionChar = "-",
[char] $InsertionChar = "+"
)
if ($CommonCost -lt 0 -or $DeletionCost -lt 0 -or $InsertionCost -lt 0)
{Write-Error "Cost 負"}
if ((@($CommonChar, $DeletionChar, $InsertionChar) | Sort-Object -Unique).Length -lt 3)
{Write-Error "Char 重複"}
$n = $Reference.Length
$m = $Difference.Length
$dp = @{
Cost = New-Object "Int[][]" ($n + 1)
Char = New-Object "Char[][]" ($n + 1)
}
foreach ($i in 0..$n)
{
$dp.Cost[$i] = New-Object "Int[]" ($m + 1)
$dp.Char[$i] = New-Object "Char[]" ($m + 1)
}
foreach ($i in 0..$n)
{
$dp.Cost[$i][0] = $i
$dp.Char[$i][0] = $DeletionChar
}
foreach ($j in 0..$m)
{
$dp.Cost[0][$j] = $j
$dp.Char[0][$j] = $InsertionChar
}
$dp.Char[0][0] = $CommonChar
if ($n -eq 0 -or $m -eq 0)
{return $dp}
foreach ($i in 1..$n)
{
foreach ($j in 1..$m)
{
$com = $dp.Cost[($i - 1)][($j - 1)] + $CommonCost
$del = $dp.Cost[($i - 1)][($j )] + $DeletionCost
$ins = $dp.Cost[($i )][($j - 1)] + $InsertionCost
$isCom = $Reference[($i - 1)] -eq $Difference[($j - 1)]
if ($isCom -and $com -lt [Math]::Min($del, $ins))
{
$dp.Cost[$i][$j] = $com
$dp.Char[$i][$j] = $CommonChar
}
elseif ($del -lt $ins)
{
$dp.Cost[$i][$j] = $del
$dp.Char[$i][$j] = $DeletionChar
}
else
{
$dp.Cost[$i][$j] = $ins
$dp.Char[$i][$j] = $InsertionChar
}
}
}
$dp
}
編集距離を求める
編集距離の表の最右下を返せばOK。
filter Measure-EditDistance
{
Param (
[string] $Reference,
[string] $Difference,
[int] $CommonCost = 0,
[int] $DeletionCost = 1,
[int] $InsertionCost = 1
)
(Get-EditTable @PSBoundParameters).Cost[$Reference.Length][$Difference.Length]
}
SESを求める
下記のような列を求める。
SESの読み方
上記画像の読み方は下記の通りである。
操作 | 意味 | 操作前 | 操作後
-----+--------------+---------------+-------------
-k | kを削除 | k itten | itten
+s | sを挿入 | itten | s itten
*i | iはそのまま | s i tten | s i tten
*t | tはそのまま | si t ten | si t ten
*t | tはそのまま | sit t en | sit t en
-e | eを削除 |sitt e n | sittn
+i | i を挿入 |sittn | sitt i n
*n | nはそのまま | sitti n | sitti n
+g | gを挿入 |sittin | sittin g
ちなみに、置換を操作に含めない場合、-と*の文字をひろうとkitten、+と*の文字をひろうとsittingになる。
実装
SESの表の最右下から逆順に辿るとSESが求まる。
filter Get-EditScript
{
Param (
[string] $Reference,
[string] $Difference,
[int] $CommonCost = 0,
[int] $DeletionCost = 1,
[int] $InsertionCost = 1,
[char] $CommonChar = "*",
[char] $DeletionChar = "-",
[char] $InsertionChar = "+"
)
$dpChar = (Get-EditTable @PSBoundParameters).Char
$stack = New-Object "System.Collections.Generic.Stack[string]"
$i = $Reference.Length
$j = $Difference.Length
while ($i -gt 0 -or $j -gt 0)
{
$char = $dpChar[$i][$j]
switch ($char)
{
$DeletionChar
{
$i--
$stack.Push(($char + $Reference[$i]))
break
}
$InsertionChar
{
$j--
$stack.Push(($char + $Difference[$j]))
break
}
Default
{
$i--; $j--
$stack.Push(($char + $Reference[$i]))
break
}
}
}
$stack
}
色付きの差分表示をさせる
はじめに見せたとおり、下記のように色付きで差分を表示できる
実装
SESから「-と*」、「+と*」をそれぞれひろってきて、-または+の場合のみ色をつけて表示すればOK
filter Write-EditDifference
{
Param (
[string] $Reference,
[string] $Difference,
[int] $CommonCost = 0,
[int] $DeletionCost = 1,
[int] $InsertionCost = 1,
[ConsoleColor] $CommonForegroundColor = [ConsoleColor]::White,
[ConsoleColor] $CommonBackgroundColor = [ConsoleColor]::DarkMagenta,
[ConsoleColor] $DeletionForegroundColor = [ConsoleColor]::DarkMagenta,
[ConsoleColor] $DeletionBackgroundColor = [ConsoleColor]::Yellow,
[ConsoleColor] $InsertionForegroundColor = [ConsoleColor]::DarkMagenta,
[ConsoleColor] $InsertionBackgroundColor = [ConsoleColor]::Yellow
)
$commonColor = @{
NoNewLine = $true
ForegroundColor = $CommonForegroundColor
BackgroundColor = $CommonBackgroundColor
}
$deletionColor = @{
NoNewLine = $true
ForegroundColor = $DeletionForegroundColor
BackgroundColor = $DeletionBackgroundColor
}
$insertionColor = @{
NoNewLine = $true
ForegroundColor = $InsertionForegroundColor
BackgroundColor = $InsertionBackgroundColor
}
$commonChar = "*"
$deletionChar = "-"
$insertionChar = "+"
$PSBoundParameters.Add('CommonChar', $commonChar)
$PSBoundParameters.Add('DeletionChar', $deletionChar)
$PSBoundParameters.Add('InsertionChar', $insertionChar)
$script = Get-EditScript @PSBoundParameters
foreach ($s in $script)
{
switch ($s[0])
{
$CommonChar
{$s[1] | Write-Host @commonColor; break}
$DeletionChar
{$s[1] | Write-Host @deletionColor; break}
}
}
Write-Host
foreach ($s in $script)
{
switch ($s[0])
{
$CommonChar
{$s[1] | Write-Host @commonColor; break}
$InsertionChar
{$s[1] | Write-Host @insertionColor; break}
}
}
Write-Host
}
おわり
以上