Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы алгоритмов и структур данныхВ 28-й статье поговорим о классической структуре данных для обработки строк — Trie.
В предыдущих 4 статьях мы представили некоторые алгоритмы теории игр, из которых наиболее широко используемым и наиболее важным является конечная функция SG. Зная это, нам достаточно, чтобы иметь дело с общими проблемами алгоритмов теории игр. Теория игр сама по себе является дисциплиной, которая имеет очень глубокую теоретическую основу, мы только касаемся поверхности, если вам интересно, вы можете изучить ее самостоятельно, и я думаю, что это будет очень полезно.
короткий рассказ
Я читал статью большой коровы раньше, и в статье обсуждалась проблема,Зачем нам изучать алгоритмы, если не для интервью?
Он рассказал свою собственную историю, сказав, что много лет назад, когда мобильный телефон был еще функциональным телефоном Nokia, он разработал адресную книгу для системы Symbian, чтобы найти программное обеспечение для контактов. Функция софта очень проста, то есть хранить контакты, а потом можноПоиск по пиньинь или первой букве пиньиньна соответствующий контакт. Здесь нам нужно разобраться с отображением китайских иероглифов и пиньинь, а это не очень сложная операция, мы должны разобраться с этим с помощью мозговой добавки.
Программное обеспечение готово очень быстро, и после его использования оказывается, что оно также очень полезно. Но вскоре столкнулся с неожиданной проблемой, а именно, когдаПосле слишком большого количества контактов скорость работы программного обеспечения становится очень низкой., то есть карта. Причина карты также очень проста, потому что на этом этапе поиска контактов он ищет, проходя метод поиска. В начале сначала сам придумал какие-то схемы оптимизации и дикие способы, хоть это и можно несколько улучшить, но кардинально проблему решить не может. Позже он был вынужден быть беспомощным. После поиска соответствующей информации он нашел Трие, нашего главного героя сегодня. После использования этого алгоритма проблема была решена мгновенно, даже если бы были сохранены тысячи контактов, она больше не застревала бы. . С тех пор он понял, что алгоритм не является странным трюком, но он действительно полезен.
Мы будем использовать проблему в этой статье в качестве основы для рассмотрения принципа Trie и того, почему он может решить эту проблему.
Введение в Три
Дерево трие имеет несколько названий в китайском переводе,Некоторые из них называются словарными деревьями, некоторые — деревьями префиксов.. Все это возможно, в зависимости от того, что вам нравится. Обычно я называю это деревом Trie, а другая сторона будет называть дерево словаря XD только в том случае, если они его не понимают.
Из названий словарного дерева и префиксного дерева мы можем составить его общий принцип, то естьХранить данные в виде словарей и префиксов. Звучит немного абстрактно, но на самом деле мы можем полностью понять это, взглянув на картинку.
Из рисунка мы видим, чтоТрие-дерево - это дерево с несколькими разветвлениями.. Каждый узел в дереве хранит символ, и символы на нашем пути от корневого узла к узлу соединяются, чтобы стать словами. То есть все слова хранятся в дереве в этой вертикальной форме.
В чем преимущество этого хранилища? Самым большим преимуществом являетсяСлова с одинаковым префиксом могут иметь общий префикс, например, первые два символа двух слов ana, ann и и совпадают с an, поэтому у них есть общая префиксная ссылка. При такой структуре, когда нам нужно узнать, находится ли слово в дереве, нам нужно только пройти от корня дерева,Если соответствующий конечный узел может быть найден, это означает, что слово существует, иначе слово не существует.
Например, если мы хотим найти слово doe, мы сначала ищем символ d в корневом узле. Обнаружил, что d существует, поэтому перешел на d. Затем мы ищем символ o, а также находим символ o под узлом d, переходим к o, ищем символ e и обнаруживаем, что e не существует, значит, слова doe не существует. Но здесь есть проблема. Предположим, у нас есть слово doea, мы все еще можем найти его, когда ищем doe, но слова doe на самом деле не существует. Разве это не неправильно?
Правда, с этим могут быть проблемы, поэтому мыНужно записать в узел, является ли он концом слова. Таким образом, нам нужно не только найти соответствующее слово, но и предотвратить обращение с префиксами других слов как со словами.
Процесс вставки слов очень близок к запросу, и это также процесс обхода дерева, но если мы обнаружим, что узел запроса не существует, он будет создан вручную. После вставки всего слова узел, соответствующий последнему символу, помечается, чтобы указать, что это конец слова.
Простому Trie-дереву нужно только выполнять добавления и запросы.Если задействованы удаления, мыНужно только поддерживать количество слов, проходящих через узел в узлеВот и все. При удалении отмечайте количество узлов, проходящих по пути - 1. Если вы встретите узел с номером 0, вы можете удалить его напрямую.
Код
Если мы просто говорим о том, чтобы не практиковать фальшивую ручку, мы, естественно, должны прийти и попрактиковаться.
Я думаю, что каждый может понять это из описания.Принцип Trie на самом деле очень прост, и его нетрудно реализовать. В интернете есть много версий, многие из которых процессно-ориентированы, я их инкапсулировал.Объектно-ориентированный с PythonРеализована версия. Поняв принцип, вы можете разработать свою собственную версию стиля в соответствии с вашими потребностями Код не очень важен, главное понять принцип.
Я разделил дерево Trie на две части, первая часть — это узлы дерева. Для узлов дерева Trie необходимо обеспечить две функции.Первая функция должна вернуть, является ли текущий узел концом определенной строки.,Вторая функция состоит в том, чтобы найти узел-преемник в соответствии с символом. Нам просто нужно установить тег флага и атрибут dict в классе для хранения последующих элементов.
class Node:
def __init__(self, is_leaf=False):
self.child = {}
self._is_leaf = is_leaf
@property
def is_leaf(self):
return self._is_leaf
@is_leaf.setter
def is_leaf(self, is_leaf):
self._is_leaf = is_leaf
# 加入孩子节点
def put(self, key, value):
self.child[key] = value
@staticmethod
# 将字符转化成数字
# 其实没有必要，因为用到了dict，如果用数组存储孩子的话，需要用它来计算下标
def get_idx_of_str(_str):
if len(_str):
return -1
if ord('a') <= ord(_str) <= ord('z'):
return ord(_str) - ord('a')
else:
return ord(_str) - ord('A') + 26
# 根据字符获取下一个节点
def get_next_node(self, _str):
if len(_str) != 1:
return None
idx = Node.get_idx_of_str(_str)
return self.child.get(idx, None)
def get_node(self, key):
return self.child.get(key, None)
Здесь я инкапсулирую два метода is_leaf со свойством, чтобы их можно было легко использовать, что также является обычной практикой. После того, как у нас есть узел, нам очень удобно разрабатывать класс Trie.Для класса Trie нам нужно реализовать только два метода.Один для вставки строк, другой для запроса строк. Имея класс Node, реализация этих двух методов также очень проста.
class Trie:
def __init__(self):
self.root = Node()
def insert(self, _str):
cur = self.root
# 遍历字符
for c in _str:
# 查找下一个节点
if cur.get_next_node(c) is None:
# 如果节点不存在，自己创建一个新节点并插入
key = Node.get_idx_of_str(c)
cur.put(key, Node())
cur = cur.get_node(key)
# 否则继续往下
else:
cur = cur.get_next_node(c)
cur.is_leaf = True
def query(self, _str):
cur = self.root
# 遍历字符
for c in _str:
# 查询，如果查询不到返回False
if cur.get_next_node(c) is None:
return False
cur = cur.get_next_node(c)
# 返回是否是字符串结尾
return cur.is_leaf
Эти два фрагмента кода должны быть нечитаемыми. Наконец, давайте попробуем использовать их для тестирования:
if __name__ == "__main__":
trie = Trie()
trie.insert('abcda')
trie.insert('abcde')
trie.insert('eecdab')
trie.insert('mout')
trie.insert('ymm')
print(trie.query('abcda'))
print(trie.query('mout'))
print(trie.query('ym'))
Выходные результаты согласуются с нашими ожиданиями, что указывает на то, что высокая вероятность верна.
Суммировать
В дереве Trie мы храним один и тот же префикс строки в одной и той же ссылке,Сэкономьте много места. А при запросе слов мы проходим по дереву Trie, и нам нужно только время длины слова, чтобы получить результаты. И мы можем хранить некоторую другую необходимую нам информацию в классе Node, чтобы Trie был преобразован в dict со строкой в качестве ключа.
Деревья Trie также широко используются в области машинного обучения, особеннообработка естественного языка. Он может реализовать функции быстрой сегментации слов, статистики частотности слов, нечеткого сопоставления и других функций текста. И есть много расширений дерева Trie, таких как дерево Trie с двойным массивом, которое сжимает пространство данных, и автомат AC и т. Д.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
В этой статье используетсяmdniceнабор текста