Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Быстрый поиск в словаре, Нужен алгоритм 
V
    Опции темы
volatile
Дата 15.2.2011, 00:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Нужен алгоритм поиска в словаре наиболее длинного слова из потока.

пример, есть словарь:
"AB"
"ABBA"
"ABCD"
"ABCDERTY"
"ABRAKADABRA"
и т.д.

и есть поток:
"ABRAKADABRASDFGBCAASDR.." и т.д.

в данном случае подходят два слова, "AB", "ABRAKADABRA". Нужно чтобы находилось самое длинное, т.е "ABRAKADABRA"

Сделал пока тупо так:
Загнал словарь в map<>, и ищу в цикле сначала самое длинное слово.
Если не находится, уменьшаю длину на 1 и снова ищу, и т.д до нулевой длины.

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

Добавлено через 10 минут и 25 секунд
Ну можно конечно разбить словарь на много частей.
1. словарь однобуквенный слов
2. словарь 2-буквенных слов
-- и т.д.
и искать сначала в самом многобуквенном, и дальше вниз.

Но в принципе это тоже самое, просто небольшая оптимизация.
Меня интересует, может быть есть более быстрый и простой алгоритм.
Посоветуйте что-нибудь.
PM MAIL   Вверх
ksili
Дата 15.2.2011, 05:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 2
Всего: 17



А нельзя в map слова сразу загнать так, чтобы они были отсортированы по-убыванию? В смысле, чтобы самое длинное слово находилось гарантировано первым, и не нужно было бы гонять цикл.


--------------------
Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)
PM MAIL   Вверх
1000000dollars
Дата 15.2.2011, 08:45 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: 1
Всего: 8



Можно. Словарь делаешь деревом: в вершинах маркеры концов строк, рёбра - буквы. Слово начинается с корня и при добавлении проходится уже существующий путь и достраиваются ветки, а при поиске идём по дереву, пока есть соответствие потоку. Если остановились в вершине с маркером - значит искомое слово - путь от корня до текущей вершины, если по дереву путь прервался - поднимаемся по дереву до маркера конца слова.
PM MAIL   Вверх
maxim1000
Дата 15.2.2011, 09:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110



есть такая штука std::lower_bound
она ищет не точное вхождение элемента, а (в каком-то смысле) место для его вставки
запустив std::lower_bound на исходном длинном слове можно получить место где слова будут на него похожи, посмотрев на слова перед и после этого места можно выбрать наиболее подходящее слово...


--------------------
qqq
PM WWW   Вверх
Pavia
Дата 15.2.2011, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12



volatile
Можно детерминированный автомат построить. Будет O(n) вопрос только в том хватит ли вам памяти? Словарь большой?
PM MAIL   Вверх
volatile
Дата 15.2.2011, 23:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Во-первых всем большое спасибо за ответы!

Цитата(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

еще раз хочу сказать, что ваши идеи мне понятны, но я не знаю способа отсортировать словарь, таки образом, чтобы подходящие слова были рядом. Если можете приведите способ такой сортировки. 
PM MAIL   Вверх
maxim1000
Дата 16.2.2011, 00:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110



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

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

зато вспомнил интересную структуру - Trie, по идее, должно подойти, скорость поиска каждого слова будет пропорциональна его длине (если я опять чего-то не напутал smile )
http://en.wikipedia.org/wiki/Trie

Добавлено через 1 минуту и 55 секунд
кстати, похоже, что 1000000dollars именно такую структуру и описал

Это сообщение отредактировал(а) maxim1000 - 16.2.2011, 00:48


--------------------
qqq
PM WWW   Вверх
volatile
Дата 16.2.2011, 01:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



maxim1000, ok. Спасибо.
Идея с деревом меня заинтересовала.

Но поскольку я достаточно туп, все же просьба к 1000000dollars, изобразить хотябы для простейшего случая
(словарь из 2-ух слов: "AB" и "ABRAKADABRA".) Как это будет выглядеть?
просто на примере мне легче понять.

И еще, может не совсем относящееся к алгоритмам, но все-же. Если смотреть в сторону С/С++, то на чем такое дерево можно приблизительно организовать.(в какую сторону смотреть?)
есть ли что-то готовое, или писать с нуля?


PM MAIL   Вверх
1000000dollars
Дата 16.2.2011, 09:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: 1
Всего: 8



volatilemaxim1000 правильно сказал - я описал Префиксное дерево (Trie).

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

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

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

Это сообщение отредактировал(а) 1000000dollars - 16.2.2011, 09:33

Присоединённый файл ( Кол-во скачиваний: 18 )
Присоединённый файл  Tree.png 35,86 Kb
PM MAIL   Вверх
volatile
Дата 16.2.2011, 23:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



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

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


PM MAIL   Вверх
1000000dollars
Дата 17.2.2011, 08:41 (ссылка)    | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: 1
Всего: 8



Пожалуйста.

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

Это сообщение отредактировал(а) 1000000dollars - 17.2.2011, 08:42
PM MAIL   Вверх
bvn13
Дата 12.4.2011, 21:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 74
Регистрация: 26.5.2009

Репутация: нет
Всего: нет



Предлагаю использовать алгоритм матрицы: Вот тут книжка небольшая (статейка)
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1330 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.