Last active
December 12, 2016 19:24
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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