Eugene Charniak (June 2, 1946 – June 13, 2023) was a professor of computer Science and cognitive Science at Brown University. He held an A.B. in Physics from the University of Chicago and a Ph.D. from M.I.T. in Computer Science. His research was in the area of language understanding or technologies which relate to it, such as knowledge representation, reasoning under uncertainty, and learning. Since the early 1990s he was interested in statistical techniques for language understanding. His research in this area included work in the subareas of part-of-speech tagging, probabilistic context-free grammar induction, and, more recently, syntactic disambiguation through word statistics, efficient syntactic parsing, and lexical resource acquisition through statistical means. He was a Fellow of the American Association of Artificial Intelligence and was previously a Councilor of the organization. He was also honored with the 2011 Association for Computational Linguistics Lifetime Achievement Award and awarded the 2011 Calvin & Rose G Hoffman Prize. In 2011, he was named a fellow of the Association for Computational Linguistics. In 2015, he won the Association for the Advancement of Artificial Intelligence (AAAI) Classic Paper Award for a paper (“Statistical Parsing with a Context-Free Grammar and Word Statistics”) that he presented at the Fourteenth National Conference on Artificial Intelligence in 1997. == Books == He published six books: Computational Semantics, (with Yorick Wilks), Amsterdam: North-Holland (1976) Artificial Intelligence Programming (now in a second edition) (with Chris Riesbeck, Drew McDermott, and James Meehan), Hillsdale NJ: Lawrence Erlbaum Associates (1980, 1987) Introduction to Artificial Intelligence (with Drew McDermott), Reading MA: Addison-Wesley (1985) Statistical Language Learning, Cambridge: MIT Press (1993) Introduction to Deep Learning, Cambridge: MIT Press (2019) AI & I: An Intellectual History of Artificial Intelligence, Cambridge: MIT Press (2024)
Inbox by Gmail
Inbox by Gmail was an email service developed by Google. Announced on a limited invitation-only basis on October 22, 2014, it was officially released to the public on May 28, 2015. Inbox was shut down by Google on April 2, 2019. Available on the web, and through mobile apps for Android and iOS, Inbox by Gmail aimed to improve email productivity and organization through several key features. Bundles gathered emails on the same topic together; highlighted surface key details from messages, reminders and assists; and a "snooze" functionality enabled users to control when specific information would appear. Updates to the service enabled an "undo send" feature; a "Smart Reply" feature that automatically generated short reply examples for certain emails; integration with Google Calendar for event organization, previews of newsletters; and a "Save to Inbox" feature that let users save links for later use. Inbox by Gmail received generally positive reviews. At its launch, it was called "minimalist and lovely, full of layers and easy to navigate", with features deemed helpful in finding the right messages—one reviewer noted that the service felt "a lot like the future of email". However, it also received criticism, particularly for a low density of information, algorithms that needed tweaking, and because the service required users to "give up the control" of organizing their own email, meaning that "Anyone who already has a system for organizing their emails will likely find themselves fighting Google's system". Google noted in March 2016 that 10% of all replies on mobile originated from Inbox's Smart Reply feature. Google announced it would discontinue Inbox by Gmail in March 2019, with many of its features integrated into Gmail proper. == Features == Inbox by Gmail scanned the user's incoming Gmail messages for information. It gathered email messages related to the same overall topic into an organized bundle, with a title describing the bundle's content. For example, flight tickets, car rentals, and hotel reservations were grouped under "Travel", giving the user an easier overview of emails. Users could also group emails together manually, to "teach" the Inbox how the user worked. The service highlighted key details and important information in messages, such as flight itineraries, event information, photos and documents. Inbox could retrieve updated information from the Internet, including the real-time status of flights and package deliveries. Users could set reminders to bring up important messages later. When a user needed particular information, Inbox could assist the user by displaying the necessary details. Where Inbox highlights information was not needed immediately, users could "snooze" a message or reminder, with options to make the information reappear at a later time or specific location. In June 2015, Google added an "Undo Send" feature to Inbox, giving the user 10 seconds to undo sending a message. In November 2015, Google added "Smart Reply" functionality to the mobile apps. With Smart Reply, Inbox determined which emails could be answered with a short reply, generating three example responses from which the user could select one with a single tap. Smart Reply (initially available only on the Android and iOS mobile apps) was added to the Inbox website in March 2016, Google announcing that "10% of all your replies on mobile already use Smart Reply". By May 2017, Google said Smart Reply was driving about 12% of replies in inbox on mobile. In April 2016, Google updated Inbox with three new features; Google Calendar event organization, newsletter previews, and a "Save to Inbox" functionality that let the user save links for later use, rather than having to email links to themselves. In December 2017, Google introduced an "Unsubscribe" card that let users easily unsubscribe from mailing lists. The card appeared for email messages (from specific senders) that the user had not opened for a month. A few popular Inbox by Gmail features were subsequently added to Gmail: "Snoozing" of emails Nudges: Gmail could move old messages back to the top of the inbox when it thought a follow up or reply might be required. Hover actions: Placing the mouse cursor over a certain part of the message could quickly effect an action, such as archiving, without its being opened. Smart reply: This feature employed boilerplate text to suggest appropriate replies. Google reportedly wished, at a time then to be decided, to add the "bundles" feature to Gmail, which at the time was available only in Inbox for Gmail. By March 2020, many Inbox features were still missing from Gmail. == Platforms == Inbox by Gmail was announced on a limited invitation-only basis on October 22, 2014, available on the web, and through the Android and iOS mobile operating systems. It was officially released to the public on May 28, 2015. == Reception == David Pierce of The Verge praised the service, writing that it was "minimalist and lovely, full of layers and easy to navigate. It's remarkably fast and smooth on all platforms, and far better on iOS than the Gmail app". However, he criticized the app's low density of information, with only a few emails visible on the screen at a time, making it "a bit of a challenge" for users who need to go through "hundreds of emails" every day. Although positive that "Inbox feels a lot like the future of email", Pierce wrote that there was "plenty of algorithm tweaking and design condensing to do", with particular attention needed on a "compact view" for denser view of information on the screen. Sarah Mitroff of CNET also praised Inbox, writing, "Not only is it visually appealing, it's also full of features that help you find every message you need, when you need it". She added that users must "give up the control" to organize their email, and that it "won't vibe with everyone", but admitted that "if you're willing ... the app will reward you with a smarter and cleaner inbox." Mitroff noted that, initially, users had to coach the app about which bundle was appropriate for certain emails, writing, "It's a tedious process at first, by [sic] in just a few days Inbox starts to get it right." Regarding any downsides of the service, Mitroff wrote that "Inbox has a built-in strategy for managing your emails that works best on its own. Anyone who already has a system for organizing their emails will likely find themselves fighting Google's system". == Discontinuation and legacy == Google ended the service in March 2019. Google called Inbox "a great place to experiment with new ideas" and noted that many of those ideas had been migrated to Gmail. The company wanted, going forward, to focus its resources on a single email system. Several services, like Shortwave, attempted to resurrect some of the features of Inbox by Gmail to attract its old users. Similarly, Inbox Reborn, an actively maintained browser extension developed by a team of volunteer developers from around the world since 2018, aims to recreate the core features and visual style of Inbox by Gmail within the standard Gmail interface. The project continues to focus on preserving functionalities such as email bundling and streamlined workflows to provide users with a familiar productivity experience. Afterwards, most people moved to Spark, Spike, or Newton. According to a product manager at Google, a "more focused approach" regarding email was the companies goal. This is likely the reason they moved away from Inbox.
Bottom-up and top-down approaches
Bottom-up and top-down are strategies of composition and decomposition in fields as diverse as information processing and ordering knowledge, software, humanistic and scientific theories (see systemics), time management, and organization. In practice they can be seen as a style of thinking, teaching, or leadership. A top-down approach (also known as stepwise design and stepwise refinement and in some cases used as a synonym of decomposition) is essentially the breaking down of a system to gain insight into its compositional subsystems in a reverse engineering fashion. In a top-down approach an overview of the system is formulated, specifying, but not detailing, any first-level subsystems. Each subsystem is then refined in yet greater detail, sometimes in many additional subsystem levels, until the entire specification is reduced to base elements. A top-down model is often specified with the assistance of black boxes, which makes it easier to manipulate. However, black boxes may fail to clarify elementary mechanisms or be detailed enough to realistically validate the model. A top-down approach starts with the big picture, then breaks down into smaller segments. A bottom-up approach is the piecing together of systems to give rise to more complex systems, thus making the original systems subsystems of the emergent system. Bottom-up processing is a type of information processing based on incoming data from the environment to form a perception. From a cognitive psychology perspective, information enters the eyes in one direction (sensory input, or the "bottom"), and is then turned into an image by the brain that can be interpreted and recognized as a perception (output that is "built up" from processing to final cognition). In a bottom-up approach the individual base elements of the system are first specified in great detail. These elements are then linked together to form larger subsystems, which then in turn are linked, sometimes in many levels, until a complete top-level system is formed. This strategy often resembles a "seed" model, by which the beginnings are small but eventually grow in complexity and completeness. But "organic strategies" may result in a tangle of elements and subsystems, developed in isolation and subject to local optimization as opposed to meeting a global purpose. == Computer science == === Software development === In the software development process, the top-down and bottom-up approaches play a key role. Top-down approaches emphasize planning and a complete understanding of the system. It is inherent that no coding can begin until a sufficient level of detail has been reached in the design of at least some part of the system. Top-down approaches are implemented by attaching the stubs in place of the module. But these delay testing of the ultimate functional units of a system until significant design is complete. Bottom-up emphasizes coding and early testing, which can begin as soon as the first module has been specified. But this approach runs the risk that modules may be coded without having a clear idea of how they link to other parts of the system, and that such linking may not be as easy as first thought. Re-usability of code is one of the main benefits of a bottom-up approach. Top-down design was promoted in the 1970s by IBM researchers Harlan Mills and Niklaus Wirth. Mills developed structured programming concepts for practical use and tested them in a 1969 project to automate the New York Times morgue index. The engineering and management success of this project led to the spread of the top-down approach through IBM and the rest of the computer industry. Among other achievements, Niklaus Wirth, the developer of Pascal programming language, wrote the influential paper Program Development by Stepwise Refinement. Since Niklaus Wirth went on to develop languages such as Modula and Oberon (where one could define a module before knowing about the entire program specification), one can infer that top-down programming was not strictly what he promoted. Top-down methods were favored in software engineering until the late 1980s, and object-oriented programming assisted in demonstrating the idea that both aspects of top-down and bottom-up programming could be used. Modern software design approaches usually combine top-down and bottom-up approaches. Although an understanding of the complete system is usually considered necessary for good design—leading theoretically to a top-down approach—most software projects attempt to make use of existing code to some degree. Pre-existing modules give designs a bottom-up flavor. === Programming === Top-down is a programming style, the mainstay of traditional procedural languages, in which design begins by specifying complex pieces and then dividing them into successively smaller pieces. The technique for writing a program using top-down methods is to write a main procedure that names all the major functions it will need. Later, the programming team looks at the requirements of each of those functions and the process is repeated. These compartmentalized subroutines eventually will perform actions so simple they can be easily and concisely coded. When all the various subroutines have been coded the program is ready for testing. By defining how the application comes together at a high level, lower-level work can be self-contained. In a bottom-up approach the individual base elements of the system are first specified in great detail. These elements are then linked together to form larger subsystems, which in turn are linked, sometimes at many levels, until a complete top-level system is formed. This strategy often resembles a "seed" model, by which the beginnings are small, but eventually grow in complexity and completeness. Object-oriented programming (OOP) is a paradigm that uses "objects" to design applications and computer programs. In mechanical engineering with software programs such as Pro/ENGINEER, Solidworks, and Autodesk Inventor users can design products as pieces not part of the whole and later add those pieces together to form assemblies like building with Lego. Engineers call this "piece part design". === Parsing === Parsing is the process of analyzing an input sequence (such as that read from a file or a keyboard) in order to determine its grammatical structure. This method is used in the analysis of both natural languages and computer languages, as in a compiler. Bottom-up parsing is parsing strategy that recognizes the text's lowest-level small details first, before its mid-level structures, and leaves the highest-level overall structure to last. In top-down parsing, on the other hand, one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. == Natural sciences == === Nanotechnology === Top-down and bottom-up are two approaches for the manufacture of products. These terms were first applied to the field of nanotechnology by the Foresight Institute in 1989 to distinguish between molecular manufacturing (to mass-produce large atomically precise objects) and conventional manufacturing (which can mass-produce large objects that are not atomically precise). Bottom-up approaches seek to have smaller (usually molecular) components built up into more complex assemblies, while top-down approaches seek to create nanoscale devices by using larger, externally controlled ones to direct their assembly. Certain valuable nanostructures, such as Silicon nanowires, can be fabricated using either approach, with processing methods selected on the basis of targeted applications. A top-down approach often uses the traditional workshop or microfabrication methods where externally controlled tools are used to cut, mill, and shape materials into the desired shape and order. Micropatterning techniques, such as photolithography and inkjet printing belong to this category. Vapor treatment can be regarded as a new top-down secondary approaches to engineer nanostructures. Bottom-up approaches, in contrast, use the chemical properties of single molecules to cause single-molecule components to (a) self-organize or self-assemble into some useful conformation, or (b) rely on positional assembly. These approaches use the concepts of molecular self-assembly and/or molecular recognition. See also Supramolecular chemistry. Such bottom-up approaches should, broadly speaking, be able to produce devices in parallel and much cheaper than top-down methods but could potentially be overwhelmed as the size and complexity of the desired assembly increases. === Neuroscience and psychology === These terms are also employed in cognitive sciences including neuroscience, cognitive neuroscience and cognitive psychology to discuss the flow of information in processing. Typically, sensory input is considered bottom-up, and higher cognitive processes, which have more information from other sources, are considered top-down. A bottom-up proc
Subject (documents)
In library and information science documents (such as books, articles and pictures) are classified and searched by subject – as well as by other attributes such as author, genre and document type. This makes "subject" a fundamental term in this field. Library and information specialists assign subject labels to documents to make them findable. There are many ways to do this and in general there is not always consensus about which subject should be assigned to a given document. To optimize subject indexing and searching, we need to have a deeper understanding of what a subject is. The question: "what is to be understood by the statement 'document A belongs to subject category X'?" has been debated in the field for more than 100 years (see below) == Theoretical view == === Charles Ammi Cutter (1837–1903) === For Cutter the stability of subjects depends on a social process in which their meaning is stabilized in a name or a designation. A subject "referred [...] to those intellections [...] that had received a name that itself represented a distinct consensus in usage" (Miksa, 1983a, p. 60) and: the "systematic structure of established subjects" is "resident in the public realm" (Miksa, 1983a, p. 69); "[s]ubjects are by their very nature locations in a classificatory structure of publicly accumulated knowledge (Miksa, 1983a, p. 61). Bernd Frohmann adds: "The stability of the public realm in turn relies upon natural and objective mental structures which, with proper education, govern a natural progression from particular to general concepts. Since for Cutter, mind, society, and SKO [Systems of Knowledge Organization] stand one behind the other, each supporting each, all manifesting the same structure, his discursive construction of subjects invites connections with discourses of mind, education, and society. The Dewey Decimal Classification (DDC), by contrast, severs those connections. Melvil Dewey emphasized more than once that his system maps no structure beyond its own; there is neither a "transcendental deduction" of its categories nor any reference to Cutter's objective structure of social consensus. It is content-free: Dewey disdained any philosophical excogitation of the meaning of his class symbols, leaving the job of finding verbal equivalents to others. His innovation and the essence of the system lay in the notation. The DDC is a poorly semiotic system of expanding nests of ten digits, lacking any referent beyond itself. In it, a subject is wholly constituted in terms of its position in the system. The essential characteristic of a subject is a class symbol which refers only to other symbols. Its verbal equivalent is accidental, a merely pragmatic characteristic... .... The conflict of interpretations over "subjects" became explicit in the battles between "bibliography" (an approach to subjects having much in common with Cutter's) and Dewey's "close classification". William Fletcher spoke for the scholarly bibliographer.... Fletcher's "subjects", like Cutter's, referred to the categories of a fantasized, stable social order, whereas Dewey's subjects were elements of a semiological system of standardized, techno-bureaucratic administrative software for the library in its corporate, rather than high culture, incarnation". (Frohmann, 1994, 112–113). Cutter's early view on what a subject is, is probably wiser than most understandings that dominated the 20th century – and also the understanding reflected in the ISO-standard quoted below. The early statements quoted by Frohmann indicate that subjects are somehow shaped in social processes. When that is said, it should be added that they are not particularly detailed or clear. We only get a vague idea of the social nature of subjects. === S. R. Ranganathan (1892–1972) === A classification system with an explicit theoretical foundation is Ranganathan's Colon Classification. Ranganathan provided an explicit definition of the concept of "subject": Subject – an organized body of ideas, whose extension and intension are likely to fall coherently within the field of interests and comfortably within the intellectual competence and the field of inevitable specialization of a normal person. A related definition is given by one of Ranganathan's students: A subject is an organized and systematized body of ideas. It may consist of one idea or a combination of several... Ranganathan's definition of "subject" is strongly influenced by his Colon Classification system. The colon system is based on the combination of single elements from facets to subject designation. This is the reason why the combined nature of subjects are emphasized so strongly. It leads, however, to absurdities such as the claim that gold cannot be a subject (but is alternatively termed "an isolate"). This aspect of the theory has been criticized by Metcalfe (1973, p. 318). Metcalfe's skepticism regarding Ranganathan's theory is formulated in hard words (op. cit., p. 317): "This pseudo-science imposed itself on British disciples from about 1950 on...". It seems unacceptable that Ranganathan defines the word subject in a way that favors his own system. A scientific concept like "subject" should make it possible to compare different ways of establishing access to information. Whether or not subjects are combined or not should be examined once their definition has been given, it should not determined a priori, in the definition. Besides the emphasis on the combined, organizing and systematizing nature of subjects contains Ranganathan's definition of subject the pragmatic demand, that a subject should be determined in a way that suits a normal person's competency or specialization. Again we see a strange kind of wishful thinking mixing a general understanding of a concept with demands put by his own specific system. One thing is what the word subject means, quite another issue is how to provide subject descriptions that fulfill demands such as the specificity of a given information retrieval language which fulfill demands put on the system, such as precision and recall. If researchers too often define terms in ways that favor specific kinds of systems, that are such definitions not useful to provide more general theories about subjects, subject analysis and IR. Among other things are comparative studies of different kinds of systems made difficult. Based on these arguments, as well as additional arguments which have been used in the literature, we may conclude that Ranganathan's definition of the concept "subject" is not suited for scientific use. Like the definition of "subject" given by the ISO-standard for topic maps, may Ranganathan's definition be useful within his own closed system. The purpose of a scientific and scholarly field is, however, to examine the relative fruitfulness of systems such as topic maps and Colon Classification. For such purpose is another understanding of "subject" necessary. === Patrick Wilson (1927–2003) === In his book Wilson (1968) examined – in particular by thought experiments – the suitability of different methods of examining the subject of a document. The methods were: identifying the author's purpose for writing the document, weighing the relative dominance and subordination of different elements in the picture, which the reading imposes on the reader, grouping or count the document's use of concepts and references, construing a set of rules for selecting elements deemed necessary (as opposed to unnecessary) for the work as a whole. Patrick Wilson shows convincingly that each of these methods are insufficient to determine the subject of a document and is led to conclude ( p. 89): "The notion of the subject of a writing is indeterminate..." or, on p. 92 (about what users may expect to find using a particular position in a library classification system): "For nothing definite can be expected of the things found at any given position". In connection to the last quote has Wilson an interesting footnote in which he writes that authors of documents often use terms in ambiguous ways ("hostility" is used as an example). Even if the librarian could personally develop a very precise understanding of a concept, he would be unable to use it in his classification, because none of the documents use the term in the same precise way. Based on this argumentation is Wilson led to conclude: "If people write on what are for them ill-defined phenomena, a correct description of their subjects must reflect the ill-definedness". Wilson's concept of subject was discussed by Hjørland (1992) who found that it is problematic to give up the precise understanding of such a basic term in LIS. Wilson's arguments led him to an agnostic position which Hjørland found unacceptable and unnecessary. Concerning the authors' use of ambiguous terms, the role of the subject analysis is to determine which documents would be fruitful for users to identify whether or not the documents use one or another term or whether a given term i
Informationist
An informationist (or information specialist in context) provides research and knowledge management services in the context of clinical care or biomedical research. Although there is no one educational pathway or formalized set of skills or knowledge for informationists, one way to think of the informationist is as one who possesses the knowledge and skill of a medical librarian with extensive research specialization and some formal clinical or public health education that goes beyond on-the-job osmosis. Medical librarians and other biomedical professional organizations have been exploring the possibilities for evaluating how informationists are being used and whether their activities supplement or replace medical library activity. More generally, an informationist is a professional who works with information within a particular business, analytic or scientific context to drive toward outcomes based on evidence, analysis, prediction and execution. For example, an extension of the term is increasingly emerging in financial services, life sciences and health care industries. Though still nascently in use, its adoption applies to individuals with extensive industry expertise, acute familiarity with organizational structures and processes, deep domain level information mastery and information systems technical savvy. Informationists in this context support transformational initiatives within and across functional areas of an enterprise as architects, governance experts, continuous improvement advocates and strategists. == Background == The term was proposed in 2000 by Davidoff & Florance. Their editorial suggested that physicians should be delegating their information needs to informationists, just as they currently order CT scans from radiologists or cardiac catheterizations from cardiologists. They conceived of an information professional who was embedded in (and indeed, supported by) the clinical departments. Supporters of the concept see it as a means for librarians to reinvigorate connections with the faculty/clinicians, as well as provide superior service by dint of informationists' biomedical training. Critics complained that the idea is nothing new; librarians already provide in-depth, high quality information services and clinical medical librarians have been working alongside physicians, nurses and other clinicians for years. Large informationist programs in the U.S. exist at the National Institutes of Health and at Vanderbilt University. Welch Medical Library at Johns Hopkins University (JHU) is developing an informationist service model in which its 10 clinical and public health librarians are moving from serving as liaison librarians for assigned departments toward becoming embedded informationists within their departments. To prepare for the embedded informationist role, librarians are undertaking education as needed to supplement their backgrounds. For example, librarians bring experience in clinical behavior counseling, public health, nursing, and more. Informationist training can then focus upon filling gaps in research methods knowledge more so than on gaining additional knowledge in the librarian's area of expertise. Courses, seminars and workshops being undertaken include those covering systematic reviews, evidence-based medicine, critical appraisal, medical language, anatomy and physiology, biostatistics, and clinical research. The term informationist is related to that of informatician—also informaticist—and many informationists do possess skills in clinical topics, bioinformatics, and biomedical informatics. Harvard University, the University of Pittsburgh, and Washington University in St. Louis are examples of institutional libraries which have hired PhD-level scientists (who may or may not have library degrees) to provide informatics support for biomedical research.
Fillrate
In computer graphics, a video card's pixel fillrate refers to the number of pixels that can be rendered on the screen and written to video memory in one second. Pixel fillrates are given in megapixels per second or in gigapixels per second (in the case of newer cards), and are obtained by multiplying the number of render output units (ROPs) by the clock frequency of the graphics processing unit (GPU) of a video card. A similar concept, texture fillrate, refers to the number of texture map elements (texels) the GPU can map to pixels in one second. Texture fillrate is obtained by multiplying the number of texture mapping units (TMUs) by the clock frequency of the GPU. Texture fillrates are given in mega or gigatexels per second. However, there is no full agreement on how to calculate and report fillrates. Another possible method is to multiply the number of pixel pipelines by the GPU's clock frequency. The results of these multiplications correspond to a theoretical number. The actual fillrate depends on many other factors. In the past, the fillrate has been used as an indicator of performance by video card manufacturers such as ATI and NVIDIA, however, the importance of the fillrate as a measurement of performance has declined as the bottleneck in graphics applications has shifted. For example, today, the number and speed of unified shader processing units has gained attention. Although fillrate doesn't provide a substantial bottleneck in games, it can still provide a bottleneck for certain parts of the game, for example applying a gaussian blur can be bottlenecked by fillrate. Scene complexity can be increased by overdrawing, which happens when an object is drawn to the frame buffer, and another object (such as a wall) is then drawn on top of it, covering it up. The time spent drawing the first object is thus wasted because it is not visible. When a sequence of scenes is extremely complex (many pixels have to be drawn for each scene), the frame rate for the sequence may drop. When designing graphics intensive applications, one can determine whether the application is fillrate-limited (or shader limited) by seeing if the frame rate increases dramatically when the application runs at a lower resolution or in a smaller window. Although this is not a full-proof method, modern videogame engines can dynamically reduce the level-of-detail required and thereby reducing fillrate-limited applications. The best way to find fillrate bottlenecks is to use GPU vendor software like NVIDIA Nsight Graphics, AMD Radeon GPU Profile and the Intel Graphics Performance Analyzers.
Knuth–Plass line-breaking algorithm
The Knuth–Plass algorithm is a line-breaking algorithm designed for use in Donald Knuth's typesetting program TeX. It integrates the problems of text justification and hyphenation into a single algorithm by using a discrete dynamic programming method to minimize a loss function that attempts to quantify the aesthetic qualities desired in the finished output. The algorithm works by dividing the text into a stream of three kinds of objects: boxes, which are non-resizable chunks of content, glue, which are flexible, resizeable elements, and penalties, which represent places where breaking is undesirable (or, if negative, desirable). The loss function, known as "badness", is defined in terms of the deformation of the glue elements, and any extra penalties incurred through line breaking. Making hyphenation decisions follows naturally from the algorithm, but the choice of possible hyphenation points within words, and optionally their preference weighting, must be performed first, and that information inserted into the text stream in advance. Knuth and Plass' original algorithm does not include page breaking, but may be modified to interface with a pagination algorithm, such as the algorithm designed by Plass in his PhD thesis. Typically, the cost function for this technique should be modified so that it does not count the space left on the final line of a paragraph; this modification allows a paragraph to end in the middle of a line without penalty. The same technique can also be extended to take into account other factors such as the number of lines or costs for hyphenating long words. == Computational complexity == A naive brute-force exhaustive search for the minimum badness by trying every possible combination of breakpoints would take an impractical O ( 2 n ) {\displaystyle O(2^{n})} time. The classic Knuth-Plass dynamic programming approach to solving the minimization problem is a worst-case O ( n 2 ) {\displaystyle O(n^{2})} algorithm but usually runs much faster, in close to linear time. Solving for the Knuth-Plass optimum can be shown to be a special case of the convex least-weight subsequence problem, which can be solved in O ( n ) {\displaystyle O(n)} time. Methods to do this include the SMAWK algorithm. == Simple example of minimum raggedness metric == For the input text AAA BB CC DDDDD with line width 6, a greedy algorithm that puts as many words on a line as possible while preserving order before moving to the next line, would produce: ------ Line width: 6 AAA BB Remaining space: 0 CC Remaining space: 4 DDDDD Remaining space: 1 The sum of squared space left over by this method is 0 2 + 4 2 + 1 2 = 17 {\displaystyle 0^{2}+4^{2}+1^{2}=17} . However, the optimal solution achieves the smaller sum 3 2 + 1 2 + 1 2 = 11 {\displaystyle 3^{2}+1^{2}+1^{2}=11} : ------ Line width: 6 AAA Remaining space: 3 BB CC Remaining space: 1 DDDDD Remaining space: 1 The difference here is that the first line is broken before BB instead of after it, yielding a better right margin and a lower cost 11.