Solved

Java Dictionary Search

Posted on 2007-11-28
11
3,184 Views
Last Modified: 2013-11-23
Hi,

I am trying to develop a piece of Java to search a dictionary for words that best-fit a charachter input stream. I found a piece of code on ee that I have included with this post that looks like it may be a fairly close fit. The problem I'm having with is that it finds things when it shouldn't!

Say the dictionary file only contained the following words:
absonant
absonous
absorb
absorbable
absorbate
absorbed
absorbefacient
absorbency
absorbent
absorber
absorbing
absorption

If the input stream was "ABSO", it should put all of those words into an array as possible options.
It would get the next character "R" and drop "absoNant" and  "absoNous", next character "B" and drop "absorPtion".
Eventually having to make a desicion on a "best-fit" word.
Problem is that i'd like it to come back with a best-fit word rather than nothing - like taking a guess.
If the next character after "B" was "X" making "ABSORBX" - it's not in the list, so perhaps getting the next character allows the guess to be made - next character after "X" is "D", "ABSORBXD" - it makes a decision to selec "ABSORBED" as a best-fit.
 
First problem I have with the code below is that
- enter "ABSO" - it returns not found (correct I think - the word is not in the dictionary, but words begin with it??)
- enter "ABSOX" - it returns found (I don't think its supposed to - word not in dictionary and no words begin with it.)

If anyone can help me overcome these problems, i'd very much appreciate the help!!

Thanks in advance!

Cheers,

Phil.

public class Wordsearch {
 
 

    public static void main(String args[]) throws IOException {
 

         ArrayList words = loadFile("dictionary.txt"); // Load the word in arrayList
 

         Collections.sort(words); //sort ArrayList required for binarySearch
 

         BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

         while (true) {

            System.out.print("Enter Word (q to quit) ");

            System.out.print("\n");

            String option = stdin.readLine();
 

            if (option.equalsIgnoreCase("q")) System.exit(-1);

            else {
 

               if (Arrays.binarySearch(words.toArray(),option.toLowerCase())== -1)

                   System.out.println("Word is not found in dictionary.");

               else

                   System.out.println("Word Found");

            }
 

         }
 

    }
 

   private static ArrayList loadFile(String fileName) throws IOException{

        String word;
 

        File file  = new File(fileName);

        BufferedReader bfreader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));

        ArrayList wordList = new ArrayList();

        while ((word=bfreader.readLine()) != null){

         wordList.add(word.toLowerCase());
 

        }
 

        return wordList;
 

   }

}

Open in new window

0
Comment
Question by:phil8258
  • 7
  • 3
11 Comments
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
That code is using exact (case-insensitive) matching. You probably need something like fuzzy matching algos
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
Java Lucene uses Levenshtein
0
 
LVL 26

Expert Comment

by:ksivananth
Comment Utility
>>enter "ABSOX" - it returns found (I don't think its supposed to - word not in dictionary and no words begin with it.)
>>

try below,

if (Arrays.binarySearch(words.toArray(),option.toLowerCase()) < 0)

the binary serach returns < 0 if it doesn't found but it is not -1 always!
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
Change

>>Arrays.binarySearch(words.toArray()

to

Collections.binarySearch(words

as there's no reason to convert
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:phil8258
Comment Utility
Ok, thanks. Those changes work pretty well.

The second part of the problem is now that I want to store a list of words
So that if you search the dictionary for the input string "absorbe", you get a list containing:
absorbed, absorbefacient, absorbency, absorbent, absorber

Anyone any idea how this could be done?
A snippet of code would be really helpful to get me kick started.

Cheers.
 
0
 
LVL 86

Accepted Solution

by:
CEHJ earned 500 total points
Comment Utility
Just need to do something like

String target = "absorbe";

ArrayList found = new ArrayList();

for(int i = 0;i < wordList.size();i++) {

    String word = (String)wordList.get(i).toLowerCase();

    if (word.substring(target) > -1) {

        found.add(word);

    }

}

Open in new window

0
 

Author Comment

by:phil8258
Comment Utility
Thanks for that prompt.
line 5 is having a little difficulty.
"The method substring(int) in the type String is not applicable for the arguments (String)"
any idea how to fix it?
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
Sorry!


if (word.indexOf(target) > -1) {

        found.add(word);

}

Open in new window

0
 

Author Comment

by:phil8258
Comment Utility
sorted. thanks :O)
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
:-)
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
sumHeights  challenge 17 59
bigHeights  challenge 13 55
XML Paring  Error - Premature end of file. 7 55
Python Assistance 7 31
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now