Легкое сжатие данных (строки)

@blackofe · Регистрация: 30.05.2014

Студворк — интернет-сервис помощи студентам

есть строка. 30 символов. почти все цифры, есть пара латинских букв. нужно втиснуть эту строку в xs:long, т.е., вообще говоря, в строку из цифр длиной 18-19 символов.

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

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

спасибо заранее.

Добавлено через 1 час 7 минут
на этом же форуме нашел пример вычисления чек-суммы CRC16 и расширил его до 64 бит.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned long long CRC16(int Count, char *Ptr)
{
    unsigned long long Data;
    long long CRC = 0xffffffffffffffff;
 
    while(Count) {  
        Data = *Ptr;
        CRC ^= Data;
        for(long long j = 0; j < 8; ++j) {
            if(CRC&1) {
                CRC >>= 1;
                CRC ^= 0xa001;
            } else
                CRC >>= 1;
        }
        ++Ptr;
        --Count;
    }
    return CRC;
}

вроде работает. и думаю я, можно ли использовать эту функцию для моих нужд?

@gazlan · 17.12.2014, 02:36

Так вам сжатие или хэш?

"почти все цифры, есть пара латинских букв" сжимаются в 4 bits per symbol.

CRC64 изобретать не надо, есть готовый.

@blackofe · 17.12.2014, 17:14 **[ТС]**

пожалуй, задача больше на хэш. говоря простым языком, мне нужна функция, которая бы генерировала 64-битное целое число по заданной строке. мне не нужно обратное восстановление (что, по идее, должно предусматривать сжатие), но на одинаковые строки должны генерироваться одинаковые числа.

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

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

по поводу "4 бит" не пойму, чем мне это поможет. я не смогу "ужать" строку, состоящую из цифр, до числа с меньшим количеством цифр.

к примеру, я могу обозначить (возьмем случай более тривиальный, когда входная строка состоит только из цифр) цифру в строке 4-мя битами. это значит, что 64 битами я могу обозначить всего 16 цифр. а мне нужно 30.

@gazlan · 17.12.2014, 18:45

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

достаточно уникальными

Несовместимые понятия.

Если набор строк известен и фиксирован, лучшим решением будет perfect hash. В противном случае, почти любой хэш, подходящего размера (CRC64, половина от MD5 итд.)

64 битами я могу обозначить всего 16 цифр. а мне нужно 30

Для 30 десятичных цифр потребуется 100 бит (30 * Log2(10) = 99.6578).

@blackofe · 18.12.2014, 20:10 **[ТС]**

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

Несовместимые понятия.

ну, почему же?

"уникальный" значит, что такой же не встретится нигде и никогда.

"достаточно уникальный" значит, что такой же может встретиться, но с очень малой вероятностью.

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

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

Если набор строк известен и фиксирован, лучшим решением будет perfect hash. В противном случае, почти любой хэш, подходящего размера (CRC64, половина от MD5 итд.)

остановился на половине MD5.

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

Для 30 десятичных цифр потребуется 100 бит (30 * Log2(10) = 99.6578).

но потом эти 100 бит превращаются в десятичное число длиной в 31 знак (2^100), которое мне все-таки надо поместить в xs:long. т.е. я ничего не выигрываю, а даже проигрываю.

@gazlan · 18.12.2014, 20:41

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

достаточно уникальный

Не по теме:

"Уникальный", как и "тривиальный" - это "булевские переменные"

не гарантируют уникальность

Perfect hash, как уже сказано, гарантирует. Но не знаю, применим ли он для вашей задачи.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	17.12.2014, 02:36
	Так вам сжатие или хэш? "почти все цифры, есть пара латинских букв" сжимаются в 4 bits per symbol. CRC64 изобретать не надо, есть готовый. 0

@blackofe 0 / 0 / 0 Регистрация: 30.05.2014 Сообщений: 32
	17.12.2014, 17:14 [ТС]
	пожалуй, задача больше на хэш. говоря простым языком, мне нужна функция, которая бы генерировала 64-битное целое число по заданной строке. мне не нужно обратное восстановление (что, по идее, должно предусматривать сжатие), но на одинаковые строки должны генерироваться одинаковые числа. числа должны быть достаточно уникальными. т.е. вероятность, что две разные строки дадут одинаковые числа должна быть достаточно мала. я больше склоняюсь к алгоритму типа контрольной суммы. за ссылочку на CRC64 спасибо (я ее видел раньше, но тогда еще не созрел до правильности выбора алгоритма. мне нужна была идея). по поводу "4 бит" не пойму, чем мне это поможет. я не смогу "ужать" строку, состоящую из цифр, до числа с меньшим количеством цифр. к примеру, я могу обозначить (возьмем случай более тривиальный, когда входная строка состоит только из цифр) цифру в строке 4-мя битами. это значит, что 64 битами я могу обозначить всего 16 цифр. а мне нужно 30. 0