Как хешировать строки в python для соответствия в пределах 1 символа?

Я читал о хешировании LSH, и мне интересно, какая реализация лучше всего подходит для сопоставления строк в пределах 1 символа?

test = {'dog':1, 'cat': 2, 'eagle': 3} 

test['dog']
>> 1

Я бы также хотел вернуть 1, если я ищу test['dogs'] или test['dogg']. Я понимаю, что он также вернул бы 1, если бы я искал «журнал» или «ког», но я могу написать метод, исключающий эти результаты.

Кроме того, как я могу использовать этот метод для общих строк, чтобы он возвращал совпадение в пределах X символов?

string1 = "brown dogs"
string2 = "brown doggie"

Предполагая, что в моем словаре хранится только строка1, поиск строки2 вернет строку1.

Спасибо


python string search hash
person nyc0202034    schedule 13.02.2013    source источник
comment
Короче говоря, вы не можете. Хэш-таблицы — неподходящий инструмент для этого.   -  person    schedule 13.02.2013
comment
Это не сработает, потому что то, что вы описываете, не является отношением эквивалентности.   -  person SLaks    schedule 13.02.2013
comment
Итак, вы пытаетесь получить значение ключа, наиболее похожего на данный ключ? Это правильно?   -  person freakish    schedule 13.02.2013
comment
@SLaks Я не знаю, какое отношение эквивалентности имеет к этому отношение.   -  person freakish    schedule 13.02.2013
comment
@freakish: сравнение ключей (хеш-функция) для хеш-таблиц должно быть отношением эквивалентности.   -  person SLaks    schedule 13.02.2013
comment
@SLaks Хорошо. Но сравнение по сходству является отношением эквивалентности (хотя зависит от определения сходства). Думаю, нам нужно больше информации по этому вопросу.   -  person freakish    schedule 13.02.2013
comment
Я уверен, что вы могли бы реализовать класс отображения на основе LSH в Python, это язык общего назначения. Если у вас есть проблемы с тем, чтобы заставить его работать, вернитесь с конкретной проблемой.   -  person martineau    schedule 13.02.2013
comment
@freakish: Нет, это не так. abc == abd и abz == xbz, но abc != xbz.   -  person SLaks    schedule 13.02.2013

Ответы (3)


arrow_upward
1
arrow_downward

Что ж, вы можете определить сходство между двумя строками по длине их общего начала (например, 3 для doga и dogs). Это упрощенно, но это может соответствовать вашим потребностям.

С этим предположением вы можете определить это:

>>> test = {'dog':1, 'cat': 2, 'eagle': 3}
>>> def same_start(s1, s2):
    ret = 0
    for i in range(min(len(s1), len(s2))):
        if s1[i] != s2[i]:
            break
        ret += 1
    return ret

>>> def closest_match(s):
    return max(((k, v, same_start(k, s)) for k, v in test.iteritems()), key=lambda x: x[2])[1]

>>> closest_match('dogs')  # matches dog
1
>>> closest_match('cogs')  # matches cat
2
>>> closest_match('eaogs') # matches eagle
3
>>>
person Emmanuel    schedule 13.02.2013

arrow_upward
0
arrow_downward

Может быть, вы могли бы попробовать использовать функцию Soundex в качестве ключа словаря?

person LAK    schedule 13.02.2013

arrow_upward
0
arrow_downward

Поскольку ваше отношение не 1: 1, возможно, вы могли бы определить свой собственный тип dict с переопределенным __getitem__, который мог бы вернуть список возможных элементов. Вот что я имею в виду:

class MyDict(dict):
  def __getitem__(self, key):
    l = []
    for k, v in self.items():
      if key.startswith(k): # or some other comparation method
        l.append(v)
    return l

Это просто идея, вероятно, следует переопределить и другие методы dict, чтобы избежать возможных ошибок или бесконечных циклов. Кроме того, здесь может быть очень полезен @Emmanuel answer, если вы хотите, чтобы вместо списка возвращался только один элемент, и таким образом вы не пришлось бы все переопределять.

person tomcaa    schedule 13.02.2013