Bagaimana cara hash string dalam python agar cocok dalam 1 karakter?

Saya telah membaca tentang hashing LSH dan saya bertanya-tanya implementasi apa yang terbaik untuk mencocokkan string dalam 1 karakter?

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

test['dog']
>> 1

Saya juga ingin mengembalikan 1 jika saya mencari test['dogs'] atau test['dogg']. Saya menyadari bahwa itu juga akan menghasilkan 1 jika saya mencari "log" atau "roda gigi", tetapi saya dapat menulis metode untuk mengecualikan hasil tersebut.

Juga bagaimana saya bisa melanjutkan metode ini agar string umum mengembalikan kecocokan dalam karakter X?

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

Dengan asumsi hanya string1 yang disimpan dalam kamus saya, pencarian string2 akan mengembalikan string1.

Terima kasih


python string search hash
person nyc0202034    schedule 13.02.2013    source sumber
comment
Singkatnya, Anda tidak bisa. Tabel hash adalah alat yang salah untuk ini.   -  person    schedule 13.02.2013
comment
Itu tidak akan berhasil, karena yang Anda gambarkan bukanlah relasi ekivalensi.   -  person SLaks    schedule 13.02.2013
comment
Jadi, apakah Anda mencoba mendapatkan nilai kunci yang paling mirip dengan kunci tertentu? Apakah itu benar?   -  person freakish    schedule 13.02.2013
comment
@SLaks Saya tidak tahu apa hubungan kesetaraan dengan itu.   -  person freakish    schedule 13.02.2013
comment
@freakish: Perbandingan kunci (fungsi hash) untuk tabel hash harus berupa relasi ekivalensi.   -  person SLaks    schedule 13.02.2013
comment
@SLaks oke. Namun membandingkan berdasarkan kesamaan adalah merupakan hubungan kesetaraan (meskipun demikian bergantung pada definisi kesamaan). Saya kira kita memerlukan lebih banyak info untuk pertanyaan itu.   -  person freakish    schedule 13.02.2013
comment
Saya yakin Anda bisa mengimplementasikan kelas pemetaan berbasis LSH dengan Python, ini adalah bahasa tujuan umum. Jika Anda memiliki masalah dalam menjalankannya, kembalilah dengan masalah nyata.   -  person martineau    schedule 13.02.2013
comment
@freakish: Tidak, tidak. abc == abd, dan abz == xbz, tetapi abc != xbz.   -  person SLaks    schedule 13.02.2013

Jawaban (3)


arrow_upward
1
arrow_downward

Nah, Anda dapat menentukan kesamaan antara 2 string berdasarkan panjang awal yang sama (3 untuk doga dan dogs, misalnya). Ini sederhana, tetapi sesuai dengan kebutuhan Anda.

Dengan asumsi ini, Anda dapat mendefinisikannya sebagai berikut:

>>> 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

Mungkin Anda bisa mencoba menggunakan fungsi Soundex sebagai kunci kamus Anda?

person LAK    schedule 13.02.2013

arrow_upward
0
arrow_downward

Karena relasi Anda bukan 1:1, mungkin Anda dapat menentukan tipe dict Anda sendiri dengan __getitem__ yang didefinisikan ulang yang dapat mengembalikan daftar item yang mungkin. Inilah yang saya maksud:

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

Ini hanyalah sebuah ide, mungkin metode dict lainnya juga harus didefinisikan ulang untuk menghindari kemungkinan kesalahan atau loop tak terbatas. Selain itu, jawaban@Emmanuel bisa sangat berguna di sini jika Anda hanya ingin satu item dikembalikan, bukan daftar, dan dengan begitu Anda tidak perlu mendefinisikan ulang segalanya.

person tomcaa    schedule 13.02.2013