@svfolder2021

Массовое сравнение сток, поиск пересечений, каким инструментом воспользоваться?

Есть некое множество слов, пусть это будет 100 000 слов.

Есть некое количество текстов, пусть будет 150 000 текстов, пусть среднее количество слов в каждом тексте будет 50.

Есть программа которая ищет в цикле каждое слово из первого множества, сейчас это все в массивах и просто сравнивается между собой, на что уходит очень много времени.

Есть ли такие системы которые могут выполнить такие проверки с большим количеством параллельных потоков или еще как то?

Какие идеи пока что посетили меня. Положить первое множество в таблицу MySQL, и навесить ключ на поле с этим множеством.

Далее положить во временную таблицу InMemory все слова из текстов и потом соеденить их через INNER JOIN, но у нас в каждом тексте может быть несколько совпадений с первым множеством и как при этом отделить одно от другого мне не совсем понятно.

Может можно как то использовать Elasticsearch, Redis и тому подобные системы?
  • Вопрос задан
  • 92 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Просто воспользуйтесь алгоритмом ахо-корасика. У вас очень мало данных. Обработка их всех займет не более 100 мс на среднем компьютере в один поток.

Существующих готовых программ я не знаю, но реализацию алгоритма в библиотеках или на гитхабе я думаю вы найти сможете запросто.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
примерно объёмы инфы:
100к слов (по 10 символов) в «первом множестве» — это примерно 1Mb
150к текстов по 50 слов по 10 символов в слове это 75Mb
Т.е. всё весьма компактно.

Искать наверное стоит программой, в оперативке.

Сначала проиндексировать тексты. Составить словарь, где ключ – слово, значение – массив индексов текстов, где оно встречается.

Затем искать среди ключей этого словаря слова из первого множества.

Можно ещё сократить/ускорить, если работать не с самими словами, а только с целыми индексами. Любое слово класть в Set (где значения уникальны) и далее работать с индексом слова в этом наборе.
Ответ написан
@mayton2019
Bigdata Engineer
Коробочное решение - это библиотеки обработки текста Apache Lucene, Sphinx. Но их нужно программировать - следовательно вам надо искать разработчика.

ElasticSearch/Solr (под капотом это тот-же Lucene) - вариант но вам надо будет его конфигурировать и тщательно подбирать настройки Analyzer чтоб не получать ложно-позитивных срабатываний. Возможно в дефолтном варианте он слишком умный и делает стемминг там где не надо.

Если самостоятельно программировать то мы имеем такую complexity : 100 000 слов проверить в 150 текстах - это примерно 15 миллиардов тривиальных проверок. Типа поиска строки в строке. Хочется от этого уйти. Поэтому надо искать какие-то структуры данных работающие на exists(..). Например Фильтры Блума. При 150 тыщ элементов он будет достаточно компактен. Или сортирующие и хеширующие структуры (R&B Trees). Тогда вместо 15 млрд мы сведем к 100 либо к 150 тыс циклов по одному из измерений как будет выбрано.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы