>>> import pdb
>>> find_words(['cat'], 3) 
['cat']
>>> pdb.run("find_words(['dog'], 3)") 
> <string>(1)<module>()
(Pdb) step
--Call--
> <stdin>(1)find_words()
(Pdb) args
text = ['dog']
wordlength = 3
result = ['cat']
Here we typed just two commands into the debugger: 
step
took us inside the function,
and 
args
showed the values of its arguments (or parameters). We see immediately that
result
has an initial value of 
['cat']
, and not the empty list as expected. The debugger
has helped us to localize the problem, prompting us to check our understanding of
Python functions.
Defensive Programming
In order to avoid some of the pain of debugging, it helps to adopt some defensive
programming habits. Instead of writing a 20-line program and then testing it, build the
program bottom-up out of small pieces that are known to work. Each time you combine
these pieces to make a larger unit, test it carefully to see that it works as expected.
Consider adding 
assert
statements to your code, specifying properties of a variable,
e.g., 
assert(isinstance(text, list))
. If the value of the 
text
variable later becomes a
string when your code is used in some larger context, this will raise an
AssertionError
and you will get immediate notification of the problem.
Once you think you’ve found the bug, view your solution as a hypothesis. Try to predict
the effect of your bugfix before re-running the program. If the bug isn’t fixed, don’t fall
into the trap of blindly changing the code in the hope that it will magically start working
again. Instead, for each change, try to articulate a hypothesis about what is wrong and
why the change will fix the problem. Then undo the change if the problem was not
resolved.
As you develop your program, extend its functionality, and fix any bugs, it helps to
maintain a suite of test cases. This is called regression testing, since it is meant to
detect situations where the code “regresses”—where a change to the code has an un-
intended side effect of breaking something that used to work. Python provides a simple
regression-testing framework in the form of the 
doctest
module. This module searches
a file of code or documentation for blocks of text that look like an interactive Python
session, of the form you have already seen many times in this book. It executes the
Python commands it finds, and tests that their output matches the output supplied in
the original file. Whenever there is a mismatch, it reports the expected and actual val-
ues. For details, please consult the 
doctest
documentation at
4.6  Program Development t | | 159
Split pdf into multiple files - Merge, append PDF files in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Provide C# Demo Codes for Merging and Appending PDF Document
batch combine pdf; scan multiple pages into one pdf
Split pdf into multiple files - VB.NET PDF File Merge Library: Merge, append PDF files in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
VB.NET Guide and Sample Codes to Merge PDF Documents in .NET Project
combine pdf; pdf combine files online
http://docs.python.org/library/doctest.html. Apart from its value for regression testing,
the 
doctest
module is useful for ensuring that your software documentation stays in
sync with your code.
Perhaps the most important defensive programming strategy is to set out your code
clearly, choose meaningful variable and function names, and simplify the code wher-
ever possible by decomposing it into functions and modules with well-documented
interfaces.
4.7  Algorithm Design
This section discusses more advanced concepts, which you may prefer to skip on the
first time through this chapter.
A major part of algorithmic problem solving is selecting or adapting an appropriate
algorithm for the problem at hand. Sometimes there are several alternatives, and choos-
ing the best one depends on knowledge about how each alternative performs as the size
of the data grows. Whole books are written on this topic, and we only have space to
introduce some key concepts and elaborate on the approaches that are most prevalent
in natural language processing.
The best-known strategy is known as divide-and-conquer. We attack a problem of
size n by dividing it into two problems of size n/2, solve these problems, and combine
their results into a solution of the original problem. For example, suppose that we had
a pile of cards with a single word written on each card. We could sort this pile by
splitting it in half and giving it to two other people to sort (they could do the same in
turn). Then, when two sorted piles come back, it is an easy task to merge them into a
single sorted pile. See Figure 4-3 for an illustration of this process.
Another example is the process of looking up a word in a dictionary. We open the book
somewhere around the middle and compare our word with the current page. If it’s
earlier in the dictionary, we repeat the process on the first half; if it’s later, we use the
second half. This search method is called binary search since it splits the problem in
half at every step.
In another approach to algorithm design, we attack a problem by transforming it into
an instance of a problem we already know how to solve. For example, in order to detect
duplicate entries in a list, we can pre-sort the list, then scan through it once to check
whether any adjacent pairs of elements are identical.
Recursion
The earlier examples of sorting and searching have a striking property: to solve a prob-
lem of size n, we have to break it in half and then work on one or more problems of
size n/2. A common way to implement such methods uses recursion. We define a
function f, which simplifies the problem, and calls itself to solve one or more easier
160 | | Chapter 4: Writing Structured Programs
C# PDF File Split Library: Split, seperate PDF into multiple files
outputFiles); Split PDF Document into Multiple PDF Files in C#. You can use the following C# demo to split PDF document to four files.
pdf split and merge; merge pdf online
VB.NET PDF File Split Library: Split, seperate PDF into multiple
Split PDF file into two or multiple files in ASP.NET webpage online. Split PDF Document into Multiple PDF Files Demo Code in VB.NET.
add pdf files together online; acrobat combine pdf files
instances of the same problem. It then combines the results into a solution for the
original problem.
For example, suppose we have a set of n words, and want to calculate how many dif-
ferent ways they can be combined to make a sequence of words. If we have only one
word (n=1), there is just one way to make it into a sequence. If we have a set of two
words, there are two ways to put them into a sequence. For three words there are six
possibilities. In general, for n words, there are n × n-1 × … × 2 × 1 ways (i.e., the factorial
of n). We can code this up as follows:
>>> def factorial1(n):
...     result = 1
...     for i in range(n):
...         result *= (i+1)
...     return result
However, there is also a recursive algorithm for solving this problem, based on the
following observation. Suppose we have a way to construct all orderings for n-1 distinct
words. Then for each such ordering, there are n places where we can insert a new word:
at the start, the end, or any of the n-2 boundaries between the words. Thus we simply
multiply the number of solutions found for n-1 by the value of n. We also need the
base case, to say that if we have a single word, there’s just one ordering. We can code
this up as follows:
>>> def factorial2(n):
...     if n == 1:
...         return 1
...     else:
...         return n * factorial2(n-1)
Figure 4-3. Sorting by divide-and-conquer: To sort an array, we split it in half and sort each half
(recursively); we merge each sorted half back into a whole list (again recursively); this algorithm is
known as “Merge Sort.”
4.7  Algorithm Design n | 161
Online Split PDF file. Best free online split PDF tool.
Easy split! We try to make it as easy as possible to split your PDF files into Multiple ones. You can receive the PDF files by simply
build pdf from multiple files; add multiple pdf files into one online
C# PDF Page Insert Library: insert pages into PDF file in C#.net
the ability to inserting a new PDF page into existing PDF PDF page using C# .NET, how to reorganize PDF document pages and how to split PDF document in
best pdf merger; combine pdf online
These two algorithms solve the same problem. One uses iteration while the other uses
recursion. We can use recursion to navigate a deeply nested object, such as the Word-
Net hypernym hierarchy. Let’s count the size of the hypernym hierarchy rooted at a
given synset s. We’ll do this by finding the size of each hyponym of s, then adding these
together (we will also add 1 for the synset itself). The following function 
size1()
does
this work; notice that the body of the function includes a recursive call to 
size1()
:
>>> def size1(s):
...     return 1 + sum(size1(child) for child in s.hyponyms())
We can also design an iterative solution to this problem which processes the hierarchy
in layers. The first layer is the synset itself 
, then all the hyponyms of the synset, then
all the hyponyms of the hyponyms. Each time through the loop it computes the next
layer by finding the hyponyms of everything in the last layer 
. It also maintains a total
of the number of synsets encountered so far 
.
>>> def size2(s):
...     layer = [s] 
...     total = 0
...     while layer:
...         total += len(layer) 
...         layer = [h for c in layer for h in c.hyponyms()] 
...     return total
Not only is the iterative solution much longer, it is harder to interpret. It forces us to
think procedurally, and keep track of what is happening with the 
layer
and 
total
variables through time. Let’s satisfy ourselves that both solutions give the same result.
We’ll use a new form of the import statement, allowing us to abbreviate the name
wordnet
to 
wn
:
>>> from nltk.corpus import wordnet as wn
>>> dog = wn.synset('dog.n.01')
>>> size1(dog)
190
>>> size2(dog)
190
As a final example of recursion, let’s use it to construct a deeply nested object. A letter
trie is a data structure that can be used for indexing a lexicon, one letter at a time. (The
name is based on the word retrieval.) For example, if 
trie
contained a letter trie, then
trie['c']
would be a smaller trie which held all words starting with cExample 4-6
demonstrates the recursive process of building a trie, using Python dictionaries (Sec-
tion 5.3). To insert the word chien (French for dog), we split off the c and recursively
insert hien into the sub-trie 
trie['c']
. The recursion continues until there are no letters
remaining in the word, when we store the intended value (in this case, the word dog).
162 | | Chapter 4: Writing Structured Programs
VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.
Images. File & Page Process. File: Merge, Append PDF Files. File: Split PDF Document. Turn multiple pages PDF into multiple jpg files in VB.NET class.
.net merge pdf files; add pdf together
VB.NET TWAIN: Scanning Multiple Pages into PDF & TIFF File Using
This VB.NET TWAIN pages scanning control add-on is developed to offer programmers an efficient solution to scan multiple pages into one PDF or TIFF
acrobat merge pdf; c# merge pdf files into one
Example 4-6. Building a letter trie: A recursive function that builds a nested dictionary structure; each
level of nesting contains all words with a given prefix, and a sub-trie containing all possible
continuations.
def insert(trie, key, value):
if key:
first, rest = key[0], key[1:]
if first not in trie:
trie[first] = {}
insert(trie[first], rest, value)
else:
trie['value'] = value
>>> trie = nltk.defaultdict(dict)
>>> insert(trie, 'chat', 'cat')
>>> insert(trie, 'chien', 'dog')
>>> insert(trie, 'chair', 'flesh')
>>> insert(trie, 'chic', 'stylish')
>>> trie = dict(trie)               # for nicer printing
>>> trie['c']['h']['a']['t']['value']
'cat'
>>> pprint.pprint(trie)
{'c': {'value': 'stylish'}}}}}
Caution!
Despite the simplicity of recursive programming, it comes with a cost.
Each time a function is called, some state information needs to be push-
ed on a stack, so that once the function has completed, execution can
continue from where it left off. For this reason, iterative solutions are
often more efficient than recursive solutions.
Space-Time Trade-offs
We can sometimes significantly speed up the execution of a program by building an
auxiliary data structure, such as an index. The listing in Example 4-7 implements a
simple text retrieval system for the Movie Reviews Corpus. By indexing the document
collection, it provides much faster lookup.
Example 4-7. A simple text retrieval system.
def raw(file):
contents = open(file).read()
contents = re.sub(r'<.*?>', ' ', contents)
contents = re.sub('\s+', ' ', contents)
return contents
def snippet(doc, term): # buggy
text = ' '*30 + raw(doc) + ' '*30
pos = text.index(term)
return text[pos-30:pos+30]
4.7  Algorithm Design n | 163
C# PDF: C#.NET PDF Document Merging & Splitting Control SDK
C#.NET PDF Splitter to Split PDF File. In this section, we aims to tell you how to divide source PDF file into two smaller PDF documents at the page
batch pdf merger; all jpg to one pdf converter
VB.NET PDF Library SDK to view, edit, convert, process PDF file
Simply integrate into VB.NET project, supporting conversions to or from multiple supported images formats; merge, append, and split PDF files; insert, delete
pdf merge files; pdf combine pages
print "Building Index..."
files = nltk.corpus.movie_reviews.abspaths()
idx = nltk.Index((w, f) for f in files for w in raw(f).split())
query = ''
while query != "quit":
query = raw_input("query> ")
if query in idx:
for doc in idx[query]:
print snippet(doc, query)
else:
print "Not found"
A more subtle example of a space-time trade-off involves replacing the tokens of a
corpus with integer identifiers. We create a vocabulary for the corpus, a list in which
each word is stored once, then invert this list so that we can look up any word to find
its identifier. Each document is preprocessed, so that a list of words becomes a list of
integers. Any language models can now work with integers. See the listing in Exam-
ple 4-8 for an example of how to do this for a tagged corpus.
Example 4-8. Preprocess tagged corpus data, converting all words and tags to integers.
def preprocess(tagged_corpus):
words = set()
tags = set()
for sent in tagged_corpus:
for word, tag in sent:
words.add(word)
tags.add(tag)
wm = dict((w,i) for (i,w) in enumerate(words))
tm = dict((t,i) for (i,t) in enumerate(tags))
Another example of a space-time trade-off is maintaining a vocabulary list. If you need
to process an input text to check that all words are in an existing vocabulary, the vo-
cabulary should be stored as a set, not a list. The elements of a set are automatically
indexed, so testing membership of a large set will be much faster than testing mem-
bership of the corresponding list.
We can test this claim using the 
timeit
module. The 
Timer
class has two parameters: a
statement that is executed multiple times, and setup code that is executed once at the
beginning. We will simulate a vocabulary of 100,000 items using a list 
or set 
of
integers. The test statement will generate a random item that has a 50% chance of being
in the vocabulary 
.
164 | | Chapter 4: Writing Structured Programs
>>> from timeit import Timer
>>> vocab_size = 100000
>>> setup_list = "import random; vocab = range(%d)" % vocab_size 
>>> statement = "random.randint(0, %d) in vocab" % vocab_size * 2 
>>> print Timer(statement, setup_list).timeit(1000)
2.78092288971
>>> print Timer(statement, setup_set).timeit(1000)
0.0037260055542
Performing 1,000 list membership tests takes a total of 2.8 seconds, whereas the equiv-
alent tests on a set take a mere 0.0037 seconds, or three orders of magnitude faster!
Dynamic Programming
Dynamic programming is a general technique for designing algorithms which is widely
used in natural language processing. The term “programming” is used in a different
sense to what you might expect, to mean planning or scheduling. Dynamic program-
ming is used when a problem contains overlapping subproblems. Instead of computing
solutions to these subproblems repeatedly, we simply store them in a lookup table. In
the remainder of this section, we will introduce dynamic programming, but in a rather
different context to syntactic parsing.
Pingala was an Indian author who lived around the 5th century B.C., and wrote a
treatise on Sanskrit prosody called the Chandas Shastra. Virahanka extended this work
around the 6th century A.D., studying the number of ways of combining short and long
syllables to create a meter of length n. Short syllables, marked S, take up one unit of
length, while long syllables, marked L, take two. Pingala found, for example, that there
are five ways to construct a meter of length 4: V
4
= {LLSSLSLSLSSSSSS}. Observe
that we can split V
4
into two subsets, those starting with L and those starting with S,
as shown in (1).
(1)
V
4
=
LL, LSS
i.e. L prefixed to each item of V
2
= {L, SS}
SSL, SLS, SSSS
i.e. S prefixed to each item of V
3
= {SL, LS, SSS}
With this observation, we can write a little recursive function called 
virahanka1()
to
compute these meters, shown in Example 4-9. Notice that, in order to compute V
4
we
first compute V
3
and V
2
. But to compute V
3
, we need to first compute V
2
and V
1
. This
call structure is depicted in (2).
4.7  Algorithm Design n | 165
Example 4-9. Four ways to compute Sanskrit meter: (i) iterative, (ii) bottom-up dynamic
programming, (iii) top-down dynamic programming, and (iv) built-in memoization.
def virahanka1(n):
if n == 0:
return [""]
elif n == 1:
return ["S"]
else:
s = ["S" + prosody for prosody in virahanka1(n-1)]
l = ["L" + prosody for prosody in virahanka1(n-2)]
return s + l
def virahanka2(n):
lookup = [[""], ["S"]]
for i in range(n-1):
s = ["S" + prosody for prosody in lookup[i+1]]
l = ["L" + prosody for prosody in lookup[i]]
lookup.append(s + l)
return lookup[n]
def virahanka3(n, lookup={0:[""], 1:["S"]}):
if n not in lookup:
s = ["S" + prosody for prosody in virahanka3(n-1)]
l = ["L" + prosody for prosody in virahanka3(n-2)]
lookup[n] = s + l
return lookup[n]
from nltk import memoize
@memoize
def virahanka4(n):
if n == 0:
return [""]
elif n == 1:
return ["S"]
else:
s = ["S" + prosody for prosody in virahanka4(n-1)]
l = ["L" + prosody for prosody in virahanka4(n-2)]
return s + l
>>> virahanka1(4)
['SSSS', 'SSL', 'SLS', 'LSS', 'LL']
>>> virahanka2(4)
['SSSS', 'SSL', 'SLS', 'LSS', 'LL']
>>> virahanka3(4)
['SSSS', 'SSL', 'SLS', 'LSS', 'LL']
>>> virahanka4(4)
['SSSS', 'SSL', 'SLS', 'LSS', 'LL']
166 | | Chapter 4: Writing Structured Programs
(2)
As you can see, V
2
is computed twice. This might not seem like a significant problem,
but it turns out to be rather wasteful as n gets large: to compute V
20
using this recursive
technique, we would compute V
2
4,181 times; and for V
40
we would compute V
2
63,245,986 times! A much better alternative is to store the value of V
2
in a table and
look it up whenever we need it. The same goes for other values, such as V
3
and so on.
Function 
virahanka2()
implements a dynamic programming approach to the problem.
It works by filling up a table (called 
lookup
) with solutions to all smaller instances of
the problem, stopping as soon as we reach the value we’re interested in. At this point
we read off the value and return it. Crucially, each subproblem is only ever solved once.
Notice that the approach taken in 
virahanka2()
is to solve smaller problems on the way
to solving larger problems. Accordingly, this is known as the bottom-up approach to
dynamic programming. Unfortunately it turns out to be quite wasteful for some ap-
plications, since it may compute solutions to sub-problems that are never required for
solving the main problem. This wasted computation can be avoided using the top-
down approach to dynamic programming, which is illustrated in the function 
vira
hanka3()
in Example 4-9. Unlike the bottom-up approach, this approach is recursive.
It avoids the huge wastage of 
virahanka1()
by checking whether it has previously stored
the result. If not, it computes the result recursively and stores it in the table. The last
step is to return the stored result. The final method, in 
virahanka4()
, is to use a Python
“decorator” called 
memoize
, which takes care of the housekeeping work done by
virahanka3()
without cluttering up the program. This “memoization” process stores
the result of each previous call to the function along with the parameters that were
used. If the function is subsequently called with the same parameters, it returns the
stored result instead of recalculating it. (This aspect of Python syntax is beyond the
scope of this book.)
This concludes our brief introduction to dynamic programming. We will encounter it
again in Section 8.4.
4.8  A Sample of Python Libraries
Python has hundreds of third-party libraries, specialized software packages that extend
the functionality of Python. NLTK is one such library. To realize the full power of
Python programming, you should become familiar with several other libraries. Most
of these will need to be manually installed on your computer.
4.8  A Sample of Python Libraries s | | 167
Matplotlib
Python has some libraries that are useful for visualizing language data. The Matplotlib
package supports sophisticated plotting functions with a MATLAB-style interface, and
is available from http://matplotlib.sourceforge.net/.
So far we have focused on textual presentation and the use of formatted print statements
to get output lined up in columns. It is often very useful to display numerical data in
graphical form, since this often makes it easier to detect patterns. For example, in
Example 3-5, we saw a table of numbers showing the frequency of particular modal
verbs in the Brown Corpus, classified by genre. The program in Example 4-10 presents
the same information in graphical format. The output is shown in Figure 4-4 (a color
figure in the graphical display).
Example 4-10. Frequency of modals in different sections of the Brown Corpus.
def bar_chart(categories, words, counts):
"Plot a bar chart showing counts for each word by category"
import pylab
ind = pylab.arange(len(words))
width = 1 / (len(categories) + 1)
bar_groups = []
for c in range(len(categories)):
bars = pylab.bar(ind+c*width, counts[categories[c]], width,
color=colors[c % len(colors)])
bar_groups.append(bars)
pylab.xticks(ind+width, words)
pylab.ylabel('Frequency')
pylab.title('Frequency of Six Modal Verbs by Genre')
pylab.show()
>>> cfdist = nltk.ConditionalFreqDist(
...              (genre, word)
...              for genre in genres
...              for word in nltk.corpus.brown.words(categories=genre)
...              if word in modals)
...
>>> counts = {}
>>> for genre in genres:
...     counts[genre] = [cfdist[genre][word] for word in modals]
>>> bar_chart(genres, modals, counts)
From the bar chart it is immediately obvious that may and must have almost identical
relative frequencies. The same goes for could and might.
It is also possible to generate such data visualizations on the fly. For example, a web
page with form input could permit visitors to specify search parameters, submit the
form, and see a dynamically generated visualization. To do this we have to specify the
168 | | Chapter 4: Writing Structured Programs
Documents you may be interested
Documents you may be interested