ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать алгоритм (см. внутри)
14 сообщений из 14, страница 1 из 1
Придумать алгоритм (см. внутри)
    #37628080
Бузелбас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бузелбас
Участник
есть 5 мрд. строк, минимальная и максимальная длина которых 10-200 символов

нужно разработать алгоритм сжатия/зашифровки этих строк до минимального набора символов

с последующей возможностью его дешифрования

длина набора символов равна 8

для зашифровки используются символы латинского алфавита (26) в нижнем регистре, а также цифры от 0 до 9 (10)

зашифрованная строка может содержать данные параметры в любой возможней комбинации

например:
строка _________шифр

Привет, мир! ___a0x72cqp

(26 + 10) 8 =~ 2.8 * 10 12

что дает нам 2 трлн. возможных комбинаций

как быть, куда копать?
...
Рейтинг: 0 / 0
24.01.2012, 00:23
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628236
Фотография FishHook
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
FishHook
Участник
Бузелбасесть 5 мрд. строк, минимальная и максимальная длина которых 10-200 символов

нужно разработать алгоритм сжатия/зашифровки этих строк до минимального набора символов

с последующей возможностью его дешифрования

длина набора символов равна 8

для зашифровки используются символы латинского алфавита (26) в нижнем регистре, а также цифры от 0 до 9 (10)

зашифрованная строка может содержать данные параметры в любой возможней комбинации

например:
строка _________шифр

Привет, мир! ___a0x72cqp

(26 + 10) 8 =~ 2.8 * 10 12

что дает нам 2 трлн. возможных комбинаций

как быть, куда копать?
Есть такое решение
...
Рейтинг: 0 / 0
24.01.2012, 06:42
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628730
Бузелбас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бузелбас
Участник
FishHook,
зашифрованные строки нужно будет хранить в БД

и в виде чего хранить эти строки, в виде zip файлов?

можно поподробней пожалуйста

возможно надо что-нибудь на подобии хеша, и главное с возможностью быстрой расшифровки
...
Рейтинг: 0 / 0
24.01.2012, 13:37
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628777
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Бузелбаскак быть, куда копать?
Ты каким-то чудесным образом смешал в кучу архивирование и криптографию.
Ты уж определись что тебе нужно. Скрытность информации или экономия
пространства. Это две разные постановкии.
...
Рейтинг: 0 / 0
24.01.2012, 13:54
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628794
Бузелбас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бузелбас
Участник
mayton,

экономия
...
Рейтинг: 0 / 0
24.01.2012, 14:01
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628797
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну если из 5 млрд. строк. есть повторяющиеся то можно завести в БД справочник а в
основной таблице - хранить ссылки на него. Вот тебе и будет естественная
реляционная экономия.
...
Рейтинг: 0 / 0
24.01.2012, 14:03
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628853
rfq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rfq
Участник
Бузелбас,

Во первых, надо уяснить, что сжатие не всегда возможно. Например, если исходные строки сгенерированы хорошим генератором (псевдо)случайных чисел, сжатие невозможно. Поэтому заранее задаваться размером шифра 8 символов нельзя.

Сжатие возможно, например, если есть повторяющиеся подстроки. Проверить это элементарно - просто зазиповать файл и посмотреть, сократился ли его объем. Если не сократился, то еще не все потеряно, но прежде чем советовать дальше, мне надо знать, откуда эти строки берутся. Если сократился, то использовать какую-либо модификацию LZW , наиболее подходящую для вашего набора данных.
...
Рейтинг: 0 / 0
24.01.2012, 14:26
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37628873
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
rfq, да нет у него никакого файла. Я вот только что эксперимент провел.
Строку "привед мир!" заархивировал с опциями gzip -n. Получил 30 байт
архив.

Поэтому раздельно архивировать каждую строку таблицы с маленькой длиной
- бесполезно. Нужна какая-то кластеризация или группировка строк.
А в группированных архивах трудно/накладно/технически осуществлять
быстрый поиск других строк.

Или ему нужно искать архиваторы оптимизированные на работу со справочником.

И еще - толерантные к возможным INSERTS/UPDATES если таковые будут.
Иначе вместо экономии получим прирост объёма.
...
Рейтинг: 0 / 0
24.01.2012, 14:33
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629162
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
Бузелбас,

набор символов произвольный или ограничен русским алфавитом и знаками припенания?
...
Рейтинг: 0 / 0
24.01.2012, 16:00
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629452
Бузелбас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бузелбас
Участник
eNose,

url'ы

по моим подсчетам база в 5 млрд. чисто из урлов будет где-то 250Гб
...
Рейтинг: 0 / 0
24.01.2012, 17:48
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629468
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно посмотреть в сторону префиксных кодов . И деревьев остатков .
Правда насчёт имплементаций пока ничего не скажу. Надо искать.
...
Рейтинг: 0 / 0
24.01.2012, 17:54
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629571
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Бузелбас,

и что ты с ними делать собираешься?
...
Рейтинг: 0 / 0
24.01.2012, 18:34
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629593
Бузелбас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бузелбас
Участник
Aleksandr SharahovБузелбас,

и что ты с ними делать собираешься?

поисковую машину собираем
...
Рейтинг: 0 / 0
24.01.2012, 18:46
| Ответить | Цитировать | Написать  
Придумать алгоритм (см. внутри)
    #37629641
Фотография Ренат
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ренат
Участник
Бузелбас,

это вам древовидную структуру таблицы нужно
И к примеру слова начинающиеся с буквы "а" искать в одном сервере. С "б" в втором итд
Вторая буква можно судить о базе.
О третей по таблице.
Если у вас слвоа состоят только из букв, то получим что в каждой таблице
И в каждой табличке по сотне слов останеться.
Правда есть уже готовые решению, в оракл к примеру.
Вот и получаться небольшие таблички у вас.
...
Рейтинг: 0 / 0
24.01.2012, 19:08
| Ответить | Цитировать | Написать  
14 сообщений из 14, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать алгоритм (см. внутри)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=37628797&tid=1342492]:
 0ms
get settings:
 5ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 54ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 33ms
get tp. blocked users:
 1ms
others: 198ms
total:  312ms
созд. / загр.: 312ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]