Задача поставлена некорректно.
А>Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым.
Очевидно, это требование выполнить невозможно, т.к. возможных строк больше, чем 2^32.
А>Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647
Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?
Уникальный идентификатор строки
От:
Аноним
Дата:
27.12.05 13:25
Оценка:
Добрый день!
Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.
Кто что посоветует?
Благодарен заранее.
Re[2]: Уникальный идентификатор строки
От:
Аноним
Дата:
27.12.05 13:48
Оценка:
Mab>Очевидно, это требование выполнить невозможно, т.к. возможных строк больше, чем 2^32.
Я это понимаю, поэтому и спрашиваю возможное решение. Но видимо, здесь для произвольных строк решения нет, прийдется отталкиваться от структуры конкретных строк. У меня она такова: "5:1020,2460,0,1,1;2460,3900,0,0,1;3900,5340,0,1,1;5340,6780,0,1,1;6780,8220,0,1,1" — это пример. Т.е. одни цифры, запятые и точки с запятой. Длина строки может меняться, но в среднем ок. 100 символов, и редко превышает 150.
Mab>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?
А что такое распределение на строках?
Здравствуйте, Аноним, Вы писали:
Mab>>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет? А>А что такое распределение на строках?
Ну как бы Вы оперируете термином "вероятность", значит и про распределения вероятностей должны знать... Для того, чтобы понять, какова вероятность колиизии, нужно знать, с какой вероятностью встречается каждая строка у Вас во входных данных.
Пока что Вы представили два формальных требования (отсутствие коллизий и верхняя оценка на вероятность таковых), которые выглядят без дополнительной информации весьма загадочно.
Здравствуйте, Аноним, Вы писали:
А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.
Гораздо большую — это какую? (На твоём наборе). Вот, скажем, CRC32.
Здравствуйте, Аноним, Вы писали:
А>Добрый день! А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек. А>Кто что посоветует? А>Благодарен заранее.
Если набор строк известен, то можно найти такую хэш-функцию. Гуглить по словам perfect hashing, начать можно отсюда
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, Аноним, Вы писали:
Mab>>>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет? А>>А что такое распределение на строках? Mab>Ну как бы Вы оперируете термином "вероятность", значит и про распределения вероятностей должны знать... Для того, чтобы понять, какова вероятность колиизии, нужно знать, с какой вероятностью встречается каждая строка у Вас во входных данных.
Что такое распределение вероятностей я знаю, просто не понял, что Вы имели в виду именно его. Распредения для этого типа строк я не знаю, но знаю, что числа в строках не превышают 90000. Видимо, исходя из этого прийдется сочинять алгоритм.
Re[2]: Уникальный идентификатор строки
От:
Аноним
Дата:
27.12.05 14:17
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Гораздо большую — это какую? (На твоём наборе). Вот, скажем, CRC32.
На моем наборе — не считал, т.к. у меня нет полного набора строк. Теоретически для произвольных строк — примерно 1/2^16.
К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать?
Здравствуйте, Аноним, Вы писали:
А>На моем наборе — не считал, т.к. у меня нет полного набора строк. Теоретически для произвольных строк — примерно 1/2^16.
Опять же, Вы оперируете числами, называя их 'вероятностями', причем делаете это весьма странным образом. Не нужно так делать.
Возможно Вы имели в виду, что у Вас хешфункция 16-битная?
А>К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать? www.google.com: crc-32 algorithm
Re[2]: Уникальный идентификатор строки
От:
Аноним
Дата:
27.12.05 14:25
Оценка:
Здравствуйте, Trean, Вы писали:
T>Если набор строк известен, то можно найти такую хэш-функцию. Гуглить по словам perfect hashing, начать можно отсюда
T>Bob Jenkins
Тут набор строк можно получить, только рассмотрев все возможные числовые комбинации — боюсь, это будет слишком большой набор. В любом случае, большое спасибо, наверняка это пригодится в другой раз!
Re[4]: Уникальный идентификатор строки
От:
Аноним
Дата:
27.12.05 14:31
Оценка:
Здравствуйте, Mab, Вы писали:
Mab>Возможно Вы имели в виду, что у Вас хешфункция 16-битная?
Именно это.
Здравствуйте, Аноним, Вы писали:
А>Добрый день! А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек. А>Кто что посоветует? А>Благодарен заранее.
А>>К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать? Mab>www.google.com: crc-32 algorithm