CS 117: AI Author

Overview

Artificial intelligence is an active and exciting area of computer science. Can computers be made to do tasks that seem "intelligent"? Some of the goals (and partial successes) of artificial intelligence include important areas such as medical diagnosis, drug discovery, and robotics. For this assignment, we will visit the part of artificial intelligence referred to as "natural language processing," i.e. getting a computer to work with a natural language such as English.

More specifically, you will write a program called AIAuthor that will actually write original prose in the style of a chosen human author. Can computers actually be creative? We'll find out!

Details

Find a source text. Specifically, find a text file that contains some text that you want the computer to creatively imitate. Project Gutenberg is a great place to start.

The technique that you will use works conceptually as follows:

• Ask the user to specify a source text file, to specify an integer to server as a key (which we'll denote as k throughout this description), and the number of characters that the program should generate.

• Read the source text into memory as a single string. Unlike previous examples of reading text (like for the spelling dictionary), we actually want to retain spaces in the original document. Therefore, you should read in an entire line at a time, instead of a word at time. Check out the Scanner class nextLine method.

  You will also want to use a StringBuffer instead of a String to hold the data as you read it in. The problem with using a String to hold the data is that every time you read a new line, you need to append it to the old one. Every time that you append to a String, Java creates a brand new one by copying the old String and then appending the new text. This is extemely slow. A StringBuffer is much faster way to manage appending multiple strings of text. When you're done appending, you can convert the StringBuffer back to a normal String. Here's an example:
  
  

  StringBuffer sbuf = new StringBuffer();
  sbuf.append("hello");
  sbuf.append(" goodbye ");
  sbuf.append("friends");
  String text = sbuf.toString(); // converts the StringBuffer to a normal string
  

  Be careful when you append the lines together that you append a space appropriately at the end of each line. If you don't handle this right, the last character of each line and the first character of the next next line will always appear right next to each other.

• Once you have the source text in memory, choose a random string of length k to start as the seed. Print it to the screen.
• Look through the entire source document to find all occurrences of this seed in order to determine what character follows. For example, if k=5, and your seed is memor, you may find that the text memor appears multiple times throughout your document sometimes followed by a i (memories) and sometimes followed by a y (memory). Determine all characters (including punctuation, etc.) that follow your seed, and choose one randomly. Make sure that you do this in such a way that if the i appears more often than the y for example, it is more likely to be chosen. Print this letter to the screen. You may find the substring method of a String to be helpful here.
• Create a new seed consisting of all characters from your previous seed except the first, and add the character you chose in the previous step to be the new seed. For example, if your previous seed was memor and you chose a i as the next character, your new seed is emori. Repeat the above process.

Here's an example of some text that my program generates, using a key of 5 on Grimm's fairy tales:

Alternatively, when I tried it with a key of 8, here's what I got one of the times that I ran it:

Finally, you may find for this assignment that instead of using arrays, the ArrayList class will be easier. We will talk about this in class, but you can also read about it in your textbook.

Making it run faster

The above technique works, but you may find it runs somewhat slowly on large source texts. Get the program to work using the above technique first. If you submit a working version of the program using the above ideas, and your program is well written (style, etc.), you'll get 15 of the 20 points for the project. To get the remaining 5 points, implement the following ideas to speed up your program.

The main speed bottleneck in your program is due to the fact that in order to generate each character, you need to do a sequential search through the entire text to look for your seed. Your program would run considerably faster if you created a list of all the possible seeds in your program followed by the characters that come next, all in sorted order. You could then use a binary search to find your seed, and quickly find all characters that follow it.

The technique to clearly use, then, is to sort all of the seed strings (and the associated next characters) before starting. The catch is that the various sorts that we have already considered (insertion sort and selection sort) are too slow given the size of the source text. Try it and see! Instead, you should use a technique called radix sort, which works quite well when the data that you use all has the same length. We'll talk about radix sort in class, but you can also find a description of radix sort here. (This linked description shows how to do it for a string of digits where the only allowable characters are 0 through 9; you'll need to do it for a string of characters where any legitimate ASCII value is allowed.)

Final notes

Make sure that you use good object-oriented design. Think carefully about how to layout your program so that you use classes and objects appropriately, and so that your methods remain short and self-contained. Follow the course style guidelines.

Remember to get a slow version of the program working first before going for the fast one. Start early, and good luck!