Как создать хэш из строки типа md5 с минимальным набором символов a-zA-Z (без цифр) и с минимальными коллизиями?

Question

[Dubrovin]

Есть некая строка, нужно создать хэш строки с минимальным набором символов и коллизий. В хэше не должно быть цифр, спец. символов и т.п., только буквы a-zA-Z.

Comments

[SagePtr]

Никак, в md5 вероятность коллизий довольно высокая и без них не обойтись

[Dubrovin]

SagePtr, вероятность коллизии md5 меня вполне устроит. Задача получить из строки хеш md5 но только в заданном алфавите a-zA-Z

[Adamos]

Так в MD5 и нет "цифр и спецсимволов". Хэш - это набор битов. Просто обычно выводят их hex представление.
Можете взять хэш от строки любой популярной функцией и записать его в своей 52-ричной системе.

[Dubrovin]

Adamos, можно для чайника функцию, которой можно хэш представить в своей системе с алфавитом a-zA-Z?

[Эдуард]

Dubrovin,

<?php

$str = 'Строка для хеширования';

echo preg_replace('~\d+~', '', md5($str));

UPD: Ещё вариант

<?php

$str = 'Строка для хеширования';

echo preg_replace('~[^\pL]+~', '', base64_encode($str));

[Adamos]

Dubrovin, ну, раз это для вас проблема, лучше обойдитесь символами a-zA-E - будет 32 варианта.
Заменяете каждые 5 бит хэша на соответствующую букву - и все. Просто получится немного подлиннее.

Или, если и это для вас сложно, самый козырной алгоритм: берете hex-строку md5 и тупо заменяете 0-9 на g-p. Получаете строку из одних только букв...

[Dubrovin]

Эдуард, может тогда и половину букв удалить? ваше решение увеличивает вероятность возникновения коллизий.

[Эдуард]

Dubrovin, думаю, что если ещё сократить строку (удаляя половину букв), то вероятность коллизий существенно увеличится.

[Dubrovin]

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

[Adamos]

Dubrovin, я ее и дал вторым вариантом. Ничего не удаляется, берете хэш
7d50b03b3e72815544fb16bdf4bf8c61
и элементарной заменой превращаете его в
ndlgbgjbjeniohllkkfbhmbdfkbfocmh

Answer 1

[FanatPHP]

В выборе "Сложность вопроса" должен быть четвертый пункт

- Сложный
- Средний
- Простой
- Дурацкий

Comments

[Dubrovin]

Может вы чего-то не понимаете?

Answer 2

[xmoonlight]

Два варианта:
1. Посмотрите здесь.
2. Создайте таблицу-связку: [имя css-класса] -> [ID] -> [сочетание на множестве по ID: короткое имя класса]

Comments

[Dubrovin]

Смотрел, конкретно решения на мой вопрос там нет. Самое лучшее, что нашёл на просторах интернета - http://proger.i-forge.net/%D0%9A%D0%BE%D0%BC%D0%BF...
Но решение, мягко говоря, громоздкое

[xmoonlight]

Dubrovin, цель - сделать урлы или для чего именно хеш без цифр (если не секрет)?

[Dubrovin]

xmoonlight, есть массив из динамического CSS-кода у компонентов на странице. Цель - собрать такой массив, удалив при этом дублирующий CSS-код, в качестве ключей массива - хэш, чтобы потом не городить функцию поиска внутри массива, этот же хэш можно использовать для имён классов у компонентов на странице, которые используют динамический CSS (Компоненты создаются PHP - не React-подход)

[Сергей delphinpro]

Dubrovin, а использование алфавита a-zA-Z для того, чтобы получить корректное имя css класса, которое не может начинаться с цифры?
Можно просто использовать всё тот же MD5, добавив один символ в начале:

$hash = 'v' . md5($content);

Такой хеш всегда можно использовать в качестве имени css класса.

[Dubrovin]

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

[xmoonlight]

Dubrovin, создать список из css-классов с ID-шниками: 1,2,... и потом распределить по набору A-Za-z.

[Сергей delphinpro]

Dubrovin, хеши не будут "как можно более короткими".
Тогда рассмотрите еще вариант:

Создать таблицу в базе для хешей.
Получить хеш - сохранить его в базе.
Из базы получить целочисленный ID хеша.
Перевести ID в 52-ричную систему счисления (26 * 2 букв латинского алфавита)
Полученное 52-ричное число использовать в качестве ключа и имени класса.

[Adamos]

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

Answer 3

[Dubrovin]

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

function string_to_short_md5( $string ) {

			$result = '';

			$alphabet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
			$raw      = md5( $string, true );
			$length   = strlen( $this->dec_to_base( $alphabet, 2147483647 ) );

			foreach ( str_split( $raw, 4 ) as $dword ) {
				$dword = ord( $dword[0] ) + ord( $dword[1] ) * 256 + ord( $dword[2] ) * 65536 + ord( $dword[3] ) * 16777216;

				$result .= str_pad( $this->dec_to_base( $alphabet, $dword ), $length, $alphabet[0], STR_PAD_LEFT );
			}

			return $result;
		}

		function dec_to_base( $alphabet, $dword ) {
			$rem = (int) fmod( $dword, strlen( $alphabet ) );
			if ( $dword < strlen( $alphabet ) ) {
				return $alphabet[ $rem ];
			}

			return $this->dec_to_base( $alphabet, ( $dword - $rem ) / strlen( $alphabet ) ) . $alphabet[ $rem ];
		}

Который возвращает md5 строки в base52 (24 символа a-zA-Z).
В результате нашёл более короткое решение:

strtr( base_convert( md5( $string ), 16, 36 ), '0123456789', 'ABCDEFGHIJ' );

Которое возвращает md5 строки в base36 (24-25 символов a-zA-Z).

Всем спасибо за помощь!

Answer 4

[Антон Р.]

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

Comments

[Dubrovin]

Ключевой момент - хеш ИЗ СТРОКИ, а не случайный.

[Антон Р.]

Dubrovin, Разобрать строку в массив-словарь через explode

[Dubrovin]

Антон Р., отлично, тогда строка будет длинной, а нужна короткая строка. Пока что самое короткое решение (24-25 букв) с минимальной вероятностью коллизий (md5) приведено в ответе чуть выше.