Мне нужна функция, которая дает аналогичные входные данные возвращает аналогичные индексы

Question

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

Пример:

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

что было бы хорошим подходом для достижения этого?Я использую Python.

Answer 1

То, что вы просите, невозможно, предполагая, что под «похожим хешем» вы подразумеваете, что значения должны быть одинаковой величины - например, 12345 аналогично 12346, но не 92345. Причина этого в том, что сходствоэта сортировка является одномерной (числовая линия), но способы, которыми строки могут быть похожи друг на друга, не имеют фиксированного измерения (например, «foo», «fob» и «fod» имеют расстояние 1 друг от друга).

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

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

Answer 2

Я полагаю, что приведенное ниже соответствует вашим заявленным требованиям.

def gethash(data):
  u"given a character string return an integer hash value"
  return reduce(lambda b1, b2: (b1 << 8) + b2,
      imap(ord, unicodedata.normalize('NFC', data).encode('UTF-8')))

По сути, значение хеш-функции представляет собой полное двоичное значение кодированных в UTF-8 байтовых значений ввода в виде единого целого числа. Подобные символьные строки производят хеш-значения с одинаковыми битами (не всегда с небольшой вычитающей разницей, но вы не указали это). Нормализация приводит к тому, что строки u'A\u030a' и u'\xc5' имеют одинаковое значение хеш-функции.

Если вы хотите ограничить максимальное значение, просто примените деление по модулю (возможно на 2 ^ 32) в качестве последнего шага.

Answer 3

Если вы уверены, что у вас всегда есть буквенно-цифровые данные, я бы порекомендовал использовать алгоритм base 36 (или выше).

Вы можете использовать метод, который я дал в качестве ответа на этот вопрос: Преобразование Base 62

import string
BASE_LIST = string.digits + string.letters
BASE_DICT = dict((c, i) for i, c in enumerate(BASE_LIST))

def base_decode(string, reverse_base=BASE_DICT):
    length = len(reverse_base)
    ret = 0
    for i, c in enumerate(string[::-1]):
        ret += (length ** i) * reverse_base[c]

    return ret

def base_encode(integer, base=BASE_LIST):
    length = len(base)
    ret = ''
    while integer != 0:
        ret = base[integer % length] + ret
        integer /= length

    return ret

Пример использования:

for i in range(100):                                    
    print i, base_decode(base_encode(i)), base_encode(i)