gpt4 book ai didi

java - 如何在不使用线性搜索的情况下有效地在字典中搜索单词java : Reducing Search Space

转载 作者:行者123 更新时间:2023-12-01 18:11:16 25 4
gpt4 key购买 nike

我有一本包含 120000 多个单词的词典。我想以有效的方式搜索它以检查它是否包含某个单词。

我想检查给定字符串的起始字符,然后仅从下面的字母表到上面的字母表执行搜索(以减少搜索空间)。

例如,如果单词是堆栈。我想以“r”开始并以“t”结束。在本例中为开始位置和结束位置。

到目前为止我已经做到了:

    inputFile = new Scanner(myFile);

while (inputFile.hasNext()) {
fileLine = inputFile.nextLine();

dictWords.add(fileLine);

no++;
}

HelperClass.setSearchPos(dictWords, "syncope", 0, dictWords.size());

public static void setSearchPos(ArrayList<String> dictList, String str, int startSearchPoint, int finishSearchPoint){

ArrayList<String> reducedSearchWords = new ArrayList<String>();

initSearchPos = startSearchPoint;
finalSearchPos = finishSearchPoint-1;
int midPos = (initSearchPos + finalSearchPos)/2;
char startWordChar = dictList.get(initSearchPos).charAt(0);
char finishWordChar = dictList.get(finalSearchPos).charAt(0);

startWordChar = shiftChar(startWordChar, 1);
finishWordChar = shiftChar(finishWordChar, -1);

while( startWordChar < str.charAt(0) &&
finishWordChar > str.charAt(0) ){
if(dictList.get(midPos).charAt(0) > str.charAt(0)){

setSearchPos(dictList, str, 0 , midPos);
}

if(dictList.get(midPos).charAt(0) < str.charAt(0)){

setSearchPos(dictList, str, midPos , finalSearchPos);
}
}
System.out.println("Star Pos " + initSearchPos);
System.out.println("Mid Pos " + midPos);
System.out.println("Finish Pos " + finalSearchPos);
}

public static char shiftChar(char c, int key) {

char shiftedChar;
shiftedChar = (char) ((char) c + key);

//This is used to bind the characters between Lowercase a-z
if (shiftedChar > 122) {
shiftedChar = (char) ((char) c - 123 + 97 + key);
}
return shiftedChar;

}

输出为:

Star Pos 88978
Mid Pos 96382
Finish Pos 103787
Star Pos 88978
Mid Pos 96382
Finish Pos 103786
Star Pos 88978
Mid Pos 96381
Finish Pos 103785

我对 Star Pos 和 Mid Pos 很满意,但循环将继续,直到 Finish Pos 为 0 并抛出 OutofBoundException。

有什么建议吗?

最佳答案

您尝试过查看 Trie 数据结构吗?

https://en.wikipedia.org/wiki/Trie

给定现有的单词词典,这可以解决搜索特定单词的问题,并且空间要求最小。

关于java - 如何在不使用线性搜索的情况下有效地在字典中搜索单词java : Reducing Search Space,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32826043/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com