|
|
|
volatile |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
Нужен алгоритм поиска в словаре наиболее длинного слова из потока.
пример, есть словарь: "AB" "ABBA" "ABCD" "ABCDERTY" "ABRAKADABRA" и т.д. и есть поток: "ABRAKADABRASDFGBCAASDR.." и т.д. в данном случае подходят два слова, "AB", "ABRAKADABRA". Нужно чтобы находилось самое длинное, т.е "ABRAKADABRA" Сделал пока тупо так: Загнал словарь в map<>, и ищу в цикле сначала самое длинное слово. Если не находится, уменьшаю длину на 1 и снова ищу, и т.д до нулевой длины. Но проблема в том что самое длинное слово в словаре может быть очень длинным, поэтому таким алгоритмом я не очень доволен. Нужен максимально быстрый алгоритм. Добавлено через 10 минут и 25 секунд Ну можно конечно разбить словарь на много частей. 1. словарь однобуквенный слов 2. словарь 2-буквенных слов -- и т.д. и искать сначала в самом многобуквенном, и дальше вниз. Но в принципе это тоже самое, просто небольшая оптимизация. Меня интересует, может быть есть более быстрый и простой алгоритм. Посоветуйте что-нибудь. |
|||
|
||||
ksili |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2069 Регистрация: 3.11.2005 Где: Красноярск Репутация: 2 Всего: 17 |
А нельзя в map слова сразу загнать так, чтобы они были отсортированы по-убыванию? В смысле, чтобы самое длинное слово находилось гарантировано первым, и не нужно было бы гонять цикл.
-------------------- Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с) |
|||
|
||||
1000000dollars |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 231 Регистрация: 6.10.2007 Репутация: 1 Всего: 8 |
Можно. Словарь делаешь деревом: в вершинах маркеры концов строк, рёбра - буквы. Слово начинается с корня и при добавлении проходится уже существующий путь и достраиваются ветки, а при поиске идём по дереву, пока есть соответствие потоку. Если остановились в вершине с маркером - значит искомое слово - путь от корня до текущей вершины, если по дереву путь прервался - поднимаемся по дереву до маркера конца слова.
|
|||
|
||||
maxim1000 |
|
|||
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
есть такая штука std::lower_bound
она ищет не точное вхождение элемента, а (в каком-то смысле) место для его вставки запустив std::lower_bound на исходном длинном слове можно получить место где слова будут на него похожи, посмотрев на слова перед и после этого места можно выбрать наиболее подходящее слово... -------------------- qqq |
|||
|
||||
Pavia |
|
|||
Опытный Профиль Группа: Участник Сообщений: 418 Регистрация: 6.12.2008 Репутация: 11 Всего: 12 |
volatile,
Можно детерминированный автомат построить. Будет O(n) вопрос только в том хватит ли вам памяти? Словарь большой? |
|||
|
||||
volatile |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
Во-первых всем большое спасибо за ответы!
Мне это первое что захотелось сделать, но отсортировать так нельзя. map должен быть отсортирован по алфавиту, иначе бинарный поиск в нем не будет работать. lower_bound это нижняя граница. map отсортирован по алфавиту. Я специально привел пример, где 2 подходящих слова, а между ними может быть очень много не подходящих. Так что lower_bound здесь просто не имеет смысла. Вот здесь я честно говоря не понял. Не могли бы вы нарисовать это дерево на моем примере.
Да словарь вообще-то большой. Но, допустим, вот мой пример это все что есть. как это будет выглядеть примерно? Добавлено через 6 минут и 51 секунду to ksili, maxim1000, еще раз хочу сказать, что ваши идеи мне понятны, но я не знаю способа отсортировать словарь, таки образом, чтобы подходящие слова были рядом. Если можете приведите способ такой сортировки. |
|||
|
||||
maxim1000 |
|
|||
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
да... то, что между ними может быть много, я не учёл... зато вспомнил интересную структуру - Trie, по идее, должно подойти, скорость поиска каждого слова будет пропорциональна его длине (если я опять чего-то не напутал ) http://en.wikipedia.org/wiki/Trie Добавлено через 1 минуту и 55 секунд кстати, похоже, что 1000000dollars именно такую структуру и описал Это сообщение отредактировал(а) maxim1000 - 16.2.2011, 00:48 -------------------- qqq |
|||
|
||||
volatile |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
maxim1000, ok. Спасибо.
Идея с деревом меня заинтересовала. Но поскольку я достаточно туп, все же просьба к 1000000dollars, изобразить хотябы для простейшего случая (словарь из 2-ух слов: "AB" и "ABRAKADABRA".) Как это будет выглядеть? просто на примере мне легче понять. И еще, может не совсем относящееся к алгоритмам, но все-же. Если смотреть в сторону С/С++, то на чем такое дерево можно приблизительно организовать.(в какую сторону смотреть?) есть ли что-то готовое, или писать с нуля? |
|||
|
||||
1000000dollars |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 231 Регистрация: 6.10.2007 Репутация: 1 Всего: 8 |
volatile, maxim1000 правильно сказал - я описал Префиксное дерево (Trie).
По моей ссылке - краткое описание на русском, по ссылке maxim1000 более детально на английском, и там же картинка. Для твоего случая дерево получается скучным, поэтому я добавил ещё одно слово (ABSINTHE) в словарь. Про С++ ничего сказать не могу - я такую штуку делал на delphi. Там всё писал сам по ряду проектозависимых причин. Это сообщение отредактировал(а) 1000000dollars - 16.2.2011, 09:33 Присоединённый файл ( Кол-во скачиваний: 18 ) Tree.png 35,86 Kb |
|||
|
||||
volatile |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
Ребята, всем большое спасибо.
1000000dollars, вам особенно! Извиняюсь, что напряг с рисунком. Но, кажется, до меня дошло наконец. Как я понял, этот алгоритм особенно хорош, при преобладании коротких слов. В общем это вроде, как раз, мой случай. Буду думать дальше. Большое СПАСИБО, еще раз!!! |
|||
|
||||
1000000dollars |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 231 Регистрация: 6.10.2007 Репутация: 1 Всего: 8 |
Пожалуйста.
volatile, у меня в такой структуре хранится словарь обычных человеческих слов, поэтому дерево ветвится не так уж и сильно, и потому памяти требует не так уж и много, а вот если бы мне надо было хранить MD5, например, я бы ещё подумал... Но задача поиска в любом случае решается за линейное время. Это сообщение отредактировал(а) 1000000dollars - 17.2.2011, 08:42 |
|||
|
||||
bvn13 |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 74 Регистрация: 26.5.2009 Репутация: нет Всего: нет |
Предлагаю использовать алгоритм матрицы: Вот тут книжка небольшая (статейка)
|
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |