Russian Qt Forum
Март 29, 2024, 10:59 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 [2]   Вниз
  Печать  
Автор Тема: Посоветуйте хэш-функцию для свертки не длинных массивов байт  (Прочитано 16651 раз)
xokc
Птица говорун
*****
Offline Offline

Сообщений: 976



Просмотр профиля
« Ответ #15 : Апрель 23, 2014, 21:08 »

Когда размеры данных превышают ключ в 256*1024/4=65536 раз (256 кБ к 32 битам), то для любой разумной хэш функции число коллизий на таких размерах будет таким же как и на 1 МБ. Существенным может быть разница для действительно коротких (до 256 байт) входных последовательностей (см., например, тут http://ru.wikipedia.org/wiki/Adler-32#.D0.9F.D1.80.D0.B5.D0.B8.D0.BC.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D0.B8_.D0.BD.D0.B5.D0.B4.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.B8)
Вот интересный вариант на 32 бита
http://code.google.com/p/xxhash/
А вот на 64 бита
http://code.google.com/p/cityhash/
Судя по замерам производительности на xxhash можно успеть трижды (по сравнению с CityHash64) посчитать xxh32 на различных вариантах входной последовательности (например, на полном входе и на каких-либо его участках) и скомбинировать из него 96 битный ключ.
Записан
OKTA
Гость
« Ответ #16 : Апрель 23, 2014, 21:47 »

CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  Смеющийся
Не понял - CRC32("codding - gnu") = 0xAD7CEA44, CRC32("exhibiters - schlager") = 0x389AE08C, CRC32("codding - gnu1") = 0xF2C016D4, CRC32("exhibiters - schlager1") = 0x67EABA5C (http://www.codenet.ru/services/crc32/)

64 разряда, если выполнится требование уникальности и работать будет быстро.
И снова не понял, о какой уникальности хэша может идти речь при ограниченной длине ключа. В любом случае для 64 битного ключа количество вариантов его значений = 2^64. То есть для 2^64+1 различных вариантов входных последовательностей будут гарантированно совпадать значения хэшей даже для идеальной в смысле минимизации коллизий функции.
Для гарантированно уникальной хэш функции на неограниченно длинной последовательности нужен неограниченно длинный ключ.

Я имел ввиду пары слов) CRC32("codding") = 0x69c8c72d И CRC32("gnu") = 0x69c8c72d и т.д.

А откройте мне глаза, о каком хэш-ключе вы тут говорите?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #17 : Апрель 24, 2014, 08:21 »

Требование уникальности есть для указанного выше диапазона входных данных. Поэтому CRC32 не подходит.
Если я правильно понял, Вы хотите использовать "результат свертки" как ключ и сам массив данных как значение. Думаю что это недостижимо - во всяком случае вероятность совпадения ключей ненулевая. А чем мудренее алгоритм свертки - тем больше он сожрет времени. Почему бы не использовать сами данные как ключ? А свертку для оптимизации, напр так
Код
C++ (Qt)
struct CTest {
bool operator == ( const CTest & sec ) const
{
return mCRC == sec.mCRC && mData == sec.mData;
}
 
int mCRC;
QVector <char> mData;
};
 
inline uint qHash( const CTest & key ) { return key.mCRC; }
 
Записан
xokc
Птица говорун
*****
Offline Offline

Сообщений: 976



Просмотр профиля
« Ответ #18 : Апрель 24, 2014, 08:28 »

А откройте мне глаза, о каком хэш-ключе вы тут говорите?
Безусловно, в академическом смысле термин "ключ" к хеш-функции не очень применим. Здесь под ключом я понимал результат, возвращаемый хеш-функцией.

Думаю что это недостижимо - во всяком случае вероятность совпадения ключей ненулевая.
Igors прав. Вероятность совпадения ключей ненулевая всегда для любой из неидеальных хеш-функций. И если нужна гарантированная проверка на уникальность, то придется в любом случае хранить все проверяемые последовательности.
« Последнее редактирование: Апрель 24, 2014, 08:40 от xokc » Записан
Old
Джедай : наставник для всех
*******
Online Online

Сообщений: 4349



Просмотр профиля
« Ответ #19 : Апрель 24, 2014, 10:14 »

Вероятность совпадения ключей ненулевая всегда для любой из неидеальных хеш-функций. И если нужна гарантированная проверка на уникальность, то придется в любом случае хранить все проверяемые последовательности.
Я не думаю, что нужна гарантированная уникальность.
Скорее всего ТС ищет функцию с минимальным уровнем коллизий для своих данных.
Если данные уже есть или их можно генерировать, то я бы просто написал тесты и погонял эти данные для разных функций, собирая статистику по уровням коллизий.
Записан
Гурман
Гуру общения
******
Offline Offline

Сообщений: 1442

Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12


Просмотр профиля
« Ответ #20 : Апрель 24, 2014, 10:52 »

Требование уникальности есть для указанного выше диапазона входных данных. Поэтому CRC32 не подходит.
Если я правильно понял, Вы хотите использовать "результат свертки" как ключ и сам массив данных как значение. Думаю что это недостижимо - во всяком случае вероятность совпадения ключей ненулевая. А чем мудренее алгоритм свертки - тем больше он сожрет времени. Почему бы не использовать сами данные как ключ? А свертку для оптимизации, напр так
Код
C++ (Qt)
struct CTest {
bool operator == ( const CTest & sec ) const
{
return mCRC == sec.mCRC && mData == sec.mData;
}
 
int mCRC;
QVector <char> mData;
};
 
inline uint qHash( const CTest & key ) { return key.mCRC; }
 

Данные - некие измеренные значения, длина которых обычно от 8 до 1024 байт. В этом диапазоне хэширование должно давать строго уникальные ключи. В диапазоне длин от 1024 до 256КБ возможны совпадения ключей, но чем длиннее данные, тем больше допускается вероятность совпадения, поскольку чем длиннее данные, тем меньше вероятность появления совпадающих по ключам. То есть, фактически, появиться разные данные с длиной около 256 КБ и совпадающими ключами никогда в реальности не могут. С длиной немного более 1 КБ - могут, но вероятность этого крайне низкая и снижается с ростом длины таких данных. Можно считать так - если одни и те же данные длиной более 1 КБ могут сгенерировать совпадающие ключи, то это значит, что появиться может только один массив таких данных. То есть для длинных данных требование уникальности ключа обеспечивается тем, что генерирующие коллизию данные никогда не появятся (по задаче я бы написал никогда не появятся одновременно, но это может только запутать). Поэтому нужен алгоритм, который дает такую свертку, при которой вероятность коллизии на коротких данных нулевая, а появляется только на длинных данных, и может расти с ростом их длины.

Сами данные как ключ использовать нельзя по условию задачи - надо иметь ключ не более 64 разрядов, но желательно 32. Большего рассказать не могу.
Записан

2^7-1 == 127, задумайтесь...
OKTA
Гость
« Ответ #21 : Апрель 24, 2014, 11:05 »

Если будете использовать хэш-функцию, которая выдает 32-битные значения и количество уникальных данных > 2^32, то коллизии будут по определению, независимо от длины данных. Так что надо придумать что-то еще  В замешательстве
Записан
OKTA
Гость
« Ответ #22 : Апрель 24, 2014, 11:24 »

Возможно удобным решением будет использование MAC(Message Authentication Code) или по-русски имитовставка. Это хэш-функция, но зависимая от ключа. Т.е. можно попробовать использовать данные дважды - как сами данные и как ключ. Но насчет коллизий в этом случае мало что известно, т.к. для таких целей MAC не используется. Но почитать можно - гуглить по "MAC на основе однонаправленной хэш-функции".

Хотя нет, тоже самое получится  В замешательстве
« Последнее редактирование: Апрель 24, 2014, 11:55 от OKTA » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #23 : Апрель 25, 2014, 08:06 »

В этом диапазоне хэширование должно давать строго уникальные ключи.
Вероятность совпадения ключа ненулевая - здесь мне нечего добавить. Если нужна строгая уникальность, хранить данные придется. А вот как - можно обсуждать. Напр неплохо в виде дерева
Записан
OKTA
Гость
« Ответ #24 : Апрель 25, 2014, 09:08 »

если ограничение на ключ 32, максимум 64 бита, то вообще не вариант
Записан
Страниц: 1 [2]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.098 секунд. Запросов: 23.