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

пакет 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");
    }

}

}

Answer 3

Если мой ответ кажется глупым, это потому, что вы действительно близки, и я не уверен, где вы застряли.

Самый простой способ, учитывая ваш код выше, это просто добавить счетчик дляколичество слов и сравните это с количеством совпавших слов

    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)