searchsolve.java

在很大的一个词库中寻找所需的单词

/* PuzzleSolve.java */
/**
 * first, read the text.
 * second, find all the words.
 * third, output all the words.
 */
import java.io.*;
import java.util.*;
import java.lang.Math;
import java.awt.List;

/**
  *DS project2: Search the words in the matrix.
  *@author ½ܲ
  *@version 1.0
  */
public class SearchSolve 
{
	/** The name of the output file. */
	String outPutFile;
	/** The array of the characters of a word. */
	char[] letters;
	/** The array of the characters of the matrix. */
	char[][] inputs;
	/** The number of the words found. */
	int count;
	/** The position of the character in the word. */
	int pos;
	/** The index recording the position of the characters in the matrix. */
	myIndex[] matrixIndex;
	/** The words found. */
	StringBuffer[] found;
	/** The file to be output. */
	FileWriter output;

/**
  *Initialization for the search.
  */
	public SearchSolve() 
	{
		count = 0;
		matrixIndex = new myIndex[676];			//26*26=676. 
		for ( int i = 0; i < 676 ; i++ )		//The index was concern about the 
			matrixIndex[i] = new myIndex();			//first two characters in the word.
		found = new StringBuffer[26];			
		for ( int i = 0; i < 26 ; i++ )			//Collect the words found into one StringBuffer
			found[i] = new StringBuffer();			//if the first characters of them are the same. 
	}

/**
  *Read in the matrix and set the index.
  *@param br the matrix to be searched.
  */
	public void readText(BufferedReader br) throws IOException
	{
		String firstLine = br.readLine();
		StringTokenizer st = new StringTokenizer(firstLine);
		int index = st.countTokens();
		
		inputs = new char[index + 2][index + 2];
		for (int a = 0; a < index + 2 ; a++ )		
		{												
			inputs[0][a] = '*';		//add walls around the characters, so I don't need to judge 
			inputs[a][0] = '*';			//whether it reaches the edge on every step while searching.
			inputs[index + 1][a] = '*';
			inputs[a][index + 1] = '*';
		}
						
		int i = 1;
		int j = 1;
		
		for (int x = 0; x < firstLine.length(); x++ )
		{
			int temp = firstLine.charAt(x);
			if ( temp == 13 )
				break;
			if ( temp >= 97 && temp <= 122 )
			{
				inputs[1][i++] = (char) temp;
				
				/* set the index. */
				if ( ( index = getIndex(inputs[1][i - 1], inputs[1][i - 2]) ) != -1 )
					matrixIndex[index].add(1, i - 1, 1, i - 2);
				if ( ( index = getIndex(inputs[1][i - 2], inputs[1][i - 1]) ) != -1 )
					matrixIndex[index].add(1, i - 2, 1, i - 1);
			}
		}
		
		i = 2;
		while ( i < inputs.length - 1 )
		{
			int temp = br.read();
			if ( temp >= 97 && temp <= 122 )
			{
				inputs[i][j++] = (char) temp;
				
				/* set the index. */
				if ( ( index = getIndex(inputs[i][j - 1], inputs[i][j - 2]) ) != -1 )
					matrixIndex[index].add(i, j - 1, i, j - 2);
				if ( ( index = getIndex(inputs[i][j - 2], inputs[i][j - 1]) ) != -1 )
					matrixIndex[index].add(i, j - 2, i, j - 1);
				if ( ( index = getIndex(inputs[i][j - 1], inputs[i - 1][j - 1]) ) != -1 )
					matrixIndex[index].add(i, j - 1, i - 1, j - 1);
				if ( ( index = getIndex(inputs[i - 1][j - 1], inputs[i][j - 1]) ) != -1 )
					matrixIndex[index].add(i - 1, j - 1, i, j - 1);
			}
			if ( j >= inputs.length - 1 )
				j = ( 0 & (i++) ) + 1;
		}
	}

/**
  *Read the dictionary word by word and search it in the matrix.
  *<p>Add the words found into the StringBuffer found.
  */
	public void searchText() throws IOException
	{
		BufferedReader dictReader = new BufferedReader(new FileReader("dict"));
		String dictn;
		while ( (dictn = dictReader.readLine()) != null)
		{

			if ( dictn == null )
				break;
			letters = dictn.toCharArray();	
			boolean isWord = compareWord();
			if (isWord)
			{
				count++;
				found[letters[0] - 97].append(dictn+" ");
			}
		}
	}

/**
  *Write the words found into the output file in the certain format.
  */
	public void output() throws IOException
	{
		int num = 1;
		output = new FileWriter(outPutFile);
		output.write("There are "+count+" words.\n");
		
		for (int i = 0; i < 26; i++ )
		{
			StringTokenizer st = new StringTokenizer(found[i].toString());
			String[] result = new String[st.countTokens()];
			int x = 0;
			while (st.hasMoreTokens())
				result[x++] = st.nextToken();
			Arrays.sort(result, 0, result.length);

			for (int j = 0; j < result.length; j++ )
			{
				output.write( (num++) + ". " + result[j]+"\n");
			}
		}
		output.close();
	}

/**
  *Search the index to find where the word maybe found <br>
  *and go there to search further.
  *@return true if the word is found, false otherwise.
  */
	public boolean compareWord()
	{	
		pos = 1;
		int index = getIndex(letters[0], letters[1]);
		
		if ( matrixIndex[index].head == null )
			return false;

		for ( myIndexNode i = matrixIndex[index].head; i != null ; i = i.next )
		{
			inputs[i.x0][i.y0] += 'a';
			int x = i.x1;
			int y = i.y1;
			
			if ( findWord(x, y) == 1 )
			{
				inputs[i.x0][i.y0] -= 'a';
				return true;
			}
			inputs[i.x0][i.y0] -= 'a';
		}
		return false;
	}

/**
  *find out whether the certain word starting from the given position exists.
  *@param i the row the second character is in.
  *@param j the column the second character is in.
  *@return 1 if the character found beside the former, 0 otherwise.
  */
	public int findWord(int i, int j)
	{
	
		if( pos == letters.length - 1)			
		{  
			pos = 1;
			return 1;
		}
		pos++ ;                                     
		inputs[i][j] += 'a' ;                 /* Mark the visited letter */

		
		if ( inputs[i-1][j] == letters[pos] )		/* go up */
		{
			if (findWord(i - 1, j) == 1)			//found it, clear the mark
			{										
				inputs[i][j] -= 'a' ;				
				pos--;
				return 1;
			}			
		}
		
		if ( inputs[i+1][j] == letters[pos] )		/* go down */
		{
			if (findWord(i + 1 ,j) == 1)
			{
				inputs[i][j] -= 'a' ; 
				pos--;
				return 1;
			}			
		}
		if ( inputs[i][j-1] == letters[pos] )		/* go left */
		{
			if (findWord(i, j - 1) == 1)
			{
				inputs[i][j] -= 'a' ; 
				pos--;
				return 1;
			}
		}
		
		if ( inputs[i][j+1] ==  letters[pos] )		/* go right */
		{
			if (findWord(i, j + 1) == 1)
			{
				inputs[i][j] -= 'a' ;
				pos--;
				return 1;
			}
		}
		
		/* no more found, then step back and clear the mark. */
		pos-- ;                          
		inputs[i][j] -= 'a' ;      
		return 0;
	}

/**
  *Compute the number of which index it should be in.
  *@param c1 the first character.
  *@param c2 the second character.
  *@return the index number. 
  */
	public int getIndex(char c1, char c2)
	{
		if ( c1 == '*' || c2 == '*' )
			return -1;
		int result = (c1 - 97)*26 + (c2 - 97);
		return result;
	}


///////// end of class
}

/**
  *My own list to store the position of the certain characters.
  *<p>It works as an index.
  */
class myIndex
{
	/** The current node of the index. */
	myIndexNode current;
	/** The first node of the index. */
	myIndexNode head;

/**
  *Creats new index.
  */
	public myIndex()
	{
		this.head = null;
		this.current = this.head;
	}

/**
  *Add new to the index.
  *@param i1 the row the first character is in.
  *@param j1 the column the first character is in.
  *@param i2 the row the second characer is in.
  *@param j2 the column the second character is in.
  */
	public void add(int i1, int j1, int i2, int j2)
	{
		if (head == null)
		{
			head = new myIndexNode(i1, j1, i2, j2);
			current = head;
		}
		else
		{
			current.next = new myIndexNode(i1, j1, i2, j2);
			current = current.next;
		}
	}

}

/**
  *
  */
class myIndexNode
{
	/** The row the first character is in. */
	int x0;
	/** The column the first character is in. */
	int y0;
	/** The row the second character is in. */
	int x1;
	/** The column the second character is in. */
	int y1;
	/** The next node of this one. */
	myIndexNode next;

/**
  *Creats new node of index.
  *@param i1 the row the first character is in.
  *@param j1 the column the first character is in.
  *@param i2 the row the second characer is in.
  *@param j2 the column the second character is in.	
  */
	public myIndexNode(int i1, int j1, int i2, int j2)
	{
		this.x0 = i1;
		this.y0 = j1;
		this.x1 = i2;
		this.y1 = j2;
	}
}