Java Dictionary Searcher

Question

사용자 입력을 받아 해당 문자열을 토큰으로 분리 한 다음 사전에서 해당 문자열의 단어를 검색하는 프로그램을 구현하려고합니다. 파싱 ​​된 문자열에 대한 나의 목표는 모든 단일 토큰을 영어 단어로 만드는 것입니다. 예를 들어

:

Input: 
     aman 

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

Desired Output: 
     a man 

나는 현재 원하는 출력 부까지 모든 것을 수행이 코드를 가지고 : 나는 그런으로 사전을 (저장하는 더 나은 방법이 알고

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); 

    } 
} 

을 이진 검색 트리 또는 해시 테이블),하지만 어쨌든 그 구현하는 방법을 모르겠습니다.

분할 문자열을 검사하여 모든 세그먼트가 사전에있는 단어인지 확인하는 방법을 구현하는 방법에 집착하고 있습니다.

어떤 도움이 좋을 것, 내 대답은 바보 보인다면 당신은 정말 가까이있어, 난 당신이 붙어있어 어디 모르겠어요 때문에, 그것의 당신에게

Answer 1

가능한 모든 방법으로 입력 문자열을 분할하는 것은 20 자 이상의 문자를 지원하려는 경우 적절한 시간 내에 완료하지 않을 것입니다. 여기에보다 효율적인 접근 방법입니다, 코멘트 인라인 :

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(); 
     } 
    } 
} 

예 출력 : 여기

Enter a string: aman 

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

Took 0ms 

는 더 이상 입력입니다 :

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

감사드립니다.

가장 간단한 방법은 (코드 위 단순히 더 좋을 수도 해시 테이블로이 구현 일치하는 단어

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); 

의 수와 그 단어의 수를 카운터를 추가하고 비교하는 것입니다 제공 그것은 더 빠르다.) 그리고 그것은 정말로 쉬울 것이다.

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++; 
} 

더 좋은 방법이 있습니다. 하나는 검색에 조금 느리지 만 데이터를보다 효율적으로 저장하는 trie (http://en.wikipedia.org/wiki/Trie)입니다. 큰 사전이있는 경우 메모리에 맞지 않을 수 있으므로 BDB (http://en.wikipedia.org/wiki/Berkeley_DB)와 같은 데이터베이스 또는 키 - 값 저장소를 사용할 수 있습니다

Answer 3

패키지 LinkedList의;

import java.util.LinkedHashSet;

공용 클래스 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"); 
    } 

} 

}의