Pencocokan nama parsial dalam jutaan catatan

Kami telah mengembangkan aplikasi berbasis web untuk pencocokan nama. Ini beroperasi dengan memecah nama menjadi beberapa bagian dan nilai Soundex dari setiap bagian disimpan dalam database. The Levenshtein metrik jarak digunakan untuk menerapkan persentase pencocokan suara serta ejaan terhadap nama yang diberikan.

Saat runtime, kami memuat semua rekaman ke dalam memori dan menerapkan jarak Levenshtein ke semua nilai Soundex dan ejaan semua bagian dari semua nama.

Awalnya ini bekerja dengan baik karena ada maksimum 20 ribu nama, tetapi sekarang salah satu klien kami memiliki 30 juta nama. Memuat daftar besar ini dalam memori untuk setiap permintaan dan menerapkan jenis pencocokan ini adalah pendekatan yang menyedihkan, menggunakan banyak memori dan waktu eksekusi.

Kami sedang mencari saran untuk mencari di database 30 juta rekaman atau lebih dalam waktu dekat dengan pencocokan persentase Suara dan Ejaan.

Fungsi Inti

Pengguna akhir memasukkan nama untuk dicocokkan dan persentase minimum. Kami seharusnya menunjukkan semua nama dalam basis data yang setiap bagian dari nama tersebut cocok dengan bagian mana pun dari nama yang diberikan hingga persentase yang diberikan. Nama lengkap tidak harus dicocokkan, bagian apa pun jika cocok hingga persentase berhasil. Sebagai contoh.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Kedua bagian dari kedua nama tidak sama persis tetapi sampai batas tertentu, mari kita asumsikan 80%, jadi jika pengguna memasukkan 80% maka nama dalam DB harus ditampilkan sebagai nama yang cocok.

Tanpa mengetahui detail lengkap dari apa yang Anda butuhkan, Anda mungkin ingin melakukan salah satu dari yang berikut:

• Gunakan alat pencarian yang ada, seperti Sphinx atau Lucene
• Lakukan pencocokan perkiraan n-gram

Saya tidak sepenuhnya tahu apa yang terlibat menginstal dan mengkonfigurasi sphinx; tapi, saya mendapat kesan Anda bisa mengarahkannya ke database, kirim bidang mana yang akan diindeks, cara menimbang hasilnya, dan itu akan memberi Anda daftar catatan pencocokan yang dipesan kembali.

Untuk hal-hal penting yang dihadapi pengguna atau misi, gunakan alat pencarian yang ada.

Jika Anda hanya merasa akademis ... Mainkan dengan ngrams:

Tabel pencarian ngram dapat berfungsi sebagai set awal dari pencocokan potensial Anda, dan Anda dapat menggunakan jarak Levenshtein untuk memangkas dan mengurutkan hasilnya.

Dengan asumsi Anda ingin mencari people, Anda dapat melakukan sesuatu seperti:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Anda dapat membangun kembali ngram Anda secara berkala atau membuatnya secara langsung. Bagaimanapun, algoritma pencarian yang sederhana dan naif dapat terlihat seperti ini:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Menggunakan sesuatu yang mirip dengan ini (tetapi dengan penyetelan "popularitas" ngram yang lebih sedikit, daftar hitam, daftar putih, dll.), Saya telah melihat algoritma semacam ini menggabungkan catatan di antara kumpulan data secara massal, serta memfasilitasi pencarian fuzzy kustom utilitas dan catatan berkelanjutan upaya de-duplikasi.

Sekarang, dalam kasus saya, saya tidak cocok dengan jutaan catatan, saya mencari untuk memilih penggabungan terbaik antara dua set data pada urutan ratusan ribu catatan masing-masing. Dan, kami ingin ini bekerja cukup cepat - dalam beberapa menit. (Cepat, berapakah 100.000 * 100.000?) Dan, kami berhasil.

Jadi, dengan penyetelan yang benar, hal semacam ini bisa cepat dan efektif. Kami pada akhirnya dapat menghasilkan set gabungan pada mesin dual-core yang sederhana, kuno, dalam beberapa menit, dengan penggabungan "dipertanyakan" secara otomatis ditandai untuk peninjauan manual. Tapi, butuh banyak waktu untuk menemukan ngram popularitas / relevansi sweet-spot, dan ambang batas jarak string yang tepat, dan daftar hitam, dan daftar putih ... dll.

BILANG BAHWA , Anda benar-benar bisa tersedot ke dalam lubang mengerjakan hal ini. Untuk hal-hal tingkat produksi dunia nyata, Anda umumnya harus menggunakan alat mapan yang sudah dibuat dan dioptimalkan untuk pencarian seperti ini.

Seperti Sphinx atau Lucene .