Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сортированный Хэш

Автор: sergejzr 16.11.2006, 14:17

Приветы! Интересует вопрос, существует ли такая функция hash для слов w{w1,w2,..wn}, что  hash(w1)>hash(w2) <=> w1>w2 .. То есть порядок должен сохранятся и после хэширования.

Автор: comp 16.11.2006, 15:04

1я мысль. Если подумать, что есть слово - это ничто иное, как число, в 26й системе счисления(естесвенно, имеется ввиду слово, из букв ангийского алфавита). Можно от этого как-нибудь поплясать... 2я мысль. Моежт подойдёт самое стандартное hesh = sum(w[i] * i)...  Т.е. найти сумму следующего вида: ascii_код_символа * его_позиция_в_слове... Не проверял. Такое ощущение, что так нельзя делать...

Автор: Sartorius 16.11.2006, 15:08

sergejzr,  можно hash(w1) >= hash(w2), все таки хэширование - это отображение в  множество..., а иначе свертки не будет.

Автор: maxim1000 16.11.2006, 15:16

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

Автор: sergejzr 16.11.2006, 15:37

Цитата(Sartorius @  16.11.2006,  14:08 ) sergejzr,  можно hash(w1) >= hash(w2), все таки хэширование - это отображение в  множество..., а иначе свертки не будет.  Скажем так, мне надо для определённой группы w. То есть числовое пространство множества можно расширить до необходимости. Цитата(maxim1000 @  16.11.2006,  14:16 ) на тот случай, если дело касается криптографии: я бы не советовал использовать такой хеш, т.к. при желании найти строку по нему можно будет использовать алгоритм бисекции, что сильно уменьшит время поиска  Не совсем... Я думал использовать такое в базах данных. То есть инфа там лежит шифровкой, но все операции доступны. Добавлено @ 15:41  Цитата(comp @  16.11.2006,  14:04 ) 2я мысль. Моежт подойдёт самое стандартное hesh = sum(w[i] * i)...  Т.е. найти сумму следующего вида: ascii_код_символа * его_позиция_в_слове... Не проверял. Такое ощущение, что так нельзя делать...  Не получится.. т.к 2*2+3*2 == 2*5

Автор: esperant0 16.11.2006, 23:45

да такая ф-я хещ есть ее еще называют ф-й равенства. отношение порядко определено  как лексокографический порядок f(W)=w

Автор: maxim1000 17.11.2006, 01:05

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)