Расстояние Яро Винклера в Objective-C или Swift - PullRequest
Новая
       63

Расстояние Яро Винклера в Objective-C или Swift

0 голосов
/ 26 февраля 2019

Мне нужно сделать нечеткое сравнение большого количества строк, и я смотрю на Яро-Винклер , который учитывает различия в порядке букв.Кто-нибудь знает способ сделать это в Objective-C или Swift, используя Jaro-Winkler или какой-нибудь метод, родной для IOS?

Спасибо за любые рекомендации или предложения.

1 Ответ

0 голосов
/ 05 мая 2019

Я черпал вдохновение в Apache Commons и переписал его в Swift: 

extension String {
    static func jaroWinglerDistance(_ first: String, _ second: String) -> Double {
        let longer = Array(first.count > second.count ? first : second)
        let shorter = Array(first.count > second.count ? second : first)

        let (numMatches, numTranspositions) = jaroWinklerData(longer: longer, shorter: shorter)

        if numMatches == 0 {
            return 0
        }

        let defaultScalingFactor = 0.1;
        let percentageRoundValue = 100.0;

        let jaro = [
            numMatches / Double(first.count),
            numMatches / Double(second.count),
            (numMatches - numTranspositions) / numMatches
        ].reduce(0, +) / 3

        let jaroWinkler: Double

        if jaro < 0.7 {
            jaroWinkler = jaro
        } else {
            let commonPrefixLength = Double(commonPrefix(first, second).count)
            jaroWinkler = jaro + Swift.min(defaultScalingFactor, 1 / Double(longer.count)) * commonPrefixLength * (1 - jaro)
        }

        return round(jaroWinkler * percentageRoundValue) / percentageRoundValue
    }

    private static func commonPrefix(_ first: String, _ second: String) -> String{
        return String(
            zip(first, second)
                .prefix { $0.0 == $0.1 }
                .map { $0.0 }
        )
    }

    private static func jaroWinklerData(
        longer: Array<Character>,
        shorter: Array<Character>
    ) -> (numMatches: Double, numTranspositions: Double) {
        let window = Swift.max(longer.count / 2 - 1, 0)

        var shorterMatchedChars: [Character] = []
        var longerMatches = Array<Bool>(repeating: false, count: longer.count)

        for (offset, shorterChar) in shorter.enumerated() {
            let windowRange = Swift.max(offset - window, 0) ..< Swift.min(offset + window + 1, longer.count)
            if let matchOffset = windowRange.first(where: { !longerMatches[$0] && shorterChar == longer[$0] }) {
                shorterMatchedChars.append(shorterChar)
                longerMatches[matchOffset] = true
            }
        }

        let longerMatchedChars = longerMatches
            .enumerated()
            .filter { $0.element }
            .map { longer[$0.offset] }

        let numTranspositions: Int = zip(shorterMatchedChars, longerMatchedChars)
            .lazy
            .filter { $0.0 != $0.1 }
            .count / 2

        return (
            numMatches: Double(shorterMatchedChars.count),
            numTranspositions: Double(numTranspositions)
        )
    }
}

Протестировано на примерах, найденных в оригинальном коде: 

print(String.jaroWinglerDistance("", ""))
print(String.jaroWinglerDistance("", "a"))
print(String.jaroWinglerDistance("aaapppp", ""))
print(String.jaroWinglerDistance("frog", "fog"))
print(String.jaroWinglerDistance("fly", "ant"))
print(String.jaroWinglerDistance("elephant", "hippo"))
print(String.jaroWinglerDistance("hippo", "elephant"))
print(String.jaroWinglerDistance("hippo", "zzzzzzzz"))
print(String.jaroWinglerDistance("hello", "hallo"))
print(String.jaroWinglerDistance("ABC Corporation", "ABC Corp"))
print(String.jaroWinglerDistance("D N H Enterprises Inc", "D & H Enterprises, Inc."))
print(String.jaroWinglerDistance("My Gym Children's Fitness Center", "My Gym. Childrens Fitness"))
print(String.jaroWinglerDistance("PENNSYLVANIA", "PENNCISYLVNIA"))

Я также нашел другую реализацию функций сходства строк в github .

...