Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

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.

@kyro38

This comment has been minimized.

Copy link

kyro38 commented Apr 19, 2015

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

@shergin

This comment has been minimized.

Copy link

shergin commented Jan 8, 2016

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

@TheDarkCode

This comment has been minimized.

Copy link

TheDarkCode commented Mar 31, 2016

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

This comment has been minimized.

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.

@RuiCarneiro

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.