如何在不使用线性搜索的情况下有效地在字典中搜索单词 java：减少搜索 Space

Question

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

我想检查给定字符串的起始字符，然后仅从下面的字母表到上面的字母表执行搜索（以减少搜索 space）。

例如，如果单词是堆栈。我想开始 '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。

有什么建议吗？

Answer 1

您是否尝试过查看 Trie 数据结构？

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

给定一个现有的单词词典，这可能会解决搜索特定单词的问题，而且 space 要求最少。

Answer 2

最常规的做法是使用二进制搜索。

另一种方法是为每个起始 aplhabet 索引字典，然后直接转到该索引。但这只有在您将它用于多个搜索时才有用，因为对于单个搜索，最好使用二进制搜索。

另一件事是，如果进行多次搜索，您可以将索引和二分搜索结合起来，这会使您的搜索速度更快。

如何在不使用线性搜索的情况下有效地在字典中搜索单词 java：减少搜索 Space

How to search a word in dictionary efficiently without using linear search java: Reducing Search Space

java

performance

search

dictionary

processing-efficiency