Java — бинарный поиск(). Как настроить бинарный поиск для проверки орфографии

Я делаю проект проверки орфографии. У меня есть список слов, а затем адрес в Геттисберге, где некоторые слова написаны с ошибками. моя работа состоит в том, чтобы определить, какие слова написаны с ошибками, а затем распечатать звездочки или что-то еще под словом с ошибкой, когда я распечатываю адрес. моя проблема в части бинарного поиска. Я не уверен в синтаксисе, и javadoc выглядит как китайский. вот мой исходный код (binarySearch внизу)

/*
 * Assignment 1: Spell Check
 * Professor Subrina Thompson
 * CS102
 */
package spellcheck;

import java.util.*;
import java.io.*;

public class SpellCheck {

    //48,219 words in the words.txt

    //Declare Variables
    static FileReader reader;
    static Scanner input;
    static ArrayList <String> wordList = new ArrayList<String>();
    static FileReader reader2;
    static Scanner input2;
    static String testWord;
    static String index;

    //Main Method
    public static void main(String[] args) throws FileNotFoundException {
        fileSort();
    }

    //Open file to be read from
    public static void openFile() throws FileNotFoundException {
        reader = new FileReader("words.txt");
        input = new Scanner(reader);

    }

    //sort the file
    public static void fileSort() throws FileNotFoundException{
        openFile();

        //read the word list into an ArrayList
        while (input.hasNext()){
            wordList.add(input.next());
        }

        //Sort the array
        Collections.sort(wordList);
    }

    //read the gettysburg address
    public static void gAddress()throws FileNotFoundException{
        reader2 = new FileReader("gettysburg.txt");
        input2 = new Scanner(reader2);

        //create loop to place word from file into a var then test to see if it is in the dictionary
        for(int i = 0; i < wordList.size(); i++){

            //place the word into a variable
            testWord = input2.next();

            //test if the word is in the dictionary
            index = Collections.binarySearch(wordList,testWord);
        }
    }

    //compare the address and array through binary search 

    //print out if spelling is correct
}

PS. Я знаю, что это не завершено и с большим количеством незавершенных концов, это все еще незавершенная работа.

РЕДАКТИРОВАТЬ:

Я попытался создать новую функцию поиска, основываясь на том, как я понимаю работу бинарного поиска. это код этой функции. «строка w» будет словом словаря для проверки на соответствие testWord из адреса:

public static int binarySearch (String w) {

        int start = 0;
        int stop  = wordList.size() - 1;

        while (start != stop){
            int half = ((stop - start)/2) + start;
            int res = wordList.get(half).compareToIgnoreCase(w);

            if( res == 0 ){
                return half;
            }
        else if( stop - start <= 1 ){
                return -1;
            }
        else if( res > 0 ){
                start = half;
            }
        else if( res < 0 ){
                stop  = half;
            }


   }

   return -1;
}

person YazanLpizra    schedule 13.02.2013    source источник


Ответы (3)


Это все, что вам нужно:

if(index < 0) {
  System.out.println(testWord + " not in dictionary");
}

Кроме того, изучив абсолютное значение index, вы можете легко найти слова в словаре, которые были в алфавитном порядке близки к вашему слову с опечаткой.

person Tomasz Nurkiewicz    schedule 13.02.2013
comment
Он все равно столкнется с проблемой, которую я изложил в своем ответе. - person Miserable Variable; 14.02.2013

Javadoc выглядит как китайский, потому что списки являются общими.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

Следует читать с T как с любым общим типом, T — это тип ключа. Первый параметр, список, должен быть списком типа, реализующего интерфейс Comparable для типа, производным от которого является T.

В вашем случае тип ключа T — String. И это список строк. String реализует Comparable, а String является суперклассом String. Так что это действительно.

Если вы заполните String, сигнатура метода превратится во что-то более обычное:

public static int binarySearch(List<String> list, String key)

Поэтому, учитывая

int index;
List<String> list;
String key;

вызов выглядит так

index = Collections.binarySearch(list, key);

после чего index будет содержать индекс ключа поиска в списке или отрицательное число, если ключ не найден. Точнее:

индекс ключа поиска, если он содержится в списке; в противном случае (-(точка вставки) - 1). Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента больше, чем ключ, или list.size(), если все элементы в списке меньше указанного ключа. Обратите внимание, что это гарантирует, что возвращаемое значение будет >= 0 тогда и только тогда, когда ключ найден.

person flup    schedule 13.02.2013
comment
Спасибо за информацию, но я все еще немного сбит с толку (java n00b здесь, лол, пожалуйста, потерпите меня). в этом последнем лакомом кусочке кода, почему тип возвращаемого значения - int? и как бы я использовал файл вместо ключа String? - person YazanLpizra; 14.02.2013
comment
Collections.binarySearch не будет искать файл в списке, а только один единственный ключ (многие из которых вы можете прочитать из файла и найти один за другим в списке). Я обновил ответ конкретным вызовом. Тип возвращаемого значения - int, потому что он (несколько скрытно) говорит так: public static ‹T› int binarySearch(yadayada) - person flup; 14.02.2013

создайте цикл, чтобы поместить слово из файла в var, затем проверьте, есть ли оно в словаре

Но это не то, что вы делаете. Вы создаете цикл, чтобы просмотреть все слова в словаре и проверить, находится ли следующее слово в адресе в словаре, и ничего с этим не делать, независимо от того, найдено оно или нет.

Если в словаре больше слов, чем адрес, вы, вероятно, получите исключение, если в адресе больше слов, вы не проверите их все.

person Miserable Variable    schedule 13.02.2013
comment
На самом деле код не работает. У меня возникают проблемы со строкой binarySearch. может быть, это потому, что индекс - это строка и должен быть другого типа? Я не уверен, что, хотя. Я никогда раньше не использовал бинарный поиск, поэтому я не знаю, что именно он вернет. - person YazanLpizra; 14.02.2013
comment
Если index является String, ваша программа даже не скомпилируется. Он компилируется? - person Miserable Variable; 14.02.2013
comment
err, есть разница между ошибками компиляции и ошибками времени выполнения. с каким вы столкнулись? - person Miserable Variable; 15.02.2013