Разработка полнотекстового поиска в PostgreSQL алгоритмом Ахо-Корасик

Тип участника: Физическое лицо

Полное наименование организации/физического лица/авторского или творческого коллектива: Ошурков Никита Алексеевич

ФИО всех участников авторского/творческого коллектива: Исполнитель - Ошурков Никита Алексеевич
Руководитель - Целебровский Олег Борисович

Идея и краткое описание ИТ-проекта: Разработка расширения pg_ac для PostgreSQL, реализующего полнотекстовый поиск на основе алгоритма Ахо-Корасик. Проект решает проблему неэффективности встроенного FTS PostgreSQL при работе с большими документами, обеспечивая линейную сложность поиска (O(H), где H — длина текста запроса) независимо от размеров автоматов.

Перечень решаемых задач:

Изучение принципов разработки расширений для PostgreSQL;
Реализация алгоритма Ахо-Корасик;
Создание SQL-интерфейса для работы с расширением;
Обеспечение совместимости с типами TSVector и TSQuery;
Сравнение со встроенным полнотекстовым поиском.

Описание функциональных возможностей и элементов проекта:

1. Инициализация сессии ac_init();

2. Построение автоматов ac_build(tsvector), ac_build(text[]);

3. Поиск ac_search(id, text), ac_search(id, tsquery);

4. Сопоставление ac_match(id, text);

5. Ранжирование ac_rank_simple;

Дата внедрения (в случае, если предполагается запуск проекта в эксплуатацию): -

Используемые платформы, средства разработки:

IDE: Visual Studio Code
Языки: SQL, C

СУБД: PostgreSQL 16

Сборка: Make, PGXS

Тестирование: Регрессионные тесты

Стоимость разработки системы: Не определено

Средний размер ежегодных затрат на эксплуатацию: Прямых трат на использование нет

Перспективы развития: • Изменение способа хранения дочерних узлов, чтобы снизить потребление памяти;
• Поддержка Unicode.
• Поддержка TSQuery для функций ранжирования и сопоставления

Достижение поставленных целей:

Поставленные цели считаются выполненными, есть перспективы развития, которые хотелось бы реализовать;
Расширение проходит все тесты;
Доказана эффективность при больших документах.

Актуальность, экономическая или социальная полезность:

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

Масштабируемость, способность к взаимодействию с другими системами, мобильность:

Масштабируемость: Обрабатывает документы до 100000 слов (ограничение — только память сервера);

Интеграция: Совместим с любыми системами на PostgreSQL. Поддерживает стандартные типы FTS (TSVector, TSQuery);

Мобильность: Не требует внешних зависимостей; развертывается как стандартное расширение.

Обоснованность применяемых проектных решений:

Алгоритм Ахо-Корасик выбран из-за линейной скорости поиска O(H);
Хранение автоматов в хеш-таблице было выбрано для обеспечения быстрого доступа к ним по ключу;
Поддержка типов TSVector и TSQuery позволяет использовать встроенные механизмы нормализации и словарей.

Оригинальность, новизна, отличие от аналогов либо отсутствие аналогов:

Существующие расширения (pg_bigm, pg_trgm) решают задачи нечеткого поиска, но не заменяют PostgreSQL FTS.

Первая реализация Ахо-Корасик для PostgreSQL как полноценное расширение полнотекстового поиска.

Гарантирую достоверность предоставленной в заявке информации. Подтверждаю, что организация не находится в состоянии ликвидации, банкротства, реорганизации (Только для организаций): Да

Презентация проекта pdf: Загрузить

Возврат к списку

нет доступа к комментариям Авторизоваться