Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник
Коллекция курьезных вопросов из форумов
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »
Страницы: 1 2

Аббревиатурный поиск


DayGaykin ©   (05.08.19 17:04

Есть список предложений от 100 000 штук. В каждом предложении по 1–6 слов.
Допустим одно из предложений "зелёный лес".
Пользователь набирает слово-запрос для поиска и из всего списка предложений нужно найти подходящие. Предложение подходит по запросу, если поисковой запрос является аббревиатурой предложения. Другими словами, если запрос состоит из конкатенации начал слов в предложении (можно с пропусками слов).

Допустим зелёному лесу соответствуют запросы:
з (зелёный лес)
зл (зелёный лес)
злес (зелёный лес)
зелле (зелёный лес)
зе (зелёный лес)
ле (зелёный лес)

А эти не соответствуют:
зес
ел
ес

Вопрос, как такой фильтр сделать эффективно и экономично?

Для примерно можно взять список словосочетаний отсюда: http://dict.ruslang.ru/magn.php?act=search


DayGaykin ©   (05.08.19 17:06[1]

Upd:
такой поиск работает в Intellij Idea для имен с помощью Shift,Shift.


Styx ©   (05.08.19 23:25[2]


> такой поиск работает в Intellij Idea для имен с помощью Shift,Shift.

Тогда на гитхабе можно посмотреть, как там сделано....


картман ©   (06.08.19 00:34[3]


>
> Для примерно можно взять список словосочетаний отсюда: http:
> //dict.ruslang.ru/magn.php?act=search

В чем прок от такого словаря?


KSergey ©   (06.08.19 07:04[4]

Просто уточнение:

зе (зелёный лес)

А вот это подходит тоже?

зе (зелёный егерь)


KSergey ©   (06.08.19 07:13[5]

Хорошо, в чем основной вопрос?
Как сделать? или как сделать этот поиск быстро?

Если про быстро - то 100 тыс - уже приличная цифра.
Я бы сформировал (помимо предложений) отдельно мапу всех различных слов (возможно, для экономии памяти, только первых 3..4 букв слов), второй элемент мапы - ссылки на предложения, где эти слова встречаются (надо только еще продумать про указание позиции слова в предложении, чтобы быстрее). Этот список будет явно меньше общего списка предложений.

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

Или вопрос в том, что нужно прям весь алгоритм продумать?
не, это мне лень, хотя задачка интересная, по работе у меня таких не бывает, надо будет побаловаться :)

PS
Люди, скажите, у кого по работе такие задачки возникают? Ну это же праздник, а не задачки! сиди себе, гоняй байтики.
Чета мне разнообразия захотелось, протомился я последние 10 лет деньги считать.


Кщд2 ©   (06.08.19 08:54[6]

>DayGaykin ©   (05.08.19 17:04)
100 000 - это ничто для любой современной СУБД
поиск - регулярками
как же ещё


Leonid Troyanovsky ©   (06.08.19 11:11[7]


> DayGaykin ©   (05.08.19 17:04) 

> Допустим зелёному лесу соответствуют запросы:
> з (зелёный лес)
> зл (зелёный лес)
> злес (зелёный лес)

Плохо, что в запросах нет разделения на слова,
т.е. "з л", "з лес", и допускается вхождение  подцепочки (а не старт)

Иначе, можно было бы  распарсив предложения построить таблицу слов:
<ид><слово><ид_предложения>  и поиск основывать на ней.

--
Regards, LVT.


DayGaykin ©   (07.08.19 14:59[8]

Спасибо за ответы.


Кщд2 ©   (06.08.19 08:54) [6]
> поиск - регулярками

Можно пример такой регулярки?


> Люди, скажите, у кого по работе такие задачки возникают?
>  Ну это же праздник, а не задачки! сиди себе, гоняй байтики.

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

Но похоже придется сделать как советует Леонид, добавить разделители. Во-первых, это упростит задачу, во-вторых, мне кажется, будет сложно объяснить пользователям как работает аббревиатурный поиск.


KSergey ©   (09.08.19 08:41[9]

Вообще наверное да: для человека будет интуитивно понятнее, если добавлять пробелы между подразумеваемыми им словами
Да и количество подходящих фраз логично для человека уменьшится.

На чем программировать этот алгоритм будешь? на каком языке?


картман ©   (10.08.19 12:52[10]


> Но похоже придется сделать как советует Леонид, добавить
> разделители

лучше реализовать оба варианта


DayGaykin ©   (10.08.19 13:43[11]


> На чем программировать этот алгоритм будешь? на каком языке?

Это для веб приложения, поэтому  на Kotlin + JavaScript.


картман ©   (11.08.19 00:21[12]

Копир, вот подсказал бы что дельное силой сисек бабьих там али еще чего загадочного


Pavia ©   (14.08.19 06:04[13]


> Если про быстро - то 100 тыс - уже приличная цифра.

В смысле неприлично малая?
Аббревиатуры хранить в нормализованном виде. Искать линейным поиском.

Есть список предложений от 100 000 штук. - это 10 МБайт. Современный процессор 3 ГГц
И того линейны поиском 3,3 мс. Это меньше реакции человека. Так что можно смело увеличивать


Кщд2 ©   (14.08.19 10:09[14]

>DayGaykin ©   (07.08.19 14:59) [8]
>Можно пример такой регулярки?
нельзя
я был не прав

>Pavia ©   (14.08.19 06:04) [13]
>В смысле неприлично малая?
это так

>Аббревиатуры хранить в нормализованном виде. Искать линейным поиском.
это не так
или покажите алгоритм


KSergey ©   (14.08.19 12:19[15]

> Pavia ©   (14.08.19 06:04) [13]
> В смысле неприлично малая?
> .....
> И того линейны поиском 3,3 мс. Это меньше реакции человека.  Так что можно смело увеличивать

Правильно или нет посчитаны 3,3 мс - это я не знаю. Примем, что правильно.
Тогда про "уже приличная цифра" я говорил по закрепившейся привычке.
В том смысле, что я последние 10 лет клепаю софт, который содержит кучу расчётов плюс таких поисков там пара..тройка сотен по разным "словарям", но весь расчет должен укладываться в 1..2 мс, иначе ахтунг.

Однако вы совершенно правы, с точки зрения реакции человека эти времена совершенно незаметны, я забыл про условия )
Хотя яб вс одно сделал как минимум бинарный поиск, ибо это то место, которе заранее понятно, что есть объёмная операция и это никак не будет пресловутой "преждевременной оптимизацией".
(и я таки по прежнему уверен, что автор этой фразы должен быть расстрелян, а все его книги сожжены; ибо выковыривать эту написанную очень безапеляционно установку из голов очень и очень сложно; хоть автор и был формально прав, если разобраться, но написал эту фразу ну слишком неаккуратно и необдуманно)


картман ©   (14.08.19 21:11[16]


KSergey ©   (06.08.19 07:13) [5]
....
PS
> Люди, скажите, у кого по работе такие задачки возникают?
>  Ну это же праздник, а не задачки! сиди себе, гоняй байтики.
>
> Чета мне разнообразия захотелось, протомился я последние
> 10 лет деньги считать.



> KSergey ©   (14.08.19 12:19) [15]

В том смысле, что я последние 10 лет клепаю софт ... плюс таких поисков там пара..тройка сотен по разным "словарям",
>  но весь расчет должен укладываться в 1..2 мс, иначе ахтунг.
>


Ты уж определись))


manaka ©   (10.09.19 15:59[17]

зеле (зеленый лес) подходит
зеле (зеленый лес) не подходит

надо менять подход к фильтру.


Кщд2 ©   (16.09.19 07:52[18]

>manaka ©   (10.09.19 15:59) [17]
прочитать "DayGaykin ©   (05.08.19 17:04) " - надо
понять прочитанное - надо
менять подход - не надо


tesseract ©   (07.10.19 14:19[19]

>>Есть список предложений от 100 000 штук. - это 10 МБайт. Современный процессор 3 ГГц
И того линейны поиском 3,3 мс.

А про оперативную память и SSD и map/reduce? И адаптивные словари?

>>Это для веб приложения, поэтому  на Kotlin + JavaScript.

AWS дешевого обходиться - там все пофиг :-)


Страницы: 1 2 версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо