Skip to content

Instantly share code, notes, and snippets.

@joncardasis
Last active December 12, 2016 19:24
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save joncardasis/7f09d1a55f3278d8ee5080e47653caff to your computer and use it in GitHub Desktop.
Save joncardasis/7f09d1a55f3278d8ee5080e47653caff to your computer and use it in GitHub Desktop.
Levenshtein Algorithm in Swift 3 - Calculates the number of differences between two strings
//CLI for using Levenshtein Comparison
class ConsoleIO{
enum OptionType: String {
case difference = "d"
case help = "h"
case unknown
init(value: String){
switch value{
case "-d" : self = .difference
case "-h" : self = .help
default : self = .unknown
}
}
}
class func printUsage() {
let executableName = (CommandLine.arguments[0] as NSString).lastPathComponent
print("Usage:")
print("\(executableName) -d string1 string2 : Difference interval between two strings")
print("or")
print("\(executableName) -h : Show usage information")
}
func getOption(_ option: String) -> OptionType{
return (OptionType(value: option))
}
}
let consoleIO = ConsoleIO()
let argCount = CommandLine.argc
if argCount < 2 {
ConsoleIO.printUsage()
exit(0)
}
let option = consoleIO.getOption(CommandLine.arguments[1]) //argument passed
if(option == .difference && argCount == 4){
let string1 = CommandLine.arguments[2]
let string2 = CommandLine.arguments[3]
let difference = string1.distanceFrom(string: string2)
print(difference)
exit(0)
}
else{
ConsoleIO.printUsage()
exit(0)
}
extension String{
private func min(numbers: Int...) -> Int {
return numbers.reduce(numbers[0], {$0 < $1 ? $0 : $1})
}
func distanceFrom(string: String) -> Int{
let x = Array(self.utf16) //convert to a unicode 16 format for comparison
let y = Array(string.utf16)
//Create the Levenshtein 2d matrix, which has an extra preceeding row and column
var matrix = Array(repeating: [Int](repeating: 0, count: y.count + 1), count: x.count + 1)
for i in 1...x.count{ //set rows (0,0 is already set from repeated value)
matrix[i][0] = i
}
for j in 1...y.count{ //set columns
matrix[0][j] = j
}
for row in 1...x.count{
for col in 1...y.count {
if(x[row-1] == y[col-1]){
matrix[row][col] = matrix[row-1][col-1] //Match
}
else{
matrix[row][col] = min(numbers:
matrix[row-1][col-1] + 1, //Subsitution
matrix[row-1][col] + 1, //Deletion
matrix[row][col-1] + 1 //Insertion
)
}
}
}
return matrix[x.count][y.count]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment