.NET Разработчик(@NetDeveloperDiary). День 1511. #Алгоритмы Использование Префиксного Дерева для Текстового Поиска Сегодня рассмотрим алго

День 1511. #Алгоритмы Использование Префиксного Дерева для Текстового Поиска Сегодня рассмотрим алгоритм префиксного дерева (Trie) и способы его использования в C# для эффективного поиска текстовых шаблонов. Trie (произносится «трай») — это древовидная структура данных, которая часто используется для быстрого хранения и извлечения строк. Она состоит из узлов, представляющих отдельные символы в строке. Корневой узел – пустая строка, а каждый дочерний представляет символ, который может следовать за строкой, представленной его родителем. Преимущества 1) Быстрое определение, присутствует ли данная строка в наборе строк. Строка представлена в виде уникального пути в дереве, что позволяет легко определить её наличие или отсутствие. 2) Способность быстро находить все строки с заданным префиксом. Все строки с общим префиксом имеют один и тот же путь в дереве до конечной точки префикса. Рассмотрим слова «cat» и «car». Сохранение: Корневой узел пустой. Первый символ в обеих строках — «c», поэтому добавляем дочерний узел. Аналогично добавляем дочерний узел для «а». Наконец, добавляем два дочерних узла из узла «a» для представления символов «t» и «r». Поиск: Теперь можно легко определить, присутствует ли в дереве, например, строка «cab». А подсчёт всех строк с префиксом «ca» — это просто количество дочерних узлов для узла «c» > «a». Реализуем структуру данных Trie. Это набор узлов, поэтому начнём с создания класса TrieNode:

public class TrieNode
{
  public bool IsWord { get; set; }
  public Dictionary<char, TrieNode> 
   Children { get; } = new();
}

TrieNode хранит флаг, указывающий, представляет ли узел конец слова в свойстве IsWord, а также словарь дочерних узлов. Теперь создадим класс Trie, который хранит ссылку на корневой узел и предоставляет методы для вставки и поиска слов:

public class Trie
{
  private readonly TrieNode _root = new();

  public void AddWord(string word)
  {
    var node = _root;
    foreach (char c in word)
    {
      if (!node.Children.ContainsKey(c))
        node.Children[c] = new();
      node = node.Children[c];
    }
    node.IsWord = true;
  }

  public bool Search(string word)
  {
    var node = _root;
    foreach (char c in word)
    {
      if (!node.Children.ContainsKey(c))
        return false;
      node = node.Children[c];
    }
    return node.IsWord;
  }
}

Чтобы вставить слово, мы начинаем с корневого узла. Для каждого символа проверяем, есть ли дочерний узел, представляющий этот символ. Если нет, создаём новый и добавляем его в словарь. Затем переходим к дочернему узлу и повторяем процесс для следующего символа. Достигнув конца слова, устанавливаем для свойства IsWord последнего узла значение true. Чтобы найти слово, начинаем с корневого узла и перебираем каждый символ в слове. Проверяем, есть ли дочерний узел, представляющий этот символ. Если нет, слова нет в дереве. Если достигаем конца слова и свойство IsWord на последнем узле - true, значит слово находится в дереве. Использование

var trie = new Trie();
var text = "The quick brown fox jumps over the lazy dog";
foreach (var word in text.Split(' '))
  trie.AddWord(word);

Console.WriteLine(trie.Search("quick"));

Создаём экземпляр Trie и добавляем каждое слово предложения в него с помощью метода AddWord(). Далее с помощью метода Search() проверяем существование слова. Источник: https://code-maze.com/csharp-using-trie-class-for-efficient-text-pattern-searching/