Как имея большой текст, найти совпадения всех предложений?

Question

[Роман Сарваров]

Представим есть таблица sentences, где хранятся сотни тысяч каких-то предложений или словосочетаний.
И есть текст из 5000 слов, который ввел пользователь (к примеру).

Есть ли какой-то способ или алгоритм, чтобы рационально используя вычислительные ресурсы выделить в тексте все совпадения (например через str_replace) из всей таблицы sentences?

Comments

[granty]

1. Вам же не надо выделять сотни тысяч совпадений, выделять надо только те, которые будут выведены на экран пользователя.
Поэтому задача разбивается на 2:
- поиск совпадений и их постраничный вывод
- подсветка результатов вывода
именно так и делают ПС.

2. Морфологию надо учитывать? "способ" -> "способы" -> "способов" -X-> "способности"

3. Семантику надо учитывать?

За песчанной косой,
косоглазый косой,
пал под острой косой
Косой бабы с косой.

какое из слов "косой" собираетесь выделять?

4. "Расстояние" между словами надо учитывать? "пластиковая карта" == "пластиковая банковская карта" или нет

5. Синонимы надо учитывать? "компьютер" == "ПК" или нет?

[Роман Сарваров]

granty, нет, точные совпадения.

[Роман Сарваров]

Вообще в идеале, чтобы в таблице sentences была колонка regular_expression с регулярным выражением.

Если сделать так:

SELECT * FROM `sentences` WHERE ('Сюда вставить какой-то большой текст' REGEXP regular_expression)

То всё работает, даже если вставить текст на 5000 слов. Но я переживаю, что будет если этих регулярок будет тысячи?

[granty]

Роман Сарваров, статья https://habr.com/ru/company/alconost/blog/339894/ прокрутить до заголовка Как все это сделать НА ПРАКТИКЕ?. Там приведена куча инструментов и библиотек для организации поиска, и есть список литературы о теории этого дела.

Скорее всего вам придётся строить инвертированный (обратный) индекс, как у Поисковых Систем, но привязывать его не к URL страниц, а к номеру записи в БД.

Answer 1

[ky0]

А почему, собственно, вы эту задачу хотите с помощью постгреса решать, а не с помощью намного более подходящих решений на базе инвертированных индексов - Lucene, Elasticsearch и т. д.?

Comments

[xmoonlight]

Не надо советовать бред.

Answer 2

[xmoonlight]

Надо построить алфавитный указатель и умножать слова на простые коэффициенты.

Comments

[Olexayko]

Чет как-то костыльненько

[Olexayko]

Костыльненько

[xmoonlight]

Olexayko, чем именно?

Answer 3

[Александр Аксентьев]

https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

Comments

[Роман Сарваров]

Мне нужно точное совпадение. Разве шинглы с этим могут помочь?

[Александр Аксентьев]

Роман Сарваров, на выходе же будет какой-то процент совпадения или полный дубликат.

Только непонятно какое полное совпадение вы хотите получить, у вас же набор предложений, а не два текста которые надо сравнить на похожесть.

В статье есть ссылка на какой-то анализ алгоритмов
rcdl2007.pereslavl.ru/papers/paper_65_v1.pdf

Может что-то из них больше подойдёт.

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