Algoritma yang efisien untuk mencari kumpulan pohon

9

Saya memiliki dataset pohon yang besar dan saya ingin mencarinya dengan menentukan treelet (subgraph yang terhubung). Kueri harus mengembalikan semua kemunculan treelet dalam dataset.

Apakah ada algoritma yang efisien untuk melakukannya?

Saya sedang memikirkan sesuatu seperti susunan sufiks, namun, secara naif menyandikan pohon sebagai string (dengan pemesanan traversal yang tetap pada node-node mereka) tidak akan berfungsi, karena lubang pencarian dapat berbentuk sembarang bentuk.

MEMPERBARUI:

Beberapa detail tentang contoh khas yang saya harapkan:

Dataset akan terdiri dari setidaknya puluhan ribu pohon, masing-masing terdiri dari sekitar dua puluh hingga tiga puluh node. Pohon-pohon tidak akan biner, tetapi jumlah anak-anak khas per node akan kecil (biasanya tidak lebih besar dari empat atau lima, meskipun dalam beberapa kasus degenerasi dapat mencapai sekitar tiga puluh). Jumlah label akan mencapai puluhan ribu.

Saya memerlukannya untuk aplikasi NLP: setiap pohon akan menjadi parse dependensi dari sebuah kalimat, setiap node mewakili kata occourrence dan setiap label kata kamus (dengan beberapa dekorasi).

Antonio Valerio Miceli-Barone
sumber
1
Volume ini menampilkan diskusi tentang algoritma paralel untuk isomorfisma subtree.
Anthony Labarre
1
Maaf, saya pikir Anda sedang mencari subgraf yang terhubung, yang tentu saja akan menjadi pohon, muncul dalam kumpulan pohon tertentu. Bisakah Anda mengklarifikasi dalam aspek apa masalah Anda berbeda dari deskripsi ini?
Anthony Labarre
1
Apakah Anda tahu sesuatu tentang pohon sebelumnya? Biner? Berapa banyak label simpul yang berbeda yang Anda harapkan? Adakah batasan efisiensi ruang? Saya bertanya karena jika Anda menjalankan banyak pertanyaan pada dataset yang sama, solusi dapat melibatkan beberapa jenis pengindeksan agresif.
Eli
1
Apakah Anda terbiasa dengan pencocokan ranting XML? Masalah Anda tampaknya merupakan kasus khusus, sehingga Anda dapat menggunakan algoritme dan perangkat lunak yang ada.
Marek Chrobak
2
Saya kira mungkin lebih baik untuk mengabaikan struktur grafik. Dengan kueri yang khas, jika Anda membuang struktur, berapa pohon yang Anda antisipasi memiliki semua kata-kata ini? Apakah pertanyaan Anda memiliki wildcard atau tepat? Jika kata-kata dalam kueri seperti "Kucing memakan topi", berapa banyak grafik yang benar-benar memiliki kata "kucing" dan "topi" di dalamnya? Jika Anda hanya mengindeks setiap kata ke satu set pohon, lalu memotong semua set, berpotensi Anda bisa mencari hasilnya secara naif tanpa mengeluarkan terlalu banyak biaya.
Eli

Jawaban:

3

Meskipun tidak secara khusus ditujukan pada pohon (yang di-root), saya pikir struktur data G-trie mungkin berkinerja cukup baik di pengaturan Anda. Ini adalah adaptasi dari trie (untuk mencari set string) ke grafik.

Joshua Grochow
sumber
1

Beberapa waktu yang lalu saya menulis algoritma kanonisasi pohon Ronald Read dan meletakkannya di wikipedia .

Saya akan membuat hashtabel untuk masing-masing tanda tangan simpul internal, dan label mereka dengan daftar pointer kembali ke subtree mereka berasal. Namun, itu hanya akan bekerja untuk pohon dengan daun asli.

Chad Brewbaker
sumber