2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Инъективная хеш-функция
Сообщение21.03.2015, 01:09 


25/11/08
449
В общем, нужно сделать кеширование картинок, сгенерированных по строкам в формате TeX. Есть ли какие-то функции, которые бы по входной строке вычисляли нечто, пригодное для имени файла. Желательно, конечно, функцию инъективную, без коллизий.

Понятно, что для входных строк неограниченной длины такой функции нет. Но можно сделать ограничение на длину входной строки.

Пока придумал только бинарный побайтовый перевод входной строки в N-ричную систему счисления, где N-кол-во букв в английском алфавите. Может есть какие-то стандартные и более экономные решения?

 Профиль  
                  
 
 Re: Инъективная хеш-функция
Сообщение21.03.2015, 03:34 


30/08/10
158
Экономные — в плане длины результата?
Какую-то такую проблему решает идеальное хеширование, но здесь может не подойти (а может подойти, это зависит от того, можем ли мы хранить единую для всех хеширователей хеш таблицу, подробности [url]http://neerc.ifmo.ru/wiki/index.php?title=Идеальное_хеширование[/url] здесь). Но это не совсем функция будет. Вернее, это не будет давать один и тот же результат на разных серверах, после разных входов.
Более удобное решение — заменять лишь некоторые символа исходного tex текста, вроде спецсимволов, а остальное оставлять как было.
Чем не нравится sha-1 и тому подобные алгоритмы? Можно добавить простую соль и использовать несколько хеш-функций сразу (будет хеш md5, после хеш sha1, потом какой-нибудь свой хеш, crc можно добавить и т.д.), и вероятность коллизии будет очень-очень мала.

 Профиль  
                  
 
 Re: Инъективная хеш-функция
Сообщение22.03.2015, 02:11 


25/11/08
449
Сделал следующим образом.

Картинки сохраняю под названием md5 от входной строки.

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

Для этого при сохранении в кеше вместе с картинкой создается одноименный текстовый файл, в котором хранится входная-строка.

Если сохраненная в текстовом файле строка совпадает с запрошенной, то выдается соответствующий сохраненный файл с картинкой, если нет, то переходим к ситуации, когда в кеше ничего не найдено, то есть заново генерируется картинка и кешированные данные перезаписываются.

С таким кешированием работает заметно быстрее.

 Профиль  
                  
 
 Re: Инъективная хеш-функция
Сообщение22.03.2015, 09:25 


11/12/14
893
Если вылезет что рехеш в каких то случаях случается слишком часто можно создавать не файл сразу, а папку с хешированным именем в которой есть предопределенный файл в котором хранится таблица какой оригинальной строке какой внутренний файл (просто инкрементирующееся число например) соответствует, раз уж в подобный файл всё равно всегда лазить приходится.

-- 22.03.2015, 10:31 --

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

 Профиль  
                  
 
 Re: Инъективная хеш-функция
Сообщение22.03.2015, 14:30 
Заслуженный участник


27/04/09
28128
Да спросите уже у cepesh, как он здесь всё устроил. Не вижу причин, по которым не поделится.

-- Вс мар 22, 2015 16:34:44 --

Ведь, насколько понимаю, цель эксперимента только в том, чтобы научиться выдавать вместе с картинкой значение её базовой линии — а как устраивать кэш и устраивать ли вообще, какая разница. Или нет?

 Профиль  
                  
 
 Re: Инъективная хеш-функция
Сообщение22.03.2015, 15:27 


11/12/14
893
aa_dav в сообщении #993923 писал(а):
И еще в вашем решении похоже возможна ситуация, когда клиенту будет отдано сперва имя одной картинки, и тут же после параллельного рехеша окажется что под этим именем скрывается уже другой файл - а это уже сбой системы.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group