Java Dictionary Searcher

Question

Estoy tratando de implementar un programa que tomará una entrada de los usuarios, dividir esa cadena en tokens, y luego buscar en un diccionario las palabras en esa cadena. Mi objetivo para la cadena analizada es que cada token sea una palabra en inglés.

Por ejemplo:

Input: 
     aman 

Split Method: 
     a man 
     a m an 
     a m a n 
     am an 
     am a n 
     ama n 

Desired Output: 
     a man 

que actualmente tiene este código que hace todo hasta la parte de salida deseada:

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

public class Words { 

    public static String[] dic = new String[80368]; 

    public static void split(String head, String in) { 

     // head + " " + in is a segmentation 
     String segment = head + " " + in; 

     // count number of dictionary words 
     int count = 0; 
     Scanner phraseScan = new Scanner(segment); 
     while (phraseScan.hasNext()) { 
      String word = phraseScan.next(); 
      for (int i=0; i<dic.length; i++) { 
       if (word.equalsIgnoreCase(dic[i])) count++; 
      } 
     } 

     System.out.println(segment + "\t" + count + " English words"); 

     // recursive calls 
     for (int i=1; i<in.length(); i++) { 
      split(head+" "+in.substring(0,i), in.substring(i,in.length())); 
     } 
    } 

    public static void main (String[] args) throws IOException { 
     Scanner scan = new Scanner(System.in); 
     System.out.print("Enter a string: "); 
     String input = scan.next(); 
     System.out.println(); 

     Scanner filescan = new Scanner(new File("src:\\dictionary.txt")); 
     int wc = 0; 
     while (filescan.hasNext()) { 
      dic[wc] = filescan.nextLine(); 
      wc++; 
     } 

     System.out.println(wc + " words stored"); 

     split("", input); 

    } 
} 

Yo sé que hay mejores formas de almacenar el diccionario (tales como una árbol binario de búsqueda o una tabla hash), pero no sé cómo implementarlos de todos modos.

Estoy atascado en cómo implementar un método que verifique la cadena dividida para ver si cada segmento era una palabra en el diccionario.

Cualquier ayuda sería grande, Gracias

Answer 1

La división de la cadena de entrada de todas las formas posibles no finalizará en un período de tiempo razonable si desea admitir 20 o más caracteres. Aquí hay un enfoque más eficiente, los comentarios en línea:

public static void main(String[] args) throws IOException { 
    // load the dictionary into a set for fast lookups 
    Set<String> dictionary = new HashSet<String>(); 
    Scanner filescan = new Scanner(new File("dictionary.txt")); 
    while (filescan.hasNext()) { 
     dictionary.add(filescan.nextLine().toLowerCase()); 
    } 

    // scan for input 
    Scanner scan = new Scanner(System.in); 
    System.out.print("Enter a string: "); 
    String input = scan.next().toLowerCase(); 
    System.out.println(); 

    // place to store list of results, each result is a list of strings 
    List<List<String>> results = new ArrayList<List<String>>(); 

    long time = System.currentTimeMillis(); 

    // start the search, pass empty stack to represent words found so far 
    search(input, dictionary, new Stack<String>(), results); 

    time = System.currentTimeMillis() - time; 

    // list the results found 
    for (List<String> result : results) { 
     for (String word : result) { 
      System.out.print(word + " "); 
     } 
     System.out.println("(" + result.size() + " words)"); 
    } 
    System.out.println(); 
    System.out.println("Took " + time + "ms"); 
} 

public static void search(String input, Set<String> dictionary, 
     Stack<String> words, List<List<String>> results) { 

    for (int i = 0; i < input.length(); i++) { 
     // take the first i characters of the input and see if it is a word 
     String substring = input.substring(0, i + 1); 

     if (dictionary.contains(substring)) { 
      // the beginning of the input matches a word, store on stack 
      words.push(substring); 

      if (i == input.length() - 1) { 
       // there's no input left, copy the words stack to results 
       results.add(new ArrayList<String>(words)); 
      } else { 
       // there's more input left, search the remaining part 
       search(input.substring(i + 1), dictionary, words, results); 
      } 

      // pop the matched word back off so we can move onto the next i 
      words.pop(); 
     } 
    } 
} 

Ejemplo de salida:

Enter a string: aman 

a man (2 words) 
am an (2 words) 

Took 0ms 

Aquí está una entrada mucho más tiempo: ListaEnlazada

Enter a string: thequickbrownfoxjumpedoverthelazydog 

the quick brown fox jump ed over the lazy dog (10 words) 
the quick brown fox jump ed overt he lazy dog (10 words) 
the quick brown fox jumped over the lazy dog (9 words) 
the quick brown fox jumped overt he lazy dog (9 words) 

Took 1ms 

Answer 2

Si mi respuesta parece tonto, es porque estás muy cerca y no estoy seguro de dónde está atascado.

La forma más sencilla dada su código anterior sería simplemente agregar un contador para el número de palabras y compararlo con el número de palabras coincidentes

int count = 0; int total = 0; 
    Scanner phraseScan = new Scanner(segment); 
    while (phraseScan.hasNext()) { 
     total++ 
     String word = phraseScan.next(); 
     for (int i=0; i<dic.length; i++) { 
      if (word.equalsIgnoreCase(dic[i])) count++; 
     } 
    } 
    if(total==count) System.out.println(segment); 

la aplicación de esta como una tabla hash podría ser mejor (es más rápido, seguro), y sería realmente fácil.

HashSet<String> dict = new HashSet<String>() 
dict.add("foo")// add your data 


int count = 0; int total = 0; 
Scanner phraseScan = new Scanner(segment); 
while (phraseScan.hasNext()) { 
    total++ 
    String word = phraseScan.next(); 
    if(dict.contains(word)) count++; 
} 

Existen otras formas mejores de hacerlo. Uno es un trie (http://en.wikipedia.org/wiki/Trie), que es un poco más lento para la búsqueda, pero almacena datos de manera más eficiente. Si tiene un diccionario grande, es posible que no pueda colocarlo en la memoria, por lo que podría usar una base de datos o una tienda de valores clave como BDB (http://en.wikipedia.org/wiki/Berkeley_DB)

Answer 3

paquete;

import java.util.LinkedHashSet;

public class {dictionaryCheck

private static LinkedHashSet<String> set; 
private static int start = 0; 
private static boolean flag; 

public boolean checkDictionary(String str, int length) { 

    if (start >= length) { 
     return flag; 
    } else { 
     flag = false; 
     for (String word : set) { 

      int wordLen = word.length(); 

      if (start + wordLen <= length) { 

       if (word.equals(str.substring(start, wordLen + start))) { 
        start = wordLen + start; 
        flag = true; 
        checkDictionary(str, length); 

       } 
      } 
     } 

    } 

    return flag; 
} 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    set = new LinkedHashSet<String>(); 
    set.add("Jose"); 
    set.add("Nithin"); 
    set.add("Joy"); 
    set.add("Justine"); 
    set.add("Jomin"); 
    set.add("Thomas"); 
    String str = "JoyJustine"; 
    int length = str.length(); 
    boolean c; 

    dictionaryCheck obj = new dictionaryCheck(); 
    c = obj.checkDictionary(str, length); 
    if (c) { 
     System.out 
       .println("String can be found out from those words in the Dictionary"); 
    } else { 
     System.out.println("Not Possible"); 
    } 

} 

}