我使用最小编辑距离算法来查找数组中最相似的字符串的捆绑。
因此,我必须经过两次for
循环才能比较所有元素。
如果数据足够大,则此算法效率低下。
是否有一种优化方法?
let data = [
"10000", // count
"asdfqwerty", "asdfzxcvgh", "asdfpoiuyt",
...
]
for i in 1..<data.count {
let string = data[i]
for j in (i + 1)..<data.count {
let newMin = string.minimumEditDistance(other: data[j])
if min >= newMin {
// some logic
}
}
}
extension String {
public func minimumEditDistance(other: String, `default`: Int = 10) -> Int {
let m = self.count
let n = other.count
if m == 0 || n == 0 {
return `default`
}
var matrix = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
// initialize matrix
for index in 1...m {
// the distance of any first string to an empty second string
matrix[index][0] = index
}
for index in 1...n {
// the distance of any second string to an empty first string
matrix[0][index] = index
}
// compute Levenshtein distance
for (i, selfChar) in self.enumerated() {
for (j, otherChar) in other.enumerated() {
if otherChar == selfChar {
// substitution of equal symbols with cost 0
matrix[i + 1][j + 1] = matrix[i][j]
} else {
// minimum of the cost of insertion, deletion, or substitution
// added to the already computed costs in the corresponding cells
matrix[i + 1][j + 1] = Swift.min(matrix[i][j] + 1, matrix[i + 1][j] + 1, matrix[i][j + 1] + 1)
}
}
}
return matrix[m][n]
}
}
您可以通过使用minimumEditDistance
作为排序函数对数组进行排序,然后获取第一个或最后一个元素(取决于定义排序的方式)以及所需的值(最小值或最大值)来实现所需的行为。它可能会在O(N*log(N))
时间运行。这已经比指数更好。
正如@Sultan所提到的,它不会在所有距离上都有效,因为传递性仅适用于度量标准(定义集合中每个元素之间距离的函数)。您正在使用Levenstain距离作为编辑距离算法,这确实是一个指标。我提到的解决方案在某些情况下应该有助于优化。
通常,当使用编辑距离时,我们正在寻找最接近搜索到的单词的单词,然后我们可以实现线性复杂度(O(n))。
但是,在您的情况下,您有一个单词数组,您正在尝试找到距离最小的单词对。
坏消息是您无法提高复杂性。问题是,使用n
个单词,您就有O(n^2)
个组合(准确地说是(n * (n - 1)) / 2
),并且必须全部检查它们。每对都是您要寻找的组合。
您获得的算法在一般情况下是最佳的。在许多实际情况下,对输入数据的了解可以帮助您减少一些可能性。但是,这依赖于一些已知的输入数据结构。对于带有随机词的一般情况,它不起作用。
注意,您可以更简单地编写它:
let data = [
"asdfqwerty", "asdfz", "asdfpoiuyt", ...
]
func editDistance(word1: String, word2: String) -> Int {
...
}
var minimum: (word1: String, word2: String, distance: Int)?
for (offset1, word1) in data.enumerated() {
for word2 in data[(offset1 + 1)...] {
let distance = editDistance(word1: word1, word2: word2)
if let minimum = minimum, minimum.distance < distance {
continue
}
minimum = (word1: word1, word2: word2, distance: distance)
}
}
if let minimum = minimum {
print("Minimum pair is \(minimum.word1), \(minimum.word2) with edit distance \(minimum.distance)")
}