2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Хеширование строки за время O(log длина)
Сообщение05.08.2016, 15:35 
Заслуженный участник


27/04/09
28128
Кажется, такой вопрос ещё не задавался. Нужда в хешировании за время $o(n)$, где $n$ — длина строки, может быть, например, при интернализации строк. Некоторые языки используют её по умолчанию (Lua), так что, видимо, должны использовать и какие-то более-менее хорошие хеши таких строк, которым гигантскими никто быть не запретит (прочитали какой-нибудь корпус для анализа).

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

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение05.08.2016, 18:06 
Заслуженный участник


26/05/14
981
Если говорить об универсальном хеше, то для любой детерминированной хеш функции со сложностью $o(n)$ можно предъявить большое число строк с одинаковым хешем. Само по себе это не беда. Беда в том что множество этих строк имеет простую структуру. Следовательно, может падать производительность при работе с хеш таблицами.

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

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение05.08.2016, 18:31 
Заслуженный участник


27/04/09
28128
Надеялся на универсальный, так как пока спрашивал просто из интереса. :-) Спасибо.

slavav в сообщении #1142250 писал(а):
Беда в том что множество этих строк имеет простую структуру.
А для (универсальной) функции со сложностью $O(n)$ возможно, чтобы это множество было не таким простым?

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение05.08.2016, 18:50 
Заслуженный участник


26/05/14
981
Вам нужна криптографическая хеш-функция. Там в требованиях прямо написано что прообраз значения должен быть трудно вычислим.

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение10.08.2016, 22:44 
Аватара пользователя


25/03/09
94
А какой-нибудь CRC не сгодится?

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение10.08.2016, 23:58 
Заслуженный участник


27/04/09
28128
$O(n)$ же.

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение11.08.2016, 10:50 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Если строки такие огромные, то, наверное, они все разные по длине? Если одинаковые — это ж патология какая-то. Вот длину и взять в качестве хеша :-) Ну, а если вдруг короткие попались, то их целиком шерстить.

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение11.08.2016, 16:10 
Заслуженный участник


20/08/14
11066
Россия, Москва
Действительно, если строки все разные по длине, то длину и взять.
Если возможны и одинаковые по длине строки, то добавить в хеш несколько символов из строки, позиции которых брать псевдослучайно (но строго детерминированно и всегда одинаково!). Для обычных сильно не совпадающих строк работать будет быстро (фактически $O(1)$), для хорошо совпадающих - зависит от выбора позиций и тут уж без априорной статистики о самих строках не обойтись (например предъявив все $k^n$ возможных перестановок строк длины $n$ из алфавитап в $k$ символов мы собъём любой возможный хеш).
Взяв не фиксированное количество символов в хеш, а например $\log n$ символов (в позициях с простыми индексами или даже с индексами $2^i, i \le n$) получим время $O(\log n)$. Тут для усложнения можно выбирать разные функции индексов в зависимости от значения $n$, на $O()$ это уже не повлияет.
Саму функцию вычисления хеша взять какую-нибудь хорошо исследованную, с известными параметрами и свойствами.

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение11.08.2016, 17:19 
Заслуженный участник


26/05/14
981
worm2 в сообщении #1143315 писал(а):
Если строки такие огромные, то, наверное, они все разные по длине? Если одинаковые — это ж патология какая-то. Вот длину и взять в качестве хеша :-) Ну, а если вдруг короткие попались, то их целиком шерстить.
Ваш подход можно переформулировать так: если вы знаете что для вашего набора длина подходит в качестве идеальной хеш-функции (это термин), то её и надо использовать. Но если вы знаете, что длина годится, то зачем хранить содержимое строк?

-- 11.08.2016, 17:23 --

Dmitriy40 в сообщении #1143374 писал(а):
Действительно, если строки все разные по длине, то длину и взять.
Если возможны и одинаковые по длине строки, то добавить в хеш несколько символов из строки, позиции которых брать псевдослучайно ...
А потом применить к задаче дедупликации данных, на которой ваша функция будет работать очень и очень плохо.

 Профиль  
                  
 
 Re: Хеширование строки за время O(log длина)
Сообщение14.08.2016, 02:18 
Аватара пользователя


07/02/12
1403
Питер
Можно под размер пространства хеш-функции взять достаточную выборку из массива, первым делом взяв его длину.
И пробежаться по детерминированному логарифмическому подмножеству массива, если оно больше.

Неплохо, но на бэкапах может здорово сливать. Там вообще не пробежавшись по массиву все сливать будет.

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

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



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

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


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

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