4

为了重写 PHP 的similar_text 算法，我尝试了几种不同的方法。所有这些都取得了一定程度的成功，但最终都失败了。

第一次尝试：我尝试从 PHP 源代码重写它。C 对指针的优雅使用使得在 Scala 中似乎不可能实现相同的精确实现并且是干净的。

第二次尝试：我尝试从某人发布在PHP similar_text() in java上的 Java 函数重写它。不幸的是，该功能在 Java 中不起作用，所以没关系将它移植到 Scala。

第三次（当前）尝试：我目前正在尝试将此 JavaScript 实现转换为 Scala： http: //phpjs.org/functions/similar_text/。我以前在 JavaScript 中使用过它，它似乎运行正常。我的 Scala 翻译（如下）无法正常运行。它使您在 1 或 2 个相似性索引范围内，但它通常不是 100% 到它的 PHP 对应物的结果。

def similartext(first:String,second:String) : Int = {
  if (first == null || second == null) {
    0
  }

  var pos1:Int = 0
  var pos2:Int = 0
  var max:Int = 0
  var sum:Int = 0
  var l:Int = 0

  val firstLength:Int = first.length
  val secondLength:Int = second.length

  for (p <- 0 until firstLength) {
    for (q <- 0 until secondLength) {
      while(p+l < firstLength && q+l < secondLength && (first.charAt(p+l) == second.charAt(q+l))) {
        if (l > max) {
            println("[" + p + "," + q + "," + l + "]" + first.charAt(p+l) + " | " + second.charAt(q+l))
            max = l
            pos1 = p
            pos2 = q
          }
        l += 1
      }
    }
  }

  sum = max;

  if (sum > 0) {
    if (pos1 > 0 && pos2 > 0) {
      sum += similartext(first.substring(0, pos2), second.substring(0, pos2))
    }

    if ((pos1 + max < firstLength) && (pos2 + max < secondLength)) {
      sum += similartext(first.substring(pos1 + max, (pos1 + max) + (firstLength - pos1 - max)), second.substring(pos2 + max, (pos2 + max) + (secondLength - pos2 - max)))
    }
  }

  sum;
}

测试：

(Scala)val st = similartext("apple","aple") Yields 3
(PHP)$similar = similar_text("apple","aple"); Yields 4

(Scala)val st = similartext("starbucks","stharducks") Yields 8
(PHP)$similar = similar_text("starbucks","stharducks"); Yields 8

(Scala)val st = similartext("hello earth!","hello world!") Yields 10
(PHP)$similar = similar_text("hello earth!","hello world!"); Yields 8

有人对这里出了什么问题有任何想法吗？

4

1 回答 1

7

这里有一个提示：仔细查看 JavaScript 版本的第 28 行——尤其是该行的最后一个字符。这就是您的实现不同的地方。（您也不会将l每对索引都重置为零，但这不是最重要的问题。）

顺便说一下，这是一个免费的varScala 版本：

def similarText(x: String, y: String): Int = {
  val indices = for {
    (s, p) <- x.tails.zipWithIndex
    (t, q) <- y.tails.zipWithIndex
    l = ((s zip t) takeWhile Function.tupled(_ == _)).size
  } yield (p, q, l)
  val (pos1, pos2, max) = indices.maxBy(_._3)

  if (max == 0) max else max +
    similarText(x take pos1, y take pos2) +
    similarText(x drop (pos1 + max), y drop (pos2 + max))
}

这是相当即兴的——我相信你可以很容易地使它更简洁和高效。

还有额外的功劳：JavaScript 版本中存在一个错误——例如尝试，"aabcd"结果"abcabcd"与 PHP（或我的）不同。

于 2012-11-11T00:44:44.367 回答