How do you implement the keyboard Word prediction?


  • 1
    S

    While typing text on our phone, we will be displayed with next possible word? What algorithm and DS can be used to implement this?


  • 0
    D

    First, you should have a dictionary of words. Assuming the dictionary of words are in lexicographic order. I would binary search to determine the range of words and data structure is array or linkedlist


  • 4
    2

    You can use a trie (prefix tree) and give suggestion based on the prefixes by doing a DFS on the trie.


  • 0
    P

    Agreed. A trie can be used, and a weight can be added to each child node, representing the probability of each subtree. The weights are adjusting according to the usage, and also, to previous words.


  • 6
    M
    /* Considering that the words were added using the "insertString" method using TrieNode,
    "printSuggestions" will print the suggested words */
    
    public class Solution {
        static class TrieNode {
            TrieNode[] children = new TrieNode[128];
            boolean leaf;
        }
        
        static void insertString(TrieNode root, String s) {
            TrieNode parent = root;
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char ch = s.charAt(i);
                if (parent.children[ch] == null)
                    parent.children[ch] = new TrieNode();
                parent = parent.children[ch];
            }
            parent.leaf = true;
        }
    
        public static void printSuggestions(TrieNode root, String prefix) {
            if (root == null || prefix == null || prefix.isEmpty()) {
                return;
            }
            int length = prefix.length();
            TrieNode parent = root;
            for (int i = 0; i < length; i++) {
                TrieNode next = parent.children[prefix.charAt(i)];
                if (next == null) {
                    return;
                }
                parent = next;
            }
            printSorted(parent, prefix);
        }
    
        static void printSorted(TrieNode node, String s) {
            if (node.leaf) {
                System.out.println(s);
            }
            for (char ch = 0; ch < node.children.length; ch++) {
                TrieNode child = node.children[ch];
                if (child != null) {
                    printSorted(child, s + ch);
                }
            }
        }
    }

  • 0
    G

    I think we need use a machine learning model. For example, we can compute P(Word|prefix) for every word that has this prefix. And then print the word in decreasing order of probability.


  • 0
    S

    @miguel.salto That code is so beautiful. get √


  • 0
    M

    @Su_23 thank you, I am glad that you like it, greetings!!


  • 0
    Z

    Why not just use a sql like
    select word from WORD_LIST where word like "pre%" order by frequency desc limit 0,10;


  • 0
    L

    @ShashiHippo
    Here is a simple solution based "208 Implement Trie (Prefix Tree) "

    public class Dictionary {
        private final Trie trie = new Trie();
        public void addWords(String[] words) {
            if(words == null || words.length ==0) return;
            //Initial trie
            for( String wd: words)  trie.insert(wd);
        }
    
        public static List<String> predictions(String prefix) {
            TrieNode node = trie.searchPrefix(prefix);
            List<String> words = new ArrayList<String>();
            if( node != null)  {
                StringBuilder sb = new StringBuilder(prefix);
                predictions(sb, node, words);
            }
            return words;
        }
        
        private static void predictions(StringBuilder sb, TrieNode root, List<String> words) {
            TrieNode node = null;
            String word;
            for(char ch='a'; ch<='z'; ch++ ) {
                if( root.containsKey(ch)) {
                    node = root.get(ch);
                    sb.append(ch);
                    if( node.isEnd()) {
                        words.add(sb.toString());
                    } else {
                        predictions(sb, node, words);
                    }
                    sb.setLength(sb.length() -1);
                }
            }
        }
    }

  • 0

    Same idea but different approach. How about this code?
    Apart from using Trie, I am storing arraylist of word combination.

    public class WordPrediction {
    	class Trie {
    		Trie child[];
    		ArrayList<String> nextWordList;
    
    		public Trie() {
    			child = new Trie[26];
    		}
    	}
    
    	Trie root = new Trie();
    	String prevWord = "";
    
    	private Trie insertIntoTrie(String word) {
    		char wordArray[] = word.toCharArray();
    
    		Trie node = root;
    		for (char c : wordArray) {
    			if (null == node.child[c - 'a']) {
    				node.child[c - 'a'] = new Trie();
    			}
    
    			node = node.child[c - 'a'];
    		}
    
    		return node;
    	}
    
    	private Trie findLastNode(String word) {
    		char wordArray[] = word.toCharArray();
    
    		Trie node = root;
    		for (char c : wordArray) {
    			if (null == node.child[c - 'a']) {
    				return null;
    			}
    
    			node = node.child[c - 'a'];
    		}
    
    		return node;
    	}
    
    	private void insert(String prevWord, String curWord) {
    		insertIntoTrie(curWord);
    
    		Trie lastNode = findLastNode(prevWord);
    		if (null != lastNode) {
    			if (null == lastNode.nextWordList) {
    				lastNode.nextWordList = new ArrayList<>();
    			}
    
    			lastNode.nextWordList.add(curWord);
    		}
    	}
    
    	private void insert(String curWord) {
    		insert(prevWord, curWord);
    		prevWord = curWord;
    	}
    
    	private ArrayList<String> predictWord(String input) {
    		ArrayList<String> list = new ArrayList<>();
    		Trie node = root;
    		char inputArray[] = input.toCharArray();
    
    		for (char c : inputArray) {
    			if (null == node.child[c - 'a']) {
    				list = new ArrayList<>();
    
    				return list;
    			}
    
    			node = node.child[c - 'a'];
    		}
    
    		list = node.nextWordList;
    
    		if (null == node.nextWordList) {
    			list = new ArrayList<>();
    		}
    
    		return list;
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		WordPrediction wp = new WordPrediction();
    		wp.insert("this");
    		wp.insert("is");
    		wp.insert("my");
    		wp.insert("pen");
    		wp.insert("this");
    		wp.insert("was");
    		wp.insert("your");
    		wp.insert("copy");
    		wp.insert("this");
    		wp.insert("went");
    		wp.insert("well");
    
    		System.out.println(wp.predictWord("this"));
    	}
    
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.