在 java 中查找模式匹配词的最快方法

Question

给定一个总字数在 100,000-500,000 之间的字典，查找 pattern/mask 的最快方法是什么？其中“-”是未知字母，即 s--t- 会 return salts, salty, scats, scots etc...

目前使用的 trie 非常适合填充首字母的单词，但当存在诸如 ---st 或 -tr- 之类的模式时，trie 的优势就完全丧失了。

我正在搜索的单词基本上是均匀分布的，其中第一个字母被填充，而那些没有。

将单词加载到 SQL 数据库中，然后使用 SQL 通配符搜索功能是否有意义？或者我只是手动搜索每个可能的字母组合以查找空白字母的哈希图呢？

非常感谢您提供的任何见解。

Answer 1

下面的小方法利用了 String#matches() method along with a dynamically created Regular Expression，它基于搜索条件字符串中提供的通配符。它将 return 一个字符串列表 (List<String>)，包含找到的与提供的条件字符串匹配的任何单词。

单词列表 file I 运行搜索条件字符串 ("s--t-") 通过（使用 BufferedReader(FileReader)) 包含 370,108 个单词，通常在大约 250 毫秒或 0.25 秒（平均）内完成任务。

至于通配符，最常用的通配符是星号（*），通常代表字符串中的零个或多个字符，以及问号(?)，通常表示任何一个字符。您显然想使用连字符 (-) 代替通常的问号，这是可以的。提供的方法可以处理所有三种通配符类型（*、? 和 -）用于特定目的的标准字符串。

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

在 java 中查找模式匹配词的最快方法

Fastest way to lookup pattern matching words in java

java

string

lookup

performance

trie