| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > структура с быстрым доступом к строкам |
| Автор: trupca 12.10.2009, 12:16 |
| можно перефразировать топик как "структура с быстрым доступом к содержащимся в ней строкам"? передо мной стала проблема - нужно разобрать входящий поток данных (данные идут строками) на наличие в ней совпадений с некоторыми данными словами (включая и их словоформы). мне представилось что решение данной задачи - это организация некой структуры данных, которая представляла бы из себя аналог дерева в вершине которого, допустим, находится буква "д", а ноды второго и последующих уровней были пусты или содержали буквы являющиеся вторыми (третьими, четвёртыми и т.д.) знаками в искомом слове. пример для наглядности: о м а д е н ь в котором вершиной "дерева" является буква "д", ноды второго уровня это "о" и "е" и т.д. смысл же данной конструкции будет более понятен на примере её использования: допустим у нас есть строка "добрый день!" и нам нужно найти в ней вхождения слова "день". алгоритм для которого придумана эта структура будет посимвольно читать строку и сравнивать каждый прочитанный элемент с вершиной дерева и если будет найдено совпадение, то будет проверяться наличие на втором уровне нодов второго символа после совпадения (после буквы "д"). то бишь, программа читая строку, обнаружит первое совпадение в первом символе, затем во втором, но не найдя на третьем уровне нодов буквы "б", перейдёт к поиску совпадений с вершиной дерева, пока не наткнётся на совпадение "день" и "день" после чего сообщит что было найдено совпадение, {блок операторов, ...} и не продолжит делать тоже самое пока не встретит конец строки. ну и теперь вопрос. xD у этого есть какое-то конкретное название? просто я не находил ничего подобного в литературе и мне не от чего оттолкнуться в поисках реализации подобной структуры, конечно, если она существует в природе. ну и хотя бы примерных оценок производительности этих структуры и алгоритма. есть ли более простые (но в достаточной мере эффективные) способы эту проблему? конечно подобные изыскания очень интересны, но всё таки надо двигать проект. |
| Автор: Void 12.10.2009, 12:29 |
| http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA? |
| Автор: AVA12 12.10.2009, 16:51 |
| Такие деревья обычно называют http://en.wikipedia.org/wiki/Trie (по-русски - "бор" или "префиксное дерево"). Сложность поиска всех ключей - линейная от длины текста и максимальной длины ключа. Правда, за счет большого расхода памяти. Можно свести расход памяти к минимуму за счет усложнения алгоритма и некоторого увеличения времени работы, пример - http://en.wikipedia.org/wiki/Radix_tree. |
| Автор: Antiquar 12.10.2009, 22:12 |
| Понятный и известный алгоритм поиска по дереву. При правильной реализации скорость будет на уровне других алгоритмов, если конечно количество искомых слов (словоформ) не достигает десятков тысяч. Я же, когда занимался подобным, для ускорения работы делал еще первичное дерево - числовое. И в его узлы вносил преобразованные в число первые 4 символа искомых слов. Дало увеличение скорости на 20-30%. Но недостаток понятный - нельзя было задать слово для поиска менее 4 символов. |
| Автор: trupca 16.10.2009, 14:33 |
| огромное спасибо. поиск по действующим названиям алгоритма и структуры данных срезу же дал результат. ps как всё было бы проще если бы каждый автор не придумывал собственное название для данной структуры... |