Самый быстрый способ поиска подходящих слов в java

Question

Учитывая словарь слов где-то между 100 000-500 000 слов всего, что является самым быстрым способом поиска шаблона / маски? где '-' - это неизвестная буква, т. е. s - t- возвращает соли, соленую, scats, scots и т. д. c ...

В настоящее время используется tr ie, который отлично подходит для слов, которые имеют начальные буквы заполнены, но когда есть такой шаблон, как --- st или -tr-, преимущество tr ie полностью теряется.

По сути, я ищу равномерное распределение слов, в которых первые буквы заполнены, а те - нет.

Будет ли смысл загружать слова в базу данных SQL, чтобы затем использовать функцию поиска по шаблону SQL? Или как насчет хэш-карты, где я просто вручную ищу каждую возможную комбинацию букв на наличие пустых букв?

Буду признателен за любую информацию, которую вы можете дать.

Answer 1

Следующий небольшой метод использует метод String # match () вместе с динамически создаваемым Регулярным выражением , основанным на том, какие символы подстановки были предоставлены в строке критериев поиска. Он вернет список строк (List<String>) всех найденных слов, которые соответствуют предоставленной строке критериев.

Список слов файл Я пропускаю строку критериев поиска ("s--t-") через (с использованием BufferedReader (FileReader) ) содержит 370 108 слов и в целом выполняет задачу примерно за 250 миллисекунд или 0,25 секунды (в среднем).

Что касается подстановочных знаков, наиболее часто используемых подстановочных знаков символами являются звездочка (*), которая обычно представляет ноль или более символов в строке символов, и знак вопроса (? ), который обычно представляет любой один символ. Вы, очевидно, хотите использовать дефис (-) вместо обычного знака вопроса, который в порядке. Предоставленный метод может обрабатывать все три типа подстановочных знаков (*, ? и - ) в пределах одной строки критериев для указанной вами цели c.

public static List<String> searchForWord(String dictionaryFilePath, 
                                         String searchCriteria) {
    // This method ignores letter case!
    List<String> foundList = new ArrayList<>();  // To hold all found words.

    // Convert the supplied criteria string to a Regular Expression 
    // for the String#matches() method located in the 'while' loop.
    String regEx = searchCriteria.replace("?", ".").replace("-", ".").replace("*", ".*?").toLowerCase();

    // 'Try With Resources' use here to auto-close the reader.
    try (BufferedReader reader = new BufferedReader(new FileReader(dictionaryFilePath))) {
        String line = "";
        while ((line = reader.readLine()) != null) {
            line = line.trim().toLowerCase();
            if (line.matches(regEx)) {
                foundList.add(line);  // There's a match...add to the List.
            }
        }
    }
    // catch Exceptions (if any).
    catch (FileNotFoundException ex) {
        System.err.println(ex);
    }
    catch (IOException ex) {
        System.err.println(ex);
    }
    return foundList;  // Return the List.
} 

Чтобы использовать этот метод:

List<String> list = searchForWord("WordFile.txt", "s--t-");
for (String str : list) {
    System.out.println(str);
}

Найдено совпадений из списка слов, который я использовал:

saeta    saite    saith    sakti    salta
salts    salty    santa    santo    santy
saute    sauty    scats    scatt    scote
scots    scott    scuta    scute    scuts
scyth    seats    sects    seity    senti
sents    septa    septi    septs    serta
sesti    sexto    sexts    sheth    shita
shits    shote    shots    shott    shute
shuts    sidth    sifts    silts    silty
sinto    sintu    sitta    sixte    sixth
sixty    skate    skats    skete    skite
skits    skyte    slate    slath    slats
slaty    slete    slite    slits    slote
sloth    slots    sluts    smeth    smite
smith    smote    smuts    smyth    snath
snite    snits    snitz    snots    softa
softs    softy    sooth    soots    sooty
sorts    sorty    south    sowte    spate
spath    spats    spete    spite    spits
spitz    spots    sputa    spute    sruti
state    stats    stets    stite    stith
stott    suets    suety    suite    suits
suity    sutta    swath    swati    swats
swith    swots    syftn