This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
Symbol Table Applications: Sets (optional)
Loading...
來自 Princeton University 的課程
Algorithms, Part I
3801 個評分
從本節課中
Symbol Table Applications
We consider various applications of symbol tables including sets, dictionary clients, indexing clients, and sparse vectors.
與講師見面
Kevin WayneSenior Lecturer
Computer Science
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Welcome back. Today we are going to look at some symbol table applications, give
you some idea of how symbol tables might be used, by client program for practical
problems. First when we look at, seems even simpler than the regular symbol
tables, and that's about sets. So, a mathematical set is just a collection of
distinct keys. And so, there are plenty of applications where we want to just be able
to implement, this really simple API. I want to be able to create an empty set,
we've got methods to add a key to the set, and to check whether a given key is in the
set or not. To remove a key, and maybe return the number of keys in the set, and
also have an iterator to iterate through keys in the set. This is simpler than
symbol tables because it's got no associated value. So, it's a very simple
API but of course, we're going to be able to do these operations efficiently, how
we'd we go ahead and implement that. Well, if you think about it for just a minute,
you see that what you need to do is just remove all references to value from any of
the symbol table implementations that we'd look at. The implementation is easy. Take
one of our symbol table implementations and get rid of the code that refers to
values. Okay, so let's look at a couple of applications where this set API might be
useful in client programs. One thing that is very common is the idea of an exception
filter. So the way we'll set that up is to think about having a list of files a list
of words in a file that are exceptional in some way. In this case, we'll have the
word, the file list.text that has these four words in it: was, it, the, and of. So
this two, complimentary ways to look at this. One is so-called White Listing where
we want to take the words in that file and, and then we have some other much
bigger file. And what we want to do is print out all the occurrences of our
exceptional words in our given file. Those are the ones that we care about, that we
want to get through. So in this case, tinyTale.txt the first couple of words
from "A Tale of Two Cities." and these words appear often, "It was the of, it was
the of." another, A complementary approach is to think of these words as words that
we don't want to ever see. They're blacklist, and we want to take them out of
our source file. So a blacklist client would print out all the words in our
source file, tinyTale.txt except was, it, be, and of. In this case, best times,
worst times, and so forth. So that's the exception filter, and that's useful in
lots of applications such as the ones listed here. For example, you might have a
spellchecker where you want to identify misspelled words. So, then your key would
be a word or a string. And in your exceptional list would be words that are
in the dictionary. And you'd want to print out all the words that are not in the
dictionary. That's an example of a, an exception filter. Or in a browser you
might want to mark your visited pages or block sites and so forth. Or like the one
at the bottom credit cards. Maybe, you run a credit card company and you want to
check for stolen cards then your keys would be numbers. I. And in your list,
might be kind of short, which would be the stolen cards that you know about, and
you'd want to run a, a white list filter for those cards and print out in your long
list of transactions which ever transactions have that stolen cards, So,
that's just a couple of examples of exception filters. What's the
implementation of an exception filters? Here's a simple one using the said API
that we just articulated. So, we start by creating an empty set of strings, and
again since we don't have associated values, we just have the one generic for
strings, and then create a new input stream from, from the first argument so
that's the name of the file that contains the exceptional words and so this just
reads the strings while the input string is not empty and then adds the m to the
set. So that now, we have our set of exceptional words. And now, from standard
input we read words, as long as our set contains the word, we print it out. And if
doesn't contain it, we don't print it out. So that's an example of a white list
filter. And to implement black list we just this call to contains, we just change
that to a, a not. If it's not in the exceptional list, then we print it out. So
that's a simple example of a filter using sets.
