Простое сжатие текста

[Kronos913]

Какие есть простые алгоритмы сжатия текста?

Лично мне на ум пришло только вот что:
Символы от #1 до #31 почти не используются в текстах, а #13 и #10 всегда стоят в паре
И на все не используемые символы назначить популярные сочетания 2-3 букв, или сразу слова

Есть ли какие-то еще простые алгоритмы? Так чтобы дешифратор занимал не более 1 экрана кода, может 2 максимум?

И сразу вопрос, есть ли какой-то более адекватный способ посимвольного заполнения строки, чем
s:=s+c где s - string а c - добавляемый char

[Vapaamies]

Сообщение от Kronos913

Какие есть простые алгоритмы сжатия текста?

А вам зачем? Мы покупаем или продаем? В общем случае внутрипрограммное сжатие — не та тема, которой нужно заниматься. Если же очень хочется нужно, все допустимые случаи проходят как особые и на 99,9% ограничиваются лишь собственным форматом данных — файла или потока, само же сжатие и распаковка выполняются вызовом готовых реализаций/библиотек. Пример — Git.

Сообщение от Kronos913

Символы от #1 до #31 почти не используются в текстах

На этом принципе (в числе прочих) основан алгоритм BOCU. Он запатентован IBM, и для использования нужно заключать с ними соглашение. Иначе суд, тюрьма...

Сообщение от Kronos913

Есть ли какие-то еще простые алгоритмы? Так чтобы дешифратор занимал не более 1 экрана кода, может 2 максимум?

Таких нет, наверное. Просто брать что-то классическое на Паскале — даже на нашем форуме находится:

Сообщение от evg_m

Хаффман на pascal c описанием алгоритма.

Если постараться, можно выковырять оттуда упаковщик и распаковщик. Вопрос только, как хранить словарь? На коротких строках присобачивание словаря к каждой сведет на нет выигрыш от сжатия, а если общий для всех словарь хранить отдельно — вопрос уже в организации формата данных (см. выше про Git).

Сообщение от Kronos913

И сразу вопрос, есть ли какой-то более адекватный способ посимвольного заполнения строки, чем
s:=s+c где s - string а c - добавляемый char

Выделить сразу длинный буфер через SetLength, а потом вписывать по символу через индекс или по скользящему адресу? В некоторых языках есть класс типа StringBuilder, предназначенный как раз для этого. В своей библиотеке для Delphi я делал нечто похожее, но ее код сильно завязан на другие классы, просто так его не вытащишь и тут не выложишь.

[NetSpace]

кто-то хочет написать свой WinRar?
я бы для начала просто пранализировал большинство текстов (художественные или научные), нашёл бы в них наиболее часто встречающиеся последовательности букв (2-3 буквы), и уж потом думал бы, чем их заменить....
те же любимые приставки -тся и -ться из глаголов точно можно чем-то заменить.

[Vapaamies]

Сообщение от NetSpace

я бы для начала просто пранализировал большинство текстов (художественные или научные), нашёл бы в них наиболее часто встречающиеся последовательности букв (2-3 буквы), и уж потом думал бы, чем их заменить....

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

[Arigato]

Сообщение от Vapaamies

создать единый словарь сжатия на все случаи жизни

Ну если затачивать алгоритм именно для текста, причем на конкретном языке, то можно выделить часто встречаемые сочетания букв. Например, беглый взгляд на ваш комментарий позволил выявить сочетание "ото", которое встречается 3 раза, "ст" - 4 раза. Проанализировав достаточно большой объем текста, можно получить пригодный к использованию в большинстве случаев словарь.

Правда кодов до 31 маловато будет для более-менее заметного результата. Тут надо смотреть в сторону оптимального кодирования и менять кодировку целиком в соответствии с частотами.

[Kronos913]

Пока что я сделал такую процедуру для дешифровки
Ну и отдельным вспомогательным кодом проанализировал, какие 30 пар символов встречаются чаще всего в тексте (13й зарезервирован под #13#10)

type
  ppChar=^PChar;
  char061= array [0..61] of char;
  p_char061= ^char061;

Procedure AddText31(var s:string; p:ppchar; codes31:p_char061);
var
  i, j, k, x:integer;
  b:byte;
begin
  j:=Length(p^);
  x:=Length(s);

  {Определяем новую длину строки}
  k:=j;
  For i:=0 to j-1 do begin
    if (p^[i]<#32) and (p^[i]>#0) then inc(k);
  end;
  SetLength(s, x+k);

  {Начинаем распаковку}
  k:=x+1;
  For i:=0 to j-1 do begin
    if (p^[i]<#32) and (p^[i]>#0) then begin
      b:=byte(p^[i])+byte(p^[i])-2;
      s[k]:=codes31[b];
      inc(k);
      s[k]:=codes31[b+1]
    end else begin
      s[k]:=p^[i];
    end;
    inc(k);
  end;
end;

[Vapaamies]

Ёлы-палы, а мы тут развели! Как всё просто, оказывается!

Похоже на то, как делают для хранения ресурсов в некоторых играх. Могу ошибаться, конечно, ибо на практике с переводом игр сталкиваться не приходилось. Точнее, один раз приходилось, но не в таком формате. Аж самому теперь смешно.

Что однозначно могу сказать: не BOCU, в тюрьму не посодють.

[Arigato]

Сообщение от Kronos913

ppChar=^PChar;

В чем тут тайный смысл?

[Kronos913]

Сообщение от Arigato

В чем тут тайный смысл?

Чтобы передать по ссылке, без дублирования

Сообщение от Vapaamies

Ёлы-палы, а мы тут развели! Как всё просто, оказывается!

Похоже на то, как делают для хранения ресурсов в некоторых играх. Могу ошибаться, конечно, ибо на практике с переводом игр сталкиваться не приходилось. Точнее, один раз приходилось, но не в таком формате. Аж самому теперь смешно.

Что однозначно могу сказать: не BOCU, в тюрьму не посодють.

Я имел в виду что может есть что-то лучше?

Потому что вообще желательно как-то сделать так, чтобы итоговое сжатие не вышло меньше места, которое будет потрачено на архиватор=))

[Kronos913]

Я еще так заметил, что символы 126-167 практически не встречаются в текстах
Во всяком случае в том что у меня - так точно

И я вот думаю над тем чтобы кодировать целые слова