寻求有关使用 DAWG 实现文字游戏的建议
Seeking suggestions on a Word Game implementation using DAWG
我正在尝试实现一个具有以下规则的小游戏:
给定一组随机字母(例如 10),我想找到可以从这些字母中组成的所有可能的单词。我为此使用标准词典。
允许多次使用字母,并非必须使用所有字母,只要它产生的单词具有 4 个或更多字符即可。我认为这类似于解决字谜,只是允许多次使用字母。
例如
给出的字母:q r b d t e s
可能的词:bedders、dessert 等
在搜索支持 O(1) 的数据结构以检查建议的单词是否在字典中时,我找到了这个 paper and subsequently also found a working Java DAWG implementation here。
这是我卡住的地方:
当尝试生成可以从这些字母创建的可能单词列表时,我想知道我是否遗漏了使用 DAWG 实现的内容。我在这里看到其他线程建议使用 Trie 并递归地遍历节点,但我希望我可以用 DAWG 做类似的事情。
我目前正在使用的实现方式是遍历字典中的所有单词,然后跳过任何包含不属于先前分配的字母的字母的单词。这行得通,但速度很慢,遍历字典中的所有单词 * ~20 个字母最坏的情况。
for(String word : dawg.getAllStrings()) {
boolean blacklist = false;
for(int i = 0; i<nonLetters.length(); i++) {
if(word.indexOf(nonLetters.charAt(i)) >= 0) {
blacklist = true;
break;
}
}
if(!blacklist)
possibleWordList.add(word);
}
我尝试实现递归单词匹配,但由于该实现不公开对其 Node 实现的访问而遇到困难,不过我可以在本地更改它。
在无法访问节点的情况下,我可以使用 dawg.contains(letter),但由于需要多次使用字母,我想知道这是否真的有帮助。例如。我将从 'A' 开始,然后是 'AA',...停在例如20个A。
使用 Trie 树会更容易吗?找到匹配的词仍然相当快,但更容易生成可能的词列表?
是否有其他 DAWG 库公开节点遍历或具有 ref 实现来生成所有可能的单词?
感谢任何帮助或指点!
我有一个想法,我不确定但希望能帮助你。
首先创建字典作为工作键,键将是单词包含的所有字母按字母顺序排列。
例如:经典 -> acils ,字母 -> elrt。
随机字符串类似。
你可以为你的程序准备这个。
并得到你需要的一切来浏览复杂度为O(n)的字典
for(Word word : dawg.getAllStrings()){
if(randomString.contains(word.getKey()))
possibleWordList.add(word);
}
我觉得这个方法不错。我向问题中引用的 DAWG 实现的 ModifiableDAWGSet 添加了一个递归方法。
getWords 使用字符串前缀调用,将字符相加。
我首先实现它以生成 DAWG 中的所有单词,并与 ModifiableDAWGSet.getAllStrings() 的现有方法进行比较。
然后我添加了跳过不包含单词的单词,不包括可能字符列表中的字符。
private ArrayList<String> allMatchingWords = new ArrayList<String>();
private ArrayList<Character> possibleCharacters;
private void getWords(ModifiableDAWGNode originNode, String prefix) {
NavigableMap<Character, ModifiableDAWGNode> transitionTreeMap = originNode.getOutgoingTransitions();
for(Map.Entry<Character, ModifiableDAWGNode> transition : transitionTreeMap.entrySet())
{
Character c = transition.getKey();
if(!possibleCharacters.contains(c))
continue;
ModifiableDAWGNode n = transition.getValue();
if(n.isAcceptNode()) //this is a word
{
allMatchingWords.add(prefix + c);
}
getWords(n, prefix + c);
}
}
public ArrayList<String> getAllMatchingWords(Character mustContain, ArrayList<Character> possibleCharacters)
{
allMatchingWords.clear();
this.mustContain = mustContain;
this.possibleCharacters = possibleCharacters;
getWords(sourceNode, "");
return allMatchingWords;
}
我正在尝试实现一个具有以下规则的小游戏: 给定一组随机字母(例如 10),我想找到可以从这些字母中组成的所有可能的单词。我为此使用标准词典。
允许多次使用字母,并非必须使用所有字母,只要它产生的单词具有 4 个或更多字符即可。我认为这类似于解决字谜,只是允许多次使用字母。
例如 给出的字母:q r b d t e s 可能的词:bedders、dessert 等
在搜索支持 O(1) 的数据结构以检查建议的单词是否在字典中时,我找到了这个 paper and subsequently also found a working Java DAWG implementation here。
这是我卡住的地方: 当尝试生成可以从这些字母创建的可能单词列表时,我想知道我是否遗漏了使用 DAWG 实现的内容。我在这里看到其他线程建议使用 Trie 并递归地遍历节点,但我希望我可以用 DAWG 做类似的事情。
我目前正在使用的实现方式是遍历字典中的所有单词,然后跳过任何包含不属于先前分配的字母的字母的单词。这行得通,但速度很慢,遍历字典中的所有单词 * ~20 个字母最坏的情况。
for(String word : dawg.getAllStrings()) {
boolean blacklist = false;
for(int i = 0; i<nonLetters.length(); i++) {
if(word.indexOf(nonLetters.charAt(i)) >= 0) {
blacklist = true;
break;
}
}
if(!blacklist)
possibleWordList.add(word);
}
我尝试实现递归单词匹配,但由于该实现不公开对其 Node 实现的访问而遇到困难,不过我可以在本地更改它。
在无法访问节点的情况下,我可以使用 dawg.contains(letter),但由于需要多次使用字母,我想知道这是否真的有帮助。例如。我将从 'A' 开始,然后是 'AA',...停在例如20个A。
使用 Trie 树会更容易吗?找到匹配的词仍然相当快,但更容易生成可能的词列表?
是否有其他 DAWG 库公开节点遍历或具有 ref 实现来生成所有可能的单词?
感谢任何帮助或指点!
我有一个想法,我不确定但希望能帮助你。 首先创建字典作为工作键,键将是单词包含的所有字母按字母顺序排列。 例如:经典 -> acils ,字母 -> elrt。 随机字符串类似。 你可以为你的程序准备这个。 并得到你需要的一切来浏览复杂度为O(n)的字典
for(Word word : dawg.getAllStrings()){
if(randomString.contains(word.getKey()))
possibleWordList.add(word);
}
我觉得这个方法不错。我向问题中引用的 DAWG 实现的 ModifiableDAWGSet 添加了一个递归方法。
getWords 使用字符串前缀调用,将字符相加。 我首先实现它以生成 DAWG 中的所有单词,并与 ModifiableDAWGSet.getAllStrings() 的现有方法进行比较。 然后我添加了跳过不包含单词的单词,不包括可能字符列表中的字符。
private ArrayList<String> allMatchingWords = new ArrayList<String>();
private ArrayList<Character> possibleCharacters;
private void getWords(ModifiableDAWGNode originNode, String prefix) {
NavigableMap<Character, ModifiableDAWGNode> transitionTreeMap = originNode.getOutgoingTransitions();
for(Map.Entry<Character, ModifiableDAWGNode> transition : transitionTreeMap.entrySet())
{
Character c = transition.getKey();
if(!possibleCharacters.contains(c))
continue;
ModifiableDAWGNode n = transition.getValue();
if(n.isAcceptNode()) //this is a word
{
allMatchingWords.add(prefix + c);
}
getWords(n, prefix + c);
}
}
public ArrayList<String> getAllMatchingWords(Character mustContain, ArrayList<Character> possibleCharacters)
{
allMatchingWords.clear();
this.mustContain = mustContain;
this.possibleCharacters = possibleCharacters;
getWords(sourceNode, "");
return allMatchingWords;
}