J'essaie de mettre en œuvre un programme qui prendra une entrée d'utilisateur, diviser cette chaîne en jetons, puis recherchez un dictionnaire pour les mots de cette chaîne. Mon objectif pour la chaîne analysée est d'avoir chaque jeton être un mot anglais.
Par exemple: P>
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 Réponses :
Si ma réponse semble stupide, c'est parce que vous êtes vraiment proche et je ne suis pas sûr où vous êtes coincé.
Le moyen le plus simple que votre code ci-dessus serait de simplement ajouter un compteur pour le nombre de mots et comparez cela au nombre de mots correspondants p> implémenter cela comme une table de hash peut être meilleur (il est plus rapide, à coup sûr), et ce serait vraiment facile. P> 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++;
}
Séfonciation La chaîne d'entrée Chaque moyen possible ne se terminera pas dans une durée raisonnable si vous souhaitez prendre en charge 20 caractères ou plus. Voici une approche plus efficace, commentaires en ligne: Exemple de sortie: p> Voici une entrée beaucoup plus longue: P> 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
Une autre façon serait de Stocker les mots dans une base de données . Cela augmentera les performances lorsque vous travaillez avec un grand nombre de mots (> 4 millions).
@JMendeth: Bien sûr, une base de données pourrait aider si le dictionnaire était assez grand et qu'il n'y avait pas assez de mémoire disponible. La plupart des dictionnaires ne sont cependant pas si grands. Le plus grand que j'ai testé avec a plus de 400k mots et nécessite 38 Mo. L'OP n'a pas besoin d'une base de données depuis son dictionnaire avec 80 000 mots et consomme seulement 7 Mo. Pour un grand nombre de mots, j'essaierais probablement d'utiliser une structure de données différente comme une trie avant d'aller dans une base de données. Une base de données fonctionnerait bien, dans l'exemple de 36 caractères, l'entrée que j'ai donnée il n'y a que 335 recherches.
Vous avez raison, mais parfois (pas dans ce cas) Les dictionnaires d'autres langues / caractères peuvent être d'environ 10 millions de mots.
Est-il possible de mettre en œuvre un arbre de recherche binaire au lieu d'un hashset? TY pour votre réponse
L'arbre de recherche binaire vous donnerait O (lg (n)) de temps de recherche au lieu de O (1), donc ce n'est pas si chaud. Une trie sur des lettres, cependant, permettrait de mettre en œuvre StartSwewith ou similaire. Avec la mise en œuvre actuelle, si vous recevez une chaîne de trois Petabyte qui ne peut pas commencer par un mot, "xzaszssxaa ..." puis vous rechercherez la chaîne entière, à la recherche à plusieurs reprises des substrives plus longues et longues du dictionnaire, à la place. de déterminer rapidement que ce n'est pas là. Avec une implémentation trie, vous vous arrêterez tôt.
Lien LinkedList Linked;
Importer Java.Util.LinkedHashSet; p>
DictaryCheck de classe publique { P>
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");
}
}
Solution simple et efficace. Faites-moi savoir si je manque quelque chose. La complexité du temps est exponentielle, je suppose. La complexité du temps polynomial peut être obtenue en utilisant une solution de programmation dynamique.
Bien que ce code puisse résoudre le problème de l'OP, vous devriez vraiment ajouter une explication sur ce que le code fait, ou comment cela le fait. Just Code Les réponses sont fronçées.
Dupliqué possible de Word est dans le dictionnaire ou non
Quelle est la plus grande chaîne d'entrée que vous attendez?
Il peut être de n'importe quelle longueur, mais je ne m'attends pas à ce qu'il soit plus de 20 caractères probablement..Je dire 50 max