LoginSignup
2

More than 3 years have passed since last update.

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

Posted at

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

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

image.png

元ネタ

やりたいこと

  • 素朴な動的計画法で下記を求める
    • 編集距離(ただし、置換は含まず、挿入・削除の編集のみ)
    • SES(Shortest Edit Script)
    • 色付きの差分表示

なお、詳細な説明も、効率的なアルゴリズムの実装もしないので、気になる人は元ネタを読んでください。

動的計画法の表を求める

下記のとおり、表(2次元配列)を2つ求める。
image.png

編集距離の表

1つ目の表は編集距離を表すものである。

最左上を 0行, 0列 とすると、上記画像の 3行, 4列 の編集距離は 3 になっている。これは、kittenの先頭3文字kitからsittingの先頭4文字sittへ、挿入または削除の操作を3回実施することで変換できることを表す。具体的には、「kit -(kを削除)-> it -(sを挿入)-> sit -(tを挿入)-> sitt」である。

このように、編集距離の表はkittenの先頭からの各部分文字列と、sittingの先頭からの各部分文字列の組み合わせの編集距離すべてを表している(動的計画法なので部分問題の解が一緒に求まる)。特に、0行目は空文字からの変換を表し、0列目は空文字への変換を表している。

SESの表

2つ目のひょうは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を求める

下記のような列を求める。
image.png

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
}

色付きの差分表示をさせる

はじめに見せたとおり、下記のように色付きで差分を表示できる
image.png

実装

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
}

おわり

以上

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
2