Хэш-функции используемые для поиска.

← →
Ypbi4 © (2008-02-04 14:37) [0]

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

← →
Заупокойник (2008-02-04 14:45) [1]

эффективная = быстрая
Бери любой 128ми битный хэш - вполне хватит для 7млн.
В инете реализаций - море.

← →
ketmar © (2008-02-04 15:00) [2]

2author: google. perfect hash.

>[1] Заупокойник (04.02.08 14:45)
>эффективная = быстрая
пожалуйста: hash = ord(s[1]);
быстрая? не вопрос. эффективная? ага, как ракета на лимонаде.

← →
Skier © (2008-02-04 15:12) [3]

>Ypbi4 © (04.02.08 14:37)
посмотри здесь :
http://www.proklondike.com/contentview.php?content=235
насколько я помню про хэш-функции там есть...

← →
palva © (2008-02-04 15:41) [4]

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

← →
Правильный_Вася (2008-02-04 15:46) [5]

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

← →
Черный Шаман (2008-02-04 15:50) [6]

> Ypbi4 © (04.02.08 14:37)

CRC32 + сортировка по CRC + бинарный поиск.

Время нахождения ~ log(К-во фамилий) + Время проверки полной строки на совпадение (1 + количество вероятных коллизий)

количество вероятных коллизий при crc32 близка к 0

← →
Заупокойник (2008-02-04 15:53) [7]

>ketmar © (04.02.08 15:00) [2]

Заупокойник (04.02.08 14:45) [1] - подразумевает наличие у вопрошающего минимальных понятий о хэш-алгоритмах. Чего не скажешь о ketmar © (04.02.08 15:00) [2]. Вы видели упоминание о 128ми битах? Зачем к словам придираться?

← →
Черный Шаман (2008-02-04 15:56) [8]

> 128ми битах

При нормальном алгоритме перестановок это 2^ 128 или 10^38 фамилий. Ну и нафига если сравнение с 32 битами быстрее в 4 раза чем со 128, а мощности 32-битного алгоритма хватит для 7 млн фамилий. В 32 бит теоретическая мощность 2^32 или 10^9.

← →
oldman © (2008-02-04 15:59) [9]

> Ypbi4 © (04.02.08 14:37)
> Задали мну такую задачу:
> даны 7 миллионов фамилий

Как даны?
Текстовый файл, БД, таблица, etc?
От этого зависит алгоритм, и (соответственно) коллизии.

← →
palva © (2008-02-04 16:02) [10]

> это обеспечение почти уникального хэша для каждого значения

Ну тогда чем больше размер хэша тем лучше. MD5 даст 128 битов, SHA1 даст 256 битов и т. д. Получим мы такой хэш от фамилии. И как мы будем использовать его для нахождения записи, связанной с этой фамилией?

← →
palva © (2008-02-04 16:09) [11]

> CRC32 + сортировка по CRC + бинарный поиск.
Что-то я не понял, какая сортировка? какой поиск?
Смысл хэширования в том и заключается, что вычислив функцию от ключа сразу получаем номер записи в файле. Далее читаем эту запись, и проверяем ключ на коллизию. Никаких сортировок.

← →
palva © (2008-02-04 16:15) [12]

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

← →
ketmar © (2008-02-04 16:29) [13]

>[7] Заупокойник (04.02.08 15:53)
вот ептить его! уж лет 6 как минимум активно использую всякие хэши, а, оказывается, и не знаю, что использую.

всё, у меня нервный срыв, пошёл рыдать.

← →
хам (2008-02-04 16:38) [14]

> [13] ketmar © (04.02.08 16:29)
> всё, у меня нервный срыв, пошёл рыдать.

Что то часто в последнее время…

← →
ketmar © (2008-02-04 16:43) [15]

>[14] хам (04.02.08 16:38)
так психика расшатана дельфимастером.

← →
oldman © (2008-02-04 16:49) [16]

> ketmar © (04.02.08 16:43) [15]
> так психика расшатана дельфимастером.

Вот и первая коллизия :)))

← →
Заупокойник (2008-02-04 17:16) [17]

ketmar © (04.02.08 16:29) [13]
Видимо не достаточно хорошо знаешь, раз допускаешь, что для 7млн. записей сгодится хэш вида "hash = ord(s[1]);"

← →
Игорь Шевченко © (2008-02-04 17:24) [18]

> Видимо не достаточно хорошо знаешь, раз допускаешь, что
> для 7млн. записей сгодится хэш вида "hash = ord(s[1]);"

"Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву."

http://ru.wikipedia.org/wiki/%D0%A5%D1%8D%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F

← →
ketmar © (2008-02-04 17:27) [19]

Удалено модератором
Примечание: Offtopic

← →
Черный Шаман (2008-02-04 17:32) [20]

> palva © (04.02.08 16:09) [11]
>
> > CRC32 + сортировка по CRC + бинарный поиск.
> Что-то я не понял, какая сортировка? какой поиск?

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

Хотя если вы имели в виду хеш-таблицы, а не хеш-массивы, то тогда да. Но хеш массивы часто эффективнее, так в хеш-массиве не может быть пустот даже при неоптимальном выборе хеш-функции, а log2(7 млн) = 23, тоесть всего 23 сравнения для поиска, что оптимально.

Хотя можно использовать комбинированный вариант хеш таблица crc16, что займет в памяти всего 64 кб и в каждой ячейке хеш-массив crc32.

/* ** $Id: ltable.c,v 2.32 2006/01/18 11:49:02 roberto Exp $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ /* ** Implementation of tables (aka arrays, objects, or hash tables). ** Tables keep its elements in two parts: an array part and a hash part. ** Non-negative integer keys are all candidates to be kept in the array ** part. The actual size of the array is the largest `n" such that at ** least half the slots between 0 and n are in use. ** Hash uses a mix of chained scatter table with Brent"s variation. ** A main invariant of these tables is that, if an element is not ** in its main position (i.e. the `original" position that its hash gives ** to it), then the colliding element is in its own main position. ** Hence even when the load factor reaches 100%, performance remains good. */

это так, с намёком, что CRC в пень не сдался никому.

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

Черный Шаман (04.02.08 17:32) [20]
Теперь понятно.
И такой массив хэшей на диске хранится?
Довольно трудоемко будет добавлять записи.

← →
Черный Шаман (2008-02-04 18:18) [24]

> palva © (04.02.08 18:10) [23]
>
> Черный Шаман (04.02.08 17:32) [20]
> Теперь понятно.
> И такой массив хэшей на диске хранится?
> Довольно трудоемко будет добавлять записи.

Обычно индексные файлы хранятся отдельно(Paradox, Dbase, Foxpro) или внутри в страницах(firebird, Ms SQL...). Вот в них и лежит индексный массив хешей.

>
> Как даны?
> Текстовый файл, БД, таблица, etc?
> От этого зависит алгоритм, и (соответственно) коллизии.

Данные представлены в текстовом файле.

Почитал Кнута "Сортировка и поиск" Т3. Алгоритмы на его примерах понятны, но простой деревенский парень не догоняет КАК это реализовать? ^(
Мое мнение такое:
еще раз повторюсь по условию задачи: дано 7 млн. фамилий в текстовом файле, необходимо разработать эффективную хэш-функцию для поиска фамилии. После прочтения вышеупомянутой литературы у мну сложился такой алгоритм:
1. Задаем 30 массивов int размером где то 65536 (m) каждый (по количеству букв в алфавите ; ы, ь, Ъ не в счет)
2. Далее открываем текстовый файл и начинаем считывать фамилии (разделены пробелом), сохраняем значение первого символа ->вычисляем хэш фамилии след. обр-м :
хэш получаем сложением кодов символов фамилии
h(k)=[m(kA mod 1)], где kA mod 1 - дробная часть kA.
в результате получаем некоторое значение
elvis=(((5*31+12)*31+22)*31+9)*31+19=4996537%11=7
*пример нашел в чужой презентации, к сожалению для мну она не полная, думаю A=31, m=11.
теперь устанавливаем в массиве Е[7]=1 - типа занята ячейка.
3.Для каждой фамилии повторяем п.2 до конца файла
4.Поиск.
Ввод фамилии -> считывание первого символа->вычисления хэш->обращение к нужному массиву, к нужной ячейке (определяется хэш), если 1, то найдена фамилия, если 0, то нет.
Эффективность будет оцениваться, процентом заполнения массивов. Еще не придумал как поступать если будут коллизии в одном массиве, либо отнести их к отчету по эффективности.Т.е. можно будет менять значение A и на нем основываться.

> Заупокойник (04.02.08 14:45) [1]
>
> эффективная = быстрая
> Бери любой 128ми битный хэш - вполне хватит для 7млн.
> В инете реализаций - море.

Можешь носом ткнуть где почитать plz, преподаватель меня консультировал с батоном в руках и что то упоминал про биты(чесслово не разобрал) сказал что хватит 2-х битов, а у меня в голове не укладывается это никак 7 млн и 2 бита О_о, либо я много про это не знаю, что более вероятно.
Фух, высказался о наболевшем. Уважаемые форумчане, подскажите мне алгоритм действия, мне оочень важно ваше мнение. Надеюсь что мой в некоторой степени верен.

агась,осенило, данные загонять в crc таблицу, нашел материал, сейчас почитаю :) может что-нибудь пойму...loading...

>[26] Ypbi4 © (2008-02-11 23:05:00)
это у тебя мегаперерасход памяти получается. нафига так много корзинок-то? они ж дырявые будут.

я так понимаю, давать тебе ссылку на простую реализацию хэшей на си — бессмысленно?

зыж а ты для начала хотя бы нижеследующую ссылку асилил?
http://en.wikipedia.org/wiki/Hash_table
только не надо про «на буржуйском не понятно», на сие здесь реагируют посыланием в магазин хозтоваров.

---
Understanding is not required. Only obedience.

Хэш-функции используемые для поиска. Найти похожие ветки