Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Хеш-функция на формулах - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: китин, _Boroda_  
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Хеш-функция на формулах
Хеш-функция на формулах
Формуляр Дата: Четверг, 27.10.2011, 18:53 | Сообщение № 1
Группа: Друзья
Ранг: Ветеран
Сообщений: 832
Репутация: 255 ±
Замечаний: 0% ±

Excel 2003, 2013
Всем добрый вечер!
Понадобилось тут зашифровать списки сотрудников так, чтобы сохранить возможность их сопоставления.
Решил использовать хеширование.
Но оказалось, грамотно его построить непросто.
Hash1 создаёт коллизии даже на 50 сотрудниках.
Hash2 - вроде бы, по-лучше, но приходится использовать вспомогательный столбец, да и подтормаживать начинает.
Может подскажет кто из опытных в этой теме людей более простые и эффективные решения?
К сообщению приложен файл: hash.xls (41.0 Kb)


Excel 2003 EN, 2013 EN

Сообщение отредактировал Формуляр - Четверг, 27.10.2011, 18:55
 
Ответить
СообщениеВсем добрый вечер!
Понадобилось тут зашифровать списки сотрудников так, чтобы сохранить возможность их сопоставления.
Решил использовать хеширование.
Но оказалось, грамотно его построить непросто.
Hash1 создаёт коллизии даже на 50 сотрудниках.
Hash2 - вроде бы, по-лучше, но приходится использовать вспомогательный столбец, да и подтормаживать начинает.
Может подскажет кто из опытных в этой теме людей более простые и эффективные решения?

Автор - Формуляр
Дата добавления - 27.10.2011 в 18:53
Serge_007 Дата: Четверг, 27.10.2011, 19:41 | Сообщение № 2
Группа: Админы
Ранг: Местный житель
Сообщений: 16475
Репутация: 2748 ±
Замечаний: ±

Excel 2016
Привет, Саня.
Думаю что таких спецов не много в принципе.

Для тех кто не знает что такое хэширование : http://ru.wikipedia.org/wiki


ЮMoney:41001419691823 | WMR:126292472390
 
Ответить
СообщениеПривет, Саня.
Думаю что таких спецов не много в принципе.

Для тех кто не знает что такое хэширование : http://ru.wikipedia.org/wiki

Автор - Serge_007
Дата добавления - 27.10.2011 в 19:41
nerv Дата: Четверг, 27.10.2011, 21:46 | Сообщение № 3
Группа: Редакторы
Ранг: Обитатель
Сообщений: 431
Репутация: 193 ±
Замечаний: 0% ±

Формуляр, здравствуйте. Если интересно, я использовал хеш-функцию здесь http://www.excelworld.ru/forum/3-717-3, правда она на VBA, но зато компактная (на мой взгляд). Разумеется, основная беда "хешей" - коллизии, как с ними бороться, думаю, знаете : )


Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук


YM 41001156540584 / WM WMR R21924176233

https://github.com/nervgh/vba


Сообщение отредактировал nerv - Четверг, 27.10.2011, 21:47
 
Ответить
СообщениеФормуляр, здравствуйте. Если интересно, я использовал хеш-функцию здесь http://www.excelworld.ru/forum/3-717-3, правда она на VBA, но зато компактная (на мой взгляд). Разумеется, основная беда "хешей" - коллизии, как с ними бороться, думаю, знаете : )

Автор - nerv
Дата добавления - 27.10.2011 в 21:46
Формуляр Дата: Четверг, 27.10.2011, 22:20 | Сообщение № 4
Группа: Друзья
Ранг: Ветеран
Сообщений: 832
Репутация: 255 ±
Замечаний: 0% ±

Excel 2003, 2013
nerv, посмотрел предложенную ф-цию - похоже, её можно реализовать на формулах.
Только хотелось бы сократить те элементы, которые не очень принципиальны. Ежели, конечно, таковые имеются.
Можете ли вы вкратце прокоментировать каждую из используемых констант?
Для меня это всё - пляски с бубном. smile

[vba]
Код
Private Function EasyHash(ByRef Str$) As Long
Dim i As Integer, Hash As Long
For i = 1 To Len(Str)
        Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223
        EasyHash = ((Hash Xor Abs(1365 / i)) And 65535) + EasyHash
Next
End Function
[/vba]
Цитата (nerv)
как с ними бороться, думаю, знаете : )

Даже не понял, вшутку это или всерьёз. На всякий случай, отвечаю: ни малейшего понятия!

PS: Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем?


Excel 2003 EN, 2013 EN

Сообщение отредактировал Формуляр - Четверг, 27.10.2011, 22:33
 
Ответить
Сообщениеnerv, посмотрел предложенную ф-цию - похоже, её можно реализовать на формулах.
Только хотелось бы сократить те элементы, которые не очень принципиальны. Ежели, конечно, таковые имеются.
Можете ли вы вкратце прокоментировать каждую из используемых констант?
Для меня это всё - пляски с бубном. smile

[vba]
Код
Private Function EasyHash(ByRef Str$) As Long
Dim i As Integer, Hash As Long
For i = 1 To Len(Str)
        Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223
        EasyHash = ((Hash Xor Abs(1365 / i)) And 65535) + EasyHash
Next
End Function
[/vba]
Цитата (nerv)
как с ними бороться, думаю, знаете : )

Даже не понял, вшутку это или всерьёз. На всякий случай, отвечаю: ни малейшего понятия!

PS: Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем?

Автор - Формуляр
Дата добавления - 27.10.2011 в 22:20
MCH Дата: Четверг, 27.10.2011, 22:48 | Сообщение № 5
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Вариант:
Код
="х"&ДЕС.В.ШЕСТН(ОСТАТ(СУММПРОИЗВ((КОДСИМВ(ПСТР(A2;СТРОКА($1:$19);1)&" ")-32)*16^ОСТАТ(СТРОКА($1:$19)-1;7));16^8);8)
 
Ответить
СообщениеВариант:
Код
="х"&ДЕС.В.ШЕСТН(ОСТАТ(СУММПРОИЗВ((КОДСИМВ(ПСТР(A2;СТРОКА($1:$19);1)&" ")-32)*16^ОСТАТ(СТРОКА($1:$19)-1;7));16^8);8)

Автор - MCH
Дата добавления - 27.10.2011 в 22:48
MCH Дата: Четверг, 27.10.2011, 22:57 | Сообщение № 6
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Quote (Формуляр)
Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем

... And 65535 вданном случае можно заменить функцией ОСТАТ(...;65536)
а Xor - побитная инверсия, в Excel аналогов данной функций нет
 
Ответить
Сообщение
Quote (Формуляр)
Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем

... And 65535 вданном случае можно заменить функцией ОСТАТ(...;65536)
а Xor - побитная инверсия, в Excel аналогов данной функций нет

Автор - MCH
Дата добавления - 27.10.2011 в 22:57
nerv Дата: Пятница, 28.10.2011, 13:29 | Сообщение № 7
Группа: Редакторы
Ранг: Обитатель
Сообщений: 431
Репутация: 193 ±
Замечаний: 0% ±

Коллизии и борьба с ними http://ru.wikipedia.org/wiki....8%D0%B8

Quote (Формуляр)
Можете ли вы вкратце прокомментировать каждую из используемых констант?

-------------------------
Decimal | Binary
--------------------------
1365 = 10101010101
65535 = 1111111111111111

Остальные две отсюда http://vak.ru/doku.php/proj/hash/efficiency, а точнее http://vak.ru/doku.php/proj/hash/sources#ly_hash_function
Признаться, я не доконца понял код на C, поэтому сделал, как сделал.

Да и, у моей хеш-функции есть коллизии. Проверено : )
К сообщению приложен файл: _hash-1.xls (45.0 Kb)


Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук


YM 41001156540584 / WM WMR R21924176233

https://github.com/nervgh/vba


Сообщение отредактировал nerv - Пятница, 28.10.2011, 13:30
 
Ответить
СообщениеКоллизии и борьба с ними http://ru.wikipedia.org/wiki....8%D0%B8

Quote (Формуляр)
Можете ли вы вкратце прокомментировать каждую из используемых констант?

-------------------------
Decimal | Binary
--------------------------
1365 = 10101010101
65535 = 1111111111111111

Остальные две отсюда http://vak.ru/doku.php/proj/hash/efficiency, а точнее http://vak.ru/doku.php/proj/hash/sources#ly_hash_function
Признаться, я не доконца понял код на C, поэтому сделал, как сделал.

Да и, у моей хеш-функции есть коллизии. Проверено : )

Автор - nerv
Дата добавления - 28.10.2011 в 13:29
Формуляр Дата: Пятница, 28.10.2011, 14:01 | Сообщение № 8
Группа: Друзья
Ранг: Ветеран
Сообщений: 832
Репутация: 255 ±
Замечаний: 0% ±

Excel 2003, 2013
MCH, спасибо! Ваш вариант явно проще первоначального. Взял за рабочую основу.

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

Не пойму в чём смысл преобразования
Code
Abs(1365 / i)

Оно ж и так всегда > 0 да ещё с плавающей точкой получается. Что там с битовой маской будет - ваще не понятно!


Excel 2003 EN, 2013 EN

Сообщение отредактировал Формуляр - Пятница, 28.10.2011, 14:01
 
Ответить
СообщениеMCH, спасибо! Ваш вариант явно проще первоначального. Взял за рабочую основу.

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

Не пойму в чём смысл преобразования
Code
Abs(1365 / i)

Оно ж и так всегда > 0 да ещё с плавающей точкой получается. Что там с битовой маской будет - ваще не понятно!

Автор - Формуляр
Дата добавления - 28.10.2011 в 14:01
nerv Дата: Пятница, 28.10.2011, 15:52 | Сообщение № 9
Группа: Редакторы
Ранг: Обитатель
Сообщений: 431
Репутация: 193 ±
Замечаний: 0% ±

Цитата (Формуляр)
Не пойму в чём смысл преобразования

happy Судя по всему остаточный артефакт от копи-паста

Цитата (Формуляр)
Буду разбираться, чем можно пожертвовать при реализации на формулах.

\Попробуйте такой вариант. На первый взгляд результат вполне приемлемый. Я бы даже сказал лучше, чем был smile

[vba]
Код
Private Function EasyHash(ByRef Str$) As Long
Dim i As Integer, Hash As Long
For i = 1 To Len(Str)
        Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223
        EasyHash = (Hash / i And 1048575) + EasyHash
Next
End Function
[/vba]

Какая хорошая разница:
Алла | 2036555
аллА | 1090691
баа | 2089824
ааб | 980141
К сообщению приложен файл: -hash-1-2.xls (49.0 Kb)


Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук


YM 41001156540584 / WM WMR R21924176233

https://github.com/nervgh/vba


Сообщение отредактировал nerv - Пятница, 28.10.2011, 15:59
 
Ответить
Сообщение
Цитата (Формуляр)
Не пойму в чём смысл преобразования

happy Судя по всему остаточный артефакт от копи-паста

Цитата (Формуляр)
Буду разбираться, чем можно пожертвовать при реализации на формулах.

\Попробуйте такой вариант. На первый взгляд результат вполне приемлемый. Я бы даже сказал лучше, чем был smile

[vba]
Код
Private Function EasyHash(ByRef Str$) As Long
Dim i As Integer, Hash As Long
For i = 1 To Len(Str)
        Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223
        EasyHash = (Hash / i And 1048575) + EasyHash
Next
End Function
[/vba]

Какая хорошая разница:
Алла | 2036555
аллА | 1090691
баа | 2089824
ааб | 980141

Автор - nerv
Дата добавления - 28.10.2011 в 15:52
MCH Дата: Пятница, 28.10.2011, 18:38 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

попытался перевести функцию Александра в Excel, результат получается другой
в отличии от UDF, ОСТАТ(...;2^20), аналог AND 1048575, делаю после суммирования, чтобы ограничить конечный хэш 20 битами:
Code
=ОСТАТ(СУММПРОИЗВ(1+ЦЕЛОЕ((1664525*КОДСИМВ(ПСТР(A2;СТРОКА(ДВССЫЛ("1:"&ДЛСТР(A2)));1))+1013904223)/СТРОКА(ДВССЫЛ("1:"&ДЛСТР(A2)))));2^20)


Сообщение отредактировал MCH - Суббота, 29.10.2011, 10:30
 
Ответить
Сообщениепопытался перевести функцию Александра в Excel, результат получается другой
в отличии от UDF, ОСТАТ(...;2^20), аналог AND 1048575, делаю после суммирования, чтобы ограничить конечный хэш 20 битами:
Code
=ОСТАТ(СУММПРОИЗВ(1+ЦЕЛОЕ((1664525*КОДСИМВ(ПСТР(A2;СТРОКА(ДВССЫЛ("1:"&ДЛСТР(A2)));1))+1013904223)/СТРОКА(ДВССЫЛ("1:"&ДЛСТР(A2)))));2^20)

Автор - MCH
Дата добавления - 28.10.2011 в 18:38
Формуляр Дата: Воскресенье, 30.10.2011, 19:40 | Сообщение № 11
Группа: Друзья
Ранг: Ветеран
Сообщений: 832
Репутация: 255 ±
Замечаний: 0% ±

Excel 2003, 2013
Цитата (nerv)
Остальные две отсюда http://vak.ru/doku.php/proj/hash/efficiency, а точнее http://vak.ru/doku.php/proj/hash/sources#ly_hash_function Признаться, я не доконца понял код на C, поэтому сделал, как сделал.


Первоисточник выглядит вот так:
[vba]
Код
    for (i = 0; i < len; str++, i++) {
     hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;
    }
[/vba]
Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения).
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).
И вообще непонятно зачем прибавлять константу, половина которой тут же улетает за границы разрядной сетки?
Короче, загадок меньше не стало...


Excel 2003 EN, 2013 EN

Сообщение отредактировал Формуляр - Воскресенье, 30.10.2011, 19:42
 
Ответить
Сообщение
Цитата (nerv)
Остальные две отсюда http://vak.ru/doku.php/proj/hash/efficiency, а точнее http://vak.ru/doku.php/proj/hash/sources#ly_hash_function Признаться, я не доконца понял код на C, поэтому сделал, как сделал.


Первоисточник выглядит вот так:
[vba]
Код
    for (i = 0; i < len; str++, i++) {
     hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;
    }
[/vba]
Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения).
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).
И вообще непонятно зачем прибавлять константу, половина которой тут же улетает за границы разрядной сетки?
Короче, загадок меньше не стало...

Автор - Формуляр
Дата добавления - 30.10.2011 в 19:40
nerv Дата: Воскресенье, 30.10.2011, 21:17 | Сообщение № 12
Группа: Редакторы
Ранг: Обитатель
Сообщений: 431
Репутация: 193 ±
Замечаний: 0% ±

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


Цитата с сайта
Quote
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:

Американский словарь из проекта Ispell, 62075 слов.
Русский словарь из проекта Ispell, 128900 слов.
Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.

Общее количество после слияния — 326797 уникальных слов.

В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:

Немецкий словарь из проекта Ispell, 39612 слов.
Венгерский словарь из проекта Ispell, 211880 слов.
Итальянский словарь из проекта Ispell, 37268 слов.
Шведский словарь из проекта Ispell, 24019 слов.

Общее количество после слияния — 310595 уникальных слов.

Мое мнение - не ищите логику там, где ее нет smile

См. таблицу http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод

CRC32 Function. Знакомое название, не правда ли?) Только если посмотреть код на той странице, ссылку на кот. я давал выше, саму таблицу вы не найдете) А она не маленькая : )

Quote (Формуляр)
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).

Не знаю, как работает C, но если писать в Ассемблере, то, действительно, будет установлен флаг OF, но при этом работа программы продолжится. Хотя, как запрограммируешь...*

*на сколько мне известно


Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук


YM 41001156540584 / WM WMR R21924176233

https://github.com/nervgh/vba


Сообщение отредактировал nerv - Воскресенье, 30.10.2011, 21:24
 
Ответить
Сообщение
Quote (Формуляр)
Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения).


Цитата с сайта
Quote
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:

Американский словарь из проекта Ispell, 62075 слов.
Русский словарь из проекта Ispell, 128900 слов.
Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.

Общее количество после слияния — 326797 уникальных слов.

В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:

Немецкий словарь из проекта Ispell, 39612 слов.
Венгерский словарь из проекта Ispell, 211880 слов.
Итальянский словарь из проекта Ispell, 37268 слов.
Шведский словарь из проекта Ispell, 24019 слов.

Общее количество после слияния — 310595 уникальных слов.

Мое мнение - не ищите логику там, где ее нет smile

См. таблицу http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод

CRC32 Function. Знакомое название, не правда ли?) Только если посмотреть код на той странице, ссылку на кот. я давал выше, саму таблицу вы не найдете) А она не маленькая : )

Quote (Формуляр)
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).

Не знаю, как работает C, но если писать в Ассемблере, то, действительно, будет установлен флаг OF, но при этом работа программы продолжится. Хотя, как запрограммируешь...*

*на сколько мне известно

Автор - nerv
Дата добавления - 30.10.2011 в 21:17
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Хеш-функция на формулах
  • Страница 1 из 1
  • 1
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!