Skip to main content

Spell Checker using TRIE






Spell checker program using TRIE data structure. Dictionary source is from Dictionary.txt, which is to be in the same directory of the program, or else change the file name and location



//Possible.java

import java.io.*;
import java.util.*;

class TrieNode {
    char letter;
    TrieNode[] links;
    boolean fullWord;

    TrieNode(char letter, boolean fullWord) {
        this.letter = letter;
        links = new TrieNode[26];
        this.fullWord = fullWord;
    }
}

public class Possible {

    static TrieNode createTree()
    {
        return(new TrieNode('', false));
    }

    static void insertWord(TrieNode root, String word)
    {
        int offset = 97;
        int l = word.length();
        char[] letters = word.toCharArray();
        TrieNode curNode = root;
        for (int i = 0; i < l; i++)
        {
            if (curNode.links[letters[i] - offset] == null)
                curNode.links[letters[i] - offset] = new TrieNode(letters[i], i == l - 1 ? true : false);
            curNode = curNode.links[letters[i] - offset];
        }
    }

    static boolean find(TrieNode root, String word)
    {
        char[] letters = word.toCharArray();
        int l = letters.length;
        int offset = 97;
        TrieNode curNode = root;
        int i;
        for (i = 0; i < l; i++)
        {
            if (curNode == null)
                return false;
            curNode = curNode.links[letters[i] - offset];
        }
        if (i == l && curNode == null)
            return false;
        if (curNode != null && !curNode.fullWord)
            return false;
        return true;
    }

    static void printTree(TrieNode root, int level, char[] branch, BufferedWriter out) throws IOException
    {
        if (root == null)
            return;
        for (int i = 0; i < root.links.length; i++)
        {
            branch[level] = root.letter;
            printTree(root.links[i], level + 1, branch, out);
        }
        if (root.fullWord)
        {
            for (int j = 1; j <= level; j++)
                out.write(branch[j]);
            out.write("n");
        }
    }

    public static void possible(TrieNode tree, String word) {
        Set<String> result = new HashSet<String>();
        // Remove a character
        for (int i = 0; i < word.length(); ++i)
            result.add(word.substring(0, i) + word.substring(i + 1));
        // Swap two consecutive characters
        for (int i = 0; i < word.length() - 1; ++i)
            result.add(word.substring(0, i) + word.substring(i + 1, i + 2) + word.substring(i, i + 1)
                    + word.substring(i + 2));
        // Replace a character with other
        for (int i = 0; i < word.length(); ++i)
            for (char c = 'a'; c <= 'z'; ++c)
                result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i + 1));
        // Add a new character
        for (int i = 0; i <= word.length(); ++i)
            for (char c = 'a'; c <= 'z'; ++c)
                result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i));
        ArrayList<String> res = new ArrayList<String>(result);
        int j = 0;
        for (int i = 0; i < result.size(); i++)
            if (find(tree, res.get(i))) {
                if (j == 0)
                    System.out.print("Do you mean : ");
                System.out.print(res.get(i) + " ");
                j++;
            }
    }

    public static void main(String[] args) throws IOException
    {
        TrieNode tree = createTree();
        long build1 = System.currentTimeMillis();
        File f = new File("Dictionary.txt");
        FileInputStream fread = new FileInputStream(f);
        BufferedReader br = new BufferedReader(new InputStreamReader(fread));
        String ele;
        while ((ele = br.readLine()) != null)
            insertWord(tree, ele);
        long build2 = System.currentTimeMillis();
        System.out.println("Time to build data structure is:" + (build2 - build1));
        BufferedReader br1 = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter the word :");
        String searchWord = br1.readLine();
        if (find(tree, searchWord))
        {
            System.out.println("The word was found");
        }
        else
        {
            long find1 = System.currentTimeMillis();
            possible(tree, searchWord);
            long find2 = System.currentTimeMillis();
            System.out.println("nTime to find possibilities is:" + (find2 - find1));
            System.out.println("Do you want to add this word to dictionary [y/n]: ");
            if (br1.readLine().equals("y")) {
                long add = System.currentTimeMillis();
                insertWord(tree, searchWord);
                long add1 = System.currentTimeMillis();
                try {
                    f.delete();
                    File f1 = new File("Dictionary.txt");
                    FileWriter fwrite = new FileWriter(f1, true);
                    BufferedWriter out = new BufferedWriter(fwrite);
                    char[] branch = new char[50];
                    printTree(tree, 0, branch, out);
                    out.close();
                } catch (Exception e) {
                    System.err.println("Error: " + e.getMessage());
                }
                long add2 = System.currentTimeMillis();
                System.out.println("Time to add a new word to Trie and file are:" + (add1 - add) + " " + (add2 - add1));
            }
        }
    }
}

Comments

Popular posts from this blog

Karabiner: Mouse/keyboard customizer for OS X

For beginners, or the one who migrated from Windows environment, Natural Gestures (Scrolling and Swiping) might be bit confusing. But, once you get familiarized with them, it may feel like "What was I doing, all those days?". It all changed, when I connected external mouse to my Macbook. When you start using that WHEEL, you will be confused. Luckily there is a setting for mouse, to change scroll behavior (natural or the other way). But, here's the catch. If you toggle that setting, it also toggles the same for TRACKPAD!!!!! I've seen that many people were freaked out and even raised BUG report to Apple. But, all those reports were closed, saying that is not a bug, but intentional feature!!! For those, who can't leave with such one-sided settings, here is a simple util, which came to my rescue: Karabiner It's simple, powerful and stable mouse/keyboard customizer for OSX. Without going into much detail, here's the configuration I used to ret...

USB port not working on Mac

Recently I connected  an external hard-disk   to my new MacBook and observed that it was not properly detected on one of the USB ports. But I can see that it is powering my HDD. I tried switching to other port and it worked. I simply ignored it by thinking that my HDD cable might be loose. Now I bought a new USB drive and to get it detected, I have to insert and detach it multiple times. And as usual, I suspected the new USB drive, as my Mac is brand new. And planned to replace my USB drive. Now my HDD came back to   my mind. And also my earlier laptop, in which few KEYS went unresponsive due to accumulated charges. By little researching I found that I'm not alone. The solution that worked for me was "Resetting SMC" Here is the procedure I followed: Shut down the Mac and connect the power cable Hold down Shift+Control+Option+Power concurrently for a few seconds. When the light on the power adapter blinks or changes colors you’ll know SMC r...

HSQLDB

It's been almost two years I've been using HSQLDB in one of my client-critical application. When I was given the task of working on this application (which was already in production), main challenge was to reduce latency and also to make it flexible enough to accommodate any future use-cases. Without going into to much details, here's my use-case: Application receives data from multiple sources Parse data from each source and extract required data Aggregate this extracted data and find best candidate which satisfies certain rules One simplest solution is to join data from all sources by having a (for-)loop, one each for a source and apply rules inside inner-most loop. As number of data sources increases, so does the latency. HSQLDB came to my rescue. I used in-memory variant, as the data is non more required, once a candidate is found. Data extracted from each source is stored into DB (from here on, DB => in-memory HSQLDB), where...