Podziel tekst równomiernie na określoną liczbę wierszy

Istnieje liniowy algorytm czasowy umożliwiający równomierne dzielenie tekstu na linie o maksymalnej szerokości. Wykorzystuje SMAWK (lub Knuth & Plass), a „równomiernie” oznacza: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Czy istnieje algorytm lub wklęsła funkcja kosztu dla algorytmu, powyżej której wziąłby pod uwagę liczbę wierszy, w których chciałbym rozbić tekst, zamiast maksymalnej szerokości linii? Również w czasie liniowym?

Innymi słowy, szukam algorytmu łamania linii (lub tworzenia akapitów lub zawijania słów), w którym dane wejściowe to żądana liczba linii, a nie pożądana szerokość linii.

Wystarczy opisać praktycznie nieużyteczne podejście: między każdą parą słów jest N słów i N-1 spacji, M jest pożądaną liczbą linii (M <= N). Po każdej spacji może być najwyżej jeden (ewentualnie zero) podział wiersza. Teraz algorytm spróbuje umieścić przerwy w każdej możliwej kombinacji, obliczając „nierówność” i zwróci najlepszą. Jak to zrobić znacznie szybciej?

Czy taki problem ma też nazwę? Do jakiej „rodziny” problemów należy? (Np. „Pakowanie pojemników”) Gdybym nie potrzebował idealnie optymalnego rozwiązania, tylko bardzo dobrego, czy można go rozwiązać znacznie szybciej? (pewna forma heurystyki mogłaby być użyteczna, gdyby dla danego wkładu zawsze istniało to samo, być może nieoptymalne rozwiązanie).

Aktualizacja

Chandra Chekuri zasugerowała poniżej „problem w rozdziale Kleinberga i Tardosa dotyczącym programowania dynamicznego”. To był dobry odczyt, ale dotyczy podziału linii na podstawie szerokości, a nie liczby linii. Być może można go dostosować do tego problemu, który próbuję teraz rozwiązać. Oto dobry link do rozwiązania, twierdzą nawet, że rozwiązuje je w czasie liniowym: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Jest też rozdział „8.5 Problem z partycjami” w Podręczniku projektowania algorytmów autorstwa Skieny, który wydaje się być dokładnie na ten temat, wciąż go czytam, ciężko. (Niestety, z tego, co zrozumiałem, ma kwadratową złożoność czasu)

ds.algorithms Ecir Hana
źródło

Fajny problem z programowaniem dynamicznym! W przyszłym semestrze mogę go wykorzystać jako zadanie domowe.

Jeffε

@ Jɛ ﬀ E jeśli chcesz użyć go do zadania domowego, lepiej zamknij pytanie, zanim odpowiedź zostanie opublikowana w Internecie.

Joe

@Joe: jako ktoś naprawdę zainteresowany odpowiedzią wolałbym raczej odpowiedzieć na pytanie niż zamknąć.

Ecir Hana

@Joe: to nie praca domowa, nawet nie uczę się CS. Co do „poziomu pracy domowej”, uważam za bardzo interesujące, że niektórzy ludzie nawet nie wyobrażają sobie, jak rozwiązać problem, podczas gdy inni uważają go za „poziom pracy domowej”. To powiedziawszy, odpowiedź może zostać usunięta za tydzień lub wysłana na przykład na mój e-mail. Byłbym również wdzięczny za nie tak „pełną odpowiedź”.

Ecir Hana

W rozdziale Kleinberga i Tardosa występuje problem dotyczący programowania dynamicznego, który należy sformatować w taki sposób, aby zminimalizować sumę luzów w wierszach.

Chandra Chekuri

Odpowiedzi:

Jeśli potrafisz obliczyć nierówność linii, nie wiedząc nic o innych liniach, możesz modelować problem jako znalezienie ścieżki łącza o minimalnej masie na wykresie. Przy wklęsłych wagach całkowitych dla krawędzi istnieje algorytm, który rozwiązuje problem w czasie , gdzie jest największą bezwzględną wagą krawędzi. Inny algorytm rozwiązuje problem w czasie dla dowolnej wagi krawędzi wklęsłej, przyjmując, że . Oba algorytmy zakładają, że można obliczyć ciężar krawędzi w stałym czasie. $M$ $O(N \log U)$ $U$ $N 2^{O(\sqrt{\log M \log \log N})}$ $M = \Omega(\log N)$

Możesz także użyć wyszukiwania binarnego, aby znaleźć szerokość linii, tak że SMAWK używa z nią liniiJednak w niektórych przypadkach ten algorytm nie gwarantuje rozwiązania z dokładnie liniami. $M$ $M$

Jouni Sirén
źródło

Bardzo mi przykro, ale nie sądzę, żebym podążał. Czy „waga krawędzi” to długość słowa? Jak wygląda „wykres”? Czy to tylko wykres liniowy, w którym węzły to punkty przerwania, a krawędzie to długości słów? A ta „ścieżka M-link” rozbija ją, aby powstałe segmenty miały minimalną sumę krawędzi? Ale co najważniejsze, w pierwszym zdaniu - nie jestem pewien, czy potrafię samodzielnie obliczyć nierówność. Z grubsza jest to różnica między najdłuższą linią a rzeczywistą linią, więc muszę wiedzieć coś o innych liniach, prawda? Co więcej, w ostatnim wierszu, patrz 15. komentarz powyżej.

Ecir Hana,

@Eir: Szukamy ścieżki o minimalnej masie mającej dokładnie krawędzi od węzła do węzła . Posiadanie krawędzi na ścieżce oznacza, że słowa od do tworzą pojedynczą linię, a ciężar krawędzi jest wkładem tej linii do nierówności rozwiązania.

M

$M$

1

$1$

N + 1

$N+1$

(i, j)

$(i,j)$

i

$i$

j - 1

$j-1$

Jouni Sirén

@Eir: Zasadniczo wszystkie algorytmy oparte na programowaniu dynamicznym wymagają, aby można było obliczyć nierówność linii niezależnie. Jeśli tak nie jest, możesz użyć czegoś takiego jak mój drugi pomysł: odgadnąć szerokość linii, obliczyć rozwiązanie na podstawie tej szerokości i iterować, aby znaleźć lepsze rozwiązania.

Jouni Sirén

Dziękuję za wyjaśnienie. Mam jeszcze dwa pytania: czy korzystając z opcji „wyszukiwania binarnego” mogę coś zrobić, aby zagwarantować liczbę M linii? Jeśli dodam mały losowy epsilon do każdej szerokości linii, aby nie było linii o tej samej szerokości, mógłbym uzyskać większą rozdzielczość niż umieszczanie przerw.

Ecir Hana,

A w przypadku „ścieżki łącza M” oba artykuły wspominają, że „łatwo jest wykazać, że minimalną ścieżkę łącza K można obliczyć w czasie O (nK)” - czy może wiesz, co one oznaczają? Nie mogłem znaleźć dalszych informacji na ten temat. Problem w tym, że te dokumenty są trochę zbyt skomplikowane dla mojej małej głowy, więc staram się znaleźć więcej informacji, być może implementację ...

Ecir Hana

-3

Nie wiem, czy to pomaga, ale pod koniec tego komentarza ktoś implementuje to, co chcesz w PHP; może uda ci się wymyślić algorytm.

adrianp
źródło

W komentarzu po prostu odcinają pozostałe linie po żądanej liczbie linii. Korzystają z PHP wordwrap(), który z kolei używa chciwego (tzn. Nie „równomiernego”) algorytmu do zawijania. Nawet wtedy pozostaje pytanie, jak „odgadnąć” $widthargument wordwrap(). Ale w każdym razie dzięki za odpowiedź!

Ecir Hana