Как решить данную задачу при помощи префиксного дерева?

C# Алгоритмы

1 ответ

Задача:
Дан текст. Определить число фрагментов слов, в которых буквы идут по алфавиту.

Тип дерева:
Префиксное дерево

— Такую лабораторную мне дали в университете. Я изучил тему префиксных деревьев и мне не очень ясно, как они могут быть применимы здесь. Как я понял, префиксное дерево просто делает из каждой буквы узел, а также хранит в нём информацию о том, является ли этот узел конечным. То есть само устройство дерева не подразумевает какой-то быстрый подход к решению конкретно этой задачи. Можно конечно просто засунуть все слова из текста в это дерева и каждому узлу присвоить char code, но тогда в чём смысл привлекать к этой задаче деревья, если это можно быстро сделать и без них?

Действительно ли можно как-то это запрограммировать при помощи префиксных деревьев или же тут нужно использовать какое-то другое дерево?

Дополнительное ТЗ:
Составить программу для поиска в линейном (одномерном или многомерном) массиве данных, представленном в виде дерева. В работе использовать следующие виды поиска:
• последовательный;
• бинарный.
Создать дерево (деревья (массив указателей на корни деревьев в случае с многомерной задачей)) поиска (в соответствии с индивидуальным заданием) и заполнить дерево данными из линейного массива данных.
Осуществить поиск данных по дереву. Провести вывод на экран (или файл, по выбору) следующих данных:
• исходного массива данных (матрица или текст в зависимости от варианта);
• значений дерева разными способами (прямой, обратный, центральный обход);
• результатов последовательного и бинарного поиска.
В случае невозможности (из условий индивидуального задания) поиска бинарным методом, провести поиск бинарным методом одной буквы (цифры). Придумать тестовые примеры, для которых были бы эффективными каждый из методов.

Дополнительно:

Да, действительно, данную задачу можно решить не используя преффексные деревья.
Возможно, вам просто нужно показать умение реализовать и использовать данную структуру данных

так и не понял, что требуется. Что такое "фрагменты слов"?

примеров бы накидать..

Alexandroppolus, честно, это вся информация, но я так полагаю, что условно в тексте «abracadabra lorem ipsum» такими фрагментами будут abr ac ad abr lor ipsu, либо же abr lor ipsu. В целом я считаю что могу себе позволить толковать это как угодно, потом всегда можно будет сослаться на неточность формулировки, препод у нас договороспособный, так что проблем вызвать не должно.

Но я всё же склоняюсь к первому варианту.

Dmitriy Grape, по Вашему примеру, я бы рассматривал "abr" как 3 фрагмента: "ab", "br" ,"abr".

Ответы:

Конечно, на эту задачу можно натянуть префиксные деревья (это же вы бор/trie имеете ввиду, да?). Но тут какая-то растянутая сова получается.

Например, можно, действительно, все слова сложить в trie, а потом его обойти. Вам нужно будет в рекурсивном обходе поддерживать количество последних ребер, которые шли по алфавиту. Еще в каждой вершине сразу хранить, сколько раз через нее проходят добавленные строки. Тогда в каждой вершине прибавляйте к ответу произведение двух счетчиков. При рекурсивном вызове или увеличивайте счетчик последних упорядоченных ребер, если следующий символ больше символа к отцу, или передавайте 1.

Но это нисколько не эффективнее наивного итеративного подхода, где вы это же максимальное количество упорядоченных букв поддерживаете идя по строке слева направо, сбрасывая в 0 на пробелах.

Да, всё верно, именно Trie. Спасибо за ответ, придётся как-то кодить этот ужас.

Нужно решить такую задачу?

Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.

Заказать помощь

Лучший ответ

Никита Орлов Ответ

Префиксное дерево, также известное как бор, является структурой данных, которая часто используется для эффективного хранения и поиска строк. Оно состоит из узлов, каждый из которых содержит символ строки, а также ссылки на дочерние узлы.

Для решения задачи при помощи префиксного дерева, мы можем использовать его для хранения всех строк, которые мы хотим проверить на наличие определенного префикса. Например, если у нас есть список слов ["apple", "application", "banana", "orange"], и мы хотим найти все слова, начинающиеся с "app", мы можем построить префиксное дерево для этих слов.

Для этого нам сначала нужно построить дерево, добавив каждое слово по одной букве. Затем мы можем пройти по дереву, начиная с корня, и искать все пути, которые соответствуют префиксу "app". Когда мы достигаем конца префикса, мы можем сохранить все слова, которые начинаются с этого префикса.

Пример реализации префиксного дерева на языке PHP:

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
}
 
class Trie {
    private $root;
 
    public function __construct() {
        $this-&gt;root = new TrieNode();
    }
 
    public function insert($word) {
        $node = $this-&gt;root;
        for ($i = 0; $i children[$char])) {
                $node-&gt;children[$char] = new TrieNode();
            }
            $node = $node-&gt;children[$char];
        }
        $node-&gt;isEndOfWord = true;
    }
 
    public function searchPrefix($prefix) {
        $node = $this-&gt;root;
        for ($i = 0; $i children[$char])) {
                return [];
            }
            $node = $node-&gt;children[$char];
        }
        return $this-&gt;getAllWordsFromNode($node, $prefix);
    }
 
    private function getAllWordsFromNode($node, $prefix) {
        $result = [];
        if ($node-&gt;isEndOfWord) {
            $result[] = $prefix;
        }
        foreach ($node-&gt;children as $char =&gt; $childNode) {
            $result = array_merge($result, $this-&gt;getAllWordsFromNode($childNode, $prefix . $char));
        }
        return $result;
    }
}
 
$trie = new Trie();
$words = ["apple", "application", "banana", "orange"];
foreach ($words as $word) {
    $trie-&gt;insert($word);
}
 
$prefix = "app";
$result = $trie-&gt;searchPrefix($prefix);
print_r($result);

class TrieNode { public $children = []; public $isEndOfWord = false; } class Trie { private $root; public function __construct() { $this->root = new TrieNode(); } public function insert($word) { $node = $this->root; for ($i = 0; $i children[$char])) { $node->children[$char] = new TrieNode(); } $node = $node->children[$char]; } $node->isEndOfWord = true; } public function searchPrefix($prefix) { $node = $this->root; for ($i = 0; $i children[$char])) { return []; } $node = $node->children[$char]; } return $this->getAllWordsFromNode($node, $prefix); } private function getAllWordsFromNode($node, $prefix) { $result = []; if ($node->isEndOfWord) { $result[] = $prefix; } foreach ($node->children as $char => $childNode) { $result = array_merge($result, $this->getAllWordsFromNode($childNode, $prefix . $char)); } return $result; } } $trie = new Trie(); $words = ["apple", "application", "banana", "orange"]; foreach ($words as $word) { $trie->insert($word); } $prefix = "app"; $result = $trie->searchPrefix($prefix); print_r($result);

В этом примере мы создаем класс Trie, который представляет префиксное дерево, и используем его для поиска всех слов, начинающихся с определенного префикса. Мы добавляем все слова из массива $words в дерево и затем вызываем метод searchPrefix с префиксом "app", чтобы найти все слова, начинающиеся с этого префикса.

Таким образом, префиксное дерево позволяет эффективно решать задачу поиска слов по заданному префиксу, обеспечивая быстрый доступ к нужным данным.

Другие ответы (0)

Пока нет других ответов. Будьте первым, кто поможет автору.

Ответить на вопрос

комментарий Отменить ответ

Вам также может быть интересно

VPN Как правильно настроить vless для Android TV? 0 ответов Pyrogram Как правильно зарегистрировать юзер бота в Telegram? 0 ответов печатные-платы Как заставить запускаться программу M3.exe от компании Hanxing AOI в инспекционной машине на Windows 7 Pro? 0 ответов Telegram Как добиться, чтобы Telegram прислал мне именно смс код, а не через звонок его диктовал? 0 ответов

Как решить данную задачу при помощи префиксного дерева?

Дополнительно:

Ответы:

комментарий Отменить ответ

Вам также может быть интересно

Ежедневно, круглосуточно