Скала слияния кортежей с использованием нечеткого совпадения строк

Входные данные:

val input = List((a, 10 Inches), (a, 10.00 inches), (a, 15 in), (b, 2 cm), (b, 2.00 CM))

Мне нравится иметь выход

val output = List((a, 10 Inches, 0.66), (b, 2 cm, 1))

У меня также есть служебная функция, которая возвращает true для нечеткого соответствия ("10 дюймов", "10,00 дюймов")

fuzzyMatch(s1, s2) returns

true for s1 = "10 Inches" and s2 = "10.00 inches"
false for s1 = "10 Inches" and s2 = "15 in"
false for s1 = "10.00 inches" and s2 = "15 in"
true for s1 = "2 cm" and s2 = "2.00 CM"

Output = List of (unique_name, max occurred string value, (max number of occurrences/total occurrences))

Как я могу уменьшить вышеупомянутый ввод для вывода

Что у меня пока

val tupleMap = input.groupBy(identity).mapValues(_.size)
val totalOccurrences = input.groupBy(_._1).mapValues(_.size)
val maxNumberOfValueOccurrences = tupleMap.groupBy(_._1._1).mapValues(_.values.max)
val processedInput = tupleMap
      .filter {
        case (k, v) => v == maxNumberOfValueOccurrences(k._1)
      }
      .map {
        case (k, v) => (k._1, k._2, v.toDouble / totalOccurrences(k._1))
      }.toSeq

который дает отношения для точных совпадений. Как я могу вписать туда свое нечеткое совпадение, чтобы оно сгруппировало все похожие значения и вычислило соотношение? Значение нечеткого совпадения может быть любым из совпадений.

По сути, это пользовательская группа, использующая мой метод fuzzyMatch(...). Но я не могу придумать решение здесь.

После некоторых размышлений я получил что-то вроде ниже. Лучшие решения будут оценены.

val tupleMap: Map[String, Seq[String]] = input.groupBy(_._1).mapValues(_.map(_._2))

val result = tupleMap mapValues {
list =>
val valueCountsMap: mutable.Map[String, Int] = mutable.Map[String, Int]()

list foreach {
  value =>
    // Using fuzzy match to find the best match
    // findBestMatch (uses fuzzyMatch) returns the Option(key) 
    // if there exists a similar key, if not returns None
    val bestMatch = findBestMatch(value, valueCountsMap.keySet.toSeq) 
    if (bestMatch.isDefined) {
      val newValueCount = valueCountsMap.getOrElse(bestMatch.get, 0) + 1
      valueCountsMap(bestMatch.get) = newValueCount
    } else {
      valueCountsMap(value) = 1
    }
}

val maxOccurredValueNCount: (String, Int) = valueCountsMap.maxBy(_._2)
(maxOccurredValueNCount._1, maxOccurredValueNCount._2)
}
Источник

2 ответа

Решение

Вот подход к предварительной обработке вашего input с fuzzy-match, который затем будет использоваться в качестве входных данных существующим кодом.

Идея состоит в том, чтобы сначала сгенерировать 2-комбинации ваших input кортежи, нечеткое сопоставление их, чтобы создать карту различных наборов, состоящую из сопоставленных значений на ключ, и, наконец, использовать карту для нечеткого сопоставления вашего оригинала input,

Чтобы убедиться, что больше произвольных случаев покрыты, я расширил ваш input:

val input = List(
  ("a", "10 in"), ("a", "15 in"), ("a", "10 inches"), ("a", "15 Inches"), ("a", "15.00 inches"),
  ("b", "2 cm"), ("b", "4 cm"), ("b", "2.00 CM"),
  ("c", "7 cm"), ("c", "7 in")
)

// Trivialized fuzzy match
def fuzzyMatch(s1: String, s2: String): Boolean = {
  val st1 = s1.toLowerCase.replace(".00", "").replace("inches", "in")
  val st2 = s2.toLowerCase.replace(".00", "").replace("inches", "in")
  st1 == st2
}

// Create a Map of Sets of fuzzy-matched values from all 2-combinations per key
val fuzMap = input.combinations(2).foldLeft( Map[String, Seq[Set[String]]]() ){
  case (m, Seq(t1: Tuple2[String, String], t2: Tuple2[String, String])) =>
    if (fuzzyMatch(t1._2, t2._2)) {
      val fuzSets = m.getOrElse(t1._1, Seq(Set(t1._2, t2._2))).map(
        x => if (x.contains(t1._2) || x.contains(t2._2)) x ++ Set(t1._2, t2._2) else x
      )
      if (!fuzSets.flatten.contains(t1._2) && !fuzSets.flatten.contains(t2._2))
        m + (t1._1 -> (fuzSets :+ Set(t1._2, t2._2)))
      else
        m + (t1._1 -> fuzSets)
    }
    else
      m
}
// fuzMap: scala.collection.immutable.Map[String,Seq[Set[String]]] = Map(
//   a -> List(Set(10 in, 10 inches), Set(15 in, 15 Inches, 15.00 inches)), 
//   b -> List(Set(2 cm, 2.00 CM)))
// )

Обратите внимание, что для больших input, может быть, имеет смысл сначала groupBy ключ и генерировать 2-комбинации на ключ.

Следующим шагом будет нечеткое сопоставление исходного ввода с использованием созданной карты:

// Fuzzy-match original input using fuzMap
val fuzInput = input.map{ case (k, v) => 
  if (fuzMap.get(k).isDefined) {
    val fuzValues = fuzMap(k).map{
      case x => if (x.contains(v)) Some(x.min) else None
    }.flatten
    if (!fuzValues.isEmpty)
      (k, fuzValues.head)
    else
      (k, v)
  }
  else
    (k, v)
}
// fuzInput: List[(String, String)] = List(
//   (a,10 in), (a,15 Inches), (a,10 in), (a,15 Inches), (a,15 Inches),
//   (b,2 cm), (b,4 cm), (b,2 cm),
//   (c,7 cm), (c,7 in)
// )
Источник

Если по какой-то причине подход с преобразованием в числовые значения не работает для вас, вот код, который, кажется, делает то, что вы хотите:

def fuzzyMatch(s1: String, s2: String): Boolean = {
  // fake implementation
  val matches = List(("15 Inches", "15.00 inches"), ("2 cm", "2.00 CM"))
  s1.equals(s2) || matches.exists({
    case (m1, m2) => (m1.equals(s1) && m2.equals(s2)) || (m1.equals(s2) && m2.equals(s1))
  })
}

 def test(): Unit = {
  val input = List(("a", "15 Inches"), ("a", "15.00 inches"), ("a", "10 in"), ("b", "2 cm"), ("b", "2.00 CM"))
  val byKey = input.groupBy(_._1).mapValues(l => l.map(_._2))
  val totalOccurrences = byKey.mapValues(_.size)
  val maxByKey = byKey.mapValues(_.head) //random "max" selection logic

  val processedInput: List[(String, String, Double)] = maxByKey.map({
    case (mk, mv) =>
      val matchCount = byKey(mk).count(tv => fuzzyMatch(tv, mv))
      (mk, mv, matchCount / totalOccurrences(mk).asInstanceOf[Double])
  })(breakOut)

  println(processedInput)
}

Это печатает

Список ((б,2 см,1,0), (а,15 дюймов, 0,6666666666666666))

Источник
Другие вопросы по тегам