Scala 字符串相似度

Question

我有一个 Scala 代码可以计算一组字符串之间的相似度并给出所有唯一的字符串。

val filtered = z.reverse.foldLeft((List.empty[String],z.reverse)) {
    case ((acc, zt), zz) =>
      if (zt.tail.exists(tt => similarity(tt, zz) < threshold)) acc 
      else zz :: acc, zt.tail
  }._1

我将尝试解释这里发生的事情：

这对反向输入数据使用了折叠，从空字符串开始（以累积结果）和剩余输入数据的（反向）（用于比较 - 我将其标记为 zt "z-tail" ).

折叠然后循环遍历数据，检查每个条目与剩余数据的尾部（因此它不会与自身或任何更早的条目进行比较）

如果匹配，则只允许现有的累加器（标记为 acc）通过，否则，将当前条目 (zz) 添加到累加器。此更新的累加器与 "remaining" 字符串 (zt.tail) 的尾部配对，以确保要与之比较的缩减集。

最后，我们得到了一对列表：所需的剩余字符串和一个空列表（没有剩余字符串可供比较），因此我们将其中的第一个作为结果。

问题就像在第一次迭代中一样，如果第 1、第 4 和第 8 个字符串相似，我只会得到第一个字符串。相反，我应该得到一组 (1st,4th,8th)，然后如果 2nd,5th,14th 和 21st 字符串相似，我应该得到一组 (2nd,5th,14th,21st).

Answer 1

如果我对你的理解是正确的——你希望结果的类型是 List[List[String]] 而不是你现在得到的 List[String]——其中每个项目都是相似字符串的列表（对吧？） .

如果是这样 - 我看不到可以实现此目的的对您的实现的微不足道的更改，因为类似的值是 lost（当您输入 if(true) 分支时只是 return acc - 你跳过了一个项目，你就再也不会 "see" 了）。

我能想到的两种可能的解决方案：

根据您的想法，但使用 (acc, zt, scanned) 形式的三元组作为 foldLeft 结果类型，其中添加的 scanned 是列表已经扫描的项目。这样当我们找到一个没有前面相似元素的元素时，我们可以回头参考它们：

val filtered = z.reverse.foldLeft((List.empty[List[String]],z.reverse,List.empty[String])) {
  case ((acc, zt, scanned), zz) =>
    val hasSimilarPreceeding = zt.tail.exists { tt => similarity(tt, zz) < threshold }
    val similarFollowing = scanned.collect { case tt if similarity(tt, zz) < threshold => tt }
    (if (hasSimilarPreceeding) acc else (zz :: similarFollowing) :: acc, zt.tail, zz :: scanned)
}._1

一个可能更慢但更简单的解决方案是 groupBy 一组相似的字符串：

val alternative = z.groupBy(s => z.collect { 
  case other if similarity(s, other) < threshold => other 
}.toSet ).values.toList

所有这些都假定函数：

f(a: String, b: String): Boolean = similarity(a, b) < threshold

具有交换性和传递性，即：

f(a, b) && f(a. c)表示f(b, c)
f(a, b) 当且仅当 f(b, a)

为了测试我使用的两个实现：

// strings are similar if they start with the same character
def similarity(s1: String, s2: String) = if (s1.head == s2.head) 0 else 100

val threshold = 1
val z = List("aa", "ab", "c", "a", "e", "fa", "fb")

并且两个选项产生相同的结果：

List(List(aa, ab, a), List(c), List(e), List(fa, fb))

Scala 字符串相似度

Scala String Similarity

string

scala

similarity