如何在scala中实现levenshtein距离算法

我有一个文本文件，其中包含有关发件人和消息的信息，格式是发件人，消息。我想使用阈值为70%的levenshtein距离算法，并希望将类似的消息存储到Map上。在Map上，我的钥匙是 String 价值就是 List[String] 例如，我的要求是：如果我的消息是、bcd、cdf。
第一步：首先我应该把信息“”添加到列表中。 map.put("Group1",.toList) 第二步：接下来，我应该比较“bcd”（第二条消息）和“”（第一条消息）。如果它们达到70%的阈值，那么我应该将“bcd”添加到列表中。现在，在名为“group1”的同一个键下添加了“”和“bcd”。
第三步：现在，我应该从Map上得到所有的元素。当前只有2个值（，bcd）的g1，接下来将当前消息“cdf”与“”或“bcd”进行比较（因为“”和“bcd”类似，与其中任何一个进行比较就足够了）
步骤4：如果没有达到阈值，我应该创建一个新的键“group2”，并将该消息添加到列表中，以此类推。
70%的阈值意味着，例如：
信息一：亲爱的顾客！您的手机号码9032412236已成功充值500.00卢比
信息二：亲爱的顾客！您的手机号码7999610201已成功充值500.00卢比
这里，这两者之间的levenshtein距离是8。我们可以在这里查看：https://planetcalc.com/1721/
需要进行8次编辑，（message1.length+message2.length）/2中有8个字符不匹配
如果我假设第一条消息是100个字符，第二条消息是100个字符，那么平均长度是100，在100个字符中，有8个字符不匹配，这意味着准确率是92%，所以在这里，我应该保持阈值70%。
如果levenshtein距离至少匹配70%，则将其视为相似。
我正在使用以下库：

libraryDependencies += "info.debatty" % "java-string-similarity" % "2.0.0"

我的代码：

import org.apache.spark.{SparkConf, SparkContext}
import scala.collection.mutable.ListBuffer

object Demo {
  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setMaster("local").setAppName("My App")
    val sc = new SparkContext(conf)
    val inputFile = "D:\\MyData.txt"
    val data = sc.textFile(inputFile)
    val data2 = data.map(line => {
      val arr = line.split(","); (arr(0), arr(1))
    })
    val grpData = data2.groupByKey()
    val myMap = scala.collection.mutable.Map.empty[String, List[String]]
    for (values <- grpData.values.collect) {
      val list = ListBuffer[String]()
      for (value <- values) {
        println(values)
        if (myMap.isEmpty) {
          list += value
          myMap.put("G1", list.toList)
        } else {
          val currentMsg = value
          val valuePartOnly = myMap.valuesIterator.toString()
          for (messages <- valuePartOnly) {
            def levenshteinDistance(currentMsg: String, messages: String) = {
              ???//TODO: Implement distance
            }
          }
        }
      }
    }
  }
}

在else部分之后，我不确定如何开始使用这个算法。
我的示例输入：

我没有任何输出样本。所以，我已经一步一步地解释了。
请检查步骤1到步骤4。
谢谢。

我不是很确定下一个代码我没有尝试过，但我希望它能证明这个想法：

import org.apache.spark.{SparkConf, SparkContext}
import scala.collection.mutable.ListBuffer

object Demo {
  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setMaster("local").setAppName("My App")
    val distance: Levenshtein = new Levenshtein(); //Create object for calculation distance

    def levenshteinDistance(left: String, right: String): Double = {
      // I'm not really certain about this, how you would like to calculate relative distance?
      // Relatevly to string with max size, min size, left or right?
      l.distance(left, right) / Math.max(left.size, right.size) 
    }

    val sc = new SparkContext(conf)
    val inputFile = "D:\\MyData.txt"
    val data = sc.textFile(inputFile)
    val data2 = data.map(line => {
      val arr = line.split(","); (arr(0), arr(1))
    })
    val grpData = data2.groupByKey()
    val messages = scala.collection.mutable.Map.empty[String, List[String]]
    var group = 1
    for (values <- grpData.values.collect) {
      val list = ListBuffer[String]()
      for (value <- values) {
        println(values)
        if (messages.isEmpty) {
          list += value
          messages.put("G$group", list.toList)
        } else {
          val currentMsg = value
          val group = messages.values.find {
            case(key, messages) => messages.forall(message => levenshteinDistance(currentMsg, message) <= 0.7)
          }._1.getOrElse {
            group += 1
            "G$group"
          }
          val groupMessages = messages.getOrEse(group, ListBuffer.empty[String])
          groupMessages.append(currentMsg)
          messages.put(currentMsg, groupMessages)
        }
      }
    }
  }
}

如何在scala中实现levenshtein距离算法

1条答案

相关问题

热门标签

最新问答