Как найти ключевое слово в строке

Поиск ключевых слов в тексте

Поиск ключевых слов в исходном тексте – одна из очень распространенных задач при работе с данными. Давайте рассмотрим её решение несколькими способами на следующем примере:

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

Способ 1. Power Query

Само-собой, сначала превращаем наши таблицы в динамические (“умные”) с помощью сочетания клавиш Ctrl+T или команды Главная – Форматировать как таблицу (Home – Format as Table), даём им имена (например Марки и Запчасти) и загружаем по очереди в редактор Power Query, выбрав на вкладке Данные – Из таблицы/диапазона (Data – From Table/Range). Если у вас старые версии Excel 2010-2013, где Power Query установлена как отдельная надстройка, то нужная кнопка будет на вкладке Power Query. Если у вас совсем новая версия Excel 365, то кнопка Из таблицы/диапазона называется там теперь С листа (From Sheet).

После загрузки каждой таблицы в Power Query возвращаемся обратно в Excel командой Главная – Закрыть и загрузить – Закрыть и загрузить в… – Только создать подключение (Home – Close & Load – Close & Load to… – Only create connection).

Теперь создадим дубликат запроса Запчасти, щёлкнув по нему правой кнопкой мыши и выбрав команду Дублировать запрос (Duplicate query), затем переименуем получившийся запрос-копию в Результаты и дальше будем работать уже с ним.

Логика действий следующая:

1. На вкладке Добавление столбца выбираем команду Настраиваемый столбец (Add column – Custom column) и вводим формулу =Марки. После нажатия на ОК получим новый столбец, где в каждой ячейке будет вложенная таблица со списком наших ключевых слов – марок автопроизводителей:

   

2. Кнопкой с двойными стрелками в шапке добавленного столбца разворачиваем все вложенные таблицы. Строки с описаниями запчастей при этом размножатся кратно количеству марок, и мы получим все возможные пары-сочетания “запчасть-марка”:

   

3. На вкладке Добавление столбца выбираем команду Условный столбец (Conditional column) и задаём условие на проверку вхождения ключевого слова (марки) в исходный текст (описание запчасти):

   

4. Чтобы поиск был регистроНЕчувствительный, добавляем вручную в строке формул третий аргумент Comparer.OrdinalIgnoreCase к функции проверки вхождения Text.Contains (если строки формул не видно, то её можно включить на вкладке Просмотр):

   
5. Фильтруем получившуюся таблицу, оставляя только единички в последнем столбце, т.е. совпадения и удаляем ненужный больше столбец Вхождения.
6. Группируем одинаковые описания командой Группировать по на вкладке Преобразование (Transform – Group by). В качестве агрегирующей операции выбираем Все строки (All rows). На выходе получаем столбец с таблицами, куда собраны все подробности по каждой запчасти, включая необходимые нам марки автопроизводителей:

   

7. Чтобы извлечь марки для каждой запчасти, добавляем еще один вычисляемый столбец на вкладке Добавление столбца – Настраиваемый столбец (Add column – Custom column) и используем формулу, состоящую из таблицы (они у нас располагаются в столбце Подробности) и имени извлекаемого столбца:

   

8. Щёлкаем по кнопке с двойными стрелками в шапке получившегося столбца и выбираем команду Извлечь значения (Extract values), чтобы вывести марки через любой желаемый символ-разделитель:

   

9. Удаляем ненужный больше столбец Подробности.
10. Чтобы добавить к получившейся таблице исчезнувшие из неё запчасти, где в описаниях не было найдено ни одной марки – выполним процедуру объединения запроса Результат с исходным запросом Запчасти кнопкой Объединить на вкладке Главная (Home – Merge queries). Тип соединения – Внешнее соединение справа (Right outer join):

    

11. Останется удалить лишние столбцы и переименовать-переместить оставшиеся – и наша задача решена:

    

Способ 2. Формулы

Если у вас версия Excel 2016 или новее, то нашу проблему можно весьма компактно и изящно решить с помощью новой функции ОБЪЕДИНИТЬ (TEXTJOIN):

Логика работы этой формулы проста:

• Функция ПОИСК (FIND) ищет вхождение по очереди каждой марки в текущее описание запчасти и выдаёт либо порядковый номер символа, начиная с которого марка была найдена, либо ошибку #ЗНАЧ! если марки в описании нет.
• Затем при помощи функции ЕСЛИ (IF) и ЕОШИБКА (ISERROR) мы заменяем ошибки на пустую текстовую строку “”, а порядковые номера символов – на сами названия марок.
• Полученный массив из пустых ячеек и найденных марок собирается в единую строку через заданный символ-разделитель с помощью функции ОБЪЕДИНИТЬ (TEXTJOIN).

Сравнение быстродействия и буферизация запроса Power Query для ускорения

Для тестирования быстродействия возьмем в качестве исходных данных таблицу из 100 000 описаний запчастей. На ней получаем следующие результаты:

• Время пересчета формулами (Способ 2) – 9 сек. при первом копировании формулы на весь столбец и 2 сек. при повторном (сказывается буферизация, видимо).
• Время обновления запроса Power Query (Способ 1) гораздо хуже – 110 сек.

Само-собой, многое зависит от “железа” отдельно взятого ПК и установленной версии Office и обновлений, но общая картина, думаю, понятна.

Для ускорения запроса Power Query давайте буферизуем таблицу-справочник Марки, т.к. она у нас не меняется в процессе выполнения запроса и постоянно пересчитывать её (как это де-факто делает Power Query) не нужно. Для этого используем функцию Table.Buffer из встроенного в Power Query языка М.

Для этого откроем запрос Результаты и на вкладке Просмотр нажмём на кнопку Расширенный редактор (View – Advanced Editor). В открывшемся окне добавим строку с новой переменной Марки2, которая будет буферизованной версией нашего справочника автопроизводителей и используем эту новую переменную далее в следующей команде запроса:

После такой доработки скорость обновления нашего запроса возрастает почти в 7 раз – до 15 сек. Совсем другое дело 🙂

Ссылки по теме

• Нечёткий текстовый поиск в Power Query
• Массовая замена текста формулами
• Массовая замена текста в Power Query функцией List.Accumulate

При поиске сочетаний из списка, кроме буквального совпадения, нужно учитывать ‘ложные’ совпадения – например, ‘ку’ является частью слова ‘кукуруза’, но это не приветствие. Также целесообразно учитывать регистры символов и возможность наличия нескольких пробелов между словами. Такой поиск сочетаний из списка можно реализовать через регулярные выражения.

import re

hello = ["привет", "ку", "здравствуйте", "здравия", "салют",
         "hello", "hi", "good morning", "good day", "good evening"]
r = '|'.join(rf'b{x}b' for x in hello).replace(' ', r's+')

for text in 'кукуруза', 'скажем ку', 'Hi, peoples', 'high voltage', 'good       morning!', 'good    day, привет, КУпите слона':
    res = re.findall(r, text, re.IGNORECASE)
    if res:
        print(f'Словосочетания из списка найдены в тексте `{text}`: `{res}`')
    else:
        print(f'Словосочетания из списка НЕ найдены в тексте `{text}`')

Словосочетания из списка НЕ найдены в тексте `кукуруза`
Словосочетания из списка найдены в тексте `скажем ку`: `['ку']`
Словосочетания из списка найдены в тексте `Hi, peoples`: `['Hi']`
Словосочетания из списка НЕ найдены в тексте `high voltage`
Словосочетания из списка найдены в тексте `good       morning!`: `['good       morning']`
Словосочетания из списка найдены в тексте `good    day, привет, КУпите слона`: `['good    day', 'привет']`

Алгоритмы поиска в строке

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска

Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)

После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)

На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск)

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.

Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.