| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Программное обеспечение под *NIX системы > помогите найти средства работы с Suffix tree |
| Автор: lemax 29.2.2008, 14:53 |
| Нужен механизм быстрого поиска подстроки. Я хотел бы воспользоваться структурой данных: Suffix tree. Ни как не могу найти способа, что бы одна программа построила Суффиксное Дерево и сохранило куда нибудь, а другие программы этим деревом пользовались. Спасибо. |
| Автор: Goganchic 29.2.2008, 16:50 |
| lemax, а ты точно не ошибся разделом? Или ты имеешь ввиду как сделать максимально быстрое взаимодействие программ? Если да - то это IPC. |
| Автор: lemax 29.2.2008, 17:37 | ||||
Просто хотел найти что то вроде:
ну а потом в любые моменты и в неограниченном количестве:
которые возвращают "есть" или "нет" такой подстроки. Написать самому (изобретать велосипед) нет времени и опыта. На счет опыта, не получается дэбагер запустить на Eclipse (но это уже другая история) |
| Автор: nickless 29.2.2008, 17:41 |
| Ссылки на библиотеки итд из http://forum.vingrad.ru/forum/computer-books-literature.html не подходят? |
| Автор: Lomir 2.3.2008, 14:41 |
| Невижу смысла записывать дерево в фаил (если строка не 100mb или больше). Суффиксное дерево строиться за О(n) от длинны строки. В из файла его загружать в любом случае надо будет. Поэтому лучше строить дерево на лету. Если, запросов подстроки не будет очень много, тогда могу посоветовать использовать КМП, общее время работы О(n+m) с гораздо меньшей константой. Если изходная стока огромна (дерево не влазит в оперативку), тогда к сожелении незнаю что посоветовать. |
| Автор: lemax 4.3.2008, 13:30 |
| Дерево на 20 мега опиративной памяти получилось. На основе проекта http://yeda.cs.technion.ac.il/~yona/suffix_tree/, сделал что-то типа Клиент-Сервер. Сервер загружает слова и строит дерево. Каждый подключившийся Клиент дает запрос к Серверу и получает ответ. Сервер хранит дерево в своей памяти. |