Язык программирования для представления алгоритмов

[Majestio]

Буэнос диас, амигос!

Есть тема за злобу или доброту дня. С "языком программирования для сервера проклятий" мы как-то худо-бедно разобрались. В принчипе даже можно открыть диавольский отдел в отделениях редакций RFC. Но тут вопрос более другой - чисто сабж... Наверное все согласятся, что визуально-графическое представление - наиболее "удобоваримое". Но это когда алгоритм укладывается на печатный лист. А когда на 10, или не дай Бог 11? А кодировать нужно и понимать нужно.

Вопрос: лучший на ваш взгляд "сабж"?

ЗЫ: Вдогоночку ... да мы можем заниматься декомпозицией-композицией, и многие ЯП своими возможностями это поддерживают, более того поощряют. Но давайте придерживаться как-то золотой середины, штоле!

Я пока топлю за два языка: Perl и чистый Си

Лец го!!!!!!!!

[korvin]

Ocaml и Scheme

[Majestio]

Цитата Majestio @ 09.07.22, 12:01

Ocaml и Scheme

Ну норм, но почему?

[Majestio]

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

[korvin]

Цитата Majestio @ 10.07.22, 02:13

функциональщина

(define (hello-world)
  (define message "Hello, World!")
  (let ((n (string-length message)))
    (for ((i 0)) (< i n) ((inc! i))
      (display (string-ref message i)))
    (newline)))
 
(define (main)
  (hello-world))
 
(main)

=>

Hello, World!

Definitions

(define-syntax for
  (syntax-rules ()
    ((_ (decl ...) condition (step ...)
        body
        ...)
     (let (decl ...)
       (let loop ()
         (when condition
           (begin
             body
             ...)
           (begin
             step
             ...)
           (loop)))))))
 
(define-syntax inc!
  (syntax-rules ()
    ((_ var)
     (set! var (+ var 1)))
 
    ((_ var delta)
     (set! var (+ var delta)))))

— https://rextester.com/FODY77261

...

class hello_world =
  object
    val message = "Hello, World!"
 
    method say =
      let n = String.length message - 1 in
      for i = 0 to n do
        print_char message.[i]
      done ;
      print_newline ()
  end
 
type message =
  <
    say : unit
  >
 
class application (msg : message) =
  object
    method main =
      msg#say
  end
 
let app = new application (new hello_world)
 
let _ = app#main

=>

Hello, World!

— https://rextester.com/QBYY22062

[Majestio]

Нет, я такое не хочу видеть! Это примерно как пытки песнями Газманова.

[korvin]

Цитата Majestio @ 10.07.22, 12:48

Нет, я такое не хочу видеть!

Оно и понятно.

[Qraizer]

Оспади.

[](const auto& msg){ std::cout << msg <<std::endl;}("Hello, world!");

Один вопрос: на...хрена

Добавлено 10.07.22, 19:23
P.S. Ну все ж поняли, что это чтоб разогреть. Ото давно друг другу морды не...не холиварили

Сообщение отредактировано: Qraizer - 10.07.22, 19:23

[OpenGL]

Befunge, конечно же!

Добавлено 11.07.22, 05:31
А если серьёзно, то в целом пофиг, лишь бы язык понимал. Я, например, на питоне люблю всякие заковыристые алгоритмы писать.

[D_KEY]

korvin, а где у тебя там алгоритмы?

[korvin]

Цитата D_KEY @ 11.07.22, 05:43

а где у тебя там алгоритмы?

А ты почитай на что я отвечал.

[kopilov]

Именно для алгоритмов, без привязки к архитектуре и прочим реализациям — ДРАКОН жеж.

[applegame]

Писать программы сразу в виде AST - такое себе.

[D_KEY]

Может быть стоит сюда какой-то алгоритм закинуть и на разных языках его написать. И посравнивать.

Есть у кого-нибудь что-то подходящее на примете?

[korvin]

Цитата applegame @ 11.07.22, 10:02

Писать программы сразу в виде AST - такое себе.

Ага. Хорошо, что этого никто не предлагает.

Цитата D_KEY @ 11.07.22, 11:44

Может быть стоит сюда какой-то алгоритм закинуть и на разных языках его написать. И посравнивать.

Есть же всякие сайты с разными алгоритмами и их реализациями на разных языках. Смотри — сравнивай.

[D_KEY]

Цитата korvin @ 11.07.22, 11:49

Есть же всякие сайты с разными алгоритмами и их реализациями на разных языках. Смотри — сравнивай.

Так а холиварить-то как? Давайте сюда что-то притащим.

[Qraizer]

LZW. Дёшево и в меру сердито.

[Qraizer]

Ну и? Мне начинать, что ли?

[Majestio]

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

Было бы неплохо

Добавлено 12.07.22, 14:28
Хотелось бы сравнить с Петоном Тьфу на него )))

[korvin]

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

Конечно! Инициатива наказуемапоощряема. Мне лично не очень интересны байто-бито-дрочерские вещи, и судя по описанию в вике, какой-то заметной разницы между языками тут не будет. Как и во многих алгоритмах. Во всяком случае, навскидку, я не вижу здесь точки отличий. Так что я не знаю, что тут можно сравнивать.

[Majestio]

Цитата korvin @ 12.07.22, 17:48

Так что я не знаю, что тут можно сравнивать.

Ты просто Бейсика не видел, или Пасквиля ... с их излишествами в синтаксисе.
А лутше ознакомься с синтаксисом PL/1. Просто чтобы ознакомится с глубинами ихних глубин.

[korvin]

Цитата Majestio @ 12.07.22, 18:24

Ты просто Бейсика не видел, или Пасквиля

С чего ты это взял?

Цитата Majestio @ 12.07.22, 18:24

А лутше ознакомься с синтаксисом PL/1

Бессмысленно.

[Majestio]

Скрытый текст

Не, про Пасквиля я мало чего могу сказать плохого - хорошо продуманный язык. Если не брать учебу, а именно практическое программирование, я с него начинал. Вспоминания только хорошие. Особенно впечатляла скорость сборки. Речь идет о Turbo Pascal 5.0/5.5 и какого-то установленного сбоку Microsoft C (версии не помню). Все это было на нативном компе IBM 8086 с 512Kb оперативной памяти... Но потом слишком "многосимвольный" синтаксис задостал. И пришлось уходить на Perl, параллельно на Си. А вот про PL/1 скажу только плохое - пришлось его выучить только для того, чтобы в институте получить "отлично" по прикладному программированию. Перфокарты, шоколадки операторшам, ацкий ад.

Цитата korvin @ 12.07.22, 18:25

С чего ты это взял?

Вообще-то это сарказм был

Добавлено 12.07.22, 18:44

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

Кстати ... есть тема. Я как-то в "Алгоритмах" предлагал интересный линк. Зацени тему!
Если тебя это зацепит, и ты сможешь это отразить изящно-алоритмически, твой опыт будет просто бесценен!!! Я серьёзно, без стеба!

[applegame]

Цитата korvin @ 11.07.22, 11:49

Ага. Хорошо, что этого никто не предлагает.

Цитата korvin @ 09.07.22, 18:17

Scheme

[Majestio]

Цитата applegame @ 13.07.22, 05:32

Scheme

Тот же Брэйнфак, но только с помощью скобочек.

[Gonarh]

Цитата Majestio @ 09.07.22, 12:01

Perl и чистый Си

Сообщение отредактировано: Gonarh - 13.07.22, 08:11

[korvin]

applegame, Scheme не AST.

[Qraizer]

Цитата korvin @ 12.07.22, 17:48

Мне лично не очень интересны байто-бито-дрочерские вещи, и судя по описанию в вике, какой-то заметной разницы между языками тут не будет. Как и во многих алгоритмах. Во всяком случае, навскидку, я не вижу здесь точки отличий. Так что я не знаю, что тут можно сравнивать.

Ну не я ж топик начал-то. Так-то и мне непонятно, чем таким кардинальным могут отличаться реализации одного алгоритма на разных языках, окромя внешнего вида. Кардинально может отличаться архитектура реализации, т.к. зависит от парадигм языка... и то не факт. А так-то, пиши, на чём тебе будет читать удобно.
Я тут случайно чуть архиватор не написал. Начал вот с такого:

кодер

/* LZW кодирование
   стартовая ширина кодирования 9 бит, максимальная 16 */
int main()
{
  std::string   buffer;
  char          ch;
  std::ifstream inFile ("in.txt", std::ios::binary);
  std::ofstream outFile("out.txt",std::ios::binary);
  Bits          bitBuffer(outFile);
  // лямбда чтения очередного кода
  auto getCh = [&inFile]{
                          char ch;
 
                          inFile.read(&ch, 1);
                          return ch;
                        };
 
  initDict();
  ch = getCh();                                 // прочитать первый символ
  if (inFile.good()) buffer = ch;               // и запомнить как текущую цепочку
  while (inFile.good())
  {
    ch = getCh();                               // прочитать следующий символ
    if (inFile.gcount() == 0) continue;         // конец потока или ошибка чтения
    if (lastCode == curDictSize-1)              // если очередной код достиг предельного значения,
    {                                           // следующий код должен быть на бит длиннее
      if (lastCode == dictSize-1)               //   если только он не максимальный,
      {
        toOut(bitBuffer, dict[buffer]);         //   тогда вывести код текущей цепочки,
        toOut(bitBuffer, reset);                //   вывести код сброса словаря,
        initDict();                             //   переинициализировать
        buffer = ch;                            //   и запомнить текущий символ как текущую цепочку
        continue;
      }
      else ++curDictBit, curDictSize *= 2;      //   иначе просто расширить характристики кодирования
    }
 
    std::string newBuf = buffer + ch;           // новая цепочка
    auto        token  = dict.find(newBuf);     // попытаться найти в словаре код для неё
 
    if (token != dict.end())                    // если нашли,
    {
      buffer = newBuf;                          // то просто запомнить новую цепочку как текущую
      continue;
    }
    toOut(bitBuffer, dict[buffer]);             // иначе вывести код текущей цепочки,
    dict[newBuf] = from_ulong(++lastCode);      // дополнить словарь кодом для новой
    buffer = ch;                                // и запомнить текущий символ как текущую цепочку
  }
  // финализация кодирования
  toOut(bitBuffer, dict[buffer]);               // вывести код для текущей цепочки
  toOut(bitBuffer, end);                        // вывести код конца потока
  bitBuffer.flush();                            // сбросить битовый буфер в поток вывода
}

и потихонечку дописал к нему ( )

фреймворк

#include <map>
#include <bitset>
#include <string>
#include <fstream>
#include <cmath>
#include <limits>
 
// максимальная ширина элементов словаря в битах
const unsigned dictBit = 16;
// максимальный размер словаря
const unsigned dictSize= std::pow(2, dictBit);
 
// тип битового набора
using bitset = std::bitset<dictBit>;
 
// текущие битность и размер словаря и последний использованный в нём код
unsigned curDictBit;
unsigned curDictSize;
unsigned lastCode;
// символы окончания потока и сброса словаря
bitset end;
bitset reset;
// словарь[строка символов] = битовый набор
std::map<std::string, bitset> dict;
 
/* преобразовать код в битовый набор */
bitset from_ulong(unsigned long val)
{
  return bitset(val);
}
 
/* преобразовать битовый набор в код */
unsigned long to_ulong(const bitset& buf)
{
  return buf.to_ulong();
}
 
/* инициализация словаря и рабочих характеристик кодирования символов */
void initDict()
{
  int i;
 
  curDictBit = 9;                               // стартовая ширина кода
  curDictSize= std::pow(2, curDictBit);         // стартовый размер словаря
 
  // заполнить словарь базовыми кодами
  dict.clear();
  for (i = 0; i <= std::numeric_limits<unsigned char>::max(); ++i)
    dict[std::string(1, static_cast<char>(i))] = from_ulong(i);
  // добавить два спец.кода
  end  = from_ulong(++i);
  reset= from_ulong(++i);
  // последний использованный код
  lastCode = to_ulong(reset);
}
 
// прокси-класс для битового вывода в байтовый поток
template <typename Ch, typename Tr>
struct Bits
{
  using os_type = std::basic_ostream<Ch, Tr>;
 
  static constexpr size_t charBits = std::numeric_limits<Ch>::digits +
                                     std::numeric_limits<Ch>::is_signed;
  std::bitset<charBits> bufChar;        // буфер ввода
  size_t                curBit;         // текущая позиция бита в буфере
  os_type              &os;
 
  /* переполнение буфера: вывести в поток */
  void overflow()
  {
    Ch ch = Tr::to_char_type(bufChar.to_ulong());
 
    os.write(&ch, sizeof(ch));          // ошибки вывода остаются на совести вызывающей стороны; тут
    curBit = 0;                         // всё равно неизвестно, что делать, а там проверить os::good()
  }                                     // ничего не стоит, та и исключения никто не отменял
 
  Bits(const Bits&)            = delete;
  Bits(Bits&&)                 = default;
  Bits& operator=(const Bits&) = delete;
  Bits& operator=(Bits&&)      = default;
 
public:
  explicit Bits(os_type &osRef): bufChar(), curBit(0), os(osRef) {}
 
  /* вывести бит
     ошибки потока не обрабатываются: базовая гарантия */
  void outBit(bool b)
  {
    bufChar[curBit++] = b;
    if (curBit == bufChar.size()) overflow();
  }
  /* сбросить буфер досрочно
     недозаписанные в буфере биты неопределены */
  void flush() { overflow(); }
};
 
/* функция вывода очередного кода, шириной curDictBit, в поток */
template <typename Ch, typename Tr>
void toOut(Bits<Ch, Tr> &bos, const bitset& bits)
{
  for (int i = 0; i < curDictBit; ++i)  // записать младшие биты битового набора в количестве,
    bos.outBit(bits[i]);                // равном текущей ширине
}

Быстро, за вечер где-то. Или два, не помню. Но вот с декодером вышло далеко не так шоколадно. Поди отладься, когда непонятно, а кто, собстна, бажит. Понятно, что скорее всего оба, но... отлаживаться-то как?
В общем на вот это безобразие

декодер

/* LZW декодирование
   стартовая ширина кодирования 9 бит, максимальная 16 */
int main()
{
  std::ifstream inFile ("out.txt", std::ios::binary);
  std::ofstream outFile("res.txt", std::ios::binary);
  Bits          bitBuffer(inFile);
 
  std::string buffer;                           // ранее декодированный код
  bitset      ch;                               // ранее прочитанный код (пока пуст)
  // лямбда инициализации процесса декодирования
  auto start = [&]{                             // кто сказал, что в Плюсах нет локальных функций?
                    initDict();
                    ch = fromIn(bitBuffer);     // прочитать первый код для декодирования
                    if (inFile.good())
                    {
                      buffer = dict[ch];        // декодировать (первый код всегда будет найден)
                      outFile << buffer;        // и вывести
                    }
                  };
 
  // инициализировать словарь, прочить первый код, декодировать его и вывести
  start();
  while (inFile.good())
  {
    bitset nextCh = fromIn(bitBuffer);          // прочитать следующий код
 
    if (!inFile.good()) continue;               // конец потока или ошибка чтения
    if (nextCh == end)  break;                  // если символ конца потока кодов, всё
    if (nextCh == reset)                        // если символ сброса словаря, переинициализация
    {
      start();
      continue;
    }
 
    auto        token = dict.find(nextCh);      // попытаться найти код в словаре
    std::string decCh = dict[ch];               // декодированный код предыдущего кода (всегда будет найден)
    std::string newBuf;                         // декодированный код нового символа
 
    if (token != dict.end())                    // если новый код найден,
    {                                           // то его декодированный код определяется содержимым
      newBuf = decCh + token->second.front();   // словаря, осталось его только вывести и сформировать
      outFile << token->second;                 // его декодированный код, как это делало кодирование
    }
    else                                        // а если не найден (декодирование отстаёт на один
    {                                           // код от кодирования, поэтому иногда такое происходит),
      newBuf = decCh + decCh[0];                // то его декодированый код однозначно определяется
      outFile << newBuf;                        // алгоритмом кодирования, просто следуем ему
    }
    dict[from_ulong(++lastCode)] = newBuf;      // пополнить словарь новым кодом
    /* если до конца кодов словаря у нас осталось два символа, то у кодера уже один, т.к. декодер
       отстаёт от него на шаг, поэтому следующий символ уже будет закодирован кодом с шириной на бит
       больше, но не при максимальном размере: в этом случае ожидается символ сброса той же ширины */
    if (lastCode == curDictSize-2 && curDictBit != dictBit)
      ++curDictBit, curDictSize *= 2;           // расширяем рабочие характеристики кодирования
    ch = nextCh;                                // новый код на следующем шаге становится предыдущим
  }
}

с собственным фреймворком ( )

он самый

#include <map>
#include <bitset>
#include <string>
#include <cmath>
#include <fstream>
#include <limits>
 
// максимальная ширина элементов словаря в битах
const unsigned dictBit = 16;
// максимальный размер словаря
const unsigned dictSize= std::pow(2, dictBit);
 
// тип битового набора
using bitset = std::bitset<dictBit>;
 
// текущие битность и размер словаря и последний использованный в нём код
unsigned curDictBit;
unsigned curDictSize;
unsigned lastCode;
// символы окончания потока и сброса словаря
bitset end;
bitset reset;
// словарь[битовый набор] = строка символов
auto comp = [](const bitset& l, const bitset& r) { return l.to_ulong() < r.to_ulong(); };
std::map<bitset, std::string, decltype(comp)> dict(comp);
 
/* преобразовать код в битовый набор */
bitset from_ulong(unsigned long val)
{
  return bitset(val);
}
 
/* преобразовать битовый набор в код */
unsigned long to_ulong(const bitset& buf)
{
  return buf.to_ulong();
}
 
/* инициализация словаря и рабочих характеристик кодирования символов */
void initDict()
{
  int i;
 
  curDictBit = 9;                               // стартовая ширина кода
  curDictSize= std::pow(2, curDictBit);         // стартовый размер словаря
 
  // заполнить словарь базовыми кодами
  dict.clear();
  for (i = 0; i <= std::numeric_limits<unsigned char>::max(); ++i)
    dict[from_ulong(i)] = std::string(1, static_cast<char>(i));
  // добавить два спец.кода
  end  = from_ulong(++i);
  reset= from_ulong(++i);
  // последний использованный код
  lastCode = to_ulong(reset);
}
 
// прокси-класс для битового ввода из байтового потока
template <typename Ch, typename Tr>
struct Bits
{
  using is_type = std::basic_istream<Ch, Tr>;
 
  static constexpr size_t charBits = std::numeric_limits<Ch>::digits +
                                     std::numeric_limits<Ch>::is_signed;
  std::bitset<charBits> bufChar;        // буфер ввода
  size_t                curBit;         // текущая позиция бита в буфере
  is_type              &is;
 
  /* опустошение буфера: ввести из потока */
  void underflow()
  {
    Ch ch;
 
    is.read(&ch, sizeof(ch));           // ошибки ввода остаются на совести вызывающей стороны; тут
    curBit = bufChar.size();            // всё равно неизвестно, что делать, а там проверить is::good()
    bufChar= Tr::to_int_type(ch);       // ничего не стоит, та и исключения никто не отменял
  }
 
  Bits(const Bits&)            = delete;
  Bits(Bits&&)                 = default;
  Bits& operator=(const Bits&) = delete;
  Bits& operator=(Bits&&)      = default;
 
public:
  explicit Bits(is_type &isRef): bufChar(), curBit(0), is(isRef) {}
 
  /* ввести бит
     ошибки потока не обрабатываются: базовая гарантия */
  bool inBit()
  {
    if (curBit == 0) underflow();
    return bufChar[bufChar.size() - curBit--];
  }
};
 
/* функция ввода очередного кода, шириной curDictBit, из потока */
template <typename Ch, typename Tr>
bitset fromIn(Bits<Ch, Tr> &bis)
{
  bitset bits;
 
  for (int i = 0; i < curDictBit; ++i)  // читать битовый набор текущей ширины, старшие биты сброшены
    bits[i] = bis.inBit();
  return bits;
}

я чуть не забил. Зато когда-таки отладился, такие планы наполеоновские попёрли... включая параметризирование битовых границ словаря.
В общем, берите это, а то не остановлюсь. Вам будет проще, алгоритм надо будет просто перевести, а не реализовывать.

Сообщение отредактировано: Qraizer - 19.07.22, 03:33

[korvin]

Цитата Qraizer @ 19.07.22, 03:13

и потихонечку дописал к нему фреймворк

https://habr.com/ru/post/153225/

[Majestio]

Цитата korvin @ 19.07.22, 06:52

https://habr.com/ru/post/153225/

Как же долго я это безуспешно искал! Эту тему я когда-то видел в виде видосика.
Всегда ее вспоминаю, когда заходит речь о шаблонах проектирования.

[korvin]

https://rosettacode.org/wiki/LZW_compression

[Qraizer]

В целом ровно то же. Из недостатков – неограниченный словарь и головная боль из-за отсутствия "фреймворка" по работе с битами. Неограниченный словарь – это плохо. Со временем компрессия сменится расширением. Хранение кодов в виде чисел не прибавляет энтузиазма для пользователей этих примеров. У меня это больше половины реализации, сам LZW короче.

Добавлено 19.07.22, 12:21
Ну и на закуску — мои примеры легко адаптируются для данных произвольных разрядностей, как и предусмотрено алгоритмом. По ссылке входными данными только байты, на выходе коды с ограничением по длине.

Добавлено 19.07.22, 12:22
Но это придирки, в целом алгоритм такой же.

Добавлено 19.07.22, 12:23
P.S. В первом варианте я вообще не имел "фреймворка", тупо писал, читал битовые последовательности в текстовом представлении. "11100101001010101010" – примерно так. Иначе б вообще хрен бы отладился.

Добавлено 19.07.22, 12:27
А вот слабо ли кому на .cmd сие написать? Там даже bash отсутствует

Сообщение отредактировано: Qraizer - 19.07.22, 12:27

[korvin]

Цитата Qraizer @ 19.07.22, 12:14

По ссылке входными данными только байты

Не везде. От языка зависит.

Цитата Qraizer @ 19.07.22, 12:14

на выходе коды с ограничением по длине.

Тебе int'а не достаточно? Сам же хотел ограниченный словарь. Зачем же больше 2-х миллиардов последовательностей/кодов в нём хранить? )

Цитата Qraizer @ 19.07.22, 12:14

Но это придирки, в целом алгоритм такой же.

Дык алгоритм-то один, детали реализаций чуть разные.

Цитата Qraizer @ 19.07.22, 03:13

Поди отладься, когда непонятно, а кто, собстна, бажит. Понятно, что скорее всего оба, но... отлаживаться-то как?

Как-как. Тесты пиши. Подставляй себе вместо файлового ввода-вывода строковые/байтовые буферы и сверяй результаты с ожидаемыми. Если непонятно, на каком шаге проблема --- декомпозируй на отдельные функции, даже если думаешь, мол, нафига мне однострочные функции. Их проще тестировать.

Чё-т посидел немного, сделал пример на OCaml, тоже "расширенный", "фреймворкистый". С ограниченным словарём, как у тебя. Типы токенов/кодов и т.п. можно переделать на абстракные и использовать хоть BitSet, хоть что душе угодно.
Есть тесты.

Исходник в цвете: https://wtools.io/paste-code/bDEq

Исходник тут

let chain (f : 'a -> unit) : 'a -> 'a =
  fun x -> f x ; x
 
module type Encoder_dict = sig
  type t
  val reset_code : int
  val make       : unit -> t
  val add        : t -> string -> unit
  val mem        : t -> string -> bool
  val find       : t -> string -> int
  val is_full    : t -> bool
  val reset      : t -> unit
end
 
module Encoder (Dict : Encoder_dict) = struct
 
  module State = struct
    type t =
      { seq   : string
      ; token : string }
  end
 
  module Change = struct
    type t =
      | Found     of found
      | Not_found of not_found
      | Overflow  of overflow
    and found =
      { seq : string }
    and not_found =
      { seq     : string
      ; new_seq : string
      ; code    : int }
    and overflow =
      { seq  : string
      ; code : int }
  end
 
  type mem     = string -> bool
  type find    = string -> int
  type is_full = unit -> bool
 
  let encode ~mem ~find ~is_full state =
    let { State. seq ; token } = state in
    let next_seq = seq ^ token in
    if mem next_seq then
      Change.Found
        { seq = next_seq }
    else if is_full () then
      Change.Overflow
        { seq = token
        ; code = find seq }
    else
      Change.Not_found
        { seq = token
        ; new_seq = next_seq
        ; code = find seq }
 
  type env =
    { mutable seq : string
    ; dict        : Dict.t }
 
  let make_env () =
    { seq = "" ; dict = Dict.make () }
 
  let update env = function
  | Change.Found { seq } ->
    env.seq <- seq
  | Change.Not_found { seq ; new_seq ; code } ->
    env.seq <- seq ;
    Dict.add env.dict new_seq
  | Change.Overflow { seq ; code } ->
    env.seq <- seq ;
    Dict.reset env.dict
 
  let emit = function
  | Change.Found     _ -> []
  | Change.Not_found v -> [ v.code ]
  | Change.Overflow  v -> [ v.code ; Dict.reset_code ]
 
  let make () =
    let env = make_env () in
    let as_state token = { State. seq = env.seq ; token = token } in
    let encode = encode
      ~mem:(Dict.mem env.dict)
      ~find:(Dict.find env.dict)
      ~is_full:(fun _ -> Dict.is_full env.dict)
    in
      fun token -> token
        |> as_state
        |> encode
        |> chain (update env)
        |> emit
 
end
 
(* ================================================================ *)
 
module Encoder_test = struct
 
  module Dict_stub = struct
    type t = unit
    let reset_code = 42
    let make () = ()
    let add d s = ()
    let mem d s = false
    let find d s = 42
    let is_full d = false
    let reset d = ()
  end
 
  module E = Encoder (Dict_stub)
 
  let name = "encode"
 
  let _ =
    "TEST : " ^ name |> print_endline;
 
    let encode = E.encode
      ~mem:(fun s -> s = "A")
      ~find:(fun _ -> 13)
      ~is_full:(fun _ -> false)
    in
      ( match encode { seq = "" ; token = "A" } with
      | E.Change.Found { seq } ->
        assert (seq = "A")
      | _ -> assert false );
 
      ( match encode { seq = "A" ; token = "A" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "A") ;
        assert (new_seq = "AA") ;
        assert (code = 13)
      | _ -> assert false );
 
      ( match encode { seq = "A" ; token = "B" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "B") ;
        assert (new_seq = "AB") ;
        assert (code = 13)
      | _ -> assert false );
 
    let encode = E.encode
      ~mem:(fun s -> s = "A")
      ~find:(fun _ -> 13)
      ~is_full:(fun _ -> true)
    in
      ( match encode { seq = "" ; token = "A" } with
      | E.Change.Found { seq } ->
        assert (seq = "A")
      | _ -> assert false );
 
      ( match encode { seq = "A" ; token = "A" } with
      | E.Change.Overflow { seq ; code } ->
        assert (seq = "A") ;
        assert (code = 13)
      | _ -> assert false );
 
      ( match encode { seq = "A" ; token = "B" } with
      | E.Change.Overflow { seq ; code } ->
        assert (seq = "B") ;
        assert (code = 13)
      | _ -> assert false );
 
    (* Cyrillic *)
    let encode = E.encode
      ~mem:(fun s -> s = "Ц")
      ~find:(fun _ -> 13)
      ~is_full:(fun _ -> false)
    in
      ( match encode { seq = "" ; token = "Ц" } with
      | E.Change.Found { seq } ->
        assert (seq = "Ц")
      | _ -> assert false );
 
      ( match encode { seq = "Ц" ; token = "Ц" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "Ц") ;
        assert (new_seq = "ЦЦ") ;
        assert (code = 13)
      | _ -> assert false );
 
      ( match encode { seq = "Ц" ; token = "Ж" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "Ж") ;
        assert (new_seq = "ЦЖ") ;
        assert (code = 13)
      | _ -> assert false );
 
    (* Japanese 絶対 *)
    let encode = E.encode
      ~mem:(fun s -> s = "絶")
      ~find:(fun _ -> 13)
      ~is_full:(fun _ -> false)
    in
      ( match encode { seq = "" ; token = "絶" } with
      | E.Change.Found { seq } ->
        assert (seq = "絶")
      | _ -> assert false );
 
      ( match encode { seq = "絶" ; token = "絶" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "絶") ;
        assert (new_seq = "絶絶") ;
        assert (code = 13)
      | _ -> assert false );
 
      ( match encode { seq = "絶" ; token = "対" } with
      | E.Change.Not_found { seq ; new_seq ; code } ->
        assert (seq = "対") ;
        assert (new_seq = "絶対") ;
        assert (code = 13)
      | _ -> assert false );
 
    "PASS : " ^ name |> print_endline
 
end
 
(* ================================================================ *)
 
module type Token_encoder = sig
  val make : unit -> string -> int list
end
 
module Encode (Enc : Token_encoder) = struct
 
  let string_to_list s =
    let codes = ref [] in
    let push c = codes := c :: !codes in
    let push_all = List.iter push in
    let encode = Enc.make () in
    let as_token c = String.make 1 c in
    let f c = c |> as_token |> encode |> push_all in
    String.iter f s ;
    f '#' ;
    List.rev !codes
 
end
 
(* ================================================================ *)
 
module type Encode_conf = sig
  val capacity : int
  val alphabet : string
end
 
module Encode_dict (Conf : Encode_conf) = struct
 
  let _ =
    let cap = Conf.capacity in
    let alpha_len = String.length Conf.alphabet in
    assert (cap > 0) ;
    assert (alpha_len <= cap) ;
    let module CS = Set.Make (Char) in
    let unique = Conf.alphabet |> String.to_seq |> CS.of_seq in
    assert (alpha_len = CS.cardinal unique)
 
  type t = (string, int) Hashtbl.t
 
  let reset_code = Conf.capacity + 1
 
  let reset dict =
    Hashtbl.clear dict ;
    let map (i, c) = (String.make 1 c, i+1) in
    Conf.alphabet
    |> String.to_seqi
    |> Seq.map map
    |> Hashtbl.add_seq dict
 
  let make () =
    let dict = Hashtbl.create Conf.capacity in
    reset dict ;
    dict
 
  let is_full dict =
    Hashtbl.length dict = Conf.capacity
 
  exception Key_duplicate
  exception Capacity_overflow
 
  let add dict key =
    if Hashtbl.mem dict key then raise Key_duplicate ;
    if is_full dict then raise Capacity_overflow ;
    Hashtbl.add dict key (Hashtbl.length dict + 1)
 
  let mem = Hashtbl.mem
 
  exception Key_not_found
 
  let find dict key =
    match Hashtbl.find_opt dict key with
    | Some v -> v
    | None   -> raise Key_not_found
 
end
 
(* ================================================================ *)
 
module Encode_test = struct
 
  let str xs =
      "[" ^
      (  xs
      |> List.map string_of_int
      |> String.concat "; " ) ^
      "]"
 
  let _ =
    let module Dict = Encode_dict (struct
      let capacity = 42
      let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    end) in
 
    let module Encode = Encode (Encoder (Dict)) in
 
    let name = "string_to_list" in
    "TEST : " ^ name |> print_endline ;
 
    let input = "TOBEORNOTTOBEORTOBEORNOT" in
    let expected =
      [ 20; 15; 2; 5; 15; 18; 14; 15
      ; 20; 27; 29; 31; 36; 30; 32; 34 ]
    in
    let actual = Encode.string_to_list input in
    if List.equal (=) actual expected then
      "PASS : " ^ name |> print_endline
    else begin
      "FAIL : " ^ name |> print_endline ;
      "    expected: " ^ str expected |> print_endline ;
      "    actual:   " ^ str actual |> print_endline
    end
 
  let _ =
    let module Dict = Encode_dict (struct
      let capacity = 26
      let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    end) in
 
    let module Encode = Encode (Encoder (Dict)) in
 
    let name = "string_to_list (with overflow)" in
    "TEST : " ^ name |> print_endline ;
 
    let input = "TOBETO" in
    let expected = [20; 27; 15; 27; 2; 27; 5; 27; 20; 27; 15; 27] in
    let actual = Encode.string_to_list input in
    if List.equal (=) actual expected then
      "PASS : " ^ name |> print_endline
    else begin
      "FAIL : " ^ name |> print_endline ;
      "    expected: " ^ str expected |> print_endline ;
      "    actual:   " ^ str actual |> print_endline
    end
 
end
 
(* ================================================================ *)
 
module Encode_demo = struct
 
  module Dict = Encode_dict (struct
    let capacity = 42
    let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  end)
 
  module Encode = Encode (Encoder (Dict))
 
  let run input = input
    |> Encode.string_to_list
    |> List.iter (Printf.printf "%d ") ;
    print_endline ""
 
  let _ =
    run "TOTO" ;
    run "TOBEORNOTTOBEORTOBEORNOT" ;
    print_endline "20 15 2 5 15 18 14 15 20 27 29 31 36 30 32 34"
 
end
 
(* ================================================================ *)
 
module type Decoder_dict = sig
  type t
  val reset_code : int
  val make       : unit -> t
  val add        : t -> string -> unit
  val find_opt   : t -> int -> string option
  val reset      : t -> unit
  val size       : t -> int
end
 
module Decoder (Dict : Decoder_dict) = struct
 
  let append_first w s =
    w ^ String.sub s 0 1
 
  module State = struct
    type t =
      { seq  : string
      ; code : int }
  end
 
  module Change = struct
    type t =
      | First of string
      | Found of found
      | Reset
      | Not_found
    and found =
      { emit_seq : string
      ; dict_seq : string }
  end
 
  type find_opt = int -> string option
  type size     = unit -> int
 
  let decode ~find_opt ~size state =
    let { State. seq ; code } = state in
    if code = Dict.reset_code then
      Change.Reset
    else if seq = "" then
      match find_opt code with
      | Some v -> Change.First v
      | None   -> Change.Not_found
    else
      match find_opt code with
      | Some v ->
        Change.Found
          { emit_seq = v
          ; dict_seq = append_first seq v }
      | None ->
        if code = size () + 1 then
          let v = append_first seq seq in
          Change.Found
            { emit_seq = v
            ; dict_seq = append_first seq v }
        else
          Change.Not_found
 
  type env =
    { mutable seq : string
    ; dict        : Dict.t }
 
  let make_env () =
    { seq = "" ; dict = Dict.make () }
 
  exception Invalid_input
 
  let update env = function
  | Change.First seq ->
    env.seq <- seq ;
  | Change.Found { emit_seq ; dict_seq } ->
    Dict.add env.dict dict_seq ;
    env.seq <- emit_seq
  | Change.Reset ->
    Dict.reset env.dict ;
  | Change.Not_found ->
    raise Invalid_input
 
  let emit = function
  | Change.First seq -> [ seq ]
  | Change.Found v   -> [ v.emit_seq ]
  | Change.Reset     -> []
  | Change.Not_found -> raise Invalid_input
 
  let make () =
    let env = make_env () in
    let as_state code = { State. seq = env.seq ; code = code } in
    let decode = decode
      ~find_opt:(Dict.find_opt env.dict)
      ~size:(fun _ -> Dict.size env.dict)
    in
      fun code -> code
        |> as_state
        |> decode
        |> chain (update env)
        |> emit
 
end
 
(* ================================================================ *)
 
module Decoder_test = struct
 
  module Dict_stub = struct
    type t = unit
    let reset_code = 42
    let make () = ()
    let add d s = ()
    let find_opt d = function
      | 1 -> Some "A"
      | 2 -> Some "B"
      | 3 -> Some "AB"
      | 4 -> Some "BB"
      | _ -> None
    let size d = 4
    let reset d = ()
  end
 
  module D = Decoder (Dict_stub)
 
  let name = "decode"
 
  let _ =
    "TEST : " ^ name |> print_endline;
 
    let dict = Dict_stub.make () in
    let decode = D.decode
      ~find_opt:(Dict_stub.find_opt dict)
      ~size:(fun _ -> Dict_stub.size dict)
    in
      ( match decode { seq = "" ; code = 1 } with
      | D.Change.First seq ->
        assert (seq = "A")
      | _ -> assert false );
 
      ( match decode { seq = "A" ; code = 1 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "A") ;
        assert (dict_seq = "AA")
      | _ -> assert false );
 
      ( match decode { seq = "A" ; code = 2 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "B") ;
        assert (dict_seq = "AB")
      | _ -> assert false );
 
      ( match decode { seq = "B" ; code = 1 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "A") ;
        assert (dict_seq = "BA")
      | _ -> assert false );
 
      ( match decode { seq = "B" ; code = 2 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "B") ;
        assert (dict_seq = "BB")
      | _ -> assert false );
 
      ( match decode { seq = "AB" ; code = 3 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "AB") ;
        assert (dict_seq = "ABA")
      | _ -> assert false );
 
      ( match decode { seq = "A" ; code = 4 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "BB") ;
        assert (dict_seq = "AB")
      | _ -> assert false );
 
      ( match decode { seq = "B" ; code = 4 } with
      | D.Change.Found { emit_seq ; dict_seq } ->
        assert (emit_seq = "BB") ;
        assert (dict_seq = "BB")
      | _ -> assert false );
 
      ( match decode { seq = "" ; code = 42 } with
      | D.Change.Reset -> ()
      | _ -> assert false );
 
      ( match decode { seq = "A" ; code = 42 } with
      | D.Change.Reset -> ()
      | _ -> assert false );
 
      ( match decode { seq = "B" ; code = 42 } with
      | D.Change.Reset -> ()
      | _ -> assert false );
 
      ( match decode { seq = "AB" ; code = 42 } with
      | D.Change.Reset -> ()
      | _ -> assert false );
 
      ( match decode { seq = "BB" ; code = 42 } with
      | D.Change.Reset -> ()
      | _ -> assert false );
 
    "PASS : " ^ name |> print_endline
 
end
 
(* ================================================================ *)
 
module type Code_decoder = sig
  val make : unit -> int -> string list
end
 
module Decode (Dec : Code_decoder) = struct
 
  let list_to_string xs =
    let tokens = ref [] in
    let push t = tokens := t :: !tokens in
    let push_all = List.iter push in
    let decode = Dec.make () in
    let f c = c |> decode |> push_all in
    List.iter f xs ;
    List.rev !tokens |> String.concat ""
 
end
 
(* ================================================================ *)
 
module type Decode_conf = sig
  val capacity : int
  val alphabet : string
end
 
module Decode_dict (Conf : Decode_conf) = struct
 
  let _ =
    let cap = Conf.capacity in
    let alpha_len = String.length Conf.alphabet in
    assert (cap > 0) ;
    assert (alpha_len <= cap) ;
    let module CS = Set.Make (Char) in
    let unique = Conf.alphabet |> String.to_seq |> CS.of_seq in
    assert (alpha_len = CS.cardinal unique)
 
  type t = (int, string) Hashtbl.t
 
  let reset_code = Conf.capacity + 1
 
  let reset dict =
    Hashtbl.clear dict ;
    let map (i, c) = (i+1, String.make 1 c) in
    Conf.alphabet
    |> String.to_seqi
    |> Seq.map map
    |> Hashtbl.add_seq dict
 
  let make () =
    let dict = Hashtbl.create Conf.capacity in
    reset dict ;
    dict
 
  let size = Hashtbl.length
 
  exception Capacity_overflow
 
  let add dict key =
    (* if size dict = Conf.capacity then raise Capacity_overflow ; *)
    Hashtbl.add dict (Hashtbl.length dict + 1) key
 
  let find_opt = Hashtbl.find_opt
 
end
 
(* ================================================================ *)
 
module Decode_test = struct
 
  let _ =
    let module Dict = Decode_dict (struct
      let capacity = 42
      let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    end) in
 
    let module Decode = Decode (Decoder (Dict)) in
 
    let name = "list_to_string" in
    "TEST : " ^ name |> print_endline ;
 
    let input =
      [ 20; 15; 2; 5; 15; 18; 14; 15
      ; 20; 27; 29; 31; 36; 30; 32; 34 ]
    in
    let expected = "TOBEORNOTTOBEORTOBEORNOT" in
    let actual = Decode.list_to_string input in
    if actual = expected then
      "PASS : " ^ name |> print_endline
    else begin
      "FAIL : " ^ name |> print_endline ;
      "    expected: " ^ expected |> print_endline ;
      "    actual:   " ^ actual |> print_endline
    end
 
  let _ =
    let module Dict = Decode_dict (struct
      let capacity = 26
      let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    end) in
 
    let module Decode = Decode (Decoder (Dict)) in
 
    let name = "string_to_list (with overflow)" in
    "TEST : " ^ name |> print_endline ;
 
    let input = [20; 27; 15; 27; 2; 27; 5; 27; 20; 27; 15; 27] in
    let expected = "TOBETO" in
    let actual = Decode.list_to_string input in
    if actual = expected then
      "PASS : " ^ name |> print_endline
    else begin
      "FAIL : " ^ name |> print_endline ;
      "    expected: " ^ expected |> print_endline ;
      "    actual:   " ^ actual |> print_endline
    end
 
end
 
(* ================================================================ *)
 
module Decode_demo = struct
 
  module Dict = Decode_dict (struct
    let capacity = 42
    let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  end)
 
  module Decode = Decode (Decoder (Dict))
 
  let run input = input
    |> Decode.list_to_string
    |> print_endline
 
  let _ =
    run [ 20; 15; 27 ] ;
    run [ 20; 15; 2; 5; 15; 18; 14; 15; 20; 27; 29; 31; 36; 30; 32; 34 ] ;
    print_endline "TOBEORNOTTOBEORTOBEORNOT"
 
end
 
(* ================================================================ *)
 
module type Full_conf = sig
  val capacity : int
  val alphabet : string
end
 
module Full_coder (Conf : Full_conf) = struct
 
  module Encode = Encode (Encoder (Encode_dict (Conf)))
  module Decode = Decode (Decoder (Decode_dict (Conf)))
 
  type decoded = string
  type encoded = int list
 
  let encode = Encode.string_to_list
  let decode = Decode.list_to_string
 
end
 
(* ================================================================ *)
 
module type Coder = sig
  type decoded = string
  type encoded
 
  val encode : decoded -> encoded
  val decode : encoded -> decoded
end
 
module Full_test (C : Coder) = struct
 
  let test input =
    let result = input |> C.encode |> C.decode in
    assert (result = input)
 
  let name = "full"
 
  let _ =
    "TEST : " ^ name |> print_endline ;
    test "TOTO" ;
    test "TOBEOR" ;
    test "TOBEORTOBEER" ;
    test "TOBEORNOTTOBE" ;
    test "TWOBEERORNOTTWOBEER" ;
    test "TOBEORNOTTOBEORTOBEORNOT" ;
    "PASS : " ^ name |> print_endline
 
end
 
module Test = struct
 
  module Conf = struct
    let capacity = 42
    let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  end
 
  module Coder = Full_coder (Conf)
 
  module T = Full_test (Coder)
 
end

Запустить можно, например, тут (нужна версия OCaml 4.12 или новее): https://www.jdoodle.com/compile-ocaml-online/

Выхлоп:

TEST : encode
PASS : encode
TEST : string_to_list
PASS : string_to_list
TEST : string_to_list (with overflow)
PASS : string_to_list (with overflow)
20 15 27
20 15 2 5 15 18 14 15 20 27 29 31 36 30 32 34
20 15 2 5 15 18 14 15 20 27 29 31 36 30 32 34
TEST : decode
PASS : decode
TEST : list_to_string
PASS : list_to_string
TEST : string_to_list (with overflow)
PASS : string_to_list (with overflow)
TOTO
TOBEORNOTTOBEORTOBEORNOT
TOBEORNOTTOBEORTOBEORNOT
TEST : full
PASS : full

Сообщение отредактировано: korvin - 24.07.22, 21:35

[Qraizer]

Цитата korvin @ 24.07.22, 21:34

Не везде. От языка зависит.

Я имел в виду конкретно Плюсовую реализацию.

Цитата korvin @ 24.07.22, 21:34

Тебе int'а не достаточно?

В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.

Цитата korvin @ 24.07.22, 21:34

Как-как. Тесты пиши. Подставляй себе вместо файлового ввода-вывода строковые/байтовые буферы и сверяй результаты с ожидаемыми.

Так а толку от тестов, я и так проблему вижу, мне б её причину найти. Ожидаемые... то-то и оно, что их хрен рассчитаешь. Помню веселье, когда Хаффмана писали лет 20 назад. На Паскале.

[Qraizer]

Цитата Qraizer @ 19.07.22, 03:13

Я тут случайно чуть архиватор не написал.
...
В общем, берите это, а то не остановлюсь.

Хреновый из меня программист. Не смог остановиться. Нате.

bits.h

#ifndef BITS_H_FA9978BA_82D1_4DC4_9FE8_AA6AEFBA4FE4
#define BITS_H_FA9978BA_82D1_4DC4_9FE8_AA6AEFBA4FE4
 
#include <cmath>
#include <bitset>
#include <vector>
 
// максимальная ширина элементов словаря в битах
inline unsigned dictBit;
// максимальный размер словаря
inline unsigned dictSize;
// максимальная ширина кода в битах
inline unsigned codeBit;
 
// тип битового набора
using codeSet = std::vector<bool>;
// тип представления кодовых цепочек
using codeKey = std::vector<codeSet>;
 
// текущие битность и размер словаря и последний использованный в нём код
inline unsigned curDictBit;
inline unsigned curDictSize;
inline unsigned lastCode;
// символы окончания потока и сброса словаря
inline codeSet end;
inline codeSet reset;
 
/* преобразовать код в битовый набор */
inline codeSet from_ulong(unsigned long val, size_t width)
{
  const auto numBits = std::numeric_limits<decltype(val)>::digits +
                       std::numeric_limits<decltype(val)>::is_signed;
  std::bitset<numBits> tmp (val);
  codeSet              bits(width);
 
  for (int i = 0; i < bits.size(); ++i)
    bits[i] = tmp[i];
  return bits;
}
 
/* преобразовать битовый набор в код */
inline unsigned long to_ulong(const codeSet& buf)
{
  const auto numBits = std::numeric_limits<decltype(to_ulong(buf))>::digits +
                       std::numeric_limits<decltype(to_ulong(buf))>::is_signed;
  std::bitset<numBits> tmp;
 
  for (int i = 0; i < buf.size(); ++i)
    tmp[i] = buf[i];
  return tmp.to_ulong();
}
 
/* инициализация словаря кодами, настроенными на указанные битности */
inline void init(auto &dict, auto initFunc)
{
  int i;
 
  dict.clear();
  // перебор всех кодов алфавита и формирование базового набора кодов для словаря
  for (i = 0; i < std::pow(2, codeBit); ++i)
    initFunc(from_ulong(i, codeBit), from_ulong(i, dictBit));
 
  // добавить два спец.кода
  end  = from_ulong(  i, dictBit);
  reset= from_ulong(++i, dictBit);
  // последний использованный код
  lastCode = i;
 
  curDictBit = codeBit + 1;                     // стартовая ширина кода
  curDictSize= std::pow(2, curDictBit);         // стартовый размер словаря
  // если почему-то end и reset переполнили базовый словарь, подправить стартовые характеристики
  if (lastCode >= curDictSize - 1 && lastCode != dictSize - 1)  // если надо
    ++curDictBit, curDictSize *= 2;
}
 
// ограничить максимальную разрядность кодирования разумной величиной
inline size_t maxBits = std::min(std::numeric_limits<decltype(to_ulong(codeSet()))>::digits +
                                 std::numeric_limits<decltype(to_ulong(codeSet()))>::is_signed,
                                 24);
 
#endif

ioBits.h

#ifndef IOBITS_H_FA9978BA_82D1_4DC4_9FE8_AA6AEFBA4FE4
#define IOBITS_H_FA9978BA_82D1_4DC4_9FE8_AA6AEFBA4FE4
 
#include <limits>
#include <iostream>
#include <string>
#include <bitset>
#include <algorithm>
#include "bits.h"
 
namespace bits_io
{
 
// базовый для прокси-классов класс
template <typename Ch, typename Tr>
class basic_Bits
{
protected:
  static constexpr size_t charBits = std::numeric_limits<Ch>::digits +
                                     std::numeric_limits<Ch>::is_signed;
  using buf_type = std::bitset<charBits>;
 
  basic_Bits(const basic_Bits&)            = delete;
  basic_Bits& operator=(const basic_Bits&) = delete;
 
public:
  basic_Bits(basic_Bits&&)                 = default;
  basic_Bits& operator=(basic_Bits&&)      = default;
 
  basic_Bits()                             = default;
};
 
// прокси-класс для битового вывода в стандартный поток
template <typename Ch, typename Tr>
struct basic_oBits: public basic_Bits<Ch, Tr>
{
  using os_type    = std::basic_ostream<Ch, Tr>;        // тип потока вывода
  using base_class = basic_Bits<Ch, Tr>;                // базовый класс
  using typename base_class::buf_type;
 
  buf_type bufChar;             // буфер вывода
  size_t   curBit;              // текущая позиция бита в буфере
  os_type &os;                  // поток вывода
 
  /* переполнение буфера: вывести в поток */
  void overflow()
  {
    if (curBit == 0) return;            // не сбрасывать, если нечего
 
    Ch ch = Tr::to_char_type(bufChar.to_ulong());
 
    os.write(&ch, sizeof(ch));          // ошибки вывода остаются на совести вызывающей стороны; тут
    curBit = 0;                         // всё равно неизвестно, что делать, а там проверить os::good()
  }                                     // ничего не стоит, та и исключения никто не отменял
 
public:
  explicit basic_oBits(os_type &osRef): bufChar(), curBit(0), os(osRef) {}
 
  /* вывести бит
     ошибки потока не обрабатываются: базовая гарантия */
  void outBit(bool b)
  {
    bufChar[curBit++] = b;
    if (curBit == bufChar.size()) overflow();
  }
  /* сбросить буфер досрочно
     недозаписанные в буфере биты неопределены */
  void flush() { overflow(); }
};
 
// прокси-класс для битового ввода из стандартного потока
template <typename Ch, typename Tr>
struct basic_iBits: public basic_Bits<Ch, Tr>
{
  using is_type    = std::basic_istream<Ch, Tr>;        // тип потока ввода
  using base_class = basic_Bits<Ch, Tr>;                // базовый класс
  using typename base_class::buf_type;
 
  buf_type bufChar;             // буфер ввода
  size_t   curBit;              // текущая позиция бита в буфере
  is_type &is;                  // поток ввода
 
  /* опустошение буфера: ввести из потока */
  void underflow()
  {
    Ch ch;
 
    is.read(&ch, sizeof(ch));
    if (is.good()) curBit = bufChar.size();     // при ошибке ввода оставить curBit в нуле
    bufChar= Tr::to_int_type(ch);
  }
 
public:
  explicit basic_iBits(is_type &isRef): bufChar(), curBit(0), is(isRef) {}
 
  /* ввести бит
     ошибки потока не обрабатываются: базовая гарантия */
  bool inBit()
  {
    if (curBit == 0) underflow();
    return is.good() ? bufChar[bufChar.size() - curBit--]
                     : false;   // не уменьшать curBit при ошибках
  }
  /* признак конца потока */
  bool eof() const
  {
    return is.eof() && curBit == 0;     // если поток в eof, и биты кончились (или ошибка)
  }
};
 
// прокси-класс для битового ввода/вывода в стандартном потоке
template <typename Ch, typename Tr>
struct basic_ioBits: public basic_iBits<Ch, Tr>,
                     public basic_oBits<Ch, Tr>
{
  using ios_type = std::basic_iostream<Ch, Tr>;                 // тип потока ввода/вывода
 
public:
  explicit basic_ioBits(ios_type &iosRef): basic_iBits(iosRef), basic_oBits(iosRef) {}
};
 
/* функция вывода очередного кода bits, шириной width, в поток bos */
template <typename Val, typename Ch, typename Tr>
void toOut(bits_io::basic_oBits<Ch, Tr> &bos, const Val& bits, size_t width)
{
  auto size = std::min(width, bits.size());     // ограничить ширину размером bits
 
  for (decltype(size) i = 0; i < size; ++i)     // записать младшие биты битового набора в количестве,
    bos.outBit(bits[i]);                        // равном указанной ширине
}
/* функция вывода очередного набора кодов bits в поток bos */
template <typename Ch, typename Tr>
void toOut(bits_io::basic_oBits<Ch, Tr> &bos, const codeKey& bits)
{
  // проциклить по всему контейнеру
  for (auto it = bits.begin(); it != bits.end(); ++it)
    toOut(bos, *it, it->size());
}
 
/* функция ввода очередного кода, шириной widthIn, из потока bis и откастить в ширину widthOut */
template <typename Ch, typename Tr>
codeSet fromIn(bits_io::basic_iBits<Ch, Tr> &bis, size_t widthIn, size_t widthOut)
{
  codeSet bits(widthOut);
  int     i;
 
  for (i = 0; i < widthIn; ++i)         // читать битовый набор указанной ширины,
  {                                     // старшие биты сброшены конструктором
    bool bit = bis.inBit();             // ввести бит
 
    if (bis.eof()) break;               // проверить ошибку
    bits[i] = bit;
  }                                     // при ошибке вернуть реальные биты вместо widthOut, что
  if (bis.eof()) bits.resize(i);        // актуально в конце потока, когда битов может оказаться
  return bits;                          // недостаточно для цельного символа указанной ширины widthIn
}                                       // вызывающая сторона ответственна за обработку этого случая
 
}
 
#endif

encoder.cpp

#include <map>
#include <iostream>
#include <string>
#include <fstream>
#include <regex>
#include <limits>
#include <bit>
#
#include "ioBits.h"
#include "bits.h"
 
using namespace std::literals;
 
// словарь[строка символов] = битовый набор
std::map<codeKey, codeSet> dict;
// имена исходного и результирующего файлов
std::string inFileName, outFileName;
 
// разбор параметров
bool parsParams(const char *const* first, const char *const* last)
{
  std::regex  bitsParam("(/|-)bits:(\\d+)?-(\\d+)?", std::regex::icase);
  std::cmatch matchs;
  int         startWidth = -1, maxWidth = -1;
 
  // по всем параметрам
  for (auto it = first; it != last; ++it)
  {
    if (std::regex_search(*it, matchs, bitsParam))      // проверяем регекспу
      try
      {                                                 // если совпало, вытаскиваем ширины
        if (matchs[2].matched) startWidth = std::stoi(matchs[2]);       // начальная
        if (matchs[3].matched) maxWidth   = std::stoi(matchs[3]);       // максимальная
        continue;
      }
      catch(...)
      {
        std::cout << (startWidth == -1 ? "Start"s : "Max"s) + " bit width is not a number" << std::endl;
        return false;
      }
    if (!outFileName.empty())                           // если не совпало, то это имя файла
    {
      std::cout << "Too many parameters" << std::endl;  // оба уже получены
      return false;
    }
    (inFileName.empty() ? inFileName : outFileName) = *it;      // иначе это либо in, либо out
  }
  // если что-то не указано, берём по умолчанию
  codeBit = startWidth == -1 ?  8 : startWidth;
  dictBit = maxWidth   == -1 ? 16 : maxWidth;
  dictSize= std::pow(2, dictBit);
  if (outFileName.empty())
    outFileName = inFileName + ".lzw";
  return true;
}
 
/* LZW кодирование
   стартовая ширина кодирования 9 бит, максимальная 16 */
int main(int argn, char *argv[])
{
  if (!parsParams(argv + 1, argv + argn)) return 2;     // получить и разгрести параметры
 
  // проверить корректность параметров
  if (codeBit == 0)
  {
    std::cout << "Start bit width is too small" << std::endl;
    return 1;
  }
  if (dictBit <= codeBit )
  {
    std::cout << "Max bit width is less than start" << std::endl;
    return 1;
  }
  if (dictBit > maxBits)
  {
    std::cout << "Max bit width too long" << std::endl;
    return 1;
  }
  if (inFileName.empty())
  {
    std::cout << "Infile file name is absent" << std::endl;
    return 1;
  }
 
  codeKey buffer(1);            // текущая цепочка, пока размером 1 символ
  codeSet ch(codeBit);          // текущий символ, пока пуст
 
  // файлы
  std::ifstream        inFile (inFileName, std::ios::binary);
  std::ofstream        outFile(outFileName,std::ios::binary);
  // битовые потоки для них
  bits_io::basic_iBits iBuffer(inFile);
  bits_io::basic_oBits oBuffer(outFile);
 
  // лямбда заполнения элемента словаря
  auto initDict = [](const auto &code, const auto &chain){ dict[codeKey{codeSet(code.begin(),
                                                                        code.begin()+codeBit)}] = chain; };
  // лямбда записи заголовка
  auto writeHead= [&]{
                       codeSet bits = from_ulong(codeBit, std::bit_width(maxBits));
 
                       toOut(oBuffer, bits, bits.size());       // начальная ширина
                       bits = from_ulong(dictBit, std::bit_width(maxBits));
                       toOut(oBuffer, bits, bits.size());       // максимальная ширина
                     };
 
  init(dict, initDict);                         // инициалиация процесса
  ch = fromIn(iBuffer, ch.size(), ch.size());   // прочитать первый символ
  if (inFile.good()) buffer[0] = ch;            // и запомнить как текущую цепочку
  writeHead();                                  // заполнить заголовок
  while (inFile.good())
  {
    ch = fromIn(iBuffer, ch.size(), ch.size()); // прочитать следующий символ
    if (lastCode == curDictSize-1)              // если очередной код достиг предельного значения,
    {                                           // следующий код должен быть на бит длиннее
      if (lastCode == dictSize-1)               //   если только он не максимальный,
      {
        toOut(oBuffer, dict[buffer], curDictBit);//  тогда вывести код текущей цепочки,
        toOut(oBuffer, reset, curDictBit);      //   вывести код сброса словаря,
        init (dict, initDict);                  //   переинициализировать
        buffer.resize(1);
        buffer[0] = ch;                         //   и запомнить текущий символ как текущую цепочку
        continue;
      }
      else ++curDictBit, curDictSize *= 2;      //   иначе просто расширить характристики кодирования
    }
    if (iBuffer.eof()) continue;                // конец потока
 
    // новая цепочка
    codeKey newBuf([&]{ decltype(buffer) temp(buffer); temp.emplace_back(ch); return temp; }());
    auto    token = dict.find(newBuf);          // попытаться найти в словаре код для неё
 
    if (token != dict.end())                    // если нашли,
    {
      buffer = newBuf;                          // то просто запомнить новую цепочку как текущую
      continue;
    }
    toOut(oBuffer, dict[buffer], curDictBit);           // иначе вывести код текущей цепочки,
    dict[newBuf] = from_ulong(++lastCode, dictBit);     // дополнить словарь кодом для новой
    buffer.resize(1);
    buffer[0] = ch;                             // и запомнить текущий символ как текущую цепочку
  }
  // финализация кодирования
  toOut(oBuffer, dict[buffer], curDictBit);     // обработать текущую цепочку (новых больше не будет)
  // учесть случай, когда декодер здесь уже увеличит разрядность кодирования
  // он-то пока не знает, что новых символов уже не будет
  if (lastCode == curDictSize-2 && curDictBit != dictBit) ++curDictBit;
  toOut(oBuffer, end, curDictBit);              // вывести код конца потока
  // докопировать последние биты, которых не хватило до заполнения целого кода символа
  toOut(oBuffer, from_ulong(ch.size(), std::bit_width(maxBits)), std::bit_width(maxBits));
  toOut(oBuffer, ch, ch.size());
  oBuffer.flush();                              // сбросить недозаполненный битовый буфер
}

decoder.cpp

#include <map>
#include <cmath>
#include <fstream>
#include <limits>
#include <bit>
#include "ioBits.h"
 
// словарь[битовый набор] = строка символов
std::map<codeSet, codeKey> dict;
 
// имена исходного и результирующего файлов
std::string inFileName, outFileName;
 
// разбор параметров
bool parsParams(const char *const* first, const char *const* last)
{
  for (auto it = first; it != last; ++it)
    (inFileName.empty() ? inFileName : outFileName) = *it;      // первый in, иначе out
  if (outFileName.empty())
    outFileName = inFileName + ".unp";          // если out не указан, берём по умолчанию
  return true;
}
 
/* LZW декодирование
   стартовая ширина кодирования 9 бит, максимальная 16 */
int main(int argn, char *argv[])
{
  if (!parsParams(argv + 1, argv + argn)) return 2;     // получить и разгрести параметры
 
  // проверить корректность параметров
  if (inFileName.empty())
  {
    std::cout << "Infile file name is absent" << std::endl;
    return 1;
  }
 
  // файлы
  std::ifstream        inFile (inFileName, std::ios::binary);
  std::ofstream        outFile(outFileName,std::ios::binary);
  bits_io::basic_iBits iBuffer(inFile);
  bits_io::basic_oBits oBuffer(outFile);
 
  codeKey buffer;                           // ранее декодированный код
  codeSet ch(dictBit);                      // ранее прочитанный код
 
  // лямбда чтения заголовка
  auto readHead = [&]{
                       codeSet bits = fromIn(iBuffer, std::bit_width(maxBits), std::bit_width(maxBits));
 
                       codeBit = to_ulong(bits);        // начальная ширина
                       bits    = fromIn(iBuffer, std::bit_width(maxBits), std::bit_width(maxBits));
                       if (!inFile.good()) return false;
                       dictBit = to_ulong(bits);        // максимальная ширина
                       dictSize= std::pow(2, dictBit);  // количество кодов в словаре
                       return true;
                     };
  // лямбда заполнения элемента словаря
  auto initDict = [](const auto &code, const auto &chain){ dict[chain] = codeKey{codeSet(code.begin(),
                                                                                 code.begin()+codeBit)}; };
  // лямбда инициализации процесса декодирования
  auto start = [&]{                             // кто сказал, что в Плюсах нет локальных функций?
                    init(dict, initDict);
                    // прочитать первый код для декодирования
                    ch = fromIn(iBuffer, curDictBit, dictBit);
                    if (!iBuffer.eof())
                    {
                      buffer = dict[ch];        // декодировать (первый код всегда будет найден)
                      toOut(oBuffer, buffer);   // и вывести
                    }
                  };
 
  // прочитать заголовок и настроить словарь
  if (!readHead())
  {
    std::cout << "Read heading error" << std::endl;
    return 1;
  }
  // инициализировать словарь, прочитать первый код, декодировать его и вывести
  start();
  while (inFile.good())
  {
    codeSet nextCh = fromIn(iBuffer, curDictBit, dictBit);      // прочитать следующий код
 
    if (iBuffer.eof()) continue;                // конец потока
    if (nextCh == end) break;                   // если символ конца потока кодов, всё
    if (nextCh == reset)                        // если символ сброса словаря, переинициализация
    {
      start();
      continue;
    }
 
    auto    token = dict.find(nextCh);          // попытаться найти код в словаре
    codeKey decCh = dict[ch];                   // декодированный код предыдущего кода (всегда будет найден)
 
    buffer = decCh;                             // декодированный код нового символа (пока не готов)
    if (token != dict.end())                    // если новый код найден, то его декодированный код
    {                                           // определяется содержимым словаря,
      buffer.emplace_back(token->second.front());//осталось его только вывести и сформировать
      toOut(oBuffer, token->second);            // его декодированный код, как это делал кодер
    }
    else                                        // а если не найден (декодирование отстаёт на один
    {                                           // код от кодирования, поэтому иногда такое происходит),
      buffer.emplace_back(decCh[0]);            // то его декодированый код однозначно определяется
      toOut(oBuffer, buffer);                   // алгоритмом кодирования, просто следуем ему
    }
    dict[from_ulong(++lastCode, dictBit)]=buffer;//пополнить словарь новым кодом
    /* если до конца кодов словаря у нас осталось два символа, то у кодера уже один, т.к. декодер
       отстаёт от него на шаг, поэтому следующий символ уже будет закодирован кодом с шириной на бит
       больше, но не при максимальном размере: в этом случае ожидается символ сброса той же ширины */
    if (lastCode == curDictSize-2 && curDictBit != dictBit)
      ++curDictBit, curDictSize *= 2;           // расширяем рабочие характеристики кодирования
    ch = nextCh;                                // новый код на следующем шаге становится предыдущим
  }
  // финализируем: читаем остаток битов, не влезжих в последний символ
  ch = fromIn(iBuffer, std::bit_width(maxBits), std::bit_width(maxBits));
  for (int i = 0; i < to_ulong(ch); ++i)
    oBuffer.outBit(iBuffer.inBit());            // и докопируем, остальные биты потока игнорируем
}

Это полноценные (почти) компрессор и декомпрессор. На входе компрессору нужно указать файл и опционально имя результирующего. А ещё распознаётся параметр /bits:<битовая ширина символа>-<максимальная ширина кодирования>, которым можно указать любую ширину кода (по умолчанию 8) и максимальную битовую ширину кодов (по умолчанию 16). Например, /bits:16-24 идеально подойдёт для юникода, а /bits:4-12 сымитирует GIF. Обе ширины указывать необязательно, отсутствие какого-либо определяется по пустоте вокруг -, типа bits:4- или там /bits:-24, почему нет. (Не стоит указывать прям-таки малые разрядности. Хоть /bits:1-2 и будет работать, но это не смешно.) С декомпрессором проще, у него просто параметром имя файла. Или два, второй для результирующего имени.

P.S. Верхняя граница захардорджена в 24 бита. Несложно изменить на 28, например. А то мало ли, вдруг у кого-то терабайт оперативы.

Добавлено 26.07.22, 18:40
P.P.S. Особую радость доставили некратные размеру файла битовые последовательности. Берём какое-нибудь /bits:11-17 и радуемся, что не вы отлаживали.

P.P.P.S. Пока писал, придумал улучшение LZW. Пойду в отпуск, попробую реализовать.

Добавлено 26.07.22, 18:41
PPS.PPS.PPS. Код предоставляется без гарантий. Баги всё ещё возможны. Правда, последними N-цатью были лишние символы в конце, что нестрашно, но всё же.

Сообщение отредактировано: Qraizer - 26.07.22, 19:07

[korvin]

Цитата Qraizer @ 26.07.22, 18:15

В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.

А long? ) Впрочем, мысль понял, я сначала предположил, что ты вообще про те примеры, а не только про плюсовый.

Цитата Qraizer @ 26.07.22, 18:15

Так а толку от тестов, я и так проблему вижу, мне б её причину найти.

Ну так тесты и помогают найти проблему. Только нужна большая декомпозиция, даже если полная реализация и так невелика.

Цитата Qraizer @ 26.07.22, 18:15

Ожидаемые... то-то и оно, что их хрен рассчитаешь.

Ну почему же? Можно взять совсем простые, короткие последовательности, сделать на их основе ппоследовательности чуть по-сложнее. Взять пример с вики. Результаты без сброса словаря можно нагенерировать с использованием точно рабочих версий с того сайта, например.

Тут-то алгоритм известный, корректные реализации существуют. Было бы что-то более специфичное, было бы чуть сложнее, да. Помогает ограничение области определения и области значений функции с помошью типизации насколько возможно, чтобы просто сложно было в принципе передать некорректные данные и получить некорректные результаты.

Цитата Qraizer @ 26.07.22, 18:32

На входе компрессору нужно указать файл и опционально имя результирующего.

Можно было бы просто использовать stdin/stdout и не париться с именами файлов в программе, как по мне.

Добавлено 26.07.22, 18:58

Цитата Qraizer @ 26.07.22, 18:32

Хреновый из меня программист. Не смог остановиться.

Я на свой код потратил примерно день, из него полдня думал над тем, какой должен быть тип результата encode (тип Change), слишком много вариантов было Тоже такое себе ))

Сообщение отредактировано: korvin - 26.07.22, 19:00

[Qraizer]

Фиксанул бажочичечичик. Компрессор падал на пустых файлах. (А я-то думаю, нафига защиту в ioBits.h вписывал, вроде ж не должно быть такого никогда. Ан-нет, бывает.)

Цитата korvin @ 26.07.22, 18:43

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

Ну так-то оно понятно. Вот только с посложнее как раз и сложно. Особенно, когда стал пакетно тестить на разных /bits. Поди пойми, почему на таком файле нормалёк, а на этом упало.

[Majestio]

Не, камарады, ИМХО вы дорогу не в ту степь выбрали! Вместо того, чтобы визуализировать как можно нагляднее алгоритм, ты тут письками кодом меряетесь! Я спецом взял тайм-аут для наблюдения. Все смотрел, чего же так не хватает. И сделал определенные выводы конечно ИМХОшные:

1. Статическая типизация захламляет "чтение" алгоритма (для собственного кодирования - нет преград патриотам)
2. Использовать чисто процедурный подход - остальное усложняет визуализацию
3. Использовать подход "композиция-декомпозиция" с помощью вынесения отдельных участков алгоритма в функции или именованные лямбды (где это допустимо)
4. Библиотечные функции алгоритмов использовать допустимо, но с подробными комментами

Мой рейтинг языков:

1) Perl - идеален
2) С - так себе, С++ (векторы, ассоциативные массивы и больше ничего) - оч хорош
3) Пасквиль - избыточен, слишком многобукф
4) OCaml - хрен его поймешь в написании от korvin, но, судя по вики, п.1-3 в нем можно исполнить
5) JavaSctipt (не TypeScript) - похоже тоже неплох
6) Forth - ьтазакс от-отч ьсюяндуртаз месвос акоп я тут

Сообщение отредактировано: Majestio - 27.07.22, 09:12

[korvin]

Цитата Majestio @ 27.07.22, 08:22

1) Perl - идеален

Как кто-то где-то когда-то сказал, "Перл гениален в своей ублюдочности".

Цитата Majestio @ 27.07.22, 08:22

Статическая типизация захламляет "чтение" алгоритма (для собственного кодирования - нет преград патриотам)

Ты просто не умеешь её готовить.

Цитата Majestio @ 27.07.22, 08:22

Использовать чисто процедурный подход - остальное усложняет визуализацию

Просто ты ни с чем больше не знаком.

Цитата Majestio @ 27.07.22, 08:22

Библиотечные функции алгоритмов использовать допустимо, но с подробными комментами

WUT?

Цитата Majestio @ 27.07.22, 08:22

визуализировать как можно нагляднее алгоритм

Это никому не интересно, он в википедии описан наглядно.

https://wtools.io/paste-code/bDLS

Скрытый текст

let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
(**
  LZW encode : string -> int list
*)
let encode s =
  let dict = Hashtbl.create (String.length alphabet) in
  let add_to_dictionary w = Hashtbl.add dict w (Hashtbl.length dict + 1) in
  let is_in_dictionary = Hashtbl.mem dict in
  let input = ref "" in
  let output = ref [] in
  let emit_index_of w = output := Hashtbl.find dict w :: !output in
 
  alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
 
  for i = 0 to String.length s - 1 do
    let c = String.sub s i 1 in
    let w = !input in
    let wc = w ^ c in
    if wc |> is_in_dictionary then
      input := wc
    else begin
      emit_index_of w ;
      input := c ;
      add_to_dictionary wc
    end
  done ;
  emit_index_of !input ;
 
  List.rev !output
 
(**
  LZW decode : int list -> string
*)
let decode codes =
  match codes with
  | [] -> ""
  | first_code :: rest_codes ->
    let dict = Hashtbl.create (String.length alphabet) in
    let add_to_dictionary w = Hashtbl.add dict (Hashtbl.length dict + 1) w in
    let word_for = Hashtbl.find_opt dict in
    let first_symbol_of s = String.sub s 0 1 in
 
    alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
 
    let first = (match word_for first_code with Some w -> w | None -> failwith "invalid input") in
    let output = ref first in
    let previous = ref first in
    let emit w = output := !output ^ w ; previous := w in
 
    rest_codes |> List.iter (fun code ->
      match word_for code with
      | Some w ->
        let v = !previous ^ first_symbol_of w in
        add_to_dictionary v ;
        emit w
      | None ->
        let v = !previous ^ first_symbol_of !previous in
        add_to_dictionary v ;
        emit v
    );
 
  !output
 
(* ---------------------------------------------------------------- *)
 
let test_phrase = "TOBEORNOTTOBEORTOBEORNOT"
 
let _ =
  print_endline test_phrase ;
  let encoded = encode test_phrase in
  List.iter (Printf.printf "%d ") encoded ; print_endline "" ;
  let decoded = decode encoded in
  print_endline decoded

Сообщение отредактировано: korvin - 28.07.22, 23:23

[Majestio]

Цитата korvin @ 28.07.22, 23:23

Ты просто не умеешь её готовить.

Болтовня.

Цитата korvin @ 28.07.22, 23:23

Просто ты ни с чем больше не знаком.

Болтовня.

Цитата korvin @ 28.07.22, 23:23

WUT?

Ну например использование вот этого.
При умении прогать на чистом Си - не каждый в этом интуитивно разберется, если будет читать С++ код.

Цитата korvin @ 28.07.22, 23:23

Это никому не интересно,

Хм. Хочется спросить - а что ты в этой теме забыл тогда?

[D_KEY]

Цитата Majestio @ 29.07.22, 05:21

При умении прогать на чистом Си - не каждый в этом интуитивно разберется, если будет читать С++ код.

Ну так это разные языки.

[Majestio]

Цитата D_KEY @ 29.07.22, 09:42

Ну так это разные языки.

Ну таки-да

[korvin]

Цитата Majestio @ 29.07.22, 05:21

Хочется спросить - а что ты в этой теме забыл тогда?

А ты не видишь? Общаюсь с Qraizer'ом. Он-то привёл код. Где твой?

[Majestio]

Цитата korvin @ 29.07.22, 10:32

Он-то привёл код. Где твой?

В этой теме мне интересно другое. А он занялся оффтопиком.
Ну интересно ему это, а мне другое.

[D_KEY]

Цитата Majestio @ 29.07.22, 10:09

Цитата D_KEY @ 29.07.22, 09:42

Ну так это разные языки.

Ну таки-да

Ну тогда странной выглядит отсылка к Си, когда речь о С++.

Добавлено 29.07.22, 12:06

Цитата Majestio @ 29.07.22, 10:56

Цитата korvin @ 29.07.22, 10:32

Он-то привёл код. Где твой?

В этой теме мне интересно другое. А он занялся оффтопиком.
Ну интересно ему это, а мне другое.

Почему оффтоп, если ребята как раз реализовали алгоритм и можно посмотреть на код и поговорить более предметно.

Добавлено 29.07.22, 12:10

Цитата Majestio @ 27.07.22, 08:22

Статическая типизация захламляет "чтение" алгоритма

Ты имеешь в виду явную, а не статическую. Статическая может быть неявной (с выводом типов) и ничего не захламлять.

Цитата

Использовать чисто процедурный подход - остальное усложняет визуализацию

Конкретно для алгоритмов нужно структурное программирование. А его элементы сейчас есть во всех современных подходах. Процедурный тут ни при чем.

Цитата

Использовать подход "композиция-декомпозиция" с помощью вынесения отдельных участков алгоритма в функции или именованные лямбды (где это допустимо)

Цитата

Библиотечные функции алгоритмов использовать допустимо, но с подробными комментами

Спорно. Почему ты так считаешь?

[Qraizer]

Цитата korvin @ 29.07.22, 10:32

Общаюсь с Qraizer'ом. Он-то привёл код.

Чтобы сравнить представленческие возможности разных языков, прозвучало предложение посмотреть на реализацию некоего алгоритма на них, я всего лишь предложил LZW для этого как относительно простой, но и не тривиальный. После поста korvin можно было бы уже ничего и не писать, просто я успел раньше.

[Majestio]

Ну ок, приведу свой код (но только для сжатия) И не по словарю ASCII, а по "ужатому". Относительно того, что присутствует в исходной строке для сжатия.

#!/usr/local/bin/perl
 
$String = "banana_bandana";
 
# начало #########################################################
 
$Str = "";
%Dic = ();
@Wrk = ();
 
# подготавливаем словарь - собираем только уникальные символы из
# входной строки в отсортированном порядке
 
map {$Tmp{$_}=''} split ('',$String);
map {$Dic{$_}=++$Cnt} sort keys %Tmp;
 
# вычисляем минимальное количество бит по словарю
 
$Max = length(sprintf("%b",scalar(keys %Dic)));
 
# читаем посимвольно входную строку, продолжаем заполнять словарь,
# попутно скидывая в рабочий массив части закодированных подстрок
 
foreach $Ch (split '', $String) {
  if (exists $Dic{$Str.$Ch}) {
    $Str .= $Ch;
  } else {
    push @Wrk, $Dic{$Str};
    $Dic{$Str.$Ch} = scalar(keys %Dic) + 1;
    $Str = $Ch;
  }
}
push @Wrk, $Dic{$Str};
 
# из рабочего массива части закодированных строк формируем
# результирующий битовый массив, представленный строкой
 
$Cnt = 0;
$Len = $Max;
 
foreach $i (@Wrk) {
  $Len = $Max + 1 if (++$Cnt > $Max);  
  $Res .= sprintf("%0${Len}b", $i);
}
$Res .= sprintf("%0${Max}b", 0);
 
# печать результата ##############################################
 
print "\n$Res\n";

Вывод:

0110101010111001000010110010101001001000

Проверить раскодирование можно тут (во второй части LZW- распаковка), а в качестве словаря для раскодирования использовать: _abdn

[Majestio]

Цитата D_KEY @ 29.07.22, 12:06

Ну тогда странной выглядит отсылка к Си, когда речь о С++.

Человек, хорошо знающий чистый СИ - вполне может худо-бедно ориентироваться в С++, если в читаемом не используется ООП и метапрограммирование. Я только об этом.

Цитата D_KEY @ 29.07.22, 12:06

Ты имеешь в виду явную, а не статическую. Статическая может быть неявной (с выводом типов) и ничего не захламлять.

Я имел ввиду - лучше автоматическую типизацию, чтобы в явном виде типы в коде не светились.

Цитата D_KEY @ 29.07.22, 12:06

Конкретно для алгоритмов нужно структурное программирование. А его элементы сейчас есть во всех современных подходах. Процедурный тут ни при чем.

Структурное программирование - это здорово. Но если его использовать в связке с ООП - это будет оффтопик, ИМНО.
И второй момент - не всегда структурное прокатывает как того хотелось бы. Я о задачах, которые решаются конечными автоматами.

Цитата D_KEY @ 29.07.22, 12:06

Спорно. Почему ты так считаешь?

Ну если мне нужно использовать какой-нить qsort, или еще какую шляпу - мне и его в представляемом алгоритме "разворачивать"? Не думаю (С)

[D_KEY]

Цитата Majestio @ 29.07.22, 14:50

Человек, хорошо знающий чистый СИ - вполне может худо-бедно ориентироваться в С++

Нет.
Это наоборот еще можно сказать. Что человек, знающий C++, вполне может худо-бедно ориентироваться в Си. И то не совсем. Например, он может не знать о всяких идиомах, принятых в Си.
А вот знание Си точно не обеспечивают знание C++.

Цитата

если в читаемом не используется ООП и метапрограммирование.

Ага, а еще стандартная библиотека, например. И вывод типов. И атрибуты. И "новый" for. И move семантика. И т.д. и т.п.
Относись к C и к C++, как к разным языкам.

Цитата

Я имел ввиду - лучше автоматическую типизацию, чтобы в явном виде типы в коде не светились.

Ну т.е. ты хочешь сказать, что для записи алгоритмов лучше иметь неявную типизацию, чем явную. Это устоявшиеся термины просто.
А статическая и динамическое - это про другое.

Цитата

Ну если мне нужно использовать какой-нить qsort, или еще какую шляпу - мне и его в представляемом алгоритме "разворачивать"? Не думаю (С)

Это говорит человек, который в своей реализации использует split, sort и пр.

Сообщение отредактировано: D_KEY - 29.07.22, 16:04

[Majestio]

Цитата D_KEY @ 29.07.22, 16:02

Это говорит человек, который в своей реализации использует split, sort и пр.

Ну так я и говорю - это можно юзать, но комментировать нужно, если по-хорошему.

[korvin]

Цитата Majestio @ 29.07.22, 14:31

приведу свой код

Слишком много $. На Госдеп работаешь?

[Majestio]

Цитата korvin @ 30.07.22, 01:40

Слишком много $. На Госдеп работаешь?

Не завидуй, что моя программа смотрится по-богатому!

[applegame]

Цитата Majestio @ 30.07.22, 04:43

Цитата korvin @ 30.07.22, 01:40

Слишком много $. На Госдеп работаешь?

Не завидуй, что моя программа смотрится по-богатому!

Еще и % много.
Буржуазией несет за версту.

[korvin]

Цитата Majestio @ 30.07.22, 04:43

моя программа смотрится по-богатому!

Ага. Дорого-богато.

Прикреплённая картинка