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).
sumber
Jawaban:
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.
sumber
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.
sumber