LINUX.ORG.RU

Хеш-функция


0

4

Алло, мы ищем таланты! (с)

Ищется хеш строки со следующими свойствами

1. hash( «abcd» ) = hash(«abc») + hash(«d») // аддитивность
2. T( hash(s) ) <= O( |s| ) // (суб-)линейная трудоемкость
3. малая коллизия

hash( «abcd» ) = hash(«abc») + hash(«d»)

я не силен в данном вопросе, но разве такое возможно по определению хеш-функций

Boy_from_Jungle ★★★★ ()

Первое что приходит в голову - сложение всех символов строки, но с коллизиями тут не очень.

KivApple ★★★★★ ()
Ответ на: комментарий от KivApple
unsigned int my_strange_hash(char * str) {
        unsigned int result = 0;
        while (*str) {
                hash += *str;
                str++;
        }
        return result;
}

Разумеется, переполнение result должно игнорироваться.

KivApple ★★★★★ ()
Ответ на: комментарий от Kalashnikov

Мой хеш подойдёт, правда, возможно он единственный, который подойдёт, а у него не очень с коллизиями (hash('abcd') == hash('dcba'))

KivApple ★★★★★ ()
Ответ на: комментарий от Kalashnikov

Согласен.

Есть смысл ввести некую полиномиальную зависимость hash( «abcd» ) = P(hash(«abc»)) + Q(hash(«d»))

malbolge ★★ ()

Вот сложение и возьми в качестве хеша. Если в первом требовании некритично именно сложение, то можно взять любую групповую операцию, например, xor. С коллизиями в среднестатистическом случае будет фигово.

const86 ★★★★★ ()
Ответ на: комментарий от KivApple

есть некоторое подозрение, что алгоритм может быть «улучшен», примерно так:

unsigned int my_strange_hash(char * str) {
        const unsigned long hashcode[256] = {скажем набор простых чисел с 6-10-ю знаками};
        unsigned long result = 0;
        while (*str) {
                hash += hashcode[*str];
                str++;
        }
        return result;
}

anonymous ()
Ответ на: комментарий от Kalashnikov

Хотя.. с теми условиями так и получается.

hash('abcd') == hash('a') + hash('b') + hash('c') + hash('d')

А поскольку результат Hash это число, то действует коммутативный закон.

KivApple ★★★★★ ()
Ответ на: комментарий от const86

Мне главное чтобы при добавлении символа к строке новый хеш считался за O(1) с приемлемой коллизией (1е-5 вполне). Аддитивность (да и полином тоже) этому требованию удовлетворяет. Вот, мож кто родит более другую идею нежели просто через к.-л. суммирование.

malbolge ★★ ()

Ситуацию с коллизиями можно улучшить, если взять некоммутативную операцию в качестве «+». f(ab) != f (ba);

Deleted ()
Ответ на: комментарий от malbolge

Мне главное чтобы при добавлении символа к строке новый хеш считался за O(1) с приемлемой коллизией (1е-5 вполне). Аддитивность (да и полином тоже) этому требованию удовлетворяет.

Большинство хешей так и работают. Аддитивность тут излишня, нужно... как бы это назвать... итеративность: hash(data + byte) = f(hash(data), byte). CRC, MD5 и SHA точно сойдут.

const86 ★★★★★ ()

Предельный размер-то не указал :). В таком случае хышем являются сами строки.

vahtu ()

В джаве для строк используют полиномиальный: hash(str + c) = hash(str) * 31 + (int) c; Вместо 31 можно поставить какое-нибудь другое простое число

BlackHawk ()
Ответ на: комментарий от malbolge

От длинных нет профита, короткие и так короче хеша который ты получишь. Могу ошибаться не профессионал и даже не любитель NLP :)

zz ★★★★ ()
Ответ на: комментарий от zz

А, в этом смысле... Ну тут свой хеш главным образом для того, чтобы найти все n-граммы всех длин за O(1) проход.

PS короче, взял за основу ряд Фибоначчи.

malbolge ★★ ()

Первое требование не дружит с третьим, любая перестановка букв в любой строке не изменит хеш. Хуже того, любой хеш будет просто суммой чисел, где каждое число однозначно задается только текущим символом.

quiet_readonly ★★★★ ()
Ответ на: комментарий от quiet_readonly

Все-таки, коммутативность и аддитивность - вещи разные. Например, если A(+)B = AB, то очевидно , такое сложение некоммутативно, но в то же время при f(x)=x имеем f(ab)=f(a)+f(b). Случаи частные, но тем не менее.

malbolge ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.