Pecahkan teks secara merata menjadi beberapa baris

Ada algoritma waktu linear untuk memecah teks menjadi garis dengan lebar maksimum. Ini menggunakan SMAWK (atau Knuth & Plass) dan "merata" berarti: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Apakah ada algoritme atau fungsi biaya cekung untuk algoritme di atas yang akan mempertimbangkan jumlah baris yang saya inginkan untuk perincian teks, alih-alih lebar garis maksimum? Juga dalam waktu linier?

Dengan kata lain, saya mencari algoritma pemecah garis (atau pembentukan paragraf, atau pembungkus kata) di mana inputnya adalah jumlah baris yang diinginkan, bukan lebar baris yang diinginkan.

Hanya untuk menggambarkan pendekatan praktis yang tidak dapat digunakan: Ada N kata dan N-1 spasi di antara setiap pasangan kata, M adalah jumlah baris yang diinginkan (M <= N). Setelah setiap ruang mungkin ada paling banyak satu (mungkin nol) line-break. Sekarang, algoritma akan mencoba untuk menempatkan jeda di setiap kombinasi yang mungkin, menghitung "raggedness" dan mengembalikan yang terbaik. Bagaimana cara melakukannya dengan lebih cepat?

Juga, apakah masalah seperti itu memiliki nama? "Keluarga" masalah apa itu? (Mis. "Tempat sampah") Jika saya tidak membutuhkan solusi optimal yang sempurna, hanya yang sangat bagus, apakah mungkin untuk menyelesaikannya lebih cepat? (beberapa bentuk heuristik dapat digunakan, jika untuk input yang diberikan selalu ada solusi yang sama, mungkin kurang optimal).

Memperbarui

Chandra Chekuri menyarankan di bawah "masalah dalam bab Kleinberg dan Tardos pada pemrograman dinamis". Itu bacaan yang bagus tetapi berkaitan dengan garis melanggar berdasarkan lebar daripada jumlah baris. Mungkin bisa beradaptasi dengan masalah ini yang merupakan sesuatu yang saya coba cari tahu sekarang. Berikut ini adalah tautan yang baik ke solusi, mereka bahkan mengklaim untuk menyelesaikannya dalam waktu linear: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Juga, ada bab "8.5 Masalah Partisi" di The Algorithm Design Manual oleh Skiena yang tampaknya tepat pada topik, saya masih membacanya, sulit. (Sayangnya, dari apa yang saya pahami memiliki kompleksitas waktu kuadratik)

ds.algorithms Ecir Hana
sumber

Masalah pemrograman dinamis yang bagus! Saya mungkin menggunakannya sebagai pekerjaan rumah di kelas saya semester depan.

Jeffε

@ Jɛ ﬀ E jika Anda ingin menggunakannya untuk masalah pekerjaan rumah, lebih baik tutup pertanyaan sebelum jawabannya dipublikasikan di web.

Joe

@ Jo: sebagai seseorang yang benar-benar tertarik pada jawaban saya lebih suka pertanyaan yang akan dijawab, daripada ditutup.

Ecir Hana

@ Jo: ini bukan pekerjaan rumah, saya bahkan tidak belajar CS. Apa yang menjadi "level pekerjaan rumah", saya merasa sangat menarik bahwa beberapa orang bahkan tidak dapat membayangkan bagaimana menyelesaikan masalah, sementara yang lain menganggapnya sebagai "level pekerjaan rumah". Konon, jawabannya bisa dihapus dalam seminggu atau dikirim ke email saya misalnya. Dan saya akan berterima kasih karena tidak begitu "jawaban penuh", juga.

Ecir Hana

Ada masalah dalam bab Kleinberg dan Tardos pada pemrograman dinamis yang memformat sedemikian rupa untuk meminimalkan jumlah slack di baris.

Chandra Chekuri

Jawaban:

$M$ $O(N \log U)$ $U$ $N 2^{O(\sqrt{\log M \log \log N})}$ $M = \Omega(\log N)$

$M$ $M$

Jouni Sirén
sumber

Saya sangat menyesal tetapi saya tidak berpikir saya mengikuti. Apakah "berat tepi" panjang kata? Bagaimana "grafik" itu terlihat? Apakah ini hanya grafik linier di mana node adalah breakpoints dan edge adalah panjang kata-kata? Dan "jalur M-link" ini memecahnya sehingga segmen yang dihasilkan memiliki jumlah tepi minimal? Tapi yang paling penting, dalam kalimat pertama - saya tidak yakin apakah saya bisa menghitung keterkaitannya secara mandiri. Ini kira-kira perbedaan antara garis terpanjang dan garis sebenarnya jadi saya perlu tahu sesuatu tentang garis lain, bukan? Terlebih lagi untuk baris terakhir, silakan lihat komentar ke-15 di atas.

Ecir Hana

M

$M$

1

$1$

N + 1

$N+1$

(i, j)

$(i,j)$

i

$i$

j - 1

$j-1$

@Ecir: Pada dasarnya semua algoritme yang didasarkan pada pemrograman dinamis mengharuskan Anda untuk dapat menghitung keteraturan garis secara mandiri. Jika bukan itu masalahnya, Anda mungkin ingin menggunakan sesuatu seperti ide kedua saya: tebak lebar garis, hitung solusi berdasarkan lebar itu, dan lakukan iterate untuk menemukan solusi yang lebih baik.

Jouni Sirén

Terima kasih atas penjelasannya. Tolong, saya punya dua pertanyaan lagi: ketika menggunakan opsi "pencarian biner", adakah yang bisa saya lakukan untuk menjamin jumlah baris M? Jika saya menambahkan epsilon acak kecil untuk setiap lebar garis sehingga tidak akan ada garis dengan lebar yang sama, saya bisa mendapatkan lebih banyak resolusi atas penempatan jeda.

Ecir Hana

Dan dalam kasus "jalur M-link", kedua makalah menyebutkan bahwa "mudah untuk menunjukkan bahwa jalur K-link minimum dapat dihitung dalam waktu O (nK)" - apakah Anda mungkin tahu apa artinya? Saya tidak dapat menemukan informasi lebih lanjut tentang itu. Masalahnya adalah, kertas-kertas itu agak terlalu rumit untuk kepala kecil saya jadi saya mencoba untuk menemukan informasi lebih lanjut, implementasi mungkin, ...

Ecir Hana

-3

Saya tidak tahu apakah ini membantu, tetapi menjelang akhir komentar ini seseorang mengimplementasikan apa yang Anda inginkan dalam PHP; mungkin Anda bisa mengetahui algoritma.

adrianp
sumber

Dalam komentar mereka hanya memotong baris yang tersisa setelah jumlah baris yang diinginkan. Mereka menggunakan PHP wordwrap(), yang pada gilirannya menggunakan algoritma serakah (yaitu tidak ada "merata") untuk pembungkus. Meski begitu, pertanyaannya tetap bagaimana "menebak" $widthargumen wordwrap(). Tapi terima kasih atas jawabannya, ngomong-ngomong!

Ecir Hana