Struktur data peta yang efisien mendukung perkiraan pencarian

Saya mencari struktur data yang mendukung pencarian kunci yang efisien (misalnya, jarak Levenshtein untuk string), mengembalikan kecocokan terdekat yang mungkin untuk kunci input. Struktur data yang paling cocok yang saya temukan sejauh ini adalah pohon Burkhard-Keller , tapi saya bertanya-tanya apakah ada struktur data lain / lebih baik untuk tujuan ini.

Sunting: Beberapa detail lebih lanjut dari kasus spesifik saya:

String biasanya memiliki perbedaan Levenshtein yang cukup besar satu sama lain.
String memiliki panjang maksimal sekitar 20-30 karakter, dengan rata-rata mendekati 10-12.
Saya lebih tertarik pada pencarian efisien daripada penyisipan karena saya akan membangun satu set sebagian besar data statis yang ingin saya tanyakan secara efisien.

data-structures strings efficiency Merijn
sumber

Apakah ada kondisi pada string input, dan ukuran jumlah item dalam peta? Seberapa efisien penyisipan ke peta harus?

edA-qa mort-ora-y

mrm, sejauh yang saya tahu BK-pohon masih melihat sebagian besar dari seluruh pohon. Tapi itu mungkin optimasi prematur di pihak saya, saya kira?

merijn

Terkait erat dengan titik hampir menjadi duplikat: Struktur data yang efisien untuk membangun pemeriksa ejaan cepat

Raphael

Jarak Levenshtein cepat dan mudah menggunakan Trie

BlueRaja - Danny Pflughoeft

Jawaban:

Apa yang Anda cari adalah "perkiraan pencarian tetangga dekat" (JST) di Levenshtein / edit jarak. Dari perspektif teoritis, jarak sunting sejauh ini ternyata relatif sulit untuk pencarian tetangga dekat, afaik. Namun, ada banyak hasil, lihat referensi dalam makalah Ostrovsky dan Rabani ini . Jika Anda ingin mempertimbangkan metrik jarak alternatif yang ada solusinya lebih sederhana dan lebih baik, lanjutkan ke paragraf berikutnya. Untuk ANNS dalam jarak sunting, ada hasil karena Indyk , yang menunjukkan bagaimana membangun struktur data berukuran yang menjawab pertanyaan apa pun dalam waktu dan melaporkan string yang paling banyak tiga kali lebih jauh dari string terdekat ke string kueri (ini menggeneralisasi ke ukuran $n^{O(\sqrt{d})}$ $O(d)$ $n^{O(d^\epsilon)}$ dan perkiraan ). Di sini adalah jumlah string dan adalah panjang maksimum string apa pun. Makalah Ostrovsky dan Rabani yang saya atas meningkatkan hasil ini dengan memetakan string ke vektor sehingga -distance (semacam jarak geometris alami yang mirip dengan jarak euclidean) antara vektor mendekati jarak edit antara string yang sesuai (ini disebut "embedding distorsi rendah"). Setelah ini selesai, struktur data ANNS untuk dapat digunakan, dan ini menjadi lebih efisien (lihat paragraf berikutnya). $3^{1/\epsilon}$ $n$ $d$ $\ell_1$ $\ell_1$

Jika Anda ingin mempertimbangkan jarak lain, maka hashing sensitifitas lokalitas (LSH) melakukan pekerjaan yang baik. Hashing sensitif lokalitas adalah teknik yang dipelopori oleh Indyk dan Motwani untuk memecahkan masalah JST, di mana titik-titik yang hidup dalam ruang dimensi tinggi (baca vektor panjang, string panjang, dll.) Disatukan ke dalam sejumlah kecil ember sehingga menunjukkan bahwa berdekatan satu sama lain dipetakan ke nampan yang sama dengan probabilitas yang baik dan poin yang jauh dari satu sama lain dipetakan ke tempat sampah yang berbeda, juga dengan probabilitas yang baik. Ada artikel survei yang hebat dan sangat mudah diakses oleh Indyk dan Andoni di CACM . Teknik ini sederhana dan cepat, dan memiliki kebutuhan ruang yang kecil; ada kode di luar sana juga (saya pikir artikel tersebut terhubung ke kode). Ini bekerja dengan baik untuk hal-hal seperti jarak Hamming (dan dalam rezim tertentu) jarak) dan jarak Euclidean, jarak cosinus. Juga,Muthu dan Sahinalpmerancang skema LSH untuk generalisasi yang sangat alami dari jarak edit,jarak edit blok(di mana beberapa operasi edit dapat beroperasi pada blok simbol). $\ell_1$

Pertanyaan semacam ini sangat cocok untuk cstheory.SE . Ada pertanyaan terkait di sana , tetapi tampaknya menanyakan persis tetangga dekat.

Sasho Nikolov
sumber

Struktur data yang Anda minati adalah pohon metrik. Artinya, mereka mendukung pencarian efisien dalam ruang metrik. Ruang metrik dibentuk oleh seperangkat objek dan fungsi jarak yang didefinisikan di antara mereka yang memenuhi ketimpangan segitiga. Tujuannya kemudian, diberikan satu set objek dan elemen permintaan, untuk mengambil objek-objek itu cukup dekat dengan permintaan.

Karena masalah pencarian benar-benar ada di mana-mana dalam ilmu komputer, ada sejumlah besar pohon metrik yang berbeda. Namun, mereka dapat dibagi setidaknya menjadi dua kelompok: pivot-based dan clustering-based (dan tentunya ada hibrida juga). Survei yang bagus adalah E. Chavez et al., Searching in Metric Spaces, 2001 . Lihat misalnya Bab 5: Solusi Saat Ini untuk Ruang Metrik, halaman 283.

$O(n^\alpha)$ $0 < \alpha < 1$ $O(n^2)$ $O(1)$

Chavez et al. juga memberikan gambaran yang bagus tentang pohon-pohon lain, dan tentu saja lebih banyak referensi jika ada orang yang tertarik pada Anda. Dalam praktiknya, kinerja berbagai pohon sering dievaluasi secara eksperimental. Ini menurut saya sangat tergantung pada struktur ruang. Karena itu sulit untuk mengatakan pohon mana yang paling efisien dalam kasus Anda. Namun demikian, saya pikir itu ide yang baik untuk pergi dengan yang termudah dulu. Jika pohon BK adalah yang paling mudah dibangun, cobalah terlebih dahulu. Jika mereka tidak memenuhi persyaratan Anda, investasikan waktu (dan mungkin waktu pemrograman) untuk mengumpulkan lebih banyak fakta tentang ruang Anda yang dapat membantu Anda membuat keputusan yang lebih tepat.

Juho
sumber