Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Быстрый поиск в словаре |
Автор: volatile 15.2.2011, 00:54 |
Нужен алгоритм поиска в словаре наиболее длинного слова из потока. пример, есть словарь: "AB" "ABBA" "ABCD" "ABCDERTY" "ABRAKADABRA" и т.д. и есть поток: "ABRAKADABRASDFGBCAASDR.." и т.д. в данном случае подходят два слова, "AB", "ABRAKADABRA". Нужно чтобы находилось самое длинное, т.е "ABRAKADABRA" Сделал пока тупо так: Загнал словарь в map<>, и ищу в цикле сначала самое длинное слово. Если не находится, уменьшаю длину на 1 и снова ищу, и т.д до нулевой длины. Но проблема в том что самое длинное слово в словаре может быть очень длинным, поэтому таким алгоритмом я не очень доволен. Нужен максимально быстрый алгоритм. Добавлено через 10 минут и 25 секунд Ну можно конечно разбить словарь на много частей. 1. словарь однобуквенный слов 2. словарь 2-буквенных слов -- и т.д. и искать сначала в самом многобуквенном, и дальше вниз. Но в принципе это тоже самое, просто небольшая оптимизация. Меня интересует, может быть есть более быстрый и простой алгоритм. Посоветуйте что-нибудь. |
Автор: ksili 15.2.2011, 05:46 |
А нельзя в map слова сразу загнать так, чтобы они были отсортированы по-убыванию? В смысле, чтобы самое длинное слово находилось гарантировано первым, и не нужно было бы гонять цикл. |
Автор: 1000000dollars 15.2.2011, 08:45 |
Можно. Словарь делаешь деревом: в вершинах маркеры концов строк, рёбра - буквы. Слово начинается с корня и при добавлении проходится уже существующий путь и достраиваются ветки, а при поиске идём по дереву, пока есть соответствие потоку. Если остановились в вершине с маркером - значит искомое слово - путь от корня до текущей вершины, если по дереву путь прервался - поднимаемся по дереву до маркера конца слова. |
Автор: maxim1000 15.2.2011, 09:43 |
есть такая штука std::lower_bound она ищет не точное вхождение элемента, а (в каком-то смысле) место для его вставки запустив std::lower_bound на исходном длинном слове можно получить место где слова будут на него похожи, посмотрев на слова перед и после этого места можно выбрать наиболее подходящее слово... |
Автор: Pavia 15.2.2011, 13:45 |
volatile, Можно детерминированный автомат построить. Будет O(n) вопрос только в том хватит ли вам памяти? Словарь большой? |
Автор: maxim1000 16.2.2011, 00:47 | ||
да... то, что между ними может быть много, я не учёл... зато вспомнил интересную структуру - Trie, по идее, должно подойти, скорость поиска каждого слова будет пропорциональна его длине (если я опять чего-то не напутал ![]() http://en.wikipedia.org/wiki/Trie Добавлено через 1 минуту и 55 секунд кстати, похоже, что 1000000dollars именно такую структуру и описал |
Автор: volatile 16.2.2011, 01:55 |
maxim1000, ok. Спасибо. Идея с деревом меня заинтересовала. Но поскольку я достаточно туп, все же просьба к 1000000dollars, изобразить хотябы для простейшего случая (словарь из 2-ух слов: "AB" и "ABRAKADABRA".) Как это будет выглядеть? просто на примере мне легче понять. И еще, может не совсем относящееся к алгоритмам, но все-же. Если смотреть в сторону С/С++, то на чем такое дерево можно приблизительно организовать.(в какую сторону смотреть?) есть ли что-то готовое, или писать с нуля? |
Автор: 1000000dollars 16.2.2011, 09:31 |
volatile, maxim1000 правильно сказал - я описал http://ru.wikipedia.org/wiki/Префиксное_дерево. По моей ссылке - краткое описание на русском, по ссылке maxim1000 более детально на английском, и там же картинка. Для твоего случая дерево получается скучным, поэтому я добавил ещё одно слово (ABSINTHE) в словарь. Про С++ ничего сказать не могу - я такую штуку делал на delphi. Там всё писал сам по ряду проектозависимых причин. |
Автор: volatile 16.2.2011, 23:14 |
Ребята, всем большое спасибо. 1000000dollars, вам особенно! Извиняюсь, что напряг с рисунком. Но, кажется, до меня дошло наконец. Как я понял, этот алгоритм особенно хорош, при преобладании коротких слов. В общем это вроде, как раз, мой случай. Буду думать дальше. Большое СПАСИБО, еще раз!!! ![]() |
Автор: 1000000dollars 17.2.2011, 08:41 |
Пожалуйста. volatile, у меня в такой структуре хранится словарь обычных человеческих слов, поэтому дерево ветвится не так уж и сильно, и потому памяти требует не так уж и много, а вот если бы мне надо было хранить MD5, например, я бы ещё подумал... Но задача поиска в любом случае решается за линейное время. |
Автор: bvn13 12.4.2011, 21:39 |
Предлагаю использовать алгоритм матрицы: http://itman.narod.ru/articles/ps_pdf_txt/findstr_ru.zip |