- предисловие
-
теоретические знания
- [что такое дерево](#что такое дерево)
- [Попробовать плюсы и минусы] (#попробовать плюсы и минусы)
- [Сценарии Trie](Сценарии применения #trie)
- Реализация кодирования
- Справочная статья
- свяжитесь со мной
предисловие
В процессе понимания пользовательских запросов существует множество процессов, которые необходимо «идентифицировать» с помощью словарей. Тем временем использование структуры данных дерева Trie неизбежно.
Итак, сегодня давайте подробно изучим теоретические знания, связанные с деревом Trie, и начнем программировать.
теоретические знания
Что такое Трие-дерево
Приведенные ниже определения взяты из Википедии.
В компьютерных науках дерево, также известное как дерево префиксов или дерево словарей, представляет собой упорядоченное дерево, используемое для хранения ассоциативных массивов, ключами которых обычно являются строки. В отличие от бинарного дерева поиска, ключ не хранится непосредственно в узле, а определяется положением узла в дереве. Все потомки узла имеют одинаковый префикс, представляющий собой строку, соответствующую этому узлу, а корневой узел соответствует пустой строке. Как правило, не все узлы имеют соответствующие значения, только ключи, соответствующие листовым узлам, и некоторые внутренние узлы имеют соответствующие значения.
Простая структура TRIE, как показано ниже:
Из приведенной выше диаграммы мы можем найти некоторые особенности Trie.
- Корневой узел не содержит символов, а каждый дочерний узел, кроме корневого узла, содержит один символ.
- От корневого узла к определенному узлу соединяются проходящие по пути символы, представляющие собой строку, соответствующую узлу.
- Общий префикс каждого слова хранится как символьный узел.
Обычно при реализации в структуре узла устанавливается флаг, чтобы отметить, сформировано ли слово (ключевое слово) в узле, или для хранения каких-то других связанных значений.
Можно видеть, что ключевые слова дерева Trie обычно представляют собой строки, и дерево Trie сохраняет каждое ключевое слово в пути, а не в узле. Кроме того, два ключевых слова с общим префиксом имеют один и тот же путь в префиксной части дерева Trie, поэтому дерево Trie также называют деревом префиксов (Prefix Tree).
Дочерние узлы каждого узла дерева Trie представляют собой набор отдельных символов, и мы можем легко отсортировать все строки в лексикографическом порядке. Вам нужно только вывести лексикографически предварительный порядок и пройти все дочерние узлы в лексикографическом порядке при выводе. Поэтому дерево Trie также называют деревом словарей.
Преимущества и недостатки Trie
Основная идея дерева Trie состоит в том, чтобы использовать пространство вместо времени и использовать общий префикс строк для сокращения накладных расходов времени запроса для достижения цели повышения эффективности.
Конечно, в случае большого количества данных пространство Trie-дерева может быть не больше, чем пространство хеш-таблицы. Пока пространство, сэкономленное общим префиксом, покрывает дополнительные накладные расходы объекта.
Сила Trie заключается в его временной сложности, а эффективность вставки и запроса очень высока.O(N), где N — длина вставляемой/запрашиваемой строки, независимо от того, сколько элементов хранится в Trie.
Что касается запроса, некоторые люди говорят, что временная сложность хеш-таблицы составляетO(1)Разве это не быстрее? Однако эффективность хеш-поиска обычно зависит от качества хеш-функции, и если плохая хеш-функция вызывает много коллизий, эффективность не обязательно выше, чем у дерева Trie.
И разные ключевые слова в дереве Trie не будут конфликтовать. Он допускает коллизии, подобные хешу, только тогда, когда несколько значений могут быть связаны с одним ключом.
Кроме того, для дерева Trie не требуется хеш-значение, что быстрее для коротких строк. Потому что обычно хеш-значение также должно пройти через строку.
То есть, теоретически, временная сложность дерева Trie стабильна, а временная сложность хеш-таблицы нестабильна, что зависит от качества хеш-функции, а также связано с хранимым набором строк.
С точки зрения промышленных приложений, личная рекомендация: если вам не нужно использовать функцию сопоставления префиксов дерева Trie, вы можете напрямую использовать хеш-таблицу.
Причины следующие:
- Реализация хэш-таблицы чрезвычайно проста, и большинство языков имеют хорошо зарекомендовавшие себя внутренние библиотеки. Легко использовать.
- В большинстве случаев, когда речь идет о хранилище K-V, хэш связан с деревом Trie, особенно с хеш-таблицей в языковой библиотеке, которая была оптимизирована различными большими шишками.
- Дерево Trie должно быть реализовано само по себе, и оно должно пройти различные логические тесты, чтобы обеспечить покрытие, стресс-тестирование и т. д., прежде чем его можно будет использовать, а стоимость слишком высока.
Попробуйте сценарии приложений
Для меня, как для инженера, самое важное в изучении чего-либо — это понимание сценариев его применения.Я пробовал все технологии, которые существуют только в книгах и не имеют зрелых приложений.
При изучении Trie tree я также потратил много времени на то, чтобы найти и записать сценарии его применения, которые перечислены здесь.Если у вас есть другие сценарии применения, вы можете оставить сообщение для обсуждения.
K-V Хранение и извлечение
Это примитивный и простой способ использования устья дерева Trie, где ему нужно конкурировать с хеш-таблицей.
Статистика частотности слов
Мы можем изменить реализацию дерева Trie, чтобы поместить是否在此构成单词Измените флаг на此处构成的单词数量, Чтобы мы могли использовать его для получения общей статистики частоты слов в сценариях поиска.
Конечно, это требование хеш-таблицы также может быть выполнено.
лексикографическая сортировка
Добавьте все наборы для сортировки в дерево Trie один за другим, а затем выполните обход и вывод всех значений в предварительном порядке. При обходе всех дочерних узлов узла вывод может быть лексикографически упорядочен.
совпадение префикса
Например: найти все строки, начинающиеся с ab в наборе строк. Нам просто нужно построить дерево со всеми строками и вывести как
Ключевое слово на пути в начале подойдет.
Сопоставление префикса Trie часто используется для поисковых подсказок. Например, вторая половина функции автоматической ассоциации в различных поисковых системах.
самый длинный общий префиксЧтобы найти самый длинный общий префикс набора строк, вам нужно всего лишь построить набор строк в дереве Trie, а затем пройти от корневого узла до тех пор, пока не будет несколько узлов (то есть произойдет разветвление).
в качестве вспомогательной конструкцииВ качестве вспомогательной структуры для других структур данных, таких как деревья суффиксов, автоматы переменного тока и т. д.
Реализация кодирования
Сначала реализуйте узлы дерева Trie:
package com.huyan.trie;
import java.util.*;
/**
* Created by pfliu on 2019/12/06.
*/
public class TNode {
/**
* 当前节点字符
*/
private char c;
/**
* 当前 节点对应数字
*/
int count = 0;
private TNode[] children;
private static int hash(char c) {
return c;
}
@Override
public String toString() {
return "TNode{" +
"c=" + c +
", count=" + count +
", children=" + Arrays.toString(children) +
'}';
}
TNode(char c) {
this.c = c;
}
/**
* 将 给定字符 添加到给定列表中。
* @param nodes 给定的 node 列表
* @param c 给定字符
* @return 插入后的节点
*/
private static TNode add(final TNode[] nodes, char c) {
int hash = hash(c);
int mask = nodes.length - 1;
for (int i = hash; i < hash + mask + 1; i++) {
int idx = i & mask;
if (nodes[idx] == null) {
TNode node = new TNode(c);
nodes[idx] = node;
return node;
} else if (nodes[idx].c == c) {
return nodes[idx];
}
}
return null;
}
/**
* 将 当前节点 放入到给定的 节点列表中。
* 用于 resize 的时候转移节点列表
* @param nodes 节点列表
* @param node 给定节点
*/
private static void add(final TNode[] nodes, TNode node) {
int hash = hash(node.c);
int len = nodes.length - 1;
for (int i = hash; i < hash + len + 1; i++) {
int idx = i & len;
if (nodes[idx] == null) {
nodes[idx] = node;
return;
} else if (nodes[idx].c == node.c) {
throw new IllegalStateException("Node not expected for " + node.c);
}
}
throw new IllegalStateException("Node not added");
}
/**
* 将 给定字符 插入到当前节点的子节点中。
* @param c 给定字符
* @return 插入后的节点
*/
TNode addChild(char c) {
// 初始化子节点列表
if (children == null) {
children = new TNode[2];
}
// 尝试插入
TNode node = add(children, c);
if (node != null)
return node;
// resize
// 转移节点列表到新的子节点列表中
TNode[] tmp = new TNode[children.length * 2];
for (TNode child : children) {
if (child != null) {
add(tmp, child);
}
}
children = tmp;
return add(children, c);
}
/**
* 查找当前节点的子节点列表中，char 等于给定字符的节点
* @param c 给定 char
* @return 对应的节点
*/
TNode findChild(char c) {
final TNode[] nodes = children;
if (nodes == null) return null;
int hash = hash(c);
int len = nodes.length - 1;
for (int i = hash; i < hash + len + 1; i++) {
int idx = i & len;
TNode node = nodes[idx];
if (node == null) {
return null;
} else if (node.c == c) {
return node;
}
}
return null;
}
}
Затем реализуйте дерево Trie.
package com.huyan.trie;
import java.util.*;
/**
* Created by pfliu on 2019/12/06.
*/
public class Trie {
/**
* 根节点
*/
final private TNode root = new TNode('\0');
/**
* 添加一个词到 Trie
*
* @param word 待添加词
* @param value 对应 value
*/
public void addWord(String word, int value) {
if (word == null || word.length() == 0) return;
TNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
// 当前 char 添加到 trie 中，并拿到当前 char 对应的那个节点
node = node.addChild(c);
}
node.count = value;
}
/**
* 查找 word 对应的 int 值。
*
* @param word 给定 word
* @return 最后一个节点上存储的 int.
*/
public int get(String word) {
TNode node = root;
for (int i = 0; i < word.length(); i++) {
node = node.findChild(word.charAt(i));
if (node == null) {
return 0;
}
}
return node.count;
}
private int get(char[] buffer, int offset, int length) {
TNode node = root;
for (int i = 0; i < length; i++) {
node = node.findChild(buffer[offset + i]);
if (node == null) {
return 0;
}
}
return node.count;
}
/**
* 从给定字符串的 offset 开始。
* 查找最大匹配的第一个 int 值。
*
* @param str 给定字符串
* @param offset 开始查找的偏移量
* @return 第一个匹配的字符串德最后一个节点的 int 值。
*/
public String maxMatch(String str, int offset) {
TNode node = root;
int lastMatchIdx = offset;
for (int i = offset; i < str.length(); i++) {
char c = str.charAt(i);
node = node.findChild(c);
if (node == null) {
break;
} else if (node.count != 0) {
lastMatchIdx = i;
}
}
return lastMatchIdx == offset ? null : str.substring(offset, lastMatchIdx + 1);
}
/**
* 从给定字符串的 offset <b>反向</b>开始。
* 查找最大匹配的第一个 int 值。
*
* @param str 给定字符串
* @param offset 开始查找的偏移量
* @return 第一个匹配的字符串德最后一个节点的 int 值。
*/
public int maxMatchBack(String str, int offset) {
TNode node = root;
int lastMatchIdx = offset;
for (int i = offset; i >= 0; i--) {
char c = str.charAt(i);
node = node.findChild(c);
if (node == null) {
break;
} else if (node.count != 0) {
lastMatchIdx = i;
}
}
return offset - lastMatchIdx + 1;
}
/**
* 从给定字符串的 offset 开始。检查 length 长度。
* 查找最大匹配的第一个 int 值。
*
* @param buffer 给定字符串
* @param offset 开始查找的偏移量
* @return 第一个匹配的字符串德最后一个节点的 int 值。
*/
public int maxMatch(char[] buffer, int offset, int length) {
TNode node = root;
int lastMatchIdx = offset;
for (int i = offset; i < offset + length; i++) {
char c = buffer[i];
node = node.findChild(c);
if (node == null) {
break;
} else if (node.count != 0) {
lastMatchIdx = i;
}
}
return lastMatchIdx - offset + 1;
}
public static void main(String[] args) {
Trie trie = new Trie();
for (String s : Arrays.asList("呼延", "呼延二十")) {
trie.addWord(s, 1);
}
String input = "延十在写文章";
System.out.println(trie.maxMatch(input, 0));
}
}
Код в основном реализует базовые функции Trie, но существует множество прикладных методов для trie, таких как сопоставление префиксов, например, нахождение длины самого длинного совпадающего префикса и т. д. Они не достигаются один за другим.
Справочная статья
woo woo woo.cn blog on.com/yellow new car…
над.
свяжитесь со мной
Наконец, приглашаю вас обратить внимание на мой личный публичный аккаунт [Huyan Shi], я буду время от времени обновлять учебные заметки многих бэкенд-инженеров. Вы также можете связаться со мной напрямую в публичном аккаунте, личном сообщении или электронной почте, Вы должны все знать и все говорить.
ChangeLog
2019-05-19 ЗавершеноВсе вышеизложенное является личными мыслями, если есть какие-либо ошибки, пожалуйста, исправьте их в комментариях.
Добро пожаловать на перепечатку, пожалуйста, подпишите и сохраните исходную ссылку.
Контактный адрес электронной почты: huyanshi2580@gmail.com
Дополнительные заметки об обучении см. в личном блоге или подпишитесь на общедоступную учетную запись WeChat ------>Хуян тен