Как записать двоичные данные в файл для реализации сжатия Хаффмана

Хотя код Сарвеша Кумара Сингха, вероятно, будет работать, мне кажется, что он выглядит настолько по-джавистски, что я думаю, что на этот вопрос нужен еще один ответ. Я представляю код Хаффмана для реализации в Scala примерно так:

import scala.collection._

type Bit = Boolean
type BitStream = Iterator[Bit]
type BitArray = Array[Bit]
type ByteStream = Iterator[Byte]
type CharStream = Iterator[Char]

case class EncodingMapping(charMapping: Map[Char, BitArray], eofCharMapping: BitArray)

def buildMapping(src: CharStream): EncodingMapping = {
  def accumulateStats(src: CharStream): Map[Char, Int] = ???

  def buildMappingImpl(stats: Map[Char, Int]): EncodingMapping = ???

  val stats = accumulateStats(src)
  buildMappingImpl(stats)
}

def convertBitsToBytes(bits: BitStream): ByteStream = {
  bits.grouped(8).map(bits => {
    val res = bits.foldLeft((0.toByte, 0))((acc, bit) => ((acc._1 * 2 + (if (bit) 1 else 0)).toByte, acc._2 + 1))
    // last byte might be less than 8 bits
    if (res._2 == 8)
      res._1
    else
      (res._1 << (8 - res._2)).toByte
  })
}

def encodeImpl(src: CharStream, mapping: EncodingMapping): ByteStream = {
  val mainData = src.flatMap(ch => mapping.charMapping(ch))
  val fullData = mainData ++ mapping.eofCharMapping
  convertBitsToBytes(fullData)
}

// can be used to encode String as src. Thanks to StringLike/StringOps extension
def encode(src: Iterable[Char]): (EncodingMapping, ByteStream) = {
  val mapping = buildMapping(src.iterator)
  val encoded = encode(src.iterator, mapping)
  (mapping, encoded)
}

def wrapClose[A <: java.io.Closeable, B](resource: A)(op: A => B): B = {
  try {
    op(resource)
  }
  finally {
    resource.close()
  }
}

def encodeFile(fileName: String): (EncodingMapping, ByteStream) = {
  // note in real life you probably want to specify file encoding as well
  val mapping = wrapClose(Source.fromFile(fileName))(buildMapping)
  val encoded = wrapClose(Source.fromFile(fileName))(file => encode(file, mapping))
  (mapping, encoded)
}

где в accumulateStats вы узнаете, как часто каждый Char присутствует в src, а в buildMappingImpl (который является основной частью всей кодировки Хаффмана) вы сначала строите дерево из этого stats, а затем используете создание фиксированного EncodingMapping. eofCharMapping - это отображение для символа псевдо-EOF, упомянутого в один из комментариев. Обратите внимание, что encode методы высокого уровня возвращают и EncodingMapping, и ByteStream, потому что в любом сценарии реальной жизни вы хотите сохранить оба.

Специально запрашиваемая часть логики находится в convertBitsToBytes методе. Обратите внимание, что я использую Boolean для представления одного бита, а не Char и, следовательно, Iterator[Bit] (фактически Iterator[Boolean]), а не String для представления последовательности битов. Идея реализации основана на методе grouped, который преобразует BitStream в поток Bit, сгруппированных в байтовые группы (кроме возможной последней).

ИМХО, главное преимущество этого потоково-ориентированного подхода по сравнению с ответом Сарвеша Кумара Сингха заключается в том, что вам не нужно сразу загружать весь файл в память или сохранять весь закодированный файл в памяти. Обратите внимание, однако, что в этом случае вам придется прочитать файл дважды: первый раз, чтобы построить EncodingMapping, и второй раз, чтобы применить его. Очевидно, что если файл достаточно мал, вы можете сначала загрузить его в память, а затем преобразовать ByteStream в Array[Byte] с помощью вызова .toArray. Но если ваш файл большой, вы можете использовать только потоковый подход и легко сохранить ByteStream в файл, используя что-то вроде _ 26_

Я не думаю, что это поможет вам достичь цели сжатия Хаффмана, но отвечу на ваш вопрос:

преобразование строки в значение

Преобразовать String в значение, которое он представляет, довольно просто.

val x: Int = "10101010".foldLeft(0)(_*2 + _.asDigit)

Примечание. Перед преобразованием вам нужно будет проверить форматирование (только единицы и нули) и переполнение (слишком длинные строки).

значение для файла

Есть несколько способов записать данные в файл. Вот простой.

import java.io.{FileOutputStream, File}

val fos = new FileOutputStream(new File("output.dat"))
fos.write(x)
fos.flush()
fos.close()

Примечание: вы захотите отловить любые возникшие ошибки.

Сначала я укажу весь необходимый импорт,

import java.io.{ File, FileInputStream, FileOutputStream}
import java.nio.file.Paths

import scala.collection.mutable.ArrayBuffer

Теперь нам понадобятся следующие более мелкие единицы, чтобы достичь всего этого,

1 - Нам нужно иметь возможность преобразовать нашу двоичную строку (например, "01010") в Array[Byte],

def binaryStringToByteArray(binaryString: String) = {
  val byteBuffer = ArrayBuffer.empty[Byte]

  var byteStr = ""
  for (binaryChar <- binaryString) {
    if (byteStr.length < 7) {
      byteStr = byteStr + binaryChar
    }
    else {
      try{
        val byte = java.lang.Byte.parseByte(byteStr + binaryChar, 2)
        byteBuffer += byte
        byteStr = ""
      }
      catch {
        case ex: java.lang.NumberFormatException =>
          val byte = java.lang.Byte.parseByte(byteStr, 2)
          byteBuffer += byte
          byteStr = "" + binaryChar
      }
    }
  }

  if (!byteStr.isEmpty) {
    val byte = java.lang.Byte.parseByte(byteStr, 2)
    byteBuffer += byte
    byteStr = ""
  }

  byteBuffer.toArray
}

2 - Нам нужно иметь возможность открыть файл для использования в нашей небольшой игре,

def openFile(filePath: String): File = {
  val path = Paths.get(filePath)
  val file = path.toFile

  if (file.exists()) file.delete()

  if (!file.exists()) file.createNewFile()

  file
}

3 - Нам нужно иметь возможность записывать байты в файл,

def writeBytesToFile(bytes: Array[Byte], file: File): Unit = {
  val fos = new FileOutputStream(file)
  fos.write(bytes)
  fos.close()
}

4 - Нам нужно иметь возможность читать байты из файла,

def readBytesFromFile(file: File): Array[Byte] = {
  val fis = new FileInputStream(file)
  val bytes = new Array[Byte](file.length().toInt)
  fis.read(bytes)
  fis.close()
  bytes
}

5 - Нам нужно иметь возможность конвертировать байты обратно в нашу двоичную строку,

def byteArrayToBinaryString(byteArray: Array[Byte]): String = {
  byteArray.map(b => b.toBinaryString).mkString("")
}

Теперь мы готовы делать все, что захотим,

// lets say we had this binary string,
scala> val binaryString = "00101110011010101010101010101"
// binaryString: String = 00101110011010101010101010101

// Now, we need to "pad" this with a leading "1" to avoid byte related issues
scala> val paddedBinaryString = "1" + binaryString
// paddedBinaryString: String = 100101110011010101010101010101

// The file which we will use for this,
scala> val file = openFile("/tmp/a_bit")
// file: java.io.File = /tmp/a_bit

// convert our padded binary string to bytes
scala> val bytes = binaryStringToByteArray(paddedBinaryString)
// bytes: Array[Byte] = Array(75, 77, 85, 85)

// write the bytes to our file,
scala> writeBytesToFile(bytes, file)

// read bytes back from file,
scala> val bytesFromFile = readBytesFromFile(file)
// bytesFromFile: Array[Byte] = Array(75, 77, 85, 85)

// so now, we have our padded string back,
scala> val paddedBinaryStringFromFile = byteArrayToBinaryString(bytes)
// paddedBinaryStringFromFile: String = 1001011100110110101011010101

// remove that "1" from the front and we have our binaryString back,
scala> val binaryStringFromFile = paddedBinaryString.tail
// binaryStringFromFile: String = 00101110011010101010101010101

ПРИМЕЧАНИЕ: возможно, вам придется внести несколько изменений, если вы хотите иметь дело с очень большими «двоичными строками» (длиной более нескольких миллионов символов) для повышения производительности или даже для того, чтобы их можно было использовать. Например - вам нужно будет начать использовать потоки или итераторы вместо Array[Byte].