0

我已经阅读了有关 LSH 散列的信息，并且想知道在 1 个字符内匹配字符串的最佳实现是什么？

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

test['dog']
>> 1

如果我查找 test['dogs'] 或 test['dogg']，我也想返回 1。我意识到如果我要查找“log”或“cog”它也会返回 1，但我可以编写一个方法来排除这些结果。

另外，如何进一步使用此方法使一般字符串返回 X 个字符内的匹配项？

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

假设我的字典中只存储了 string1，那么查找 string2 将返回 string1。

谢谢

4

3 回答 3

1

好吧，您可以通过它们共有的开头长度来定义 2 个字符串之间的相似性（例如， 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
>>>
于 2013-02-13T15:57:34.337 回答
0

由于您的关系不是 1:1，也许您可​​以使用 redefined 定义自己的 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 的答案在这里可能非常有用，这样您就不必重新定义所有内容。

于 2013-02-13T16:26:31.550 回答
0

也许您可以尝试使用 Soundex 函数作为您的字典键？

于 2013-02-13T21:35:01.500 回答