Task #1

package ru.niner

import java.nio.file.{Paths, Files}


object TaskOne extends App {
  // считываем последовательность байт из файла
  val data : Array[Byte] = Files.readAllBytes(Paths.get("plrabn12.txt"))
  println(data.length)
  // для длин последовательностей от 1 до 4
  for (length <- 1 to 4) {
    var freq = Map[Int,Int]()
    for (pos <- 0 to data.length - length) {
      // считаем число вхождений бита
      val value = compute(data,pos,length)
      val oldFreq = if (freq.contains(value)) freq(value) else 0
      freq += (value -> (oldFreq + 1))
    }
    val e0 = entropyJustOccured(freq,data.length - length + 1) / length
    val e1 = entropyAllAlphabet(freq,data.length - length + 1,length) / length

    println(length + " " + e0 + " " + e0 * data.length / 8 + " " + e1 + " " + e1 * data.length / 8)
  }

  // энтропия при учете только возникших
  def entropyJustOccured(freq : Map[Int, Int], n : Int): Double = {
    var entropy = 0.0
    for ((key, value) <- freq) {
      val prob = (1.0 * value)/n
      entropy += prob * (Math.log(prob) / Math.log(2))
    }
    -entropy
  }

  // энтропия при учете всего алфавита
  def entropyAllAlphabet(freq : Map[Int, Int], n : Int, length : Int): Double = {
    var entropy = 0.0
    var count = Math.pow(256, length)
    var overall = 0.0
    // вошедшие буквы
    for ((key,value) <- freq) {
      count -= 1
      var prob = 1.0 * value / n
      // нормировка
      prob *= 1 / (1+(Math.pow(256,length) - freq.size)/Math.pow(256,length))
      //val prob = 1.0 * (value / Math.pow(n,length)) / Math.pow(256,length)
      overall += prob
      entropy += prob * (Math.log(prob) / Math.log(2))
    }
    // суммарная вероятность для появившихся букв
    println(overall)
    // Невошедшие буквы
    while (count > 0) {
      count -= 1
      //val prob = 1.0 / (freq.size * Math.pow(256,length))
      var prob = 1.0 / Math.pow(256,length)
      // нормировка
      prob *= 1 / (1+(Math.pow(256,length) - freq.size)/Math.pow(256,length))
      entropy += prob * (Math.log(prob) / Math.log(2))
      overall += prob
    }
    // суммарная вероятность для всех (должны быть равна единице)
    println(overall)
    -entropy
  }

  def compute(data : Array[Byte], pos : Int, length : Int): Int = {
    var res = 0
    for (i <- 0 until length) {
      res = res * 256 + data(pos+i)
    }
    res
  }
}