首页 文章

Java - binarySearch（） . 如何为拼写检查设置binarySearch

提问于
浏览 次
1

我正在做一个拼写检查项目 . 我有一个单词列表，然后是Gettysburg地址，其中一些单词拼写错误 . 我的工作是确定哪些单词拼写错误，然后在我打印出地址时打印出拼写错误字样的星号或其他内容 . 我的问题是在binarySearch部分 . 我不确定语法，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 . 我知道它不完整，有很多松散的目的，它仍然是一个正在进行的工作 .

编辑：

我尝试根据我理解binarySearch的工作方式创建一个新的搜索功能 . 这是该函数的代码 . “string 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;
}
java binary-search

3 回答

  • 1

    这就是你所需要的：

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

    此外，通过检查 index 的绝对值，您可以轻松地在字典中找到按字母顺序靠近错误字词的单词 .

    回复于
  • 2

    javadoc看起来像中文，因为列表是Generic .

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

    应该用T作为任何泛型类型读取，T是键的类型 . 第一个参数列表必须是实现T派生类型的Comparable接口的类型列表 .

    在您的情况下，密钥类型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 .

    回复于
  • 2

    创建循环以将文件从文件放入var然后测试以查看它是否在字典中

    但这不是你在做什么 . 您正在创建一个循环来遍历字典中的所有单词，并检查地址中的下一个单词是否在字典中，并且无论是否找到它都不执行任何操作 .

    如果字典有更多的单词然后地址你可能会得到例外，如果地址有更多的单词，那么你将不会检查所有单词 .

    回复于

相关问题