Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

Update: I'd like to revive (and revise) this question a bit because there have been some recent developments, and furthermore I would be happy to encourage some up-to-date discussion.

I'm thinking (from a professional point of view) about fully automatic generation of newspapers from data.

More precisely, the system under consideration would get as input an 'attributed' data stream of articles (subject classification, headers, author info &c, text, images) plus some hints on the way things should be layouted, but only on the level of "lead story", "short message", "weather report".

As output, a complete newspaper would be generated automatically without further user interaction (with a focus on print, not online; i.e. PDF rather than HTML).

Note that I'm not looking for help on how to do this with LaTeX. There won't be technical difficulties with page and article layout using my system DocScape. I'm asking (myself) about the basic algorithm for "geometrically" generating the page layout based on the given content stream. There has to be some 'artificial intelligence' in there to make the newspaper look good also from a professional newspaper editor's point of view.

Of course, any production-quality system would yield a valid answer, including those based on TeX ;-)

googling yields some interesting references, but it's hard to distinguish which of them would really lead to an effective implementation. I'm not talking about an academic exercise here but about a real system which would be used by a publisher to produce hundreds of newspapers each week.

There are further interesting references in the area of floorplanning for VLSI layout, but these lack consideration for specific needs of newspapers, of course ;-)

Now my questions a bit more precisely:

  1. Does a system like described above effectively exist (it doesn't have to be based on TeX)? I'd be interested in pointers to concrete systems as well as publications about them.
  2. Are there publishers who really use a system like this for making newspapers (online would be interesting as well)?
  3. Has anyone here ever worked with such a system and would care to describe how it's used?
  4. What are the most interesting "scientific" publications on this subject which I should consider when designing such a system myself?

I have seen the question Automatic newspaper creation in LaTeX, but it's got a slightly different focus than mine (what LaTeX tools to use), and unfortunately the discussion there wasn't very intense, yielding no pointers which would help me.

Some Literature

Here I'll add a review of literature I've collected on the subject. Note that I have not read all of it, so if I have misrepresended something, please comment.

  1. Schoon, Benjamin Durant
    Fishpaper : automatic personalized newspaper layout
    Thesis (B.S.)-Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1994.

    More of a historical account than a real contribution to this subject. "automatic personalized newspaper layout" here doesn't include automatically finding a good page layout. The page layout is given by a fixed template, though the system supposedly can account for different text lengths or image sizes of article content, or display alternative content when some element is missing.

    It is historically interesting because it falls in the advent of the WWW. The browser Mosaic is explicitly mentioned as a device for electronically presenting news items, but in a time before HTML 2.0, apparently the possibilities for screen formatting were limited. TeX is also explicitly mentioned, in the sense of a somewhat competing product to the software fishpaper presented, which produces PostScript files from a given stream of news content and given page layout templates.

    Example from the paper:
    enter image description here

  2. Gonzalez J, Rojas I, Pomares H, Salmeron M, Merelo JJ.
    Web Newspaper Layout Optimization Using Simulated Annealing
    IEEE Trans Syst Man Cybern B Cybern. 2002;32(5):686-91.

    Thanks to Martin for the link.

    This is a classical research paper in the sense that the main focus lies on applying a specific optimization method (simulated annealing) to a precisely mathematically specified problem (web newspaper layout).

    The concrete results shown in the paper are not overwhelming, and in some sense the problem which is solved is not completely compatible with my own interest (this is for web pages, so no length restriction for the page produced; furthermore the design of a single article is rather uninspired), but from the results shown, it can be expected that the method could be extended towards solving the "complete" problem discussed here. Furthermore, the algorithm is tailored for "real time" application and takes only a couple of seconds for a realistic sample size.

    Example from the paper:
    enter image description here

The State of the Art?

Since I'm thinking about this subject, ads and blog posts about systems to make newspapers keep popping out to me ;-)

Without a connection to one specific vendor, I'd just mention two examples which seem to represent the state of the art for systems which make newspaper layout easy:

A tool named "publishing cloud" seems to be a good representative of a large range of almost equivalent editing systems (easy to find with google) based on some easy-to-use web-based layout editor which is, however, template-based with a mostly manual page layouting process. The tools automate several stages of the publishing process, offering import filters for content (mostly to get content from web pages or newswire systems) and export to PDF or digital printing services, but not the part I'm interested in here, namely the process of arranging content on the document pages.

I would be interested in any hint that one of the systems in this area offers "real" automtic page layouting for a non-trivial newspaper layout, not just a really easy-to-use web frontend to do it manually.

Last but not least, I should mention that we have implemented a newsletter-generating system for a news agency which is completely automatically generating different types of newsletters every day and every week:

  1. EPD Wochenspiegel, a weekly news compilation which exists in a multitude of local and thematic variants.
  2. EPD Medien, another weekly newsletter with a specific theme (media) and a slightly different layout.
  3. EPD Zentralausgabe, a daily newsletter, again existing in multiple local variants.

On the linked pages, you can download example PDF files to take a look at the different layouts.

Here, everything is fully automatic: Only the compilation of articles has to be selected in the wire service application. But the layout is not what I would consider "Newspaper Layout", so these examples represent the state of the art we can currently produce, but do not answer my question.

share|improve this question
    
Interesting question! I've run into something potentially applicable in the Lists in TeX's mouth TUGboat article, which mentions at the end of the article MagTeX, and “infinite list of ouput routines”. I haven't found more information on MagTeX, though. –  morbusg Mar 28 '12 at 9:51
    
@morbusg While this might be an interesting question from the TeX point of view (making this even a bit more on topic :) I can assure you I have the technical demands of page layout sorted out in DocScape. See for instance [flipcat2.giata-web.de/…. –  Stephan Lehmke Mar 28 '12 at 9:58
    
Stephan: OK, I guess I don't understand the question, then. But just to be on the safe side, please, let the sentence “infinite list of output routines” sink in. To help with that, I thought it could be good to repeat it one more time ;-D infinite list of output routines. –  morbusg Mar 28 '12 at 10:22
2  
Well, this really depends. First, DocScape globally redefines \shipout to \newcommand\shipoutoff@DocScape{\setbox\@tempboxa=} so while \output might be triggered occasionally when a macro generates spurious spaces or text is output owing to error states, this doesn't really output anything for certain. On the other hand, things get output of course, only not by an output routine in the sense of plain or LaTeX, but from a much more sophisticated "object-oriented" page model. –  Stephan Lehmke Mar 28 '12 at 10:38
1  
At least using the online free service, you are limited to A4 size. I ran my blog through it and got a pretty good result with no input on my part (other than the URL) and different size articles and images were placed appropriately. It would be interesting to see if the pro version is capable of handling A3 size paper. –  user26732 Dec 28 '13 at 18:09

5 Answers 5

up vote 27 down vote accepted
+100

Not much of an answer, more a couple of loose thoughts ...

Off-hand I'm not aware of any such system and also not aware of any research that deals with automatic newspaper layout. As far as I know there has been only very very limited attempts to approach the subject of automatic typesetting with more complex layout rules and dependencies that go beyond what is largely a linear process. You can count the with your hands:

  • Michael Plass (under Knuth)
  • Graham Asher in 1990 or so (Type & Set) - not sure what happened to that
  • Anne Brüggemann-Klein in the mid 90ties
  • Richard Furuta and a few others in the 90ties
  • Stephan Wohlfeil 1997 (Phd: On the Pagination of Complex Book-like Documents)

and to my knowledge nada otherwise. And those are all looking more at the questions arising from "book-like" documents rather than newspapers/journals. But I might be very wrong as I didn't follow that area closely in the last 10 years.

But assuming my knowledge is correct for a moment, it isn't really really surprising, is it? What you have is a global optimization problem of a constraint system where the possibilities that you need to test grow astronomically the moment you have more than a single column and a good number of floats with a certain set of constraints. And so far any serious attempts to do much better than choosing the trivial way out (no floats, just linear typesetting - aka MS-Word model) or a simple greedy algorithm that never looks back (like LaTeX does) got defeated by the complexity of the task.

Now newspaper typesetting on one hand comes with the additional complexity (but perhaps also the freedom) of having multiple input streams of limited length which allow for reordering (to some extent). On the other hand it will have much different requirements on picture order and call-outs.

By the way, to my knowledge it is quite common in newspaper writing that the authors have to write to length and if they don't they get edited to it. Are you thinking of taking that into account? Because if so that would simplify the task probably considerably.

So I think the first task would be to understand and research the constraint system, e.g., what kind of rules make newspapers or journals tick. Those will not be universal and most likely they are contradicting each other if taken all together. But they form a basis of what an algorithm needs to be able to be configured for. And only when those boundaries are known can one delve deeper into the question of designing such an algorithm. How close one can get to an ideal, I don't know. In some respects, I would assume that it might in fact be simpler for newspapers due to the flexibility of reordering stories but in any case I believe this is an open research topic that is so far unsolved (just like "the pagination of complex book-like documents" effectively is). --- I'm certainly interested and have been for more than two decades, even if I had to take a longer break after the millennium.

I don't know if Wohlfeil's PhD work is still easily available (it was difficult for me to get back then) but a quick search on the web brought up a shorter paper by Brüggeman-Klein/Klein/Wohlfeil "On the Pagination of Complex Documents" which is from around the same time. And I also found "Pagination reconsidered" by the same authors (but no date to go with it, but from the number it was probably earlier).

I'm sure that there are probably many other sources but one good book that I think is worth looking at for those who speak German is "Praxishandbuch Gestaltungsraster" by Andreas and Regina Maxhauer. Its focus isn't the newspaper angle, but rather the grid one but that naturally covers a good number of possible rules.

By the way, a good way to do some research (through far from perfect at the moment) is to look around in Microsoft's Academic Search. For example that gives you some more background on what Anne was doing over the years and which papers she co-authored. But you have to be aware that there is a lot of rubbish in the data they have and it is horribly incomplete in parts.

Update

Upon reading a bit in Stefan's PhD thesis again (which I incorrectly labeled habil initially) I came across the work of Krista Lagus who wrote in her master thesis about "Automated pagination of the generalized newspaper using simulated annealing". I didn't find the thesis on the web but perhaps it is worth exploring further.

share|improve this answer
1  
Thank you very much for the answer, and for all the references. They will surely be useful. Looking at this I'm almost tempted to make a research project from this after all ;-) But if this project is to happen at all, it has to be with a totally pragmatic approach, yielding acceptable results within a reasonable amount of implementation time. Fortunately, we meanwhile have plenty of experience with automatically generating complex page structures. This would without doubt be the most complex we ever attempted, but still I think our basic techniques can be applied. –  Stephan Lehmke Apr 1 '12 at 23:11
    
Another note: I doubt we can have the editors modifying text to get a better fit. If they had resources for that, they would surely do the whole layout the traditional way. It's the sheer amount of pages which have to be produced per week which calls for automation, and this would also prohibit adaption on a per-article basis. One thing which could be considered would be to declare parts of a text as optional, as the same text can appear on a lot of pages (these are localised newspapers). But most of the time flexibility has to come from adding fillers or white space. –  Stephan Lehmke Apr 1 '12 at 23:16
    
@Stephan doesn't really surprise me. I was assuming this. Still, there may be variants possible either by specification in the text or by allowing pictures to go with the text to be adjusted in size, for example. Either way, the opimization job may not become easier only wider in options :-) –  Frank Mittelbach Apr 1 '12 at 23:20
    
Of course, this will boil down to pre-determining a "geometric solution space" for every article, describing the range of all geometries it can assume by choosing different templates, compressing or extending. The layouting process will then combine geometries from the ranges of different articles. The interesting part will be to asses the total quality of a page candidate based on criteria acquired from domain experts. btw, thanks for the update. I didn't have this paper, but I will surely try to get hold of it. –  Stephan Lehmke Apr 1 '12 at 23:25
    
Google Scholar leads to this article by Lagus. –  Martin Schröder Dec 11 '13 at 13:38

I am not familiar with any literature other than some papers that concentrate on page description languages. However, I think Håkon Wium Lie's thesis on Cascading Style Sheets, might be partially relevant to what you are looking at least from the point of developing a robust "templating" or "templet" system (also has an interesting bibliography). However, as you said:

There won't be technical difficulties with page and article layout using my system DocScape. I'm asking (myself) about the basic algorithm for "geometrically" generating the page layout based on the given content stream.

The difficulty lies in defining an algorithm for nicely placing textual objects on a page, trying the various permutations etc. The answer certainly lies in the realm of AI and especially machine learning.

I would envision a system that has scanned and translated into templates (based on an as yet to be developed system) 1000s of editions and then out of this corpus to train the algorithm to produce similar designs using pattern recognition algorithms.

However, the problem will become more tractable if you re-phrase as: from a set of pre-determined typographical layouts can you automate the production of a newspaper. The answer for this is almost certain as proven by LaTeX that automates the production of pre-determined styles for books etc. Such a system has been described by DeTreville in a PhD Thesis. The dissertation is a bit dated but has a good approach in abstracting layouts.

I tried hard on and off to try and define an algorithm that from a set of figures and text produce art book like output. So far I have a collection of about 100 different designs. How do you choose one from another still evades me and this is three orders of magnitude easier.

But, please don't let me discourage you. I think is a great area to develop and research or create a start-up for it.

share|improve this answer
    
Thank you for this answer. See my edit above on accepting answers. I'm not discouraged at all. We've already successfully designed systems for optimal ad placement, so I'm really confident we can solve the computing problem involved. The most challenging task will be to design an "intelligent" function for assessing the "fitness" of a given page layout based on criteria which express the opinion of professional editors. Personally, I don't believe in approaching this type of problem with a learning algorithm (NN or ILP or whatever). I've seen too much of this while at university. –  Stephan Lehmke Mar 28 '12 at 20:04
1  
@Yiannis I would be thrilled to learn more about your collection of layouts. This is just what I would need for working on the new layout config concepts for LaTeX3 –  Frank Mittelbach Apr 1 '12 at 22:05
    
@FrankMittelbach I am back on 17 April and will email them with pleasure. –  Yiannis Lazarides Apr 2 '12 at 3:46
    
@YiannisLazarides Thank you very much for the additional link. I'll take a look. –  Stephan Lehmke Apr 8 '12 at 15:36
    
@YiannisLazarides can I ping you once more for your layout collection? I think a lot of people would benefit. –  Frank Mittelbach Jun 28 '12 at 16:41

I feel that in light of this blog post, I have to add an approach I had mentioned under "state of the art" as an answer.

A recent blog post reports on an effort to produce a specific digitally printed edition of The Guardian for a cafe. There is a lot of talk about "experimental, algorithmic newspaper" there, but the tool which was employed, named ARTHR, seems to fall exactly in the category of easy-to-use web-based layout editor I described in my question above under "state of the art".

This blog post seems to imply that layouting is indeed automatic:

Tom Taylor, head of engineering for The Newspaper Club, said they use a semi-automated version of ARTHR for The Long Good Read, which allows an editor to enter story links and lets the program develop the layout on its own.

But I couldn't find any details on how the automatism works.

The impression that a fully automatic layout engine was really developed is also underlined by this quotation from the blog posting linked to at the top of this answer:

ARTHR has been written by Newspaper Club to handle the job of laying out newspapers, this can range from a creator very carefully deciding where everything goes on each page, to being given a simple URL and deciding for itself where headlines, images and body text should go.

It's this last option I quite enjoy, the tool as I understand it tries out various layouts before deciding on which one it thinks is the best. Sometimes it produces some crazy looking pages, but even then at least its only taking a couple of seconds rather then me figuring it all out by hand.

My roll as newspaper baron is to feed in several URLs selected from our "Top Stories" leave ARTHR to do its own thing, and then shuffle the results around bit, it rather feels like cheating.

So from second-hand accounts, it can be concluded that the approach taken for The Long Good Read constitutes an answer to my question, with the following two issues remaining:

  1. I could not find any detailed description how the algorithm works. If it really "intelligently" tries a variety of layouts, deciding which to take, there must surely be some evaluation rules for what is "best" and parameters which can be configured. Also, I could not find any mention of this functionality in the demo version of ARTHR.
  2. Honestly, although the page layout which can be observed in several example images is undoubtedly suited for the task at hand (a publication mainly composed of "long form articles"), it is a bit too boring for my taste and does not really fall into the category "newspaper layout" I was aiming at with this question.

Hence, while this approach deserves to appear as an answer, I am not completely satisfied yet.

share|improve this answer
    
The Newspaper Club has been active. There was just a post on Hacker News which links to their new beta. They take web pages and convert them to print newspapers: paperlater.com. I have no link to the company. –  user26732 Jun 30 at 12:37

Here's what feedjournal yields. How they do it, I have no idea. They take a URL and provide the following result as shown in the image. FeedJournal.com example

The Duplo program is used for automatic layout:

http://engineering.flipboard.com/2014/03/web-layouts/

share|improve this answer

First of all, LaTeX is not really intended for unattended typesetting of large documents. ConTeXT may lend itself marginally better for this, but will still not be on par with the requirements for automatically typesetting a newspaper.

By contrast, the combination of HTML and CSS performs way much better at automatically positioning and resizing content whilst not requiring much effort by the designer. After all, this is not surprising as this is exactly what we expect fluid web pages to do: adapting content to unknown screen dimensions.

This is why the commercial software Prince XML deserves mentioning here as a bridge from HTML to printed media. On the product's website there are several examples of entire magazines automatically typeset from HTML & CSS. Under specific circumstances the use of Prince XML is free of charge.

Myself, I am using the non-commercially licensed Prince XML in my automatic work flow from Pandoc Markdown over HTML & CSS to Letter & A4-sized PDF. Check out my website for examples and the makefile.

Even though I have a good amount of experience with TeX, I was unable to achieve such nice-looking automatically generated results with LaTeX nor with ConTeXt. Moreover, the HTML, CSS & Prince XML combo is extremely fast. Whereas ConTeXt would typical require at least 3 seconds for a couple of pages, Prince XML does the same and better in a fraction a second. So server-side on-demand typesetting with the commercially licensed Prince XML certainly belongs to the realm of workable possibilities.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.