Java Dictionary Searcher
Я пытаюсь реализовать программу, которая будет принимать пользовательский ввод, разбивать эту строку на токены, а затем искать в словаре слова в этой строке. Моя цель для разбираемой строки - чтобы каждый токен был английским словом.
Например:
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);
}
}
Я знаю, что есть лучшие способы хранения словаря (например, двоичное дерево поиска или хэш-таблица), но я все равно не знаю, как их реализовать.
Я застрял на том, как реализовать метод, который проверял бы разделенную строку, чтобы видеть, был ли каждый сегмент словом в словаре.
Любая помощь будет здорово, спасибо
3 ответа
Разбиение входной строки любым возможным способом не завершится за разумное время, если вы хотите поддерживать 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
Если мой ответ кажется глупым, это потому, что вы действительно близки, и я не уверен, где вы застряли.
Самый простой способ, учитывая приведенный выше код, состоит в том, чтобы просто добавить счетчик количества слов и сравнить его с количеством подходящих слов.
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)
Пакет LinkedList;
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");
}
}
}