- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我有一个简单的 Trie,我用它来存储大约 80k 个长度为 2 - 15 的单词。它非常适合检查一个字符串是否是一个单词;但是,现在我需要一种方法来获取给定长度的随机单词。换句话说,我需要“getRandomWord(5)”来返回一个 5 个字母的单词,所有 5 个字母的单词被返回的机会均等。
我能想到的唯一方法是选择一个随机数并以宽度优先的方式遍历树,直到我传递了那么多所需长度的单词。有更好的方法吗?
可能没有必要,但这是我的 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;
}
}
编辑:标记的答案效果很好;我将在此处添加我的实现以供后代使用,以防它对遇到类似问题的任何人有所帮助。
首先,我创建了一个辅助类来保存有关我在搜索中使用的 TrieNode 的元数据:
class TrieBranch {
TrieNode node;
int letter;
int depth;
public TrieBranch(TrieNode n, int l, int d) {
letter = l; node = n; depth = d;
}
}
这是保存 Trie 并实现随机词搜索的类。我是一个初学者,所以可能有更好的方法来做到这一点,但我对此进行了一些测试,它似乎有效。没有错误处理,所以买者自负。
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";
}
}
使用普通字典(8 万个单词,最大长度 12)每次调用 getRandomWord() 大约需要 0.2 毫秒,而使用更详尽的字典(25 万个单词,最大长度 24)每次调用大约需要 1 毫秒。
最佳答案
为确保您有均匀的机会获得每个 5 个字母的单词,您需要知道树中有多少个 5 个字母的单词。因此,在构建树时,您将要添加的单词的长度添加到两个计数器:一个整体频率计数器和一个字母频率计数器:
int lengthFrequencyByLetter[letterIndex][maxWordLength-1]
int totalLengthFrequency[maxWordLength-1]
所以如果你有 4000 个 5 个字母的单词,其中 213 个以“d”开头,那么
lengthFrequencyByLetter[3][4] = 213
和
totalLengthFrequency[4] = 4000
将所有内容添加到树后。 (字母“a”为0,“b”为1,...“z”为25。)
从这里,您可以搜索给定 length
的第 n
个单词,其中 n
是从中选取的随机整数在 (0, totalLengthFrequency[length-1]
) 范围内的均匀随机分布。
假设您的结构中有 4000 个由 5 个字母组成的单词。您选择随机数 1234。现在您可以检查
lengthFrequencyByLetter[0][4]
lengthFrequencyByLetter[1][4]
lengthFrequencyByLetter[2][4]
lengthFrequencyByLetter[3][4]
依次递增,直到总数超过1234。那么你很快就知道第1234个5个字母的单词的首字母是什么,然后去那里找。您不必每次都从头搜索树中的每个单词。
关于java - 如何从 Trie 中检索给定长度的随机单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17152269/
我让随机数低于之前的随机数。 if Airplane==1: while icounter0: print "You have enoph fuel to get to New
是否可以生成 BigFloat 的随机数?类型均匀分布在区间 [0,1)? 我的意思是,因为 rand(BigFloat)不可用,看来我们必须使用 BigFloat(rand())为了那个结局。然而,
我正在尝试学习 Kotlin,所以我正在学习互联网上的教程,其中讲师编写了一个与他们配合良好的代码,但它给我带来了错误。 这是错误 Error:(26, 17) Kotlin: Cannot crea
是否有任何方法可以模拟 Collections.shuffle 的行为,而不使比较器容易受到排序算法实现的影响,从而保证结果的安全? 我的意思是不违反类似的契约(Contract)等.. 最佳答案 在
我正在创建一个游戏,目前必须处理一些math.random问题。 我的Lua能力不是那么强,你觉得怎么样 您能制定一个使用 math.random 和给定百分比的算法吗? 我的意思是这样的函数: fu
我想以某种方式让按钮在按下按钮时随机改变位置。我有一个想法如何解决这个问题,其中一个我在下面突出显示,但我已经认为这不是我需要的。 import javafx.application.Applicat
对于我的 Java 类(class),我应该制作一个随机猜数字游戏。我一直陷入过去几天创建的循环中。程序的输出总是无限循环,我不明白为什么。非常感谢任何帮助。 /* This program wi
我已经查看了涉及该主题的一些其他问题,但我没有在任何地方看到这个特定问题。我有一个点击 Web 元素的测试。我尝试通过 ID 和 XPath 引用它,并使用 wait.until() 等待它变得可见。
我在具有自定义类的字典和列表中遇到了该异常。示例: List dsa = (List)Session["Display"]; 当我使用 Session 时,转换工作了 10-20 次..然后它开始抛
需要帮助以了解如何执行以下操作: 每隔 2 秒,这两个数字将生成包含从 1 到 3 的整数值的随机数。 按下“匹配”按钮后,如果两个数字相同,则绿色标签上的数字增加 1。 按下“匹配”按钮后,如果两个
void getS(char *fileName){ FILE *src; if((src = fopen(fileName, "r")) == NULL){ prin
如果我有 2 个具有以下字段的 MySQL 数据库... RequestDB: - Username - Category DisplayDB: - Username - Category
我有以下语句 select random() * 999 + 111 from generate_series(1,10) 结果是: 690,046183290426 983,732229881454
我有一个使用 3x4 CSS 网格构建的简单网站。但出于某种原因,当我在 chrome“检查”中检查页面时,有一个奇怪的空白 显然不在我的代码中的标签。 它会导致网站上出现额外的一行,从而导致出现
我有两个动画,一个是“过渡”,它在悬停时缩小图像,另一个是 animation2,其中图像的不透明度以周期性间隔重复变化。 我有 animation2 在图像上进行,当我将鼠标悬停在它上面时,anim
如图所示post在 C++ 中有几种生成随机 float 的方法。但是我不完全理解答案的第三个选项: float r3 = LO + static_cast (rand()) /( static_c
我正在尝试将类添加到具有相同类的三个 div,但我不希望任何被添加的类重复。 我有一个脚本可以将一个类添加到同时显示的 1、2 或 3 个 div。期望的效果是将图像显示为背景图像,并且在我的样式表中
我有一个基本上可以工作的程序,它创建由用户设置的大小的嵌套列表,并根据用户输入重复。 但是,我希望各个集合仅包含唯一值,目前这是我的输出。 > python3 testv.py Size of you
我正在尝试基于 C# 中的种子生成一个数字。唯一的问题是种子太大而不能成为 int32。有什么方法可以像种子一样使用 long 吗? 是的,种子必须很长。 最佳答案 这是我移植的 Java.Util.
我写这个函数是为了得到一个介于 0 .. 1 之间的伪随机 float : float randomFloat() { float r = (float)rand()/(float)RAN
我是一名优秀的程序员,十分优秀!