Kompresi efisien pohon yang tidak berlabel

20

Pertimbangkan pohon biner yang tidak berlabel dan berakar. Kami dapat kompres pohon seperti: setiap kali ada pointer ke sub pohon dan dengan (menafsirkan kesetaraan struktural), kami menyimpan (wlog) dan mengganti semua pointer ke dengan pointer ke . Lihat jawaban uli sebagai contoh.T T = T = T T TTT=T=TTT

Berikan algoritma yang mengambil pohon dalam arti di atas sebagai input dan menghitung jumlah (minimal) node yang tersisa setelah kompresi. Algoritma harus dijalankan dalam waktu (dalam model biaya seragam) dengan jumlah node dalam input.nO(nlogn)n

Ini merupakan pertanyaan ujian dan saya belum dapat menemukan solusi yang bagus, saya juga belum melihatnya.

Raphael
sumber
Dan apa "biaya", "waktu", operasi dasar di sini? Jumlah node yang dikunjungi? Jumlah tepi yang dilalui? Dan bagaimana ukuran input ditentukan?
uli
Kompresi pohon ini adalah turunan hash . Tidak yakin apakah itu mengarah ke metode penghitungan generik.
Gilles 'SO- stop being evil'
@ iuli saya menjelaskan apa itu . Saya pikir "waktu" cukup spesifik. Dalam pengaturan non-konkuren, ini setara dengan menghitung operasi yang dalam istilah Landau setara dengan menghitung operasi dasar yang paling sering terjadi. n
Raphael
@ Raphael Tentu saja saya bisa menebak apa operasi dasar yang seharusnya dan mungkin akan memilih yang sama seperti orang lain. Tapi, dan aku tahu aku jagoan di sini, setiap kali "batas waktu" diberikan, penting untuk menyatakan apa yang sedang dihitung. Apakah itu swap, membandingkan, penambahan, akses memori, node diperiksa, tepi dilalui, apa saja. Ini seperti menghilangkan satuan pengukuran dalam fisika. Apakah atau ? Dan saya kira akses memori hampir selalu merupakan operasi yang paling sering. 1010kg10ms
uli
@uli Ini adalah jenis rincian yang seharusnya disampaikan oleh “model biaya seragam”. Sangat menyakitkan untuk mendefinisikan dengan tepat operasi apa yang elementer, tetapi dalam 99,99% kasus (termasuk yang ini) tidak ada ambiguitas. Kelas kompleksitas pada dasarnya tidak memiliki unit, mereka tidak mengukur waktu yang diperlukan untuk melakukan satu contoh tetapi cara kali ini bervariasi karena input semakin besar.
Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

10

Ya, Anda dapat melakukan kompresi ini dalam waktu , tetapi itu tidak mudah :) Pertama-tama kita membuat beberapa pengamatan dan kemudian menyajikan algoritma. Kami menganggap pohon tersebut awalnya tidak dikompresi - ini tidak benar-benar diperlukan tetapi membuat analisis lebih mudah.O(nlogn)

Pertama, kami mencirikan 'kesetaraan struktural' secara induktif. Biarkan dan menjadi dua (sub) pohon. Jika dan keduanya pohon nol (tidak memiliki simpul sama sekali), mereka secara struktural setara. Jika dan keduanya bukan pohon nol, maka mereka secara struktural setara jika anak-anak kiri mereka setara secara struktural dan anak-anak kanan mereka setara secara struktural. 'Kesetaraan struktural' adalah titik tetap minimal atas definisi-definisi ini.T T T T T TTTTTT

Sebagai contoh, setiap dua simpul daun secara struktural setara, karena mereka berdua memiliki pohon nol sebagai kedua anak-anak mereka, yang secara struktural setara.

Karena agak menjengkelkan untuk mengatakan 'anak-anak kiri mereka secara struktural setara dan begitu juga anak-anak mereka', kita akan sering mengatakan 'anak-anak mereka setara secara struktural' dan bermaksud sama. Perhatikan juga kita kadang mengatakan 'titik ini' ketika kita berarti 'subtree berakar pada titik ini'.

Definisi di atas segera memberi kita petunjuk bagaimana melakukan kompresi: jika kita mengetahui kesetaraan struktural semua sub-pohon dengan kedalaman paling banyak , maka kita dapat dengan mudah menghitung kesetaraan struktural dari sub-pohon dengan kedalaman . Kita harus melakukan perhitungan ini dengan cara yang cerdas untuk menghindari waktu berjalan .d + 1 O ( n 2 )dd+1O(n2)

Algoritme akan menetapkan pengidentifikasi untuk setiap titik selama eksekusi. Identifier adalah angka dalam set . Pengidentifikasi unik dan tidak pernah berubah: oleh karena itu kami menganggap kami menetapkan beberapa variabel (global) ke 1 pada awal algoritma, dan setiap kali kami menetapkan pengidentifikasi ke beberapa titik, kami menetapkan nilai saat ini dari variabel tersebut ke titik dan penambahan nilai variabel itu.{1,2,3,,n}

Kami pertama-tama mengubah pohon input menjadi (paling banyak ) daftar yang berisi simpul dengan kedalaman yang sama, bersama dengan pointer ke induknya. Ini mudah dilakukan dalam waktu O ( n ) .nO(n)

Pertama-tama kita mengompres semua daun (kita dapat menemukan daun-daun ini dalam daftar dengan simpul kedalaman 0) menjadi satu simpul tunggal. Kami menetapkan titik ini sebagai pengidentifikasi. Kompresi dua simpul dilakukan dengan mengarahkan induk dari salah satu simpul untuk menunjuk ke simpul lain sebagai gantinya.

Kami membuat dua pengamatan: pertama, setiap simpul memiliki anak-anak dengan kedalaman yang sangat kecil, dan kedua, jika kami telah melakukan kompresi pada semua simpul kedalaman yang lebih kecil dari (dan telah memberi mereka pengidentifikasi), maka dua simpul kedalaman d secara struktural setara dan dapat dikompresi jika pengidentifikasi anak-anak mereka bertepatan. Pengamatan terakhir ini mengikuti dari argumen berikut: dua simpul secara struktural setara jika anak-anak mereka setara secara struktural, dan setelah kompresi ini berarti pointer mereka menunjuk ke anak yang sama, yang pada gilirannya berarti pengidentifikasi anak-anak mereka sama.dd

Kami beralih melalui semua daftar dengan node dengan kedalaman yang sama dari kedalaman kecil ke kedalaman besar. Untuk setiap level kami membuat daftar pasangan bilangan bulat, di mana setiap pasangan sesuai dengan pengidentifikasi anak-anak dari beberapa titik pada tingkat itu. Kami memiliki dua simpul pada level tersebut yang secara struktural setara jika pasangan integer yang sesuai adalah sama. Dengan menggunakan pemesanan leksikografis, kita dapat mengurutkannya dan mendapatkan set pasangan integer yang sama. Kami memampatkan set ini ke simpul tunggal seperti di atas dan memberi mereka pengidentifikasi.

Pengamatan di atas membuktikan bahwa pendekatan ini bekerja dan menghasilkan pohon terkompresi. Total waktu berjalan adalah ditambah waktu yang dibutuhkan untuk mengurutkan daftar yang kami buat. Karena jumlah total pasangan integer yang kita buat adalah n , ini memberi kita bahwa total waktu berjalan adalah O ( n log n ) , seperti yang diperlukan. Menghitung berapa banyak node yang tersisa di akhir prosedur adalah sepele (lihat saja berapa banyak pengidentifikasi yang telah kami bagikan).O(n)nO(nlogn)

Alex ten Brink
sumber
Saya belum membaca jawaban Anda secara mendetail, tetapi saya pikir Anda kurang lebih telah menemukan kembali hash, dengan cara khusus yang aneh dalam mencari node.
Gilles 'SO- stop being evil'
@Alex "anak-anak dari tingkat yang sangat kecil degree" mungkin seharusnya depth? Dan meskipun CS-pohon tumbuh ke bawah, saya menemukan “ketinggian pohon” kurang membingungkan daripada “kedalaman pohon”.
uli
Jawaban bagus. Saya merasa harus ada cara untuk menyortir. Komentar kedua saya pada jawaban @Gilles juga berlaku di sini.
Raphael
@ rei: ya, Anda benar, saya sudah memperbaikinya (tidak yakin mengapa saya bingung dua kata). Tinggi dan kedalaman adalah dua konsep yang agak berbeda, dan saya membutuhkan yang terakhir :) Saya pikir saya akan tetap pada 'kedalaman' konvensional daripada membingungkan semua orang dengan menukar mereka.
Alex ten Brink
4

Mengkompresi struktur data yang tidak bisa diubah sehingga tidak menduplikasi subterm yang sama secara struktural dikenal sebagai hash consing . Ini adalah teknik penting dalam manajemen memori dalam pemrograman fungsional. Hash consing adalah semacam memoisasi sistematis untuk struktur data.

nO(nlg(n))

Saya akan menganggap pohon memiliki struktur berikut (ditulis di sini dalam sintaksis Haskell):

data Tree = Leaf
          | Node Tree Tree

nodes:T×TNTNT=N{}

Kita dapat menggunakan struktur data waktu logaritmik untuk nodes, seperti pohon pencarian biner seimbang. Di bawah ini saya akan memanggil lookup nodesoperasi yang mencari kunci dalam nodesstruktur data, dan insert nodesoperasi yang menambahkan nilai di bawah kunci baru dan mengembalikan kunci itu.

Sekarang kita melintasi pohon dan menambahkan node saat kita melanjutkan. Walaupun saya menulis dalam pseudocode mirip Haskell, saya akan memperlakukannya nodessebagai variabel global yang bisa berubah; kami hanya akan menambahkannya, tetapi sisipan perlu di utas seluruhnya. The addfungsi recurses di pohon, menambahkan sub pohon kepada nodespeta, dan mengembalikan identifier dari akar.

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

Jumlah insertpanggilan, yang juga merupakan ukuran akhir dari nodesstruktur data, adalah jumlah node setelah kompresi maksimum. (Tambahkan satu untuk pohon kosong jika diperlukan.)

Gilles 'SANGAT berhenti menjadi jahat'
sumber
nO(nlg(n))nodes
Saya hanya mempertimbangkan hashing substruktur ke angka dalam cara terstruktur sehingga secara mandiri menghitung hash untuk pohon yang sama akan selalu menghasilkan hasil yang sama. Solusi Anda juga baik-baik saja, asalkan kami memiliki struktur data yang dapat berubah di tangan kami. Saya pikir itu bisa dibersihkan sedikit, meskipun; interleaving insertdan addharus dibuat eksplisit dan fungsi yang sebenarnya memecahkan masalah harus diberikan, imho.
Raphael
1
@Raphael Hash yang bergantung pada struktur peta hingga tupel pointer / pengidentifikasi, Anda dapat menerapkannya dengan waktu logaritma untuk pencarian dan menambahkan (misalnya dengan pohon pencarian biner seimbang). Solusi saya tidak memerlukan mutabilitas; Saya membuat nodesvariabel yang bisa berubah untuk kenyamanan, tetapi Anda dapat memasangnya di seluruh. Saya tidak akan memberikan kode lengkap, ini bukan SO.
Gilles 'SANGAT berhenti menjadi jahat'
1
@Raphael Hashing structure, sebagai ganti menugaskan mereka angka acak, agak cerdik. Dalam model biaya seragam, Anda dapat menyandikan apa pun ke dalam bilangan bulat besar dan melakukan operasi waktu konstan di atasnya, yang tidak realistis. Di dunia nyata, Anda dapat menggunakan hash kriptografi untuk memiliki pemetaan satu-ke-satu secara de facto dari himpunan tak terbatas ke kisaran integer terbatas, tetapi mereka lambat. Jika Anda menggunakan non-crypto checksum sebagai hash, Anda perlu memikirkan tabrakan.
Gilles 'SANGAT berhenti menjadi jahat'
3

Berikut adalah ide lain yang bertujuan (secara injeksi) mengkodekan struktur pohon menjadi angka, bukan hanya memberi label secara sewenang-wenang. Untuk itu, kami menggunakan bahwa factorisation utama nomor apa pun adalah unik.

EN(l,r)lrN(E,E)

f(E)=0f(N(l,r))=2f(l)3f(r)

f

Asumsi terakhir ini adalah peregangan pada mesin nyata; dalam hal ini, seseorang akan lebih suka menggunakan sesuatu yang mirip dengan fungsi pemasangan Cantor daripada eksponensial.

O(nlogn)O(nlogn)

Raphael
sumber
1

Karena gambar tidak diperbolehkan dalam komentar:

masukkan deskripsi gambar di sini

kiri atas: pohon input

kanan atas: subpohon yang berakar pada node 5 dan 7 juga isomorfik.

kiri bawah dan kanan: pohon yang dikompresi tidak didefinisikan secara unik.

7+5|T|6+|T|

uli
sumber
Ini memang contoh operasi yang diinginkan, terima kasih. Perhatikan bahwa contoh terakhir Anda identik jika Anda tidak membedakan antara referensi asli dan yang ditambahkan.
Raphael
-1

Sunting: Saya membaca pertanyaan karena T dan T ′ adalah anak-anak dari orang tua yang sama. Saya mengambil definisi kompresi untuk menjadi rekursif juga, yang berarti Anda dapat mengompres dua subtree yang sebelumnya dikompresi. Jika itu bukan pertanyaan aktual, maka jawaban saya mungkin tidak berfungsi.

O(nlogn)T(n)=2T(n/2)+cn

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1    

Di mana hasSameStructure()ada fungsi yang membandingkan dua subtree yang telah dikompresi dalam waktu linier untuk melihat apakah mereka memiliki struktur yang sama persis. Menulis fungsi rekursif waktu linier yang melintasi masing-masing dan memeriksa apakah subtree memiliki anak kiri setiap kali yang lain lakukan dll seharusnya tidak sulit.

nnr

T(n)=T(n1)+T(n2)+O(1) if nnr
2T(n/2)+O(n) otherwise
Joe
sumber
Bagaimana jika subtree bukan saudara kandung? Perawatan untuk ((T1, T1), (T2, T1)) T1 dapat disimpan dua kali dengan menggunakan pointer dua kejadian ketiga.
uli
TT
Pertanyaan-pertanyaan hanya menyatakan bahwa dua subtress diidentifikasi sebagai isomorfik. Tidak ada yang dikatakan tentang mereka yang memiliki orang tua yang sama. Jika subtree T1 muncul tiga kali dalam pohon, seperti pada contoh saya sebelumnya ((T1, T1), (T1, T2)) dua kejadian dapat dikompresi dengan menunjuk ke orcurence ketiga.
uli