Get Levenshtein Distance

Here is my development series (in parentheses: approx fast ratio compared with the previous, tested using strings cca 100 characters in size, see the comparison table below):

• Get-LevenshteinDistanceOrig  (= 1×, for comparison): the original function body (Copy&Paste);
• Get-LevenshteinDistanceOrig+ (> 3×, still insufficient): removed all time-expensive Write-Verbose output;
• Get-LevenshteinDistanceTry1  (> 50×, a substantial improvement): time-expensive pipeline to Measure-Object replaced by [math]::Min(n,m) static method (see .NET system.math class). The following are only minor advancement steps:
• Get-LevenshteinDistanceTry2  (~ 1×..2×): slight algorithm renovation:
  • instead calculating the cost ($cost variable): if compared characters are equal then computing and comparing values $cellAbove, $cellLeft and $cellUpperLeft is useless as we already know the necessary value;
  • added: if strings are equal the LD is known (zero) and we can stop;
• Get-LevenshteinDistance      (~ 2×): PoSH array implementation: instead of two-dimensional comparison matrix used a rectangular jagged array.

Comparison table: .\CR\164518test.ps1 | Format-Table -AutoSize

cmdlet similarity runtime (ms) lengths LD ------ ---------- ------------ ------- -- Get-LevenshteinDistanceOrig equal 6829.1053 106 106 0 Get-LevenshteinDistanceOrig+ equal 2010.4538 106 106 0 Get-LevenshteinDistanceTry1 equal 35.8835 106 106 0 Get-LevenshteinDistanceTry2 equal .1795 106 106 0 Get-LevenshteinDistance equal .1539 106 106 0 Get-LevenshteinDistanceOrig stochastic 6556.4117 106 102 79 Get-LevenshteinDistanceOrig+ stochastic 1932.6051 106 102 79 Get-LevenshteinDistanceTry1 stochastic 33.9023 106 102 79 Get-LevenshteinDistanceTry2 stochastic 28.3165 106 102 79 Get-LevenshteinDistance stochastic 13.4852 106 102 79 Get-LevenshteinDistanceOrig similar 6640.5884 106 102 4 Get-LevenshteinDistanceOrig+ similar 2023.8179 106 102 4 Get-LevenshteinDistanceTry1 similar 31.5843 106 102 4 Get-LevenshteinDistanceTry2 similar 14.9307 106 102 4 Get-LevenshteinDistance similar 8.4234 106 102 4 Get-LevenshteinDistanceOrig different 6613.5267 106 102 106 Get-LevenshteinDistanceOrig+ different 1943.7630 106 102 106 Get-LevenshteinDistanceTry1 different 35.1824 106 102 106 Get-LevenshteinDistanceTry2 different 27.1371 106 102 106 Get-LevenshteinDistance different 13.8924 106 102 106 

Column explanation:

• cmdlet       - function name
• similarity   - in brief "like" similarity of input strings
• runtime (ms) - TotalMilliseconds
• lengths      - lengths of input strings, space delimited
• LD           - the Levenshtein Distance of input strings

Comparison script 164518test.ps1:

Function TestLD { param ([string]$Similarity = '') $aux = 0 Write-Progress -Activity "LD info ($Similarity strings)" ` -CurrentOperation 'Start' -PercentComplete $aux $cmdletTails = 'Orig','Orig+','Try1','Try2','' foreach ( $cmdletTail in $cmdletTails ) { $cmdlet = "Get-LevenshteinDistance$cmdletTail" $scriptBlock = { $LevenshteinDistance = & $cmdlet ` -CompareString $strC -DifferenceString $strD } $TimeSpan = Measure-Command -Expression $scriptBlock $aux += [int](100 / $cmdletTails.Count) Write-Progress -Activity "LD info ($Similarity strings)" ` -CurrentOperation $cmdlet -PercentComplete $aux [PSCustomObject]@{ 'cmdlet' = $cmdlet 'similarity' = $Similarity 'runtime (ms)' = $($TimeSpan.TotalMilliseconds. ToString('#####.###0',$cultureinfo). PadLeft(10)) 'lengths' = "$($strC.Length) $($strD.Length)" 'LD' = $LevenshteinDistance } } } . D:\PShell\CR\164518.ps1 # reload the functions $cultureinfo = [cultureinfo]::InvariantCulture # my one is different $strC='Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vestibulum placerat leo ut turpis viverra lacinia' $strD=$strC TestLD -Similarity 'equal' $strD='Cras efficitur nec orci et posuere. Suspendisse potenti. Quisque blandit auctor purus id facilisis est' TestLD -Similarity 'stochastic' $strC='a' * $strC.Length $strD='a' * $strD.Length TestLD -Similarity 'similar' $strD='x' * $strD.Length TestLD -Similarity 'different' 

The main script 164518.ps1 (functions are defined here in the reverse order):

function Get-LevenshteinDistance{ param( [string]$CompareString, [string]$DifferenceString ) # Collect the string lengths $compareStringLength = $CompareString.Length $differenceStringLength = $DifferenceString.Length # If either of the strings are empty the LD is known and we can stop if($compareStringLength -eq 0){return $differenceStringLength} if($differenceStringLength -eq 0){return $compareStringLength} # If strings are equal the LD is known and we can stop if ($CompareString -ceq $DifferenceString) { return 0 } # Build the comparison matrix as a (rectangular) jagged array # $comparisonMatrix = New-Object 'object[]' ($differenceStringLength+1) $comparisonMatrix = [System.Array]::CreateInstance([System.Object], ($differenceStringLength+1)) for($index=0; $index -le $differenceStringLength; $index++){ # Create row # $comparisonMatrix[$index]=New-Object 'object[]' ($compareStringLength+1) $comparisonMatrix[$index]=[System.Array]::CreateInstance([System.Object], ($compareStringLength+1)) # Populate the first column $comparisonMatrix[$index][0]=$index } # Populate the first row for($index=0; $index -le $compareStringLength; $index++){ $comparisonMatrix[0][$index]=$index } # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns for($columnIndex=1; $columnIndex -le $compareStringLength; $columnIndex++){ # Cycle each character in the list $compareCharacter = $compareString[$columnIndex-1] # multiple use => to a variable # Working the rows for($rowIndex=1; $rowIndex -le $differenceStringLength; $rowIndex++){ # Cycle each character in the list (a variable for the only use) # $differenceCharacter = $differenceString[$rowIndex-1] # the only use # Calculate the cost if($compareCharacter -ceq $differenceString[$rowIndex-1]){ $comparisonMatrix[$rowIndex][$columnIndex] = $comparisonMatrix[($rowIndex -1)][($columnIndex -1)] } else { # $cost = 1 # unneeded variable for the only use # The cell immediately above plus 1 $cellAbove = $comparisonMatrix[($rowIndex-1)][$columnIndex] + 1 # The cell immediately to the left plus 1 $cellLeft = $comparisonMatrix[$rowIndex][($columnIndex-1)] + 1 # # The cell diagonally above and to the left plus the cost ↓ $cellUpperLeft = $comparisonMatrix[($rowIndex-1)][($columnIndex-1)] + 1 # Select minumum of the of the last 3 cells calculations and assign it to the current matrix position. $comparisonMatrix[$rowIndex][$columnIndex] = [math]::Min([math]::Min($cellAbove,$cellLeft),$cellUpperLeft) } } } # The cacluated LD will now be in the bottom right of the matrix. return $comparisonMatrix[$differenceStringLength][$compareStringLength] } function Get-LevenshteinDistanceTry2{ param( [string]$CompareString, [string]$DifferenceString ) # Collect the string lengths $compareStringLength = $CompareString.Length $differenceStringLength = $DifferenceString.Length # If either of the strings are empty the LD is known and we can stop if($compareStringLength -eq 0){return $differenceStringLength} if($differenceStringLength -eq 0){return $compareStringLength} # If strings are equal the LD is known and we can stop if ($CompareString -ceq $DifferenceString) { return 0 } # Build the comparison matrix and populate the first column and first row. $comparisonMatrix = New-Object 'object[,]' ($differenceStringLength+1),($compareStringLength+1) # $comparisonMatrix = [System.Array]::CreateInstance([System.Object], ($differenceStringLength+1),($compareStringLength+1)) # Populate the first row for($index=0; $index -le $compareStringLength; $index++){ $comparisonMatrix[0,$index]=$index } # Populate the first column for($index=0; $index -le $differenceStringLength; $index++){ $comparisonMatrix[$index,0]=$index } # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns for($columnIndex=1; $columnIndex -le $compareStringLength; $columnIndex++){ # Cycle each character in the list $compareCharacter = $compareString[$columnIndex-1] # Working the rows for($rowIndex=1; $rowIndex -le $differenceStringLength; $rowIndex++){ # Cycle each character in the list $differenceCharacter = $differenceString[$rowIndex-1] # Calculate the cost if($compareCharacter -ceq $differenceCharacter){ $comparisonMatrix[$rowIndex,$columnIndex] = $comparisonMatrix[($rowIndex -1),($columnIndex -1)] } else { $cost = 1 # a variable for the only use? Useless! # The cell immediately above plus 1 $cellAbove = $comparisonMatrix[($rowIndex-1), $columnIndex] + 1 # The cell immediately to the left plus 1 $cellLeft = $comparisonMatrix[$rowIndex,($columnIndex-1)] + 1 # The cell diagonally above and to the left plus the cost $cellUpperLeft = $comparisonMatrix[($rowIndex-1),($columnIndex-1)] + $cost # Select minumum of the of the last 3 cells calculations and assign it to the current matrix position. # $comparisonMatrix[$rowIndex,$columnIndex] = $cellAbove,$cellLeft,$cellUpperLeft | Measure-Object -Minimum | select -ExpandProperty Minimum # $comparisonMatrix[$rowIndex,$columnIndex] = ($cellAbove,$cellLeft,$cellUpperLeft | Measure-Object -Minimum).Minimum $comparisonMatrix[$rowIndex,$columnIndex] = [math]::Min([math]::Min($cellAbove,$cellLeft),$cellUpperLeft) } } } # The cacluated LD will now be in the bottom right of the matrix. return $comparisonMatrix[$differenceStringLength,$compareStringLength] } function Get-LevenshteinDistanceTry1{ #[cmdletbinding()] param( [string]$CompareString, [string]$DifferenceString ) # Collect the string lengths $compareStringLength = $CompareString.Length $differenceStringLength = $DifferenceString.Length ##Write-Verbose "Comparision String: '$CompareString' with length '$compareStringLength'" ##Write-Verbose "Difference String: '$DifferenceString' with length '$differenceStringLength'" # If either of the strings are empty the LD is known and we can stop if($compareStringLength -eq 0){return $differenceStringLength} if($differenceStringLength -eq 0){return $compareStringLength} # Build the comparison matrix and populate the first column and first row. $comparisonMatrix = New-Object 'object[,]' ($differenceStringLength+1),($compareStringLength+1) # Populate the first row for($index=0; $index -le $compareStringLength; $index++){ $comparisonMatrix[0,$index]=$index } # Populate the first column for($index=0; $index -le $differenceStringLength; $index++){ $comparisonMatrix[$index,0]=$index } # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns for($columnIndex=1; $columnIndex -le $compareStringLength; $columnIndex++){ # Cycle each character in the list $compareCharacter = $compareString[$columnIndex-1] # Working the rows for($rowIndex=1; $rowIndex -le $differenceStringLength; $rowIndex++){ # Cycle each character in the list $differenceCharacter = $differenceString[$rowIndex-1] ##Write-Verbose "Matrix location: [$rowIndex, $columnIndex]" ##Write-Verbose "Compare character: $compareCharacter - Difference character: $differenceCharacter" # Calculate the cost $cost=if($compareCharacter -ceq $differenceCharacter){0}else{1} ##Write-Verbose "Cost: $cost" # The cell immediately above plus 1 $cellAbove = $comparisonMatrix[($rowIndex-1), $columnIndex] + 1 ##Write-Verbose "Cell Above: [$($rowIndex-1), $columnIndex] + 1 = $cellAbove" # The cell immediately to the left plus 1 $cellLeft = $comparisonMatrix[$rowIndex,($columnIndex-1)] + 1 ##Write-Verbose "Cell Left: [$rowIndex,$($columnIndex-1)] + 1 = $cellLeft" # The cell diagonally above and to the left plus the cost $cellUpperLeft = $comparisonMatrix[($rowIndex-1),($columnIndex-1)] + $cost ##Write-Verbose "Cell Upper Left: [$($rowIndex-1),$($columnIndex-1)] + cost($cost) = $cellUpperLeft" # Select minumum of the of the last 3 cells calculations and assign it to the current matrix position. # $comparisonMatrix[$rowIndex,$columnIndex] = $cellAbove,$cellLeft,$cellUpperLeft | Measure-Object -Minimum | select -ExpandProperty Minimum $comparisonMatrix[$rowIndex,$columnIndex] = [math]::Min([math]::Min($cellAbove,$cellLeft),$cellUpperLeft) } } # The cacluated LD will now be in the bottom right of the matrix. return $comparisonMatrix[$differenceStringLength,$compareStringLength] } function Get-LevenshteinDistanceOrig+{ [cmdletbinding()] param( [string]$CompareString, [string]$DifferenceString ) # Collect the string lengths $compareStringLength = $CompareString.Length $differenceStringLength = $DifferenceString.Length ##Write-Verbose "Comparision String: '$CompareString' with length '$compareStringLength'" ##Write-Verbose "Difference String: '$DifferenceString' with length '$differenceStringLength'" # If either of the strings are empty the LD is known and we can stop if($compareStringLength -eq 0){return $differenceStringLength} if($differenceStringLength -eq 0){return $compareStringLength} # Build the comparison matrix and populate the first column and first row. $comparisonMatrix = New-Object 'object[,]' ($differenceStringLength+1),($compareStringLength+1) # Populate the first row for($index=0; $index -le $compareStringLength; $index++){ $comparisonMatrix[0,$index]=$index } # Populate the first column for($index=0; $index -le $differenceStringLength; $index++){ $comparisonMatrix[$index,0]=$index } # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns for($columnIndex=1; $columnIndex -le $compareStringLength; $columnIndex++){ # Cycle each character in the list $compareCharacter = $compareString[$columnIndex-1] # Working the rows for($rowIndex=1; $rowIndex -le $differenceStringLength; $rowIndex++){ # Cycle each character in the list $differenceCharacter = $differenceString[$rowIndex-1] ##Write-Verbose "Matrix location: [$rowIndex, $columnIndex]" ##Write-Verbose "Compare character: $compareCharacter - Difference character: $differenceCharacter" # Calculate the cost $cost=if($compareCharacter -ceq $differenceCharacter){0}else{1} ##Write-Verbose "Cost: $cost" # The cell immediately above plus 1 $cellAbove = $comparisonMatrix[($rowIndex-1), $columnIndex] + 1 ##Write-Verbose "Cell Above: [$($rowIndex-1), $columnIndex] + 1 = $cellAbove" # The cell immediately to the left plus 1 $cellLeft = $comparisonMatrix[$rowIndex,($columnIndex-1)] + 1 ##Write-Verbose "Cell Left: [$rowIndex,$($columnIndex-1)] + 1 = $cellLeft" # The cell diagonally above and to the left plus the cost $cellUpperLeft = $comparisonMatrix[($rowIndex-1),($columnIndex-1)] + $cost ##Write-Verbose "Cell Upper Left: [$($rowIndex-1),$($columnIndex-1)] + cost($cost) = $cellUpperLeft" # Select minumum of the of the last 3 cells calculations and assign it to the current matrix position. $comparisonMatrix[$rowIndex,$columnIndex] = $cellAbove,$cellLeft,$cellUpperLeft | Measure-Object -Minimum | select -ExpandProperty Minimum } } # The cacluated LD will now be in the bottom right of the matrix. return $comparisonMatrix[$differenceStringLength,$compareStringLength] } function Get-LevenshteinDistanceOrig{ [cmdletbinding()] param( [string]$CompareString, [string]$DifferenceString ) # Collect the string lengths $compareStringLength = $CompareString.Length $differenceStringLength = $DifferenceString.Length Write-Verbose "Comparision String: '$CompareString' with length '$compareStringLength'" Write-Verbose "Difference String: '$DifferenceString' with length '$differenceStringLength'" # If either of the strings are empty the LD is known and we can stop if($compareStringLength -eq 0){return $differenceStringLength} if($differenceStringLength -eq 0){return $compareStringLength} # Build the comparison matrix and populate the first column and first row. $comparisonMatrix = New-Object 'object[,]' ($differenceStringLength+1),($compareStringLength+1) # Populate the first row for($index=0; $index -le $compareStringLength; $index++){ $comparisonMatrix[0,$index]=$index } # Populate the first column for($index=0; $index -le $differenceStringLength; $index++){ $comparisonMatrix[$index,0]=$index } # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns for($columnIndex=1; $columnIndex -le $compareStringLength; $columnIndex++){ # Cycle each character in the list $compareCharacter = $compareString[$columnIndex-1] # Working the rows for($rowIndex=1; $rowIndex -le $differenceStringLength; $rowIndex++){ # Cycle each character in the list $differenceCharacter = $differenceString[$rowIndex-1] Write-Verbose "Matrix location: [$rowIndex, $columnIndex]" Write-Verbose "Compare character: $compareCharacter - Difference character: $differenceCharacter" # Calculate the cost $cost=if($compareCharacter -ceq $differenceCharacter){0}else{1} Write-Verbose "Cost: $cost" # The cell immediately above plus 1 $cellAbove = $comparisonMatrix[($rowIndex-1), $columnIndex] + 1 Write-Verbose "Cell Above: [$($rowIndex-1), $columnIndex] + 1 = $cellAbove" # The cell immediately to the left plus 1 $cellLeft = $comparisonMatrix[$rowIndex,($columnIndex-1)] + 1 Write-Verbose "Cell Left: [$rowIndex,$($columnIndex-1)] + 1 = $cellLeft" # The cell diagonally above and to the left plus the cost $cellUpperLeft = $comparisonMatrix[($rowIndex-1),($columnIndex-1)] + $cost Write-Verbose "Cell Upper Left: [$($rowIndex-1),$($columnIndex-1)] + cost($cost) = $cellUpperLeft" # Select minumum of the of the last 3 cells calculations and assign it to the current matrix position. $comparisonMatrix[$rowIndex,$columnIndex] = $cellAbove,$cellLeft,$cellUpperLeft | Measure-Object -Minimum | select -ExpandProperty Minimum } } # The cacluated LD will now be in the bottom right of the matrix. return $comparisonMatrix[$differenceStringLength,$compareStringLength] } 

Please note case sensitivity of the above functions. For case insensitive Levenshtein Distance:

• permanently: change -ceq to -eq in their two occurrences, or
• ad hoc, in a particular case: use .ToUpper() or .ToLower() functions, e.g. as

Get-LevenshteinDistance -CompareString $strC.ToUpper() -DifferenceString $strD.ToUpper() # or Get-LevenshteinDistance -CompareString $strC.ToLower() -DifferenceString $strD.ToLower()