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 つの文字列の類似性は、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

Soundex 関数を辞書キーとして使用してみてはいかがでしょうか。

于 2013-02-13T21:35:01.500 に答える
0

__getitem__あなたの関係は1:1ではないので、可能なアイテムのリストを返すことができる再定義された独自のdictタイプを定義することができます。これが私が意味することです：

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 メソッドも再定義する必要があります。また、リストの代わりに1つのアイテムのみを返す場合は、 @ Emmanuelの回答が非常に役立ちます。そうすれば、すべてを再定義する必要がなくなります。

于 2013-02-13T16:26:31.550 に答える