Переписать PHP Similar_text в Scala

Question

В попытке переписать алгоритм PHP Similar_text в PHP я попробовал несколько разных подходов. Все были в меру успешными, но в конечном итоге потерпели неудачу.

Первая попытка: я попытался просто переписать его из исходного кода PHP. Изящное использование указателей в C делает такую ​​же точную реализацию, казалось бы, невозможной в Scala и быть чистой.

Вторая попытка: я попытался переписать его с помощью функции Java, которую кто-то опубликовал на PHP Similar_text() в 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

У кого-нибудь есть идеи о том, что здесь происходит не так?

Answer 1

Вот подсказка: посмотрите внимательно на строку 28 версии JavaScript, особенно на последний символ строки. Вот где ваша реализация отличается. (Вы также не сбрасываете l на ноль для каждой пары индексов, но это не самая важная проблема.)

Вот varверсия Scala, кстати:

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 (или у меня).