I look for a faster java algorithm

Question

I look for a faster algorithm. I try to verify that a word exist in a dictionary.

Here is my code in java.

public class Searcher {

public static void main(String[] args){

    File file = new File("pathToFile");

    Scanner scanner = null;

    try{
        scanner = new Scanner(file);
    }catch(FileNotFoundException e){
        System.err.println("Le fichier n'a pas ete trouve");
    }

    //Word to look for.
    String word = "mot";
    //indicator of word existence.
    boolean nonExistence = true;

    while(scanner.hasNext()){
        if(Pattern.matches(word, scanner.next())){
            System.out.println("\"" + word + "\"" + " est un mot francais.");
            nonExistence = false;
            break;
        }
    }

    if(nonExistence){
        System.out.println("\'" + word + "\'" + " n'est pas un mot francais.");
    }

}

}

I would like to do not have to explore the whole file. Thanks.

Do you have any additional properties on the file? For example, are the words in the file ordered? — blazs, Jan 09 '18 at 08:00
There are many things to improve here - for one, don't use `Scanner`; it's very slow. Use a `BufferedReader`. For two, if you are not using Regex, don't use Regex - again, it adds overhead. Finally, finding a something in a set of things must be `O(n)` - so you will have to read the whole file, unless there are some other properties that you haven't mentioned. — Boris the Spider, Jan 09 '18 at 08:01
Replace `Pattern.matches` by `word.equals`. Yet the answer will get more complex if you search substrings instead of words. — CoronA, Jan 09 '18 at 08:26
Also, you may post your code in [Codereview](https://codereview.stackexchange.com/) for a better analysis — Shirkam, Jan 09 '18 at 11:06

Said A. Sryheni · Accepted Answer · 2018-01-21T20:30:52.007

I think it depends on the size of your file. If you are performing many search operations, and you can load the file into RAM and perform search operations there, here are a few ideas that come to my mind.

The first idea is a little complex but is really a powerful way to do the search. You can build a Trie Tree. This way your search complexity will be reduced to the length of the word you are searching for, rather than the size of the file. This solution is helpful when you need to search for existing words, and even add new ones to your dictionary, because both operations have a complexity O(|WORD|), where |WORD| is the length of the word you are adding/searching for.

Another solution would be to store the words in an array in lexicographical order, and use binary search to find the word you are searching for. Of course this solution is only helpful when your searching operations are a lot more frequent than the operation of adding a new word. The complexity of searching for a word is equal to O(|LEN| * Log(N)), where |LEN| is the approximate length of a single word in your dictionary, and N is the number of words in your dictionary. However adding a new word is quite expensive, since you will need to insert it in its correct location, and perform a shifting operation on the words that follow it.

If your file is pretty large and loading it to RAM is not an option, and based on a quick seach (check this question for example), I believe all programming languages (including java) don't contain a way to read specific lines from a file, and sequential scanning is the only way to do so, which means you can only scan your file sequentially searching for your word in the same way you are doing now.

score 1 · Answer 2 · answered Jan 09 '18 at 08:41

Go to Coursera: Algorithms on Strings - Suffix Trees. This is what exactly what you're looking for. There you can find couple videos and slides (it is free). These materials help you to realise the problem and you will be able easily to implement it then.

In a breaf way: the most effective way is to build a Suffix Tree of a text and then match your patterns with this Suffix Tree.

score 1 · Answer 3 · answered Jan 09 '18 at 08:58

Well, It actually looks simple to me. I did not try the code but here is the idea:

You dont want to look for whole file right? But the word you specify is clear.No matter what is "Look" "Take" "Get" I dont know something;

Add more constraint to your code that getting the first letter of your word and search inside the dictionary only the words that also starts with that letter. (Java has libraries and easy iterations for that)

For example if your word is "Take" you can say something like search index find the words starting by "t" (ignore the case) depends on your dictionary.

With that you dont have to look for whole file and it becomes just faster.

I look for a faster java algorithm

3 Answers3