Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
abortion error
3 / 3 / 0
Регистрация: 19.04.2018
Сообщений: 104
1

Оптимизация алгоритма быстрого поиска

24.03.2019, 07:53. Просмотров 134. Ответов 1

Допустим есть строка: "Съешь ещё этих мягких французских булок, да выпей же чаю",и есть массив готовых строк, к примеру
{ "съе", "ещ", "ъешь","ещё", "мяг,"бу", "було","французских","же","Ё","А","Б","В","Г","Д","Е","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У","Ф","Х","Ц ","Ч","Ш","Щ","Ъ","Ы","Ь","Э","Ю","Я"}
Я хочу собрать из предоставленных в массиве фраз и букв предложение данное вначале. Дело в том что я хочу добиться чтоб программа собирала к примеру слово "булок" не как "бу"+"л"+"о"+"к", а как можно короче, то есть "було"+"к".
Единственный алгоритм который лезит в голову таков:
"с"-> "съе" -- совпадение есть
"с"-> "ещ" -- совпадений нет
"с"-> "ъешь" -- совпадений нет
"с"-> "ещё" -- совпадений нет
...
"с"->"с" -- совпадение есть
...
"ъ"->"съе" -- совпадений нет
"ъ"->"ещ" -- совпадений нет
"ъ"->"ъешь" -- совпадение есть
...
"ъ"->"ъ" -- совпадение есть
...
в итоге оно найдёт совпадения и возьмёт из них то, у которого будет больше всего размер,в моём случае "ъешь"
... кароче алгоритм какой-то муторный и странный. Есть что-то попроще?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2019, 07:53
Ответы с готовыми решениями:

Кто знаком с алгоритмом быстрого поиска
Поиск в массиве Расскажите и если можно код на языке с++ с комметариями Добавлено через 5 минут...

Телефонная книга: подскажите алгоритм быстрого поиска контактов
привет всем! какой самый быстрий алгоритм поиска контактов.и какие вы предлагайте допустим у нас...

Отсортированный хэш-вектор бинарной схожести для быстрого поиска
Есть набор 64-х разрядных чисел, их может быть примерно 20 000 ... 40 000. Нужна какая-то хеш...

Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице
задание таково организовать асоциированную карту строк, с возможностью быстрого поиска по...

Оптимизация алгоритма
#include<iostream> #include<stdlib.h> #include<time.h> #include<iomanip> using namespace std; ...

1
valen10
Параллельный Кот
1260 / 530 / 209
Регистрация: 25.03.2016
Сообщений: 1,186
Завершенные тесты: 1
24.03.2019, 10:38 2
abortion error, не понял логику: почему в первый раз был выбран короткий вариант из двух возможных, а во второй раз - длинный? Полагаю, что принимать оптимальные решения на каждом шаге не получится.

Упростим задачу. Пусть имеется слово булок и фрагменты б у улок бул лок о к. Если выбирать каждый раз самый длинный фрагмент, получится бул+о+к, что несколько хуже, чем б+улок. Но как сделать этот выбор?

Можно попробовать строить слова разной длины, перебирая подходящие фрагменты.

Шаг 0. Изначально есть пустое слово (длины 0). Из него можно получить слова: б[1], бул[3].

Шаг 1. Из имеющегося слова длины 1 аналогичным образом создаем новые слова: б+у[2], б+улок[5].

Шаг 2. Берем слово длины 2 и продолжаем: б+у+лок[5] - такое слово уже есть, оставляем из них только то, что состоит из меньшего числа фрагментов.

Шаг 3. Берем слово длины 3: бул+о[4].

Шаг 4. Берем слово длины 4: бул+о+к[5], снова выбираем более подходящее из двух.

Шаг 5. Последний шаг - взять единственное слово из 5 букв: б+улок.

Эту логику можно также использовать для целого текста.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2019, 10:38

Оптимизация алгоритма
Условие: Дана выборка (X_i, Y_i)_{i=1}^N. Предполагается, что она была построена по следующему...

Оптимизация алгоритма
Всем привет. Если кто-то сможет оптимизировать "это", то я отблагодарю его материально. uint32_t...

Оптимизация алгоритма Хаффмана
Сделал архиватор, но работает он запредельно долго ~ 30 мин на папку размером 50Mb(и это только...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru