下記のように、文字列の差分を求めるアルゴリズムの確認をしたかったので、PowerShellで実装してみた。

(アドカレ用に記事を書いていたわけではないが、時期的に被ったので投稿)

元ネタ

やりたいこと

素朴な動的計画法で下記を求める
- 編集距離（ただし、置換は含まず、挿入・削除の編集のみ）
- 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の最短経路問題を解いていることになる。

Get-EditTable.ps1

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。

Measure-EditDistance.ps1

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が求まる。

Get-EditScript.ps1

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

Write-EditDifference.ps1

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
}

おわり

以上

PowerShellで文字列の差分を求める

元ネタ