Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
FutureCome
104 / 104 / 9
Регистрация: 19.12.2010
Сообщений: 417
Завершенные тесты: 2
1

Быстрый поиск строки в списке строк с предварительным хешированием

26.01.2013, 21:36. Просмотров 850. Ответов 3
Метки нет (Все метки)

Здравствуйте.
Необходимо реализовать быстрый поиск строки в списке строк с предварительным хешированием в целях исследования (изучения).
Реализовываться будет на Java, если это имеет значение.
Теперь подробнее.
Входные данные
  1. Список (массив, List) строк, назовём его lstStrings;
  2. Список дополнительных данных, ассоциированных со строками, предназначенных для сортировки результата (например, дата последнего изменения строки);
  3. Строка, которую нужно искать в исходном списке строк srcStrings, назовём её ptrnString;
  4. Число limitNumber, ограничивающее максимальное количество строк, которые могут быть возвращены в качестве результата выполнения алгоритма (т.е. в результате не более limitNumber найденных строк).
Задача алгоритма
Поиск всех строк в списке lstStrings, которые начинаются со строки ptrnString, за максимально короткое время.
Подробности реализации
Реализовать придётся, скорее всего, как-то через хеширование или индексацию для достижения максимальной скорости при сотнях тысяч исходных строк и запросов.
Например, первый метод индексирует весь список исходных строк, подготавливает необходимые структуры для дальнейшего поиска. А второй метод уже непосредственно осуществляет поиск.
Найти нужно не более limitNumber строк.
Результирующий список необходимо отсортировать по определённым правилам: с каждой строкой ассоциирована дата её изменения. Сортировку результатов необходимо провести по дате изменения. Если даты изменения совпадают - в лексикографическом (алфавитном) порядке.
Выходные данные
  1. Список (массив) строк, которые начинаются с искомой строки ptrnString, в нужной последовательности.

В какую сторону мне начать искать...? Какие быстрые алгоритмы существуют для решения этой задачи? Подскажите, как лучше решить эту задачу?
Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2013, 21:36
Ответы с готовыми решениями:

Быстрый поиск пар
Здравствуйте. Задача такая: есть N прямоугольных "коробок" и N прямоугольных...

Быстрый поиск слова
Поделитесь кто-нибудь знаниями по быстрому поиску в большом объеме текста,...

Быстрый поиск k ближайших соседей
Имеется 10000 точек в 20-мерном пространстве. Распределены более менее...

Быстрый поиск папок на сервере
Здравствуйте! Задача: Есть сервер. На сервере хранятся определенные папки с...

Быстрый поиск элементов массива
Есть два частично заполненных трёхмерных массива. Массивы не ограничены по...

3
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
13.04.2013, 10:29 2
с помощью хэшей вы можете отвечать на каждый запрос за O(1). таким образом итоговая сложность O(n*l + q). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк.
в общем понятно уже, что тонкий момент в этой задаче - подсчет хэшей. прежде всего нужно понять, что хэши нужно считать только для префикса длины искомой строки. то есть если мы ищем "abcd" в строке "abcdefgrjf", то смысл есть знать только хэш первых четырех символов строки "abcdefgrjf". если вы грамотно посчитаете хэши, то дальше давать ответ будет сплошным удовольствием.
если будут вопросы, пишите, не стесняйтесь)

Добавлено через 9 минут
извините, не то сказал... с помощью хэшей вы можете отвечать на каждый запрос за O(n). таким образом итоговая сложность O(n*l + n*q). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк.
0
Ks4ndr
0 / 0 / 0
Регистрация: 06.01.2014
Сообщений: 1
10.01.2014, 02:03 3
Здравствуйте! Сейчас решаю подобную задачу. Длина искомой строки известна только после индексации данных. Получается в любом случае нужно считать хэши всех префиксов и потом уже брать нужной длины. Если так делать, то подозреваю, что не получится уложиться в ограничение по памяти в 64 Мб (по ТЗ). А если сохранять в файлы, то это дополнительно время. Буду очень признателен, если подбросите идей или датите комментарии. Спасибо.
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
10.01.2014, 08:59 4
если вас устраивает отвечать на каждый запрос за O(L), где L - длина искомой строки, то можно строить бор. тогда длина префикса абсолютно не принципиальна.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2014, 08:59

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

Быстрый поиск строки в списке строк
Здравствуйте. Необходимо реализовать быстрый поиск строки в списке строк в...

Очень быстрый поиск в списке
В файле есть около 1.000.000 строк до 20 символов, для начала я заношу его в...


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

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

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