Алгоритм поиска: парсинг и обработка запроса в стиле ООП

Question

Скажем, вам нужно было создать поисковую систему, которая могла бы принимать оператор запроса в форме строки.Оператор может использоваться для извлечения различных типов объектов с заданным набором характеристик и, возможно, связанных с другими объектами.В простом английском или псевдокоде с использованием подхода ООП, как бы вы пошли в парсинге и обработке операторов следующим образом, чтобы получить серию желаемых объектов?

• получить фрукты с зеленым цветом
• получить сорт яблок, груш от Энди
• получить клубнику с цветом "темно-красный" и происхождением не из Испании
• получить общий объем продаж дынь в период с 2010-10-10 по 2010-12-30
• получите последнюю дату доставки бананов от "Пита" и состояние не продано

Надеюсь, вопрос ясен.Если нет, я буду более чем рад переформулировать.

PS: Это не домашняя работа;)

Answer 1

Ваша проблема хорошо подходит для ориентированного на документы магазина, такого как Lucene.Например, вы можете создать схему, такую ​​как

Тип
Сорт
Цвет
Источник DateSold и т. Д .:

Затем вы можете написать запрос Lucene, такой как Type: Fruit ANDЦвет: зеленый.Вы также можете создавать вложенные запросы, такие как (Fruit: Straberry И Color: Deep Red) И НЕ Происхождение: Испания.

Apache Lucene - это библиотека Java с портами, доступными для большинства основных языков. Apache Solr - это полноценный поисковый сервер, построенный с использованием Lucene lib и легко интегрируемый в выбранную вами платформу, поскольку он имеет RESTful API.

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

---

Тип: - Фрукты (109) - Орех (99)

Происхождение: - Испания (32) - Франция (39)

Цвет: - Красный (22) - Темно-красный (45)

---

Нажатие на каждую из граней фильтрует результаты с пересечением.Поэтому, если вам нужна более удобная модель взаимодействия, фасетирование / фильтрация намного проще, чем заставлять пользователей печатать обширные запросы Lucene.

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

Answer 2

Я согласен с Джоном.

а) Начните с лексического анализа б) взять статистику поисков и использовать их для индексации в) Найти отношения, анализируя возможные похожие поиски

Хотя это просто дикое предположение, никогда раньше не пробовал.

Answer 3

Похоже, вы разрабатываете мини-язык, так как вы заинтересованы в синтаксисе и разборе. Итак, ознакомьтесь со многими инструментами, используемыми для генерации лексеров и парсеров. Вы можете начать здесь: http://en.wikipedia.org/wiki/Lexical_analysis