arrays - Swift 中的最接近匹配字符串数组排序

Question

使用 Swift4，我想根据与给定 searchTerm 的最接近匹配项对字符串数组进行排序。对我来说重要的是，如果可以找到完全匹配的 searchTerm，那么 returnArray 应该预先显示这个 searchTerm!

示例:给定 Array = ["Hello world", "Hello Jamaica", "Hello", "Family", "Hel"]

而 searchTerm = "Hello"，算法应该返回:

["Hello", "Hello world", "Hello Jamaica", "Hel", "Family"]。

方法一: 我尝试使用 FuzzyMatching - 它以某种方式起作用(即它确实根据给定的搜索词对 inputArray 进行了排序，但是它没有预先进行精确匹配!即使用 FuzzyMatching 我根据子字符串匹配和句法排序实现了良好的排序。但它没有在 returnArray 中预先给我精确匹配)。

方法二: 然后我尝试了我自己的算法——(见下面的代码)。但是，如果数组中有几个字符串都以我的 searchTerm 开头(即以 searchTerm 作为前缀)，那么不知何故我的算法就不太好了。

static func bestMatchFilterdStringArray(inputArray: [String], searchTerm: String) -> [String] {

    let matchingTerms = inputArray
        .filter { $0.range(of: searchTerm, options: .caseInsensitive) != nil }
        .sorted { ($0.hasPrefix(searchTerm) ? 0 : 1) < ($1.hasPrefix(searchTerm) ? 0 : 1) }
    return matchingTerms
}

如何在 Swift4 中完成“最接近匹配的字符串数组排序”？特别是在 returnArray 中预先给我精确匹配？任何帮助表示赞赏!

Answer 1

您可以使用 Levenshtein distance分数将您的搜索词与数组中的每个字符串进行比较，得分最高的将是结果数组中的第一个词等。您的结果将是按降序顺序排序的字符串数组的分数。

以下字符串扩展可用于获取 Levenshtein 距离分数。在此算法中，值越高，相等性越好。

 extension String {
    func levenshteinDistanceScore(to string: String, ignoreCase: Bool = true, trimWhiteSpacesAndNewLines: Bool = true) -> Double {

        var firstString = self
        var secondString = string

        if ignoreCase {
            firstString = firstString.lowercased()
            secondString = secondString.lowercased()
        }
        if trimWhiteSpacesAndNewLines {
            firstString = firstString.trimmingCharacters(in: .whitespacesAndNewlines)
            secondString = secondString.trimmingCharacters(in: .whitespacesAndNewlines)
        }

        let empty = [Int](repeating:0, count: secondString.count)
        var last = [Int](0...secondString.count)

        for (i, tLett) in firstString.enumerated() {
            var cur = [i + 1] + empty
            for (j, sLett) in secondString.enumerated() {
                cur[j + 1] = tLett == sLett ? last[j] : Swift.min(last[j], last[j + 1], cur[j])+1
            }
            last = cur
        }

        // maximum string length between the two
        let lowestScore = max(firstString.count, secondString.count)

        if let validDistance = last.last {
            return  1 - (Double(validDistance) / Double(lowestScore))
        }

        return 0.0
    }
}