На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила раздела:
1. Название темы - краткое описание кто/что против кого/чего
2. В первом сообщении - список параметров, по которым идет сравнение.
3. Старайтесь аргументировать свои высказывания. Фразы типа "Венда/Слюникс - ацтой" считаются флудом.
4. Давайте жить дружно и не доводить обсуждение до маразма и личных оскорблений.
Модераторы: Модераторы, Комодераторы
Страницы: (4) 1 2 [3] 4  все  ( Перейти к последнему сообщению )  
> Язык программирования для представления алгоритмов
      В целом ровно то же. Из недостатков – неограниченный словарь и головная боль из-за отсутствия "фреймворка" по работе с битами. Неограниченный словарь – это плохо. Со временем компрессия сменится расширением. Хранение кодов в виде чисел не прибавляет энтузиазма для пользователей этих примеров. У меня это больше половины реализации, сам LZW короче.

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

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

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

      Добавлено
      А вот слабо ли кому на .cmd сие написать? Там даже bash отсутствует
      Сообщение отредактировано: Qraizer -
        Цитата Qraizer @
        По ссылке входными данными только байты

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

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

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

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

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

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

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

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

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

        Исходник тут
        ExpandedWrap disabled
          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/

        Выхлоп:

        ExpandedWrap disabled
          TEST : encode
          PASS : encode
          TEST : string_to_list
          PASS : string_to_list
          TEST : string_to_list (with overflow)
          PASS : string_to_list (with overflow)
          20 15 27
          20 15 2 5 15 18 14 15 20 27 29 31 36 30 32 34
          20 15 2 5 15 18 14 15 20 27 29 31 36 30 32 34
          TEST : decode
          PASS : decode
          TEST : list_to_string
          PASS : list_to_string
          TEST : string_to_list (with overflow)
          PASS : string_to_list (with overflow)
          TOTO
          TOBEORNOTTOBEORTOBEORNOT
          TOBEORNOTTOBEORTOBEORNOT
          TEST : full
          PASS : full
        Сообщение отредактировано: korvin -
          Цитата korvin @
          Не везде. От языка зависит.
          Я имел в виду конкретно Плюсовую реализацию.
          Цитата korvin @
          Тебе int'а не достаточно?
          В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.
          Цитата korvin @
          Как-как. Тесты пиши. Подставляй себе вместо файлового ввода-вывода строковые/байтовые буферы и сверяй результаты с ожидаемыми.
          Так а толку от тестов, я и так проблему вижу, мне б её причину найти. Ожидаемые... то-то и оно, что их хрен рассчитаешь. Помню веселье, когда Хаффмана писали лет 20 назад. На Паскале.
            Цитата Qraizer @
            Я тут случайно чуть архиватор не написал.
            ...
            В общем, берите это, а то не остановлюсь.
            Хреновый из меня программист. Не смог остановиться. Нате.
            bits.h
            ExpandedWrap disabled
              #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
            ExpandedWrap disabled
              #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
            ExpandedWrap disabled
              #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
            ExpandedWrap disabled
              #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-цатью были лишние символы в конце, что нестрашно, но всё же.
            Сообщение отредактировано: Qraizer -
              Цитата Qraizer @
              В отдельно взятой бздюшечке int может оказаться 16-битным, а то и ещё меньше. LZW, вроде бы, очень хорош как раз для встроенных систем.

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

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

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

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

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

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

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

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

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

              Я на свой код потратил примерно день, из него полдня думал над тем, какой должен быть тип результата encode (тип Change), слишком много вариантов было :lool: Тоже такое себе ))
              Сообщение отредактировано: korvin -
                Фиксанул бажочичечичик. Компрессор падал на пустых файлах. (А я-то думаю, нафига защиту в ioBits.h вписывал, вроде ж не должно быть такого никогда. Ан-нет, бывает.)
                Цитата korvin @
                Можно взять совсем простые, короткие последовательности, сделать на их основе ппоследовательности чуть по-сложнее.
                Ну так-то оно понятно. Вот только с посложнее как раз и сложно. Особенно, когда стал пакетно тестить на разных /bits. Поди пойми, почему на таком файле нормалёк, а на этом упало.
                  Не, камарады, ИМХО вы дорогу не в ту степь выбрали! :lol: Вместо того, чтобы визуализировать как можно нагляднее алгоритм, ты тут письками кодом меряетесь! Я спецом взял тайм-аут для наблюдения. Все смотрел, чего же так не хватает. И сделал определенные выводы конечно ИМХОшные:

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

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

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

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

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

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

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

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

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

                    WUT?

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

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

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

                    Скрытый текст
                    ExpandedWrap disabled
                      let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                       
                      (**
                        LZW encode : string -> int list
                      *)
                      let encode s =
                        let dict = Hashtbl.create (String.length alphabet) in
                        let add_to_dictionary w = Hashtbl.add dict w (Hashtbl.length dict + 1) in
                        let is_in_dictionary = Hashtbl.mem dict in
                        let input = ref "" in
                        let output = ref [] in
                        let emit_index_of w = output := Hashtbl.find dict w :: !output in
                       
                        alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
                       
                        for i = 0 to String.length s - 1 do
                          let c = String.sub s i 1 in
                          let w = !input in
                          let wc = w ^ c in
                          if wc |> is_in_dictionary then
                            input := wc
                          else begin
                            emit_index_of w ;
                            input := c ;
                            add_to_dictionary wc
                          end
                        done ;
                        emit_index_of !input ;
                       
                        List.rev !output
                       
                      (**
                        LZW decode : int list -> string
                      *)
                      let decode codes =
                        match codes with
                        | [] -> ""
                        | first_code :: rest_codes ->
                          let dict = Hashtbl.create (String.length alphabet) in
                          let add_to_dictionary w = Hashtbl.add dict (Hashtbl.length dict + 1) w in
                          let word_for = Hashtbl.find_opt dict in
                          let first_symbol_of s = String.sub s 0 1 in
                       
                          alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
                       
                          let first = (match word_for first_code with Some w -> w | None -> failwith "invalid input") in
                          let output = ref first in
                          let previous = ref first in
                          let emit w = output := !output ^ w ; previous := w in
                       
                          rest_codes |> List.iter (fun code ->
                            match word_for code with
                            | Some w ->
                              let v = !previous ^ first_symbol_of w in
                              add_to_dictionary v ;
                              emit w
                            | None ->
                              let v = !previous ^ first_symbol_of !previous in
                              add_to_dictionary v ;
                              emit v
                          );
                       
                        !output
                       
                      (* ---------------------------------------------------------------- *)
                       
                      let test_phrase = "TOBEORNOTTOBEORTOBEORNOT"
                       
                      let _ =
                        print_endline test_phrase ;
                        let encoded = encode test_phrase in
                        List.iter (Printf.printf "%d ") encoded ; print_endline "" ;
                        let decoded = decode encoded in
                        print_endline decoded
                    Сообщение отредактировано: korvin -
                      Цитата korvin @
                      Ты просто не умеешь её готовить.

                      Болтовня.

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

                      Болтовня.

                      Цитата korvin @
                      WUT?

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

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

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

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

                          Ну таки-да :rolleyes:
                            Цитата Majestio @
                            Хочется спросить - а что ты в этой теме забыл тогда?

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

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

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

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

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

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

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

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

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

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

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

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

                                :good:

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

                                Спорно. Почему ты так считаешь?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (4) 1 2 [3] 4  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0841 ]   [ 15 queries used ]   [ Generated: 3.10.23, 03:34 GMT ]