Skip to content

Instantly share code, notes, and snippets.

@bgreenlee
Created June 27, 2014 05:54
  • Star 13 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save bgreenlee/52d93a1d8fa1b8c1f38b to your computer and use it in GitHub Desktop.
Levenshtein Distance in Swift
/**
* Levenshtein edit distance calculator
* Usage: levenstein <string> <string>
*
* To compile:
* sudo xcode-select -switch /Applications/Xcode6-Beta.app/Contents/Developer
* xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) levenshtein.swift
*/
import Foundation
// return minimum value in a list of Ints
func min(numbers: Int...) -> Int {
return numbers.reduce(numbers[0], {$0 < $1 ? $0 : $1})
}
func levenshtein(aStr: String, bStr: String) -> Int {
// create character arrays
let a = Array(aStr)
let b = Array(bStr)
// initialize matrix of size |a|+1 * |b|+1 to zero
var dist = Int[][]()
for row in 0...a.count {
dist.append(Int[](count: b.count + 1, repeatedValue: 0))
}
// 'a' prefixes can be transformed into empty string by deleting every char
for i in 1...a.count {
dist[i][0] = i
}
// 'b' prefixes can be created from empty string by inserting every char
for j in 1...b.count {
dist[0][j] = j
}
for i in 1...a.count {
for j in 1...b.count {
if a[i-1] == b[j-1] {
dist[i][j] = dist[i-1][j-1] // noop
} else {
dist[i][j] = min(
dist[i-1][j] + 1, // deletion
dist[i][j-1] + 1, // insertion
dist[i-1][j-1] + 1 // substitution
)
}
}
}
return dist[a.count][b.count]
}
if Process.arguments.count != 3 {
println("Usage: levenstein <string> <string>")
exit(0)
}
println(levenshtein(Process.arguments[1], Process.arguments[2]))
@Smotrov
Copy link

Smotrov commented Nov 18, 2014

Dramatically slower then this implementation https://gist.github.com/boratlibre/1593632
I've send couple of hours to make it faster but... It seems like Swift arrays and Strings manipulation are not as fast as objC.

On 2000 random Strings calculations Swift implementation is about 100(!!!) times slower then ObjC.

@JeanMeche
Copy link

You'll find an improved version here : https://gist.github.com/kyro38/50102a47937e9896e4f4

@shergin
Copy link

shergin commented Jan 8, 2016

Here is my (more generalized) version: https://gist.github.com/shergin/a6dba6ee5ae3b9ecb16c

@TheDarkCode
Copy link

I went and improved on the prior versions to incorporate all of the optimizations available in Swift 2.2. You can find the gist here: https://gist.github.com/TheDarkCode/341ec5b84c078a0be1887c2c58f6d929

However, I've also turned it into a cocoapod: https://www.github.com/TheDarkCode/SwiftyLevenshtein

@joe528
Copy link

joe528 commented Sep 22, 2016

Statements like this for i in 1...a.count will lead to crash if a.count is 0.

Always use something like 1..<count to avoid any possibility of crashing.

@RuiNelson
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment