Order-Zero, Order-One

Loading...

Del curso dictado por Duke University

Java Programming: Principles of Software Design

702 calificaciones

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Duke University

Java Programming: Principles of Software Design

702 calificaciones

Curso 4 de 5 en SpecializationJava Programming and Software Engineering Fundamentals

Solve real world problems with Java using multiple classes. Learn how to create programming solutions that scale using Java interfaces. Recognize that software engineering is more than writing code - it also involves logical thinking and design. By the end of this course you will have written a program that analyzes and sorts earthquake data, and developed a predictive text generator. After completing this course, you will be able to: 1. Use sorting appropriately in solving problems; 2. Develop classes that implement the Comparable interface; 3. Use timing data to analyze empirical performance; 4. Break problems into multiple classes, each with their own methods; 5. Determine if a class from the Java API can be used in solving a particular problem; 6. Implement programming solutions using multiple approaches and recognize tradeoffs; 7. Use object-oriented concepts including interfaces and abstract classes when developing programs; 8. Appropriately hide implementation decisions so they are not visible in public methods; and 9. Recognize the limitations of algorithms and Java programs in solving problems. 10. Recognize standard Java classes and idioms including exception-handling, static methods, java.net, and java.io packages.

De la lección

N-Grams: Predictive Text

In this module, you will explore some of the underlying concepts of predictive text. The first lesson will introduce random character generation and then how to train the character selection based on an input text. The second lesson will extend this concept to complete words. By the end of this module, you will be able to: (1) base random text generation on the frequency of characters in a training text, (2) collect a set of characters that occur in a text after randomly chosen initial character(s) to create a semi-random text, (3) extend the predictive text generation to use whole words, and (4) implement your own .equals method to compare complex data types.

Introduction5:45

Order-Zero, Order-One6:40

Finding Follow Set7:25

Implementing Order-Two9:23

Testing and Debugging7:36

Interfaces and Abstract Classes9:14

Conoce a los instructores

Robert Duvall
Lecturer
Computer Science
Owen Astrachan
Professor of the Practice
Computer Science
Andrew D. Hilton
Associate Professor of the Practice
Electrical and Computer Engineering
Susan H. Rodger
Professor of the Practice
Computer Science

Hi, in this lesson, we're going to walk through creating the class that

generates text at random, using an order-zero Markov algorithm.

We'll also describe what changes you'll need to make to create an order-one or

more Markov class.

Order-zero is straightforward to program,

and will be a model for other Markov classes.

All Markov models will use a training text as the basis for

generating text at random.

In an order-zero model, we don't use any characters to predict the next character.

We choose every character at random from the entire training text.

You can see an order-zero text here.

Words are long, and letter combinations don't always make sense.

It's hard to pronounce words like tmba, for example, or dnkmo.

In an order-one Markov model, we choose a character based on one previous character.

This makes letter combinations more common than an order-zero model

as you may see here, where words like bests are created randomly, and

words are easier to pronounce.

Even where they are words like stesurd and tico.

We'll provide a quick overview of developing the MarkovZero class.

And you'll be able to use it to generate text randomly.

We'll think about methods first.

Sometimes this is called the class' behavior.

Thinking about methods will help as we think about what state or

instance variables are needed.

We'll need to be able to set the training text for

the MarkovZero class, and we'll need to be able to generate text randomly.

That's two different methods.

We could combine these into one method, but

in general, keeping methods single purpose is a good idea.

In this case we might want to create several texts at random from this same

training text.

So keeping the methods separate makes lots of sense.

First we'll look at setting the training text in MarkovZero.

The training text is used when generating random text.

As I mentioned earlier,

we might want to create several texts at random from the same training text.

This means we'll need to store the training text in an instance variable.

The instance variable is assigned a value when the set training method is called,

and then accessed when text is generated at random.

The other method we'll design and implement generates text at random.

The getRandomText method will choose a character at random

from the training text.

We'll use the nextInt method from the class java.util.random to create a random

index, and we'll use this index to access the training text for a random character.

We'll create a StringBuilder object to store the random text, since adding or

concatenating to a StringBuilder is efficient.

We'll append to the StringBuilder object, and

we'll use the toString method to return a string when we're done.

We'll also need a constructor and perhaps other methods in the MarkovZero class.

Constructors typically initialize fields or instance variables.

In the MarkovZero class,

we have an instance field that stores a random object from the java.util package.

We create a new random object in the constructor.

It's often useful to generate a reproducible sequence

of random numbers to help with debugging.

We can do that by setting what's called the seed of the random number generator,

which we do here in creating a new random object.

This may help as you debug the Markov classes.

There's also an instance field myText, that's not initialized in the constructor,

but is by the setTrainingText method we discussed earlier.

This is enough background to write and test the MarkovZero class.

But we'll provide some guidance for MarkovOne as well.

We have a test program named MarkovRunner to test the MarkovZero class.

The user selects a file to use as the training text.

The code in MarkovRunner replaces each new line character with a space.

This preserves words which might be separated by spaces, but

doesn't treat new lines as special.

The MarkovRunner class creates several examples

of random text from the same training text.

What will change when you develop and use MarkovOne?

You'll use the same method, names, and the same state.

By using the same method names, the MarkovRunner test class can be used

to test MarkovOne as well as MarkovZero.

You'll need to change the getRandomText method, since one character

is used to predict the next character, in order-one Markov text generation.

We'll provide a quick overview of the concepts in MarkovOne.

You'll see more of the algorithmic development in a later lesson.

In an order-one Markov model,

one character is used to predict the next character at random.

In this diagram, we see that the letter a follows the letter t 12% of the time.

But the letter y follows 7% of the time.

This means that if we generate a t, then we're more likely to pick an e than an r

next, and both of those are more likely than picking an a,

according to the probabilities shown in the diagram.

The training data is used to create these probabilities.

But we don't actually create the probabilities, which would be possible but

more difficult and unnecessary compared to the method you'll use.

You'll write code to find every t in the training text.

Each time a t is found,

the next character is added to a list that represents the characters that follow t.

For example we might find the letters a, e, a, r,

a, e and y after the first seven ts in the training text.

Choosing from this list will be the same as using the probabilities,

since there will be more es in the list than ys.

We'll develop this algorithm using our seven step process.

Happy programming.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play