parse a document with million words

Question

I have implemented some code to find the anagrams word in the txt sample.txt file and output them on the console. The txt document contains String (word) in each of line.

Is that the right Approach to use if I want to find the anagram words in txt.file with Million or 20 Billion of words? If not which Technologie should I use in this case?

I appreciate any help.

Sample

abac
aabc
hddgfs
fjhfhr
abca
rtup
iptu
xyz
oifj
zyx
toeiut
yxz
jrgtoi

oupt

abac aabc abca
xyz zyx yxz

Code

package org.reader;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    // To store the anagram words
    static List<String> match = new ArrayList<String>();
    // Flag to check whether the checkWorld1InMatch() was invoked.
    static boolean flagCheckWord1InMatch;

    public static void main(String[] args) {
        String fileName = "G:\\test\\sample2.txt";
        StringBuilder sb = new StringBuilder();
        // In case of matching, this flag is used to append the first word to
        // the StringBuilder once.
        boolean flag = true;

        BufferedReader br = null;
        try {
            // convert the data in the sample.txt file to list
            List<String> list = Files.readAllLines(Paths.get(fileName));

            for (int i = 0; i < list.size(); i++) {

                flagCheckWord1InMatch = true;
                String word1 = list.get(i);

                for (int j = i + 1; j < list.size(); j++) {

                    String word2 = list.get(j);

                    boolean isExist = false;

                    if (match != null && !match.isEmpty() && flagCheckWord1InMatch) {
                        isExist = checkWord1InMatch(word1);

                    }

                    if (isExist) {
                        // A word with the same characters was checked before
                        // and there is no need to check it again. Therefore, we
                        // jump to the next word in the list.
                        // flagCheckWord1InMatch = true;
                        break;
                    } else {
                        boolean result = isAnagram(word1, word2);
                        if (result) {

                            if (flag) {
                                sb.append(word1 + " ");
                                flag = false;
                            }

                            sb.append(word2 + " ");

                        }
                        if (j == list.size() - 1 && sb != null && !sb.toString().isEmpty()) {
                            match.add(sb.toString().trim());
                            sb.setLength(0);
                            flag = true;

                        }

                    }

                }
            }

        } catch (

        IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (br != null) {
                    br.close();
                }
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }

        for (String item : match) {
            System.out.println(item);
        }

        // System.out.println("Sihwail");

    }

    private static boolean checkWord1InMatch(String word1) {
        flagCheckWord1InMatch = false;
        boolean isAvailable = false;
        for (String item : match) {
            String[] content = item.split(" ");
            for (String word : content) {
                if (word1.equals(word)) {
                    isAvailable = true;
                    break;

                }
            }
        }
        return isAvailable;
    }

    public static boolean isAnagram(String firstWord, String secondWord) {
        char[] word1 = firstWord.toCharArray();
        char[] word2 = secondWord.toCharArray();
        Arrays.sort(word1);
        Arrays.sort(word2);
        return Arrays.equals(word1, word2);
    }

}

Answer 1

For 20 billion words you will not be to able to hold all of them in RAM so you need an approach to process them in chunks.

20,000,000,000 words. Java needs quite a lot of memory to store strings so you can count 2 bytes per character and at least 38 bytes overhead.

This means 20,000,000,000 words of one character would need 800,000,000,000 bytes or 800 GB, which is more than any computer I know has.

Your file will contain much less than 20,000,000,000 different words, so you might avoid the memory problem if you store every word only once (e.g. in a Set).

Answer 2

First for a smaller number.

As it is better to use a more powerful data structure, do not read all lines in core, but read line-wise.

Map<String, Set<String>> mapSortedToWords = new HashMap<>();

Path path = Paths.get(fileName);
try (BufferedReader in = Files.newBufferedReader(Path, StandardCharsets.UTF_8)) {
    for (;;) {
        String word = in.readLine();
        if (word == null) {
            break;
        }
        String key = sorted(word);
        Set<String> words = mapSortedToWords.get(key);
        if (words == null) {
            words = new TreeSet<String>();
            mapSortedToWords.put(key, words);
        }
        words.add(word);
    }
}
for (Set<String> anagrams : mapSortedToWords.values()) {
    if (anagrams.size() > 1) {
        ... anagrams
    }
}

static String sorted(String word) {
    char[] letters = word.toCharArray();
    Arrays.sort(letters);
    return new String(letters);
}

This stores in the map a set of words. Comparable with abac aabc abca.

For a large number a database where you store (sortedLetters, word) would be better. An embedded database like Derby or H2 poses no installation problems.

Answer 3

For the kind of file size that you specify ( 20 billion words), obviously there are two main problems with your code,

List<String> list = Files.readAllLines(Paths.get(fileName)); 

AND

for (int i = 0; i < list.size(); i++)

These two lines in your programs basically question,

1. Do you have enough memory to read full file in one go?
2. Is it OK to iterate 20 billion times?

For most systems, answer for both above questions would be NO.

So your target is to cut down memory foot print and reduce the number of iterations.

So you need to read your files chunk by chunk and use some kind of search data structures ( like Trie ) to store your words.

You will find numerous questions on SO for both of above topics like,

Fastest way to incrementally read a large file

Finding anagrams for a given word

Above algorithm says that you have to first create a dictionary for your words.

Anyway, I believe there is no ready made answer for you. Take a file with one billion words ( that is a very difficult task in itself ) and see what works and what doesn't but your current code will obviously not work.

Hope it helps !!

Answer 4

Update

You can use a map for finding the anagrams like below. For each word you have you may sort its chars and obtain a sorted String. So, this would be the key of your anagrams map. And values of this key will be the other anagram words.

public void findAnagrams(String[] yourWords) {
    Map<String, List<String>> anagrams = new HashMap<String, List<String>>();
    for (String word : yourWords) {
        String sortedWord = sortedString(word);
        List<String> values = anagrams.get(sortedWord);
        if (values == null) 
            values = new LinkedList<>();

        values.add(word);
        anagrams.put(sortedWord, values);
    }

    System.out.println(anagrams);
}

private static String sortedString(String originalWord) {

    char[] chars = originalWord.toCharArray();
    Arrays.sort(chars);
    String sorted = new String(chars);
    return sorted;
}

Answer 5

Use a stream to read the file. That way you are only storing one word at once.

FileReader file = new FileReader("file.txt"); //filestream

String word;

while(file.ready()) //return true if there a bytes left in the stream
{
    char c = file.read(); //reads one character
    if(c != '\n') 
    {
        word+=c;
    }
    else {
    process(word); // do whatever you want
    word = "";
    }
}