It doesn't have to be a txt file, its just any file that contains words. When I implemented a dictionary into my last program the file didn't even have an extention. It was just called "words." Just google "dictionary file" or something similar and download a txt, doc, or any type of file that contains words.
And as for the searching algorithm, when it comes to dictionary's I believe the Trie is the fastest you can get. I believe it is O(1) where a hash table would be O(n).
Below is a Trie class one of my dev teams made for a project, its been a while since I've looked at the code - its pretty complex, but if you are good with Java you should be able to work your way through it.
Code:
package codecall.net
import java.util.ArrayList;
import java.util.List;
/**
* Provides a trie structure for an implementation of a dictionary. Since words
* never need to be removed from a dictionary during play, there is no option in
* this trie to remove a word.
*
*
*
* Created on: Apr 13, 2006
*
*/
public class Trie {
private TrieRecursive[] _trie = new TrieRecursive[26];
// is the ASCII value of 'A'. When subtracted from a char's value, will provide the char's index value.
private static final int ASCII_MOD = 65;
/**
* Creates a new Trie structure, base case, which contains no datum, but only contains
* 26 references to recursive trie structures.
*/
public Trie() {
}
/**
* Adds the given word into the trie structure.
* @param word The word to be added to the trie.
* @return true if the word was successfully added.
*/
public boolean addWord(String word) {
if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
return false;
}
char firstLetter = Character.toUpperCase(word.charAt(0));
int index = (int)firstLetter - ASCII_MOD;
if (_trie[index] == null) {
_trie[index] = new TrieRecursive(firstLetter);
}
return _trie[index].addWord(word.substring(1));
}
/**
* Checks to see if the given word is in the trie.
* @param word The word to be checked.
* @return true if the word is in the trie.
*/
public boolean isWord(String word) {
if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
return false;
}
int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
if (_trie[index] == null) {
return false;
}
return _trie[index].isWord(word.substring(1));
}
/**
* Returns an ArrayList containing all words that are stored in the trie.<br><br>
*
* An equivalent method can be performed by calling <tt>getWords("");</tt>
* @return All words, in the form of an ArrayList<String>.
*/
public List<String> getAllWords() {
List<String> wordList = new ArrayList<String>();
for (int i = 0; i < 26; i++) {
if (_trie[i] != null)
_trie[i].getAllWords(wordList, "");
}
return wordList;
}
/**
* Returns an ArrayList containing all words stored in the trie that begin with the specified letters.
* @param initial The first letters of the words to be found.
* @return All words beginning with the specified letters, in the form of an ArrayList<String>.
*/
public List<String> getWords(String initial) {
List<String> wordList = new ArrayList<String>();
if (initial.equals("")) {
for (int i = 0; i < 26; i++) {
if (_trie[i] != null)
_trie[i].getWords(wordList, initial, "");
}
}
else if (Character.isLetter(initial.charAt(0))) {
int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
if (_trie[index] != null) {
_trie[index].getWords(wordList, initial.substring(1), "");
}
}
return wordList;
}
/**
* The recursive structure of the Trie superclass.
*
* @author Team S
*
* Created on: Apr 13, 2007
*
*/
private class TrieRecursive {
private char _datum;
private boolean _isEndOfWord = false;
private TrieRecursive[] _subtrie = new TrieRecursive[26];
/**
* Creates a new recursive Trie object. Each object contains a datum and
* an array of 26 potential subTries.
* @param c The char representation of the Trie object.
*/
public TrieRecursive(char c) {
_datum = c;
}
/**
* Adds the given word into the trie structure.
* @param word The word to be added to the trie.
* @return true if the word was successfully added.
*/
public boolean addWord(String word) {
if (word.equals("")) {
if (_isEndOfWord)
return false;
_isEndOfWord = true;
return true;
}
if ( !Character.isLetter( word.charAt(0) )) {
return false;
}
char firstLetter = Character.toUpperCase(word.charAt(0));
int index = (int)firstLetter - ASCII_MOD;
if (_subtrie[index] == null) {
_subtrie[index] = new TrieRecursive(firstLetter);
}
return _subtrie[index].addWord(word.substring(1));
}
/**
* Checks to see if the given word is in the trie.
* @param word The word to be checked.
* @return true if the word is in the trie.
*/
public boolean isWord(String word) {
if (word.equals("")) {
return _isEndOfWord;
}
if ( !Character.isLetter( word.charAt(0) )) {
return false;
}
int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
if (_subtrie[index] == null) {
return false;
}
return _subtrie[index].isWord(word.substring(1));
}
/**
* If a word ends at this level, adds the word to the wordList. Then, calls
* this method on all the subTries.
* @param wordList The List to which valid words are added.
* @param stub A string representing the word formed by the path of parent nodes.
*/
public void getAllWords(List<String> wordList, String stub) {
stub += _datum;
if (_isEndOfWord)
wordList.add(stub);
for (int i = 0; i < 26; i++) {
if (_subtrie[i] != null)
_subtrie[i].getAllWords(wordList, stub);
}
}
/**
* Adds to the wordList all words that begin with the specified letters.
* @param wordList The List to which valid words are added.
* @param initial The first letters of the words to be found.
* @param stub A string representing the word formed by the path of parent nodes.
*/
public void getWords(List<String> wordList, String initial, String stub) {
if (initial.equals("")) {
this.getAllWords(wordList, stub);
}
else {
stub += _datum;
int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
if (_subtrie[index] == null) {
return;
}
_subtrie[index].getWords(wordList, initial.substring(1), stub);
}
}
}
}
Implementation
Code:
package codecall.net;
import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
/**
* Checks validation of submitted words.
*/
public class Dictionary {
/**
* Takes the List of words provided and has them checked by calling the check method. If check determines it is not a word, IllegalWordException is thrown.
*
* @param wordList The list of words that a player has created with the tiles they have added on a certain turn.
* @throws IllegalWordException
*/
public static void checkAll(ArrayList<Word> wordList, Trie dictionary) throws IllegalWordException{
Iterator<Word> iter = wordList.iterator();
while(iter.hasNext()){
String temp = iter.next().toString();
if(!dictionary.isWord(temp)){
throw new IllegalWordException(temp + " is not a valid word.");
}
}
}
/**
* Adds all the words in the given file path to the given Trie dictionary.
* @param dictionary the Trie into which the words will be added
* @param path the path of the file containing the word list
*/
@SuppressWarnings("deprecation")
public static void initializeDictionary(Trie dictionary, String path) {
File f = new File(path);
try {
FileInputStream fis = new FileInputStream(f);
BufferedInputStream bis = new BufferedInputStream(fis);
DataInputStream dis = new DataInputStream(bis);
while(dis.available() != 0){
//
dictionary.addWord(dis.readLine());
}
fis.close();
bis.close();
dis.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}