Levenshtein Distance in Swift3

Levenshtein distance in Swift3

There were a couple of changes to make.

• The construction of the Array empty.
• enumerate() is now enumerated()
• successor() doesn't exist anymore so I replaced it with +1

So the function is now

Swift 4:

func levDis(_ w1: String, _ w2: String) -> Int {
    let empty = [Int](repeating:0, count: w2.count)
    var last = [Int](0...w2.count)

    for (i, char1) in w1.enumerated() {
        var cur = [i + 1] + empty
        for (j, char2) in w2.enumerated() {
            cur[j + 1] = char1 == char2 ? last[j] : min(last[j], last[j + 1], cur[j]) + 1
        }
        last = cur
    }
    return last.last!
}

Swift 3:

func levDis(w1: String, w2: String) -> Int {

    let (t, s) = (w1.characters, w2.characters)

    let empty = Array<Int>(repeating:0, count: s.count)
    var last = [Int](0...s.count)

    for (i, tLett) in t.enumerated() {
        var cur = [i + 1] + empty
        for (j, sLett) in s.enumerated() {
            cur[j + 1] = tLett == sLett ? last[j] : min(last[j], last[j + 1], cur[j])+1
        }
        last = cur
    }
    return last.last!
}

Matching text to keywords in Swift

The Levenshtein distance, aka edit distance, is a metric for measuring the difference between two strings. The implementation of it is here:

func levenshteinDist(test: String, key: String) -> Int {
    let empty = Array<Int>(repeating:0, count: key.count)
    var last = [Int](0...key.count)

    for (i, testLetter) in test.enumerated() {
        var cur = [i + 1] + empty
        for (j, keyLetter) in key.enumerated() {
            cur[j + 1] = testLetter == keyLetter ? last[j] : min(last[j], last[j + 1], cur[j]) + 1
        }
        last = cur
    }
    return last.last!
}

You can use it as follows:

let test1 = "Test©/Testing© Keyword Finder"
let test2 = "Test© Word Finder"
let test3 = "Number Categorizer"
let test4 = "Alphabet in Order"

let key = "Test Testing Keyword"

print(levenshteinDist(test: test1, key: key)) // 10
print(levenshteinDist(test: test2, key: key)) // 14
print(levenshteinDist(test: test3, key: key)) // 18
print(levenshteinDist(test: test4, key: key)) // 15
print(levenshteinDist(test: key, key: key)) // 0

As you can see, levensthlindist(test: key, key: key) outputs 0, since the strings are same. Also, the minimum output is 10 and it corresponds to the expected test string.

Slow Swift Arrays and Strings performance

There are multiple reasons why the Swift code is slower than the Objective-C code.
I made a very simple test case by comparing two fixed strings 100 times.

• Objective-C code: 0.026 seconds
• Swift code: 3.14 seconds

The first reason is that a Swift Character represents an "extended grapheme cluster",
which can contain several Unicode code points (e.g. "flags"). This makes the
decomposition of a string into characters slow. On the other hand, Objective-C
NSString stores the strings as a sequence of UTF-16 code points.

If you replace

let a = Array(aStr)
let b = Array(bStr)

by

let a = Array(aStr.utf16)
let b = Array(bStr.utf16)

so that the Swift code works on UTF-16 sequences as well then the time goes down
to 1.88 seconds.

The allocation of the 2-dimensional array is also slow. It is faster to allocate
a single one-dimensional array. I found a simple Array2D class here:
http://blog.trolieb.com/trouble-multidimensional-arrays-swift/

class Array2D {
    var cols:Int, rows:Int
    var matrix: [Int]

    init(cols:Int, rows:Int) {
        self.cols = cols
        self.rows = rows
        matrix = Array(count:cols*rows, repeatedValue:0)
    }

    subscript(col:Int, row:Int) -> Int {
        get {
            return matrix[cols * row + col]
        }
        set {
            matrix[cols*row+col] = newValue
        }
    }

    func colCount() -> Int {
        return self.cols
    }

    func rowCount() -> Int {
        return self.rows
    }
}

Using that class in your code

func levenshtein(aStr: String, bStr: String) -> Int {
    let a = Array(aStr.utf16)
    let b = Array(bStr.utf16)

    var dist = Array2D(cols: a.count + 1, rows: b.count + 1)

    for i in 1...a.count {
        dist[i, 0] = i
    }

    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]
}

the time in the test case goes down to 0.84 seconds.

The last bottleneck that I found in the Swift code is the min() function.
The Swift library has a built-in min() function which is faster. So just removing
the custom function from the Swift code reduces the time for the test case to
0.04 seconds, which is almost as good as the Objective-C version.

Addendum: Using Unicode scalars seems to be even slightly faster:

let a = Array(aStr.unicodeScalars)
let b = Array(bStr.unicodeScalars)

and has the advantage that it works correctly with surrogate pairs such
as Emojis.

Sort by distance Swift 3

Sort the malls first, and then use it as TableView's datasource, TableView will display the cells sorted as the order in Array sorted malls:

    let sortedMalls = malls.sorted { (mallOne, mallTwo) -> Bool in
        return mallOne.distance < mallTwo.distance
    }

Also a one liner:

let sortedMalls = malls.sorted { $0.mallOne.distance < $1.mallTwo.distance }

Use sortedMalls for:

override func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell

How can I calculate Difference from two times in swift 3?

Use timeIntervalSince(_ anotherDate: Date) function to get difference between two dates.

func findDateDiff(time1Str: String, time2Str: String) -> String {
    let timeformatter = DateFormatter()
    timeformatter.dateFormat = "hh:mm a"

    guard let time1 = timeformatter.date(from: time1Str),
        let time2 = timeformatter.date(from: time2Str) else { return "" }

    //You can directly use from here if you have two dates

    let interval = time2.timeIntervalSince(time1)
    let hour = interval / 3600;
    let minute = interval.truncatingRemainder(dividingBy: 3600) / 60
    let intervalInt = Int(interval)
    return "\(intervalInt < 0 ? "-" : "+") \(Int(hour)) Hours \(Int(minute)) Minutes"
}

Call the function with two times to find the difference.

let dateDiff = findDateDiff(time1Str: "09:54 AM", time2Str: "12:59 PM")
print(dateDiff)

How can I calculate the distance between two points in MkMapview?

You can get lat/lon of the center with:

convertPoint:toCoordinateFromView:

loc1 and loc2 are both CLLocation objs.

CLLocationDistance dist = [loc1 distanceFromLocation:loc2];

So these two tips should help you. if you need some code, let me know :-)

---

Related Topics