Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Holy Wars > Язык программирования для представления алгоритмов


Автор: Majestio 09.07.22, 12:01
Буэнос диас, амигос!

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

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

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

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

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

Автор: korvin 09.07.22, 18:17
Ocaml и Scheme

Автор: Majestio 09.07.22, 18:42
Цитата Majestio @
Ocaml и Scheme

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

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

Автор: korvin 10.07.22, 09:33
Цитата Majestio @
функциональщина


<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    (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)

=>
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    Hello, World!


Definitions

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    (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

...

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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

=>
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    Hello, World!

https://rextester.com/QBYY22062

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

Автор: korvin 10.07.22, 13:12
Цитата Majestio @
Нет, я такое не хочу видеть!

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

Автор: Qraizer 10.07.22, 19:21
Оспади.
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    [](const auto& msg){ std::cout << msg <<std::endl;}("Hello, world!");
Один вопрос: на...хрена

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

Автор: OpenGL 11.07.22, 05:29
Befunge, конечно же!

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

Автор: D_KEY 11.07.22, 05:43
korvin, а где у тебя там алгоритмы? :)

Автор: korvin 11.07.22, 06:07
Цитата D_KEY @
а где у тебя там алгоритмы?

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

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

Автор: applegame 11.07.22, 10:02
Писать программы сразу в виде AST - такое себе.

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

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

Автор: korvin 11.07.22, 11:49
Цитата applegame @
Писать программы сразу в виде AST - такое себе.

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

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

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

Автор: D_KEY 11.07.22, 12:21
Цитата korvin @
Есть же всякие сайты с разными алгоритмами и их реализациями на разных языках. Смотри — сравнивай.

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

Автор: Qraizer 11.07.22, 12:56
LZW. Дёшево и в меру сердито.

Автор: Qraizer 12.07.22, 12:43
Ну и? Мне начинать, что ли?

Автор: Majestio 12.07.22, 14:27
Цитата Qraizer @
Ну и? Мне начинать, что ли?

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

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

Автор: korvin 12.07.22, 17:48
Цитата Qraizer @
Ну и? Мне начинать, что ли?

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

Автор: Majestio 12.07.22, 18:24
Цитата korvin @
Так что я не знаю, что тут можно сравнивать.

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

Автор: korvin 12.07.22, 18:25
Цитата Majestio @
Ты просто Бейсика не видел, или Пасквиля

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

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

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

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


Цитата korvin @
С чего ты это взял?

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

Добавлено
Цитата Qraizer @
Ну и? Мне начинать, что ли?

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

Автор: applegame 13.07.22, 05:32
Цитата korvin @
Ага. Хорошо, что этого никто не предлагает.

Цитата korvin @
Scheme

Автор: Majestio 13.07.22, 06:27
Цитата applegame @
Scheme

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

Автор: Gonarh 13.07.22, 08:11
Цитата Majestio @
Perl и чистый Си

:wub:

Автор: korvin 14.07.22, 04:44
applegame, Scheme не AST.

Автор: Qraizer 19.07.22, 03:13
Цитата korvin @
Мне лично не очень интересны байто-бито-дрочерские вещи, и судя по описанию в вике, какой-то заметной разницы между языками тут не будет. Как и во многих алгоритмах. Во всяком случае, навскидку, я не вижу здесь точки отличий. Так что я не знаю, что тут можно сравнивать.
Ну не я ж топик начал-то. Так-то и мне непонятно, чем таким кардинальным могут отличаться реализации одного алгоритма на разных языках, окромя внешнего вида. Кардинально может отличаться архитектура реализации, т.к. зависит от парадигм языка... и то не факт. А так-то, пиши, на чём тебе будет читать удобно.
Я тут случайно чуть архиватор не написал. Начал вот с такого:
кодер
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    /* 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();                            // сбросить битовый буфер в поток вывода
    }
и потихонечку дописал к нему ( :jokingly: )
фреймворк
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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]);                // равном текущей ширине
    }
Быстро, за вечер где-то. Или два, не помню. Но вот с декодером вышло далеко не так шоколадно. Поди отладься, когда непонятно, а кто, собстна, бажит. Понятно, что скорее всего оба, но... отлаживаться-то как?
В общем на вот это безобразие
декодер
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    /* 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;                                // новый код на следующем шаге становится предыдущим
      }
    }
с собственным фреймворком ( :lol: )
он самый
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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;
    }
я чуть не забил. Зато когда-таки отладился, такие планы наполеоновские попёрли... включая параметризирование битовых границ словаря.
В общем, берите это, а то не остановлюсь. Вам будет проще, алгоритм надо будет просто перевести, а не реализовывать.

Автор: korvin 19.07.22, 06:52
Цитата Qraizer @
и потихонечку дописал к нему фреймворк

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

Автор: Majestio 19.07.22, 07:10

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

Автор: korvin 19.07.22, 07:28
https://rosettacode.org/wiki/LZW_compression

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

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

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

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

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

Автор: korvin 24.07.22, 21:34
Цитата Qraizer @
По ссылке входными данными только байты

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

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

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

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

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

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

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

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

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

Исходник тут
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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/

Выхлоп:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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

Автор: Qraizer 26.07.22, 18:15
Цитата korvin @
Не везде. От языка зависит.
Я имел в виду конкретно Плюсовую реализацию.
Цитата korvin @
Тебе int'а не достаточно?
В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.
Цитата korvin @
Как-как. Тесты пиши. Подставляй себе вместо файлового ввода-вывода строковые/байтовые буферы и сверяй результаты с ожидаемыми.
Так а толку от тестов, я и так проблему вижу, мне б её причину найти. Ожидаемые... то-то и оно, что их хрен рассчитаешь. Помню веселье, когда Хаффмана писали лет 20 назад. На Паскале.

Автор: Qraizer 26.07.22, 18:32
Цитата Qraizer @
Я тут случайно чуть архиватор не написал.
...
В общем, берите это, а то не остановлюсь.
Хреновый из меня программист. Не смог остановиться. Нате.
bits.h
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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, например. А то мало ли, вдруг у кого-то терабайт оперативы.

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

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

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

Автор: korvin 26.07.22, 18:43
Цитата Qraizer @
В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.

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

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

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

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

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

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

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

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

Добавлено
Цитата Qraizer @
Хреновый из меня программист. Не смог остановиться.

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

Автор: Qraizer 26.07.22, 19:11
Фиксанул бажочичечичик. Компрессор падал на пустых файлах. (А я-то думаю, нафига защиту в ioBits.h вписывал, вроде ж не должно быть такого никогда. Ан-нет, бывает.)
Цитата korvin @
Можно взять совсем простые, короткие последовательности, сделать на их основе ппоследовательности чуть по-сложнее.
Ну так-то оно понятно. Вот только с посложнее как раз и сложно. Особенно, когда стал пакетно тестить на разных /bits. Поди пойми, почему на таком файле нормалёк, а на этом упало.

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

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

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

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

Автор: korvin 28.07.22, 23:23
Цитата Majestio @
1) Perl - идеален

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

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

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

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

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

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

WUT?

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

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

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

Скрытый текст
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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

Автор: Majestio 29.07.22, 05:21
Цитата korvin @
Ты просто не умеешь её готовить.

Болтовня.

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

Болтовня.

Цитата korvin @
WUT?

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

Цитата korvin @
Это никому не интересно,

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

Автор: D_KEY 29.07.22, 09:42
Цитата Majestio @
При умении прогать на чистом Си - не каждый в этом интуитивно разберется, если будет читать С++ код.

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

Автор: Majestio 29.07.22, 10:09
Цитата D_KEY @
Ну так это разные языки.

Ну таки-да :rolleyes:

Автор: korvin 29.07.22, 10:32
Цитата Majestio @
Хочется спросить - а что ты в этой теме забыл тогда?

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

Автор: Majestio 29.07.22, 10:56
Цитата korvin @
Он-то привёл код. Где твой?

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

Автор: D_KEY 29.07.22, 12:06
Цитата Majestio @
Цитата D_KEY @
Ну так это разные языки.

Ну таки-да :rolleyes:

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

Добавлено
Цитата Majestio @
Цитата korvin @
Он-то привёл код. Где твой?

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

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

Добавлено
Цитата Majestio @
Статическая типизация захламляет "чтение" алгоритма

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

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

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

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

:good:

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

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

Автор: Qraizer 29.07.22, 12:16
Цитата korvin @
Общаюсь с Qraizer'ом. Он-то привёл код.
Чтобы сравнить представленческие возможности разных языков, прозвучало предложение посмотреть на реализацию некоего алгоритма на них, я всего лишь предложил LZW для этого как относительно простой, но и не тривиальный. После поста korvin можно было бы уже ничего и не писать, просто я успел раньше.

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

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #!/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";

Вывод:
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    0110101010111001000010110010101001001000


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

Автор: Majestio 29.07.22, 14:50
Цитата D_KEY @
Ну тогда странной выглядит отсылка к Си, когда речь о С++.

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

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

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

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

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

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

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

Автор: D_KEY 29.07.22, 16:02
Цитата Majestio @
Человек, хорошо знающий чистый СИ - вполне может худо-бедно ориентироваться в С++

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

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

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

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

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

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

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

Автор: Majestio 29.07.22, 16:31
Цитата D_KEY @
Это говорит человек, который в своей реализации использует split, sort и пр.

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

Автор: korvin 30.07.22, 01:40
Цитата Majestio @
приведу свой код

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

Автор: Majestio 30.07.22, 04:43
Цитата korvin @
Слишком много $. На Госдеп работаешь?

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

Автор: applegame 04.08.22, 09:38
Цитата Majestio @
Цитата korvin @
Слишком много $. На Госдеп работаешь?

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

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

Автор: korvin 04.08.22, 11:40
Цитата Majestio @
моя программа смотрится по-богатому!

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

Perl.jpg (, : 83)

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)