我不确定你想要做什么,但是你可以在这里找到一个trie的例子。
基本上,我通过一个构建器来创建trie。让我们简单地了解一下如何将一个单词添加到trie中:
final TrieNodeBuilder nodeBuilder = new TrieNodeBuilder();
public TrieBuilder addWord(@Nonnull final String word)
{
Objects.requireNonNull(word);
final int length = word.length();
if (length == 0)
throw new IllegalArgumentException("a trie cannot have empty "
+ "strings (use EMPTY instead)");
nrWords++;
maxLength = Math.max(maxLength, length);
nodeBuilder.addWord(word);
return this;
}
这会将单词添加到TrieNodeBuilder中,具体步骤如下:
private boolean fullWord = false;
private final Map<Character, TrieNodeBuilder> subnodes
= new TreeMap<>();
TrieNodeBuilder addWord(final String word)
{
doAddWord(CharBuffer.wrap(word));
return this;
}
private void doAddWord(final CharBuffer buffer)
{
if (!buffer.hasRemaining()) {
fullWord = true;
return;
}
final char c = buffer.get();
TrieNodeBuilder builder = subnodes.get(c);
if (builder == null) {
builder = new TrieNodeBuilder();
subnodes.put(c, builder);
}
builder.doAddWord(buffer);
}
假设我们将“trouble”和“troubling”都添加到trie中,会发生以下情况:
- 第一次,为“trouble”的每个字符创建节点;
- 第二次,所有节点直到“l”存在;然后为“ing”创建所有节点。
现在,如果我们添加“troubles”,则在“e”后面的“s”将创建另一个节点。
fullWord
变量告诉我们这里是否有潜在的完全匹配;这是搜索函数:
public final class Trie
{
private final int nrWords;
private final int maxLength;
private final TrieNode node;
public int search(final String needle)
{
return node.search(needle);
}
}
在TrieNode
中,我们有:
public final class TrieNode
{
private final boolean fullWord;
private final char[] nextChars;
private final TrieNode[] nextNodes;
public int search(final String needle)
{
return doSearch(CharBuffer.wrap(needle), fullWord ? 0 : -1, 0);
}
private int doSearch(final CharBuffer buffer, final int matchedLength,
final int currentLength)
{
final int nextLength = fullWord ? currentLength : matchedLength;
if (!buffer.hasRemaining())
return nextLength;
final int index = Arrays.binarySearch(nextChars, buffer.get());
return index < 0
? nextLength
: nextNodes[index].doSearch(buffer, nextLength, currentLength + 1);
}
}
请注意,在第一次调用
doSearch()
时,“nextLength”参数传递了-1。
假设我们有一个包含上述三个单词的trie树,以下是搜索“tr”(失败)的调用序列:
- doSearch("tr", -1, 0) (节点为根);
- doSearch("tr", -1, 1) (节点为't');
- doSearch("tr", -1, 2) (节点为'r');
- 没有下一个字符:返回nextLength;nextLength为-1,没有匹配项。
现在,如果我们有“troubles”:
- doSearch("troubles", -1, 0) (节点为根);
- doSearch("troubles", -1, 1) (节点为't');
- doSearch("troubles", -1, 2) (节点为'r');
- doSearch("troubles", -1, 3) (节点为'o');
- doSearch("troubles", -1, 4) (节点为'u');
- doSearch("troubles", -1, 5) (节点为'b');
- doSearch("troubles", -1, 6) (节点为'l');
- doSearch("troubles", -1, 7) (节点为'e');
- doSearch("troubles", 7, 8) (fullword为true!节点为's');
- 没有下一个字符:返回nextLength,即8;我们有一个匹配项。