如何从Trie中检索给定长度的随机单词 [英] How to retrieve a random word of a given length from a Trie
问题描述
我有一个简单的Trie，我用来存储长度为2到15的大约80k字。它非常适合检查字符串是否为单词;但是，现在我需要一种获取给定长度的随机单词的方法。换句话说，我需要getRandomWord（5）来返回一个5个字母的单词，所有5个字母的单词都有相同的返回机会。
I have a simple Trie that I'm using to store about 80k words of length 2 - 15. It works great for checking to see if a string is a word; However, now I need a way of getting a random word of a given length. In other words, I need "getRandomWord(5)" to return a 5 letter word, with all 5 letter words having an equal chance of being returned.
我能想到的唯一方法就是选择一个随机数并遍历树的广度优先，直到我传递了所需长度的多个单词。有没有更好的方法呢？
The only way I can think of is to pick a random number and traverse the tree breadth-first until I've passed that many words of the desired length. Is there a better way to do this?
可能没必要，但这是我的特里的代码。
Possibly unnecessary, but here's the code for my trie.
class TrieNode {
private TrieNode[] c;
private Boolean end = false;
public TrieNode() {
c = new TrieNode[26];
}
protected void insert(String word) {
int n = word.charAt(0) - 'A';
if (c[n] == null)
c[n] = new TrieNode();
if (word.length() > 1) {
c[n].insert(word.substring(1));
} else {
c[n].end = true;
}
}
public Boolean isThisAWord(String word) {
if (word.length() == 0)
return false;
int n = word.charAt(0) - 'A';
if (c[n] != null && word.length() > 1)
return c[n].isThisAWord(word.substring(1));
else if (c[n] != null && c[n].end && word.length() == 1)
return true;
else
return false;
}
}
编辑：标记的答案效果很好;我会在这里为后代添加我的实现，以防它可以帮助任何有类似问题的人。
The marked answer worked well; I'll add my implementation here for posterity, in case it helps anyone with a similar problem.
首先，我做了一个帮助类来保存关于TrieNodes的元数据我m在搜索中使用：
First, I made a helper class to hold metadata about the TrieNodes I'm using in the search:
class TrieBranch {
TrieNode node;
int letter;
int depth;
public TrieBranch(TrieNode n, int l, int d) {
letter = l; node = n; depth = d;
}
}
这是持有Trie并实现搜索随机单词。我是一个初学者，所以可能有更好的方法来做到这一点，但我测试了一下，它似乎工作。没有错误处理，所以需要注意。
This is the class that holds the Trie and implements the search for the random word. I'm kind of a beginner so there may be better ways to do this, but I tested this a bit and it seems to work. No error handling, so caveat emptor.
class Dict {
final static int maxWordLength = 13;
final static int lettersInAlphabet = 26;
TrieNode trie;
int lengthFrequencyByLetter[][];
int totalLengthFrequency[];
public Dict() {
trie = new TrieNode();
lengthFrequencyByLetter = new int[lettersInAlphabet][maxWordLength + 1];
totalLengthFrequency = new int[maxWordLength + 1];
}
public String getRandomWord(int length) {
// Returns a random word of the specified length from the trie
// First, pick a random number from 0 to [number of words with this length]
Random r = new Random();
int wordIndex = r.nextInt(totalLengthFrequency[length]);
// figure out what the first letter of this word would be
int firstLetter = -1, totalSoFar = 0;
while (totalSoFar <= wordIndex) {
firstLetter++;
totalSoFar += lengthFrequencyByLetter[firstLetter][length];
}
wordIndex -= (totalSoFar - lengthFrequencyByLetter[firstLetter][length]);
// traverse the (firstLetter)'th node of trie depth-first to find the word (wordIndex)'th word
int[] result = new int[length + 1];
Stack<TrieBranch> stack = new Stack<TrieBranch>();
stack.push(new TrieBranch(trie.getBranch(firstLetter), firstLetter, 1));
while (!stack.isEmpty()) {
TrieBranch n = stack.pop();
result[n.depth] = n.letter;
// examine the current node
if (n.depth == length && n.node.isEnd()) {
wordIndex--;
if (wordIndex < 0) {
// search is over
String sResult = "";
for (int i = 1; i <= length; i++) {
sResult += (char)(result[i] + 'a');
}
return sResult;
}
}
// handle child nodes unless they're deeper than target length
if (n.depth < length) {
for (int i = 25; i >= 0; i--) {
if (n.node.getBranch(i) != null)
stack.push(new TrieBranch(n.node.getBranch(i), i, n.depth + 1));
}
}
}
return "failure of some sort";
}
}
使用随意字典（80k字最大长度12）每次调用getRandomWord（）都需要重复.2ms，并且使用更彻底的字典（250K字，最大长度为24），每次调用大约需要1ms。
Using a casual dictionary (80k words max length 12) each call to getRandomWord() takes abount .2ms, and using a more thorough dictionary (250K words, max length 24) each call takes about 1ms.
推荐答案
为了确保你有机会得到每个5个字母的单词，你需要知道你的树中有多少个5个字母的单词。因此，当您构建树时，您将添加到两个计数器的单词的长度：一个整体频率计数器和一个字母频率计数器：
To make sure you have an even chance of getting each 5-letter word, you need to know how many 5-letter words there are in your tree. So as you construct the tree, you add the length of the word you're adding to two counters: an overall frequency counter, and a by-letter frequency counter:
int lengthFrequencyByLetter[letterIndex][maxWordLength-1]
int totalLengthFrequency[maxWordLength-1]
因此，如果你有4000个5个字母的单词，其中213个以d开头，那么
So if you have 4000 5-letter words, and 213 of them start with "d", then
lengthFrequencyByLetter[3][4] = 213
和
totalLengthFrequency[4] = 4000
<完成后，将所有内容添加到树中。 （字母a为0，b为1，...z为25。）
after you're done adding everything to your tree. (The letter "a" is 0, "b" is 1, ... "z" is 25.)
从此处，您可以搜索 n 给定长度的单词，其中 n 是从均匀随机分布中选取的随机整数，范围为（0， totalLengthFrequency [length-1] ）。
From here, you can do a search for the nth word of a given length, where n is a random integer picked from a uniform random distribution, in the range (0, totalLengthFrequency[length-1]).
假设您的结构中有4000个5个字母的单词。你选择随机数1234.现在你可以检查
Let's say you have 4000 5-letter words in your structure. You pick random number 1234. Now you can check
lengthFrequencyByLetter[0][4]
lengthFrequencyByLetter[1][4]
lengthFrequencyByLetter[2][4]
lengthFrequencyByLetter[3][4]
反过来，直到你总共超过1234.然后你很快就知道第1234个5个字母单词的起始字母是什么，然后在那里搜索。您不必每次都从头开始搜索树中的每个单词。
in turn, until you exceed a total of 1234. Then you know quickly what the start letter of the 1234th 5-letter word is, and then search there. You don't have to search every word in the tree from the beginning each time.
这篇关于如何从Trie中检索给定长度的随机单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
