Инъективный хэш для pascal-строк?

← →
Полвторого (2010-12-07 23:20) [0]

Всем доброго времени суток.

Вопрос мой заключается в следующем:
Есть массив из миллиона строк фиксированной длины 255 байт.
Каждый символ строки может принимать всего 27 значений (вся строчная латиница + \0).
Возможно ли, опираясь на конкретные данные, построить хэш-функцию с областью значений, влезающей в Int64, не содержащую коллизий на этих данных, и если да, то как (или если нет, то почему)?

Буду рад как прямым советам, так и литературе по теме.
Не беда, если на английском языке.

← →
Ega23 © (2010-12-07 23:29) [1]

1. 27 значений укладываются в 5 бит. Это к вопросу об упаковке.
2. Никакая хэш-функция не даст гарантию отсутствия повторов.

← →
Anatoly Podgoretsky © (2010-12-07 23:36) [2]

> Полвторого (07.12.2010 23:20:00) [0]

Невозможно, через 2^64 комбинаций числа будут повторяться, а это всего лишь
первые 8 байт. Уже на 9 байте будет 256 коллизий для каждого хеш кода.

← →
Полвторого (2010-12-07 23:46) [3]

> 1. 27 значений укладываются в 5 бит. Это к вопросу об упаковке.

Так это-то понятно.
Сделать из каждых 255 байт 160 — это уже рассматривалось, в частности в рамках построения хэша по принципу (s[i]-"a")*29^(255-i).
29 бралось из-за того, что это наименьшее простое число, строго большее 27.
Но неужели зависимость между строкой и её хэшем возможна исключительно прямая?
Ведь в миллионе строк никак не может уместиться 27^255 комбинаций.

> 2. Никакая хэш-функция не даст гарантию отсутствия повторов.

Так и не нужна функция вообще без повторов.
Хотелось бы построить такую, у которой повторы были бы, но для каждой строки из текущего набора, их бы не встретилось.

← →
Leonid Troyanovsky © (2010-12-07 23:57) [4]

> Полвторого (07.12.10 23:46) [3]

> функцию с областью значений, влезающей в Int64, не содержащую
> коллизий на этих данных, и если да, то как (или если нет,
> то почему)?

8 <> 255.

--
Regards, LVT.

← →
Ega23 © (2010-12-08 00:12) [5]

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

CRC2048 - гарантия. Других гарантий нет.

← →
Игорь Шевченко © (2010-12-08 00:15) [6]

> Буду рад как прямым советам, так и литературе по теме.

http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

← →
Полвторого (2010-12-08 00:17) [7]

> 8 <> 255.

Так, опять же, и не требуется «сжать 255 байт в 8»!
Требуется просто сопоставить каждой уникальной строке из данного миллиона уникальный идентификатор из 0…2^64-1 с сохранением порядка, аналогичного лексикографическому у строк.

Вариант «отсортировать и пронумеровать» также рассматривался.
Вопрос касается только общего вида данных, когда исходные строки могут идти в произвольном порядке.

Пример.
Есть два набора строк:

abbb bbbb aaaa bbbb aaab aaaa

Так вот, идеальным с точки зрения моего вопроса был бы алгоритм, который смог бы без сортировки сопоставить, в первом случае:

строке aaaa число A1, abbb — B1, bbbb — C1

а во втором:

строке aaaa число A2, aaab — B2, bbbb — C2

такие, что A1 < B1 < C1, A2 < B2 < C2.

← →
vuk © (2010-12-08 01:12) [8]

А как вообще возможно отобразить большее множество на меньшее без коллизий?

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

Индекс в наборе. :)

← →
Ega23 © (2010-12-08 01:23) [9]

> Так вот, идеальным с точки зрения моего вопроса был бы алгоритм,
> который смог бы без сортировки сопоставить, в первом случае:
>

Гугли на тему "суррогатный первичный ключ"

← →
DiamondShark © (2010-12-08 01:30) [10]

> Требуется просто сопоставить каждой уникальной строке из
> данного миллиона

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

← →
MBo © (2010-12-08 08:31) [11]

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

> [11]
но без соответствия лекс. порядку

> CRC2048 - гарантия. Других гарантий нет.

CRC не совсем хэш. Собственно чем плох Md5 или баркер?

> Собственно чем плох Md5 или баркер?

Тем что нет никакой гарантии, что у тебя не сгенерится два одинаковых md5 из двух разных наборов байт.

Точнее, она исчезающе мала, но - есть.

← →
Полвторого (2010-12-08 16:41) [16]

> поможет perfect hash - идеальное хэширование.

> но без соответствия лекс. порядку

Монотонное идеальное хэширование сохраняет порядок.
Спасибо огромное MBo! Ушёл читать.

Инъективный хэш для pascal-строк? Найти похожие ветки