| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.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 10.07.22, 02:13 |
| И, если честно, функциональщина - она не для всех, возможно для избранных. Себя я в это число не могу причислить. |
| Автор: korvin 10.07.22, 09:33 |
| <{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 |
| Оно и понятно. |
| Автор: 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 |
| А ты почитай на что я отвечал. |
| Автор: 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 |
| Ага. Хорошо, что этого никто не предлагает. Цитата 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 |
| Было бы неплохо  Добавлено Хотелось бы сравнить с Петоном  Тьфу на него ))) |
| Автор: korvin 12.07.22, 17:48 |
| Конечно! Инициатива |
| Автор: Majestio 12.07.22, 18:24 |
| Ты просто Бейсика не видел, или Пасквиля ... с их излишествами в синтаксисе. А лутше ознакомься с синтаксисом PL/1. Просто чтобы ознакомится с глубинами ихних глубин. |
| Автор: korvin 12.07.22, 18:25 |
| С чего ты это взял? Бессмысленно. |
| Автор: Majestio 12.07.22, 18:33 |
| Скрытый текст Не, про Пасквиля я мало чего могу сказать плохого - хорошо продуманный язык. Если не брать учебу, а именно практическое программирование, я с него начинал. Вспоминания только хорошие. Особенно впечатляла скорость сборки. Речь идет о Turbo Pascal 5.0/5.5 и какого-то установленного сбоку Microsoft C (версии не помню). Все это было на нативном компе IBM 8086 с 512Kb оперативной памяти... Но потом слишком "многосимвольный" синтаксис задостал. И пришлось уходить на Perl, параллельно на Си. А вот про PL/1 скажу только плохое - пришлось его выучить только для того, чтобы в институте получить "отлично" по прикладному программированию. Перфокарты, шоколадки операторшам, ацкий ад. Вообще-то это сарказм был  Добавлено Кстати ... есть тема. Я как-то в "Алгоритмах" предлагал интересный линк. Зацени тему! Если тебя это зацепит, и ты сможешь это отразить изящно-алоритмически, твой опыт будет просто бесценен!!! Я серьёзно, без стеба! |
| Автор: applegame 13.07.22, 05:32 |
| |
| Автор: Majestio 13.07.22, 06:27 |
| Тот же Брэйнфак, но только с помощью скобочек. |
| Автор: Gonarh 13.07.22, 08:11 |
 |
| Автор: 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(); // сбросить битовый буфер в поток вывода }  )фреймворк <{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; // новый код на следующем шаге становится предыдущим } }  )он самый <{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 |
| https://habr.com/ru/post/153225/ |
| Автор: Majestio 19.07.22, 07:10 |
 Как же долго я это безуспешно искал! Эту тему я когда-то видел в виде видосика. Всегда ее вспоминаю, когда заходит речь о шаблонах проектирования. |
| Автор: 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 |
| Не везде. От языка зависит. Тебе int'а не достаточно? Сам же хотел ограниченный словарь. Зачем же больше 2-х миллиардов последовательностей/кодов в нём хранить? ) Дык алгоритм-то один, детали реализаций чуть разные. Цитата 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 |
| Я имел в виду конкретно Плюсовую реализацию.В отдельно взятой бздюшечке 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()); // и докопируем, остальные биты потока игнорируем } 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? ) Впрочем, мысль понял, я сначала предположил, что ты вообще про те примеры, а не только про плюсовый. Ну так тесты и помогают найти проблему. Только нужна большая декомпозиция, даже если полная реализация и так невелика. Ну почему же? Можно взять совсем простые, короткие последовательности, сделать на их основе ппоследовательности чуть по-сложнее. Взять пример с вики. Результаты без сброса словаря можно нагенерировать с использованием точно рабочих версий с того сайта, например. Тут-то алгоритм известный, корректные реализации существуют. Было бы что-то более специфичное, было бы чуть сложнее, да. Помогает ограничение области определения и области значений функции с помошью типизации насколько возможно, чтобы просто сложно было в принципе передать некорректные данные и получить некорректные результаты. Можно было бы просто использовать stdin/stdout и не париться с именами файлов в программе, как по мне. Добавлено Я на свой код потратил примерно день, из него полдня думал над тем, какой должен быть тип результата encode (тип Change), слишком много вариантов было Тоже такое себе )) |
| Автор: Qraizer 26.07.22, 19:11 |
| Фиксанул бажочичечичик. Компрессор падал на пустых файлах. (А я-то думаю, нафига защиту в ioBits.h вписывал, вроде ж не должно быть такого никогда. Ан-нет, бывает.) Цитата korvin @ Ну так-то оно понятно. Вот только с посложнее как раз и сложно. Особенно, когда стал пакетно тестить на разных /bits. Поди пойми, почему на таком файле нормалёк, а на этом упало. Можно взять совсем простые, короткие последовательности, сделать на их основе ппоследовательности чуть по-сложнее. |
| Автор: Majestio 27.07.22, 08:22 |
| Не, камарады, ИМХО вы дорогу не в ту степь выбрали! Вместо того, чтобы визуализировать как можно нагляднее алгоритм, ты тут Мой рейтинг языков: 1) Perl - идеален 2) С - так себе, С++ (векторы, ассоциативные массивы и больше ничего) - оч хорош 3) Пасквиль - избыточен, слишком многобукф 4) OCaml - хрен его поймешь в написании от korvin, но, судя по вики, п.1-3 в нем можно исполнить 5) JavaSctipt (не TypeScript) - похоже тоже неплох 6) Forth - ьтазакс от-отч ьсюяндуртаз месвос акоп я тут |
| Автор: korvin 28.07.22, 23:23 |
| Как кто-то где-то когда-то сказал, "Перл гениален в своей ублюдочности". Цитата Majestio @ Статическая типизация захламляет "чтение" алгоритма (для собственного кодирования - нет преград патриотам) Ты просто не умеешь её готовить. Просто ты ни с чем больше не знаком. Цитата Majestio @ Библиотечные функции алгоритмов использовать допустимо, но с подробными комментами WUT? Это никому не интересно, он в википедии описан наглядно. 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 |
| Болтовня. Болтовня. Ну например использование вот этого. При умении прогать на чистом Си - не каждый в этом интуитивно разберется, если будет читать С++ код. Хм. Хочется спросить - а что ты в этой теме забыл тогда? |
| Автор: D_KEY 29.07.22, 09:42 |
| Цитата Majestio @ При умении прогать на чистом Си - не каждый в этом интуитивно разберется, если будет читать С++ код. Ну так это разные языки. |
| Автор: Majestio 29.07.22, 10:09 |
| Ну таки-да |
| Автор: korvin 29.07.22, 10:32 |
| А ты не видишь? Общаюсь с Qraizer'ом. Он-то привёл код. Где твой? |
| Автор: Majestio 29.07.22, 10:56 |
| В этой теме мне интересно другое. А он занялся оффтопиком. Ну интересно ему это, а мне другое. |
| Автор: D_KEY 29.07.22, 12:06 |
| Ну тогда странной выглядит отсылка к Си, когда речь о С++. Добавлено Цитата Majestio @ В этой теме мне интересно другое. А он занялся оффтопиком. Ну интересно ему это, а мне другое. Почему оффтоп, если ребята как раз реализовали алгоритм и можно посмотреть на код и поговорить более предметно. Добавлено Ты имеешь в виду явную, а не статическую. Статическая может быть неявной (с выводом типов) и ничего не захламлять. Цитата Использовать чисто процедурный подход - остальное усложняет визуализацию Конкретно для алгоритмов нужно структурное программирование. А его элементы сейчас есть во всех современных подходах. Процедурный тут ни при чем. Цитата Использовать подход "композиция-декомпозиция" с помощью вынесения отдельных участков алгоритма в функции или именованные лямбды (где это допустимо)  Цитата Библиотечные функции алгоритмов использовать допустимо, но с подробными комментами Спорно. Почему ты так считаешь? |
| Автор: Qraizer 29.07.22, 12:16 |
| Чтобы сравнить представленческие возможности разных языков, прозвучало предложение посмотреть на реализацию некоего алгоритма на них, я всего лишь предложил 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 @ Конкретно для алгоритмов нужно структурное программирование. А его элементы сейчас есть во всех современных подходах. Процедурный тут ни при чем. Структурное программирование - это здорово. Но если его использовать в связке с ООП - это будет оффтопик, ИМНО. И второй момент - не всегда структурное прокатывает как того хотелось бы. Я о задачах, которые решаются конечными автоматами. Ну если мне нужно использовать какой-нить qsort, или еще какую шляпу - мне и его в представляемом алгоритме "разворачивать"? Не думаю (С) |
| Автор: D_KEY 29.07.22, 16:02 |
| Нет. Это наоборот еще можно сказать. Что человек, знающий C++, вполне может худо-бедно ориентироваться в Си. И то не совсем. Например, он может не знать о всяких идиомах, принятых в Си. А вот знание Си точно не обеспечивают знание C++. Цитата если в читаемом не используется ООП и метапрограммирование. Ага, а еще стандартная библиотека, например. И вывод типов. И атрибуты. И "новый" for. И move семантика. И т.д. и т.п. Относись к C и к C++, как к разным языкам. Цитата Я имел ввиду - лучше автоматическую типизацию, чтобы в явном виде типы в коде не светились. Ну т.е. ты хочешь сказать, что для записи алгоритмов лучше иметь неявную типизацию, чем явную. Это устоявшиеся термины просто. А статическая и динамическое - это про другое. Цитата Ну если мне нужно использовать какой-нить qsort, или еще какую шляпу - мне и его в представляемом алгоритме "разворачивать"? Не думаю (С) Это говорит человек, который в своей реализации использует split, sort и пр.  |
| Автор: Majestio 29.07.22, 16:31 |
| Ну так я и говорю - это можно юзать, но комментировать нужно, если по-хорошему. |
| Автор: korvin 30.07.22, 01:40 |
| Слишком много $. На Госдеп работаешь? |
| Автор: Majestio 30.07.22, 04:43 |
| Не завидуй, что моя программа смотрится по-богатому! |
| Автор: applegame 04.08.22, 09:38 |
| Еще и % много. Буржуазией несет за версту. |
| Автор: korvin 04.08.22, 11:40 |
| Ага. Дорого-богато.  Perl.jpg (, : 56)
|