swift - 如何有效地比较 Swift 中的字符

Question

我在 Swift 中有一个函数可以计算 hamming distance两个字符串，如果结果为 1，则将它们放入连通图中。

例如，read to hear 返回的汉明距离为 2，因为 read[0] != hear[0] 和 read[3] != hear[3]。

起初，我以为我的函数因为输入量(8,000+ 词典)而需要很长时间，但我知道几分钟太长了。因此，我用 Java 重写了相同的算法，计算仅用了 0.3 秒。

我试过用两种不同的方式用 Swift 写这个:

---

方式 1 - 子串

extension String {

    subscript (i: Int) -> String {
        return self[Range(i ..< i + 1)]
    }

}

private func getHammingDistance(w1: String, w2: String) -> Int {
    if w1.length != w2.length { return -1 }

    var counter = 0
    for i in 0 ..< w1.length {
        if w1[i] != w2[i] { counter += 1 }
    }

    return counter
}

结果: 434 秒

---

方式2 - 删除字符

private func getHammingDistance(w1: String, w2: String) -> Int {
    if w1.length != w2.length { return -1 }

    var counter = 0
    var c1 = w1, c2 = w2      // need to mutate
    let length = w1.length

    for i in 0 ..< length {
        if c1.removeFirst() != c2.removeFirst() { counter += 1 }
    }

    return counter
}

结果: 156 秒

---

Java 中的相同内容

结果: 0.3 秒

---

在哪里调用

var graph: Graph

func connectData() {
    let verticies = graph.canvas // canvas is Array<Node>
                                 // Node has key that holds the String

    for vertex in 0 ..< verticies.count {
        for compare in vertex + 1 ..< verticies.count {
            if getHammingDistance(w1: verticies[vertex].key!, w2: verticies[compare].key!) == 1 {
                graph.addEdge(source: verticies[vertex], neighbor: verticies[compare])
            }
        }
    }
}

---

156 秒对我来说还是太低效了。在 Swift 中比较字符的绝对最有效的方法是什么？是否有一种可能的解决方法来计算不涉及比较字符的汉明距离？

---

编辑

编辑 1:我正在使用包含 4 个和 5 个字母单词的整个字典并创建一个连接图，其中的边表示汉明距离为 1。因此，我将 8,000 多个单词与每个单词进行比较其他生成边缘。

编辑 2: 添加了方法调用。

Answer 1

除非您为字符串选择固定长度的字符模型，否则方法和属性(例如 .count 和 .characters)的复杂度为 O(n) 或最多为 O(n/2)(其中 n 是字符串长度).如果您将数据存储在字符数组中(例如 [Character] )，您的函数会执行得更好。

您还可以使用 zip() 函数将整个计算合并到一次传递中

let hammingDistance = zip(word1.characters,word2.characters)
                      .filter{$0 != $1}.count 

但这仍然需要遍历每个单词对的所有字符。

...

鉴于您只寻找 1 的汉明距离，有一种更快的方法可以找到所有唯一的单词对:

策略是根据对应于一个“缺失”字母的 4(或 5)种模式对单词进行分组。这些模式组中的每一个都为单词对定义了一个较小的范围，因为不同组中的单词之间的距离不是 1。

每个单词将属于与其字符数一样多的组。

例如:

"hear" will be part of the pattern groups:
"*ear", "h*ar", "he*r" and "hea*".

对应于这 4 个模式组之一的任何其他单词与“听到”的汉明距离为 1。

这是如何实现的:

// Test data 8500 words of 4-5 characters ...
var seenWords = Set<String>()
var allWords = try! String(contentsOfFile: "/usr/share/dict/words")
                     .lowercased()                        
                     .components(separatedBy:"\n")
                     .filter{$0.characters.count == 4 || $0.characters.count == 5}
                     .filter{seenWords.insert($0).inserted}
                     .enumerated().filter{$0.0 < 8500}.map{$1}

// Compute patterns for a Hamming distance of 1
// Replace each letter position with "*" to create patterns of
// one "non-matching" letter
public func wordH1Patterns(_ aWord:String) -> [String]
{
   var result       : [String]    = []
   let fullWord     : [Character] = aWord.characters.map{$0}
   for index in 0..<fullWord.count
   {
      var pattern    = fullWord
      pattern[index] = "*" 
      result.append(String(pattern))                     
   }
   return result
}

// Group words around matching patterns
// and add unique pairs from each group
func addHamming1Edges()
{
   // Prepare pattern groups ...
   // 
   var patternIndex:[String:Int] = [:]
   var hamming1Groups:[[String]]  = []
   for word in allWords
   {
      for pattern in wordH1Patterns(word)
      {
         if let index = patternIndex[pattern]
         { 
           hamming1Groups[index].append(word) 
         }
         else
         {
           let index = hamming1Groups.count
           patternIndex[pattern] = index
           hamming1Groups.append([word])
         }        
      }
   }

   // add edge nodes ...
   //
   for h1Group in hamming1Groups
   {
       for (index,sourceWord) in h1Group.dropLast(1).enumerated()
       {
          for targetIndex in index+1..<h1Group.count
          { addEdge(source:sourceWord, neighbour:h1Group[targetIndex]) } 
       }
   }
}

在我的 2012 MacBook Pro 上，8500 个单词在 0.12 秒内通过 22817 个(唯一的)边对。

[编辑] 为了说明我的第一点，我使用字符数组而不是字符串创建了一个“强力”算法:

   let wordArrays = allWords.map{Array($0.unicodeScalars)}
   for i in 0..<wordArrays.count-1
   {
      let word1 = wordArrays[i]
      for j in i+1..<wordArrays.count
      {
         let word2 = wordArrays[j]
         if word1.count != word2.count { continue }

         var distance = 0
         for c in 0..<word1.count 
         {
            if word1[c] == word2[c] { continue }
            distance += 1
            if distance > 1 { break }
         }
         if distance == 1
         { addEdge(source:allWords[i], neighbour:allWords[j]) }
      }
   }

这会在 0.27 秒内完成唯一对。速度差异的原因是 Swift Strings 的内部模型，它实际上不是一个等长元素(字符)的数组，而是一串不同长度的编码字符(类似于 UTF 模型，其中特殊字节表示以下 2 或3个字节是单个字符的一部分。这种结构没有简单的Base+Displacement索引，必须始终从头迭代到第N个元素。

请注意，我使用 unicodeScalars 而不是 Character，因为它们是 16 位固定长度的字符表示形式，允许直接进行二进制比较。 Character 类型不是那么简单，需要更长的时间进行比较。