给出一个总字典数在100,000-500,000之间的单词词典,查找图案/遮罩的最快方法是什么?其中“-”是一个未知的字母,即s--t-会返回盐,盐,粪便,苏格兰威士忌等...
当前使用特里树(trie)非常适合填充了首字母的单词,但是当出现--- st或-tr-这样的模式时,特里树的好处将完全丧失。
我正在搜索的单词基本上是均匀分布的,其中第一个字母被填充,而第一个字母不被填充。
将单词加载到SQL数据库中是否有意义,然后再使用SQL通配符搜索功能?还是散列图呢,我只是手动搜索每个可能的字母组合中的空白字母?
非常感谢您能提供的见解。
以下小方法利用String#matches()方法以及动态创建的Regular Expression,该方法基于在搜索条件字符串中提供了哪些通配符。它将返回找到与提供的标准字符串匹配的所有单词的字符串列表(List<String>
)。
单词列表文件我运行搜索条件字符串("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