Text Justification Algorithm Memory Leak and also incorrect amount of characters per line

Question

I'm having trouble implementing a text justification algorithm on a large book.The program is able to take in smaller passages but once I load in the whole book I get a memory leak. More importantly, my algorithm is not putting the right amount of characters on a single line. I'm not quite sure why this is but if someone can please take a look at this and help me figure it out it will be greatly appreciated!

public class TextJustification {

 public String justify(String words[], int width) {

    int cost[][] = new int[words.length][words.length];

    //next 2 for loop is used to calculate cost of putting words from
    //i to j in one line. If words don't fit in one line then we put
    //Integer.MAX_VALUE there.
    for (int i = 0; i < words.length; i++) {
        cost[i][i] = width - words[i].length();
        for (int j = i + 1; j < words.length; j++) {
            cost[i][j] = cost[i][j - 1] - words[j].length() - 1;
        }
    }

    for (int i = 0; i < words.length; i++) {
        for (int j = i; j < words.length; j++) {
            if (cost[i][j] < 0) {
                cost[i][j] = Integer.MAX_VALUE;
            } else {
                cost[i][j] = (int) Math.pow(cost[i][j], 2);
            }
        }
    }

    //minCost from i to len is found by trying
    //j between i to len and checking which
    //one has min value
    int minCost[] = new int[words.length];
    int result[] = new int[words.length];
    for (int i = words.length - 1; i >= 0; i--) {
        minCost[i] = cost[i][words.length - 1];
        result[i] = words.length;
        for (int j = words.length - 1; j > i; j--) {
            if (cost[i][j - 1] == Integer.MAX_VALUE) {
                continue;
            }
            if (minCost[i] > minCost[j] + cost[i][j - 1]) {
                minCost[i] = minCost[j] + cost[i][j - 1];
                result[i] = j;
            }
        }
    }
    int i = 0;
    int j;

    System.out.println("Minimum cost is " + minCost[0]);
    System.out.println("\n");
    //finally put all words with new line added in
    //string buffer and print it.
    StringBuilder builder = new StringBuilder();
    do {
        j = result[i];
        for (int k = i; k < j; k++) {
            builder.append(words[k] + " ");
        }
        builder.append("\n");
        i = j;
    } while (j < words.length);

    return builder.toString();
}

public static void main(String args[]) throws IOException {

    File read = new File("TaleOfTwoCities.txt");
    Scanner in = new Scanner(read);

    ArrayList<String> temporary = new ArrayList<String>();

    while (in.hasNext()) {
        temporary.add(in.next());
    }

    String[] words1 = temporary.toArray(new String[temporary.size()]);


    //String words1[] = {"I", "am", "so", "stuck,", "please,", "help", "me"};
    TextJustification awl = new TextJustification();
    System.out.println(awl.justify(words1, 60));
}
}

Here is my code I hope someone is able to help me out as I have been scratching my head for a few days. Also the link to the txt file I am trying to parse is https://www.dropbox.com/s/5sy5zp4n3b6wgfz/TaleOfTwoCities.txt?dl=0 Thanks again guys and hope someone can help out!

EDIT: This is an image of how I am trying to justify the text since I didn't make that clear enough before: https://www.dropbox.com/s/f9xt83nflwj1q5p/project1.png?dl=0

Answer 1

The program is able to take in smaller passages but once I load in the whole book I get a memory leak.

I don't think your code has an actual "memory leak" — that is, your code isn't holding on to any object references that your algorithm doesn't actually need. Rather, it's just that your algorithm needs a lot of memory when applied to a large text.

Specifically, the problem is that you're using the algorithm for something it wasn't designed for. English prose is broken into paragraphs that are separated by line breaks (plus some extra horizontal and/or vertical space) and justified separately. Your code is eliminating all line-breaks in the entire novel, and trying to justify the entire thing as a single enormous paragraph. If that's intentional, then you'll probably want to use a less-expensive algorithm that provides less-perfect justification but doesn't require as much memory and computation.

More importantly, my algorithm is not putting the right amount of characters on a single line.

The algorithm (intentionally) allows the last line of the paragraph to be any length. That is, again, in keeping with the conventions of English prose. If that's not what you want, you'll need to make several adjustments to the algorithm. (Before you do that, you'll want to spend some time making sure you understand the algorithm.)

---

Edited to add (per comments):

Yes, that is completely what I want, to strip the text of all formatting and apply a line break once words of maximum 60 characters are in the line. I figured that the last line being able to hold any amount is fine since the rest of the text before would be formatted correctly, so the last line would always be a maximum of 60 characters. You speak of a less expensive algorithm, where can I find that?

The less expensive algorithm is to keep a variable currentLineLength (initially zero), and for each word:

• If (currentLineLength == 0 ? 0 : currentLineLength + 1) + word.length() <= 60, print a space, print the word, and update currentLineLength to (currentLineLength == 0 ? 0 : currentLineLength + 1) + word.length().
• Otherwise:
  • While word.length() > 60:
    • Print a newline, print word.substring(0, 59) (= the first 59 characters of word), print a hyphen.
    • Update word = word.substring(59).
  • Print a newline, print word, and update currentLineLength to word.length().

Answer 2

You do not have a memory leak. You are simply trying to use more memory than the JVM has available or can obtain. Sometimes a good solution to such a problem is simply to allow the VM to use more memory (this can be done via command-line options), but your particular program is flagrantly inefficient in its memory use, and I don't think you have any chance of making it work as written for large texts on anything short of a supercomputer.

First, you read the entire text into memory, as an ArrayList of separate Strings. This is pretty wasteful already, for you really need only to hold on to a few words at a time -- fewer than will fill two justified lines -- in order to compute the required justification.

But the real killer is this:

    int cost[][] = new int[words.length][words.length];

Your words is an array containing all the words in the work. For A Tale of Two Cities, that's about 135000 words, and you're creating a 2D array with the square of that number of elements, each of them four bytes wide. That would require around 73 GB of memory.

If you are at liberty to choose a different justification algorithm, then a good solution might be to switch to a line-by-line justification approach, enabling you to read only enough words at a time as needed, and to output each line as it is justified.

If you must use the current approach then you probably need to perform justification on smaller blocks of text -- around one tenth as many words at a time or fewer. For a book with distinct chapters or sections, it would make sense to justify on a chapter-by-chapter basis.

As for

More importantly, my algorithm is not putting the right amount of characters on a single line.

we cannot really address that, as you haven't specified how the right number of characters is supposed to be determined, or indeed any details of the specific form of justification you intend to implement.

Update

Per your comment on another answer, the justification rule you want to apply seems to be simply to greedily put as many words as possible onto each line, up to the specified maximum line length. The justification algorithm you have implemented does not do exactly that, however, and it is far more costly, both in memory and in processing time, than you need for the justification style you want.

You can and should perform a rewrite to use a simpler algorithm, as I described above. Read words from the input and pack them into lines as you go, inserting a space between words when the next one fits on the current line, and a line break instead when it doesn't. You don't really need to retain even a whole line in memory at a time, just a count of the current line length, and the single next word. As for getting the right number of characters, don't forget to count the spaces between words.