Pertanyaan Menemukan bagaimana dua senar serupa


Saya mencari algoritma yang mengambil 2 string dan akan memberi saya kembali "faktor kesamaan".

Pada dasarnya, saya akan memiliki masukan yang mungkin salah eja, memiliki surat yang dialihkan, dll, dan saya harus menemukan kecocokan terdekat dalam daftar nilai yang mungkin saya miliki.

Ini bukan untuk mencari di database. Saya akan memiliki daftar di memori sebanyak 500 string untuk melawan, semua di bawah 30 karakter, sehingga bisa relatif lambat.

Saya tahu ini ada, saya pernah melihatnya sebelumnya, tetapi saya tidak ingat namanya.


Edit: Terima kasih telah menunjukkan Levenshtein dan Hamming. Sekarang, mana yang harus saya terapkan? Mereka pada dasarnya mengukur hal-hal yang berbeda, yang keduanya dapat digunakan untuk apa yang saya inginkan, tetapi saya tidak yakin mana yang lebih tepat.

Saya sudah membaca tentang algoritme, Hamming jelas lebih cepat. Karena tidak akan mendeteksi dua karakter yang dialihkan (mis. Jordan dan Jodran), yang saya percaya akan menjadi kesalahan umum, yang akan lebih akurat untuk apa yang saya inginkan? Bisakah seseorang menceritakan sedikit tentang trade-off?


32
2018-02-23 12:18


asal


Jawaban:


Oke, jadi algoritma standarnya adalah:

1) Jarak Hamming  Hanya bagus untuk string dengan panjang yang sama, tetapi sangat efisien. Pada dasarnya itu hanya menghitung jumlah karakter yang berbeda. Tidak berguna untuk pencarian fuzzy teks bahasa alami.

2) Jarak Levenstein. Jarak Levenstein mengukur jarak dalam hal jumlah "operasi" yang dibutuhkan untuk mengubah satu string ke string lainnya. Operasi ini termasuk penyisipan, penghapusan dan substitusi. Pendekatan standar menghitung jarak Levenstein adalah menggunakan pemrograman dinamis.

3) Generalized Levenstein / (Damerau-Levenshtein jarak) Jarak ini juga mempertimbangkan transposisi karakter dalam satu kata, dan mungkin merupakan jarak pengeditan yang paling cocok untuk pencocokan fuzzy teks yang dimasukkan secara manual. Algoritma untuk menghitung jarak sedikit lebih terlibat daripada jarak Levenstein (mendeteksi transposisi tidak mudah). Implementasi yang paling umum adalah modifikasi dari bitap algoritma (seperti grep).

Secara umum Anda mungkin ingin mempertimbangkan implementasi opsi ketiga yang diimplementasikan dalam semacam pencarian tetangga terdekat berdasarkan pohon k-d


33
2018-02-23 13:00



  • Jarak Levenstein
  • Jarak Hamming
  • soundex
  • metafora

3
2018-02-23 12:25



itu Jarak Damerau-Levenshtein mirip dengan jarak Levenshtein, tetapi juga mencakup transposisi dua karakter. halaman wikipedia (tertaut) termasuk pseudocode yang seharusnya cukup sepele untuk diterapkan.


3
2018-02-23 12:55



Anda sedang mencari Jarak Levenshtein


2
2018-02-23 12:23