Сортировка массива строк с ближайшим совпадением в Swift

Используя Swift4, я хотел бы отсортировать массив строк в соответствии с ближайшим совпадением с заданным searchTerm. Для меня важно, что если searchTerm может быть найден как точное совпадение, то returnArray должен показать этот searchTerm заранее!

Пример: Учитывая Array = ["Hello world", "Hello Jamaica", "Hello", "Family", "Hel"]

И searchTerm = "Hello" алгоритм должен вернуть:

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

Подход 1: я попытался использовать FuzzyMatching - и это каким-то образом сработало (т.е. он отсортировал inputArray в соответствии с заданный searchTerm, однако он не помещал точные совпадения вперед! То есть с помощью FuzzyMatching я добился хорошей сортировки в соответствии с совпадениями подстрок и синтаксической сортировкой. Но это не принесло мне точных совпадений заранее в returnArray).

Подход 2: Затем я попробовал свой собственный алгоритм (см. код ниже). Но если в массиве есть несколько строк, которые начинаются с моего 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? Любая помощь приветствуется!


swift arrays sorting match closest
person iKK    schedule 13.12.2017    source источник
comment
Возможный дубликат Как отсортировать массив строки по сходству с конкретным ключом   -  person Martin R    schedule 13.12.2017

Ответы (1)


arrow_upward
6
arrow_downward

Вы можете использовать расстояние Левенштейна, чтобы сравнить поисковый запрос с каждой строкой в ​​массиве, а с наивысшей оценкой будет первым элементом в вашем массиве результатов и т. д. Результатом будет массив строк, отсортированных в убывающем порядке оценки.

Для получения оценки расстояния Левенштейна можно использовать следующее расширение строки. В этом алгоритме чем выше значение, тем выше равенство.

 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
    }
}
person Ankit Rathi    schedule 12.02.2019
comment
Спасибо, Анкит, ...поскольку я давно не задавал этот вопрос, мне нужно сначала покопаться. Еще раз большое спасибо за ваше решение! - person iKK; 12.02.2019