scala абсолютное минимальное расстояние между словами в тексте

Question

Я пытаюсь найти минимальное расстояние между несколькими словами в данном тексте.

Предположим, что у меня есть строка, такая как: " a b собака-кошка x y z n m p-лиса x собака b b кошка "

Найти минимальное расстояние всех совпадений подстрок: (лиса, собака, кошка)

есть несколько вхождений каждой подстроки в этом тексте:

• один в начале:

кошка - 4 собака - 8 лиса - 24

dist = 24 - 4 = 20

• И один в конце строки:

лиса - 24 собака - 30 кот - 38

dist = 38 - 24 = 14

мин. Расст = 14

Вот алгоритм, который я придумал:

 object MinKWindowSum {
  def main(args: Array[String]): Unit = {   

    val document =
      """This Hello World is a huge text with thousands
Java of Hello words and Scala other lines and World and many other Hello docs
Words of World in many langs Hello and features
Java Scala AXVX TXZX ASDQWE OWEQ World asb eere qwerer
asdasd Scala Java Hello docs World KLKM NWQEW ZXCASD OPOOIK Scala ASDSA
"""
    println(getMinWindowSize(document, "Hello World Scala"))
  }   

  def getMinWindowSize(str:String, s:String): Int = {

    /* creates a list of tuples List[(String, Int)] which contains each keyword and its
    respective index found in the text sorted in order by index.
    */
    val keywords = s.split(" ").toSet
    val idxs = keywords.map(k => (k -> ("(?i)\\Q" + k + "\\E").r.findAllMatchIn(str).map(_.start)))
      .map{ case (keyword,itr) => itr.map((keyword, _))}
      .flatMap(identity).toSeq
      .sortBy(_._2)

    // Calculates the min window on the next step.
    var min = Int.MaxValue
    var minI, minJ = -1

    // current window indexes and words
    var currIdxs = ListBuffer[Int]()
    var currWords = ListBuffer[String]()

    for(idx <- idxs ) {

      // check if word exists in window already
      val idxOfWord = currWords.indexOf(idx._1)

      if (!currWords.isEmpty && idxOfWord != -1) {
        currWords = currWords.drop(idxOfWord + 1)
        currIdxs = currIdxs.drop(idxOfWord + 1)
      }
      currWords += idx._1
      currIdxs += idx._2

      // if all keys are present check if it is new min window
      if (keywords.size == currWords.length) {
        val currMin = Math.abs(currIdxs.last - currIdxs.head)
        if (min > currMin) {
          min = currMin
          minI = currIdxs.head
          minJ = currIdxs.last
        }
      }
    }

    println("min = " + min + " ,i = " + minI + " j = " + minJ)
    min
  }

}

В приведенном выше примере мы пытаемся найти минимальное расстояние между всеми совпадениями «Hello World Scala»

Самое короткое окно между индексами найдено между индексами: i = 235, j = 257 -> min = 22 * ​​1037 *

Интересно, есть ли лучший способ сделать это идиоматическим способом или лучше с точки зрения эффективности, масштабируемости, читабельности и простоты?

Answer 1

Мой подход начинается с аналогичной предпосылки, но использует хвостовой рекурсивный вспомогательный метод для поиска в проиндексированных словах.

def getMinWindowSize(str :String, s :String) :Int = {
  val keywords = s.split("\\s+").toSet
  val re = "(?i)\\b(" + keywords.mkString("|") + ")\\b"
  val idxs = re.r.findAllMatchIn(str).map(w => w.start -> w.toString).toList

  def dist(input :List[(Int, String)], keys :Set[String]) :Option[Int] = input match {
    case Nil => None
    case (idx, word) :: rest =>
      if (keys(word) && keys.size == 1) Some(idx)
      else dist(rest, keys diff Set(word))
  }

  idxs.tails.collect{
    case (idx, word)::rest => dist(rest, keywords diff Set(word)).map(_ - idx)
  }.flatten.reduceOption(_ min _).getOrElse(-1)
}

Нет изменяемых переменных или структур данных. Я также использовал Option, чтобы помочь вернуть более значимое значение, если минимальное окно невозможно.

Использование:

getMinWindowSize(document, "Hello World Scala")  //res0: Int = 22
getMinWindowSize(document, "Hello World Scal")   //res1: Int = -1

Answer 2

Вот несколько «более функциональная» альтернатива:

val document =
  """This Hello World is a huge text with thousands Java of Hello words and Scala other lines and World and many other Hello docs
     Words of World in many langs Hello and features Java Scala AXVX TXZX ASDQWE OWEQ World
  """
val WORDS = Set("Hello", "World", "Scala")

var minDistance = document.trim
  .split(" ")
  .foldLeft(List[(String, Int)](), None: Option[Int], 0) {
    case ((words, min, idx), word) if WORDS.contains(word) =>
      val newWords = (word, idx) :: words.filter(_._1 != word)
      if (newWords.map(_._1).toSet == WORDS) { // toSet on only 3 elmts
        var idxes = newWords.map(_._2)
        var dist = idxes.max - idxes.min
        var newMin = min match {
          case None                    => dist
          case Some(min) if min < dist => min
          case _                       => dist
        }
        (newWords, Some(newMin), idx + word.length + 1)
      }
      else {
        (newWords, min, idx + word.length + 1)
      }
    case ((words, min, idx), word) =>
      (words, min, idx + word.length + 1)
  }
  ._2

println(minDistance)

, который производит:

Some(38)