Струнное хеширование с линейным зондированием

Question

Я застрял, пытаясь понять, как выполнять хеширование строк с помощью линейного зондирования.

По сути, идея состоит в том, чтобы хэшировать каждую строку из словаря (90000 слов) и извлекать анаграммы выбранных слов.

Вот что я сделал:

1. создал хеш-таблицу размером 2 * 90000

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

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

4. после каждого слова в хеш-таблице, и я выполняю поиск

5. поисковое слово получит хеш-значение после хеш-функции, и будет проверено, существует ли это значение в хеш-таблице или нет.

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

проблема в том, что весь процесс очень медленный ... он отлично индексируется, но поиск занимает ДЕЙСТВИТЕЛЬНО много времени.

У меня нет идей, как сделать это быстрее ..

Спасибо, что уделили мне время.

Answer 1

Сначала поместите все буквы в алфавитном порядке, а затем хэшируйте результат с помощью любого алгоритма хэширования (crc32, md5sum, sha1, считайте гласные, что угодно ... хотя подсчет гласных приведет к менее эффективному решению)и сохраните слово как листовой узел для этой записи хеша (очевидно, в связанном списке) - выполните мод (x) для результата хеша, чтобы ограничить сегменты 2 ^ x.

Затем,когда вы найдете анаграмму, выполните ту же самую процедуру «вставки» на вашем тесте слове: расположите буквы в алфавитном порядке, а затем выполните ту же хеш-функцию.Затем для каждого конечного узла сравните список алфавитных букв с алфавитным списком сохраненного слова.Каждое совпадение - это анаграмма.

(Обычно я не люблю помогать с домашними заданиями, но это было слишком заманчиво. Теперь я хочу написать небольшую забавную программу, чтобы найти все анаграммы вданный словарь.)

Answer 2

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

Этот метод имеет недостаток в том, что если будет одно столкновение, будет больше.

Одним из способов является то, что вы можете использовать Separate Chaining и использовать сбалансированные деревья в качестве сегментов для улучшения поиска.

Если вы просто хотите улучшить производительность, убедитесь, что нет коллизий (в этом случае поиск идеально равен O (1)), и, если есть, увеличьте размер хеш-таблицы.

Answer 3

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

Вместо этого выберите хеш-функцию, которая одинакова для любой перестановки (анаграммы) слова. Например, один основан на сумме кодов символов символов в слове.

Answer 4

Вы пытаетесь создать анаграммы для данной строки? В этом случае просто создайте анаграмму для получения строки в качестве входных данных. Какой смысл хэшировать эти строки?

РЕДАКТИРОВАТЬ: Прежде всего, я бы предложил вам получить все перестановки данной строки, а затем перебрать файл словаря, содержащий все слова. Это имеет то преимущество, что вам не нужно хранить все слова в памяти. Если вы хотите оптимизировать дальше, сортируйте весь файл по длинам строк в порядке возрастания или убывания и продолжайте проверять строки в файле словаря, пока не достигнете <= длины следующей строки.