Computer Science Reflections on the Field, Reflections from the Field (2004) / Chapter Skim
Currently Skimming:
8 Research Behind Everyday Computation
8 Research Behind Everyday Computation
Pages 159-178
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 159... ...
, and easily usable browsers together with new algorithms for searching has led to an explosion of information-retrieval opportunities that has changed forever the way we do business. Computers now perform most of the document-preparation tasks that used to be handled by secretaries: typing drafts, correcting drafts, positioning figures, formatting final copy, and the like.
|
From page 160... ...
The idea of information retrieval is far from new, but the ability to dedicate computing power to amplifying human effort has led to new wrinkles, such as attempts to establish the relevance of information based on the number of people referring to it. Norvig explains the technology behind modern Internet searches.
|
From page 161... ...
program. A "macro" capability was added to allow repetitive formatting concepts, such as section headers or indented paragraphs, to be defined once and used easily many times.
|
From page 162... ...
This device allowed printing to be done in several fonts and font sizes. Unlike today's laser printers, it printed only on photographic paper, which was then reproduced by one of several processes, such as a "Xerox machine." NROFF evolved into TROFF (typesetter runoff)
|
From page 163... ...
As envisioned, the Dover changed markedly the way students and faculty prepared papers. Also as envisioned, the cost for building such devices has dropped dramatically over the years, and the dream of a laser printer on every desk has become real.
|
From page 164... ...
TeX's paragraphing algorithm looks at the words of an entire paragraph before deciding on line-breaks, and thereby improves the look of the text when compared with "greedy" algorithms that look at text a line at a time and fit whatever they can on each line in succession. The TeX paragraphing algorithm is an excellent example of a general computational approach called "dynamic programming." It works roughly as follows.
|
From page 165... ...
It allows global changes in the way elements such as sections are displayed, just as the early Bell Labs macro packages did.
|
From page 166... ...
The system provides a virtually unlimited number of fonts. Perhaps as a reflection on how prevalent word processing has become in ordinary discourse, neither Microsoft nor other manufacturers of wordprocessing applications have felt the need to integrate mathematical typesetting nearly as closely as did EQN.
|
From page 167... ...
The VisiCalc spreadsheet program (whose commercial successors include Microsoft's Excel) caused many financial analysts, business people, accountants, and students to buy personal computers (first the Apple II and later the IBM PC)
|
From page 168... ...
In multiple ways: 3Strictly speaking, as soon as any of the variables such as B6 or C5 change, the equation is re-evaluated and the new value is placed in cell B9, whereas with the programming languages the assignment statement is executed only when the program flow of control comes to the statement. This means that the VisiCalc equation is a more powerful construct than the programming language assignment statement.
|
From page 169... ...
user interface, in which one sees the spreadsheet and can directly manipulate cells in the spreadsheet by pointing at them. Dan Bricklin states in his Web pages4 that he was aware of and influenced by the early research work of Doug Engelbart on text editors using a mouse, and that he had probably seen a demonstration of Xerox PARC's Alto computer system, which was in turn also influenced by Engelbart.
|
From page 170... ...
The idea of programming by example was developed in a slightly different form by Moshe Zloof of IBM research a few years earlier. Zloof wanted to allow users to specify database queries without having to learn a query programming language (such as SQL)
|
From page 171... ...
as VisiCalc leveraged and accelerated the availability of PCs and e-mail leveraged the Internet and Web browsers leveraged the World Wide Web protocols. We also note that only Web browsing was well anticipated as a killer app -- anticipated by Vannevar Bush in the 1940s and researched by a number of prominent computer scientists from the late 1960s into the 1980s.
|
From page 172... ...
Many cars already have built-in wireless phones, global positioning systems, limited voice recognition, and navigation aids. Many people spend tens of hours a week in a car, and there are significant personal and societal benefits to further leveraging the automotive computing infrastructure to make driving safer, to connect us with the outside world, and to entertain us.
|
From page 173... ...
RESEARCH BEHIND EVERYDAY COMPUTATION 173 the early days when the automobile was still known as the "horseless buggy." At that time, nearly a century ago, one could not imagine the cars and highways of today. While we can and should be proactive in exploring these possibilities and their implications for our lives, it is also true that only time will tell.
|
From page 174... ...
However, the conceptual simplicity hides a large number of practical complications: sites may be busy or down at one point and come back to life later; pages may be duplicated at multiple sites (or with different URLs at the same site) and must be dealt with accordingly; many pages have text that does not conform to the standards for HTML, HTTP redirection, robot exclusion, or other protocols; some information is hard to access because it is hidden behind a form, Flash animation, or Javascript program.
|
From page 175... ...
, which again means that distributed computing is required. Most modern search engines index link data as well as word data.
|
From page 176... ...
Of the three, Internet searching is by far the most sophisticated example of computer science technology. Building a high-quality search engine requires extensive knowledge and experience in information retrieval, data structure design, user interfaces, and distributed systems implementation.
|
From page 177... ...
It turns out that the vast amount of correctly and incorrectly spelled text available to a search engine makes it easier to create a good spelling corrector than traditional techniques based on dictionaries. It is likely that there will be other examples of text understanding that can be accomplished better with a data-oriented approach; this is an area that search engines are just beginning to explore.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.