Инъективная хеш-функция

[ellipse]

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

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

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

[Tookser]

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

[ellipse]

Сделал следующим образом.

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

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

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

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

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

[aa_dav]

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

-- 22.03.2015, 10:31 --

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

[arseniiv]

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

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

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

[aa_dav]

aa_dav в сообщении #993923 писал(а):

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

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