алгоритм преобразования путевого имени в уникальный номер

Question

Я хочу преобразовать путь к Windows в уникальное целое число.

Например:

Для пути C: \ temp \ a.out, если я добавлю ascii значение всех символов, я получу 1234. Но какой-то другой путь также может генерировать то же число. Итак, каков наилучший способ создания уникальных чисел для разных путей?

Answer 1

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

Скорее всего, используемый вами язык предоставляет библиотечную функцию (или набор функций), которая может принимать хеш строки (или только данные). SHA1 популярен и имеет низкое столкновение.

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

Answer 2

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

Answer 3

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

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

Answer 4

Идеальное хеширование

Answer 5

Как насчет чего-то вроде этого: Используйте хэш (String-> n битов) для каждого уровня каталога. Выделение 20 битов для каждого из 10 уровней каталогов явно не масштабируется, но, возможно, телескопический уровень битов при условии, что самый низкий уровень каталогов будет самым заполненным -

например. если у вас есть (от корня) / A / B / C / D / E / F, вывести какое-то n-битное число, где

биты n / 2 - n хэшей F

биты n / 4 - n / 2 бит хэши E

n / 8 - n / 4-битные хэши D

и т.д.. и т. д.

Answer 6

Вы можете прочитать здесь Лучший способ определить, есть ли две пути ссылки на один и тот же файл в C # , как можно однозначно определить путь. Вам нужны три числа (dwVolumeSerialNumber, nFileIndexHigh и nFileIndexLow), может быть, вы можете объединить эти три числа в новое число с битами в три раза больше. Смотрите также здесь: Какие ваши любимые методы расширения для C #? (codeplex.com/extensionoverflow).

Answer 7

Джимми Саид

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

Я не думаю, что есть больше возможных имен путей, чем целые числа. В качестве конструкции для создания уникального числа из имени пути мы можем преобразовать каждую букву в (двузначное) число (то есть из 10-25,26 =., Затем другие специальные символы и 27, являющиеся / - это предполагает, что там меньше 89 разных символов, иначе мы можем перейти к трехзначной кодировке)

home/nlucaroni/documents/cv.pdf
1724221427232130121027242318271324122827123136251315

Это формирует биекцию (хотя, если вы подсчитываете только допустимые имена путей, свойство сюръектива терпит неудачу, но обычно это не заботит удержание) - Придумайте путь, который не целое число.

Это число явно не вписывается в 64-разрядное целое число без знака (макс. 18446744073709551615), поэтому оно не практично, но это не точка моего ответа.

Answer 8

Для всех людей, говорящих «это невозможно, потому что у вас есть больше возможных путей, чем целых чисел для их хранения»: нет. На плакате никогда не указывался язык реализации; некоторые языки поддерживают числа произвольной длины. Python, например.

Скажем, мы берем 32 000 символьных путей в качестве предела, упомянутого в одном из других комментариев. Если у нас есть 256 различных символов для использования с путями, мы получим:

Python 2.5.1 (r251:54863, May 18 2007, 16:56:43)
[GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 32000L**256L
20815864389328798163850480654728171077230524494533409610638224700807216119346720596024478883464648369684843227908562015582767132496646929816279813211354641525848259018778440691546366699323167100945918841095379622423387354295096957733925002768876520583464697770622321657076833170056511209332449663781837603694136444406281042053396870977465916057756101739472373801429441421111406337458176000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>>

Заметьте, как Python отлично это представляет? Да, возможно, есть лучший способ сделать это, но это не значит, что это невозможно.

РЕДАКТИРОВАТЬ: rjack указал, что это на самом деле 256 ^ 32000, а не наоборот. Python по-прежнему справляется с этим просто отлично. Спектакль может оставить желать лучшего, но сказать, что это математически невозможно, неправильно.

Answer 9

Если это в Unix, вы можете просто получить его номер инода. ls -i показывает это в командной строке. Команда stat () позволяет извлечь его из программы.

Мягкие ссылки отображаются как один и тот же файл, а жесткие ссылки отображаются как другой файл. Это может или не может быть поведение, которое вы хотите.

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