Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Быстрый поиск в словаре


Автор: 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) вопрос только в том хватит ли вам памяти? Словарь большой?

Автор: volatile 15.2.2011, 23:32
Во-первых всем большое спасибо за ответы!

Цитата(ksili @  15.2.2011,  05:46 Найти цитируемый пост)
А нельзя в map слова сразу загнать так, чтобы они были отсортированы по-убыванию? В смысле, чтобы самое длинное слово находилось гарантировано первым, и не нужно было бы гонять цикл. 

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

Цитата(maxim1000 @  15.2.2011,  09:43 Найти цитируемый пост)
есть такая штука std::lower_bound

lower_bound это нижняя граница. map отсортирован по алфавиту. Я специально привел пример, где 2 подходящих слова, а между ними может быть очень много не подходящих. Так что lower_bound здесь просто не имеет смысла.

Цитата(1000000dollars @  15.2.2011,  08:45 Найти цитируемый пост)
Можно. Словарь делаешь деревом: в вершинах маркеры концов строк, рёбра - буквы. Слово начинается с корня и при добавлении проходится уже существующий путь и достраиваются ветки, а при поиске идём по дереву, пока есть соответствие потоку. Если остановились в вершине с маркером - значит искомое слово - путь от корня до текущей вершины, если по дереву путь прервался - поднимаемся по дереву до маркера конца слова. 

Вот здесь я честно говоря не понял. Не могли бы вы нарисовать это дерево на моем примере.

Цитата(Pavia @  15.2.2011,  13:45 Найти цитируемый пост)
Можно детерминированный автомат построить. Будет O(n) вопрос только в том хватит ли вам памяти? Словарь большой? 

Да словарь вообще-то большой. Но, допустим, вот мой пример это все что есть. как это будет выглядеть примерно?

Добавлено через 6 минут и 51 секунду
to
ksili
maxim1000

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

Автор: maxim1000 16.2.2011, 00:47
Цитата(volatile @  15.2.2011,  23:32 Найти цитируемый пост)
lower_bound это нижняя граница. map отсортирован по алфавиту. Я специально привел пример, где 2 подходящих слова, а между ними может быть очень много не подходящих. Так что lower_bound здесь просто не имеет смысла.

да... то, что между ними может быть много, я не учёл...

зато вспомнил интересную структуру - Trie, по идее, должно подойти, скорость поиска каждого слова будет пропорциональна его длине (если я опять чего-то не напутал smile )
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
volatilemaxim1000 правильно сказал - я описал http://ru.wikipedia.org/wiki/Префиксное_дерево.

По моей ссылке - краткое описание на русском, по ссылке maxim1000 более детально на английском, и там же картинка.

Для твоего случая дерево получается скучным, поэтому я добавил ещё одно слово (ABSINTHE) в словарь.

Про С++ ничего сказать не могу - я такую штуку делал на delphi. Там всё писал сам по ряду проектозависимых причин.

Автор: volatile 16.2.2011, 23:14
Ребята, всем большое спасибо.
1000000dollars, вам особенно!
Извиняюсь, что напряг с рисунком.  Но, кажется, до меня дошло наконец.
Как я понял, этот алгоритм особенно хорош, при преобладании коротких слов.
В общем это вроде, как раз, мой случай. Буду думать дальше.

Большое СПАСИБО, еще раз!!!  smile 


Автор: 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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)