Простейший полнотекстовый поиск на Python с поддержкой морфологии

В прошлой статье я рассказывала, что составила для своего проекта словарь «Властелина Колец», причем для каждого англоязычного терма (слова/словосочетания) хранится перевод и список глав, в которых встречается это выражение. Все это составлено вручную. Однако мне не дает покоя, что многие вхождения термов могли быть пропущены.

В первой версии MVP я частично решила эту проблему обычным поиском по подстроке (\b{term}, где \b – граница слова), что позволило найти вхождения отдельных слов без учета морфологии или с некоторыми внешними флексиями (например, -s, -ed, -ing). Фактически это поиск подстроки с джокером на конце. Но для многословных выражений и неправильных глаголов, составляющих весомую долю моего словаря, этот способ не работал.

После пары безуспешных попыток установить Elasticsearch я, как типичный изобретатель велосипеда и вечного двигателя, решила писать свой код. Скудным словообразованием английского языка меня не запугать ввиду наличия опыта разработки полнотекстового поиска по документам на великом и могучем русском языке. Кроме того, для моей задачи часть вхождений уже все равно выбрана вручную и потому стопроцентная точность не требуется.

Подготовка словаря

Итак, дан словарь. Ну как дан – составлен руками за несколько месяцев упорного труда. Дан с точки зрения программиста. После прошлой статьи словарь подрос вдвое и теперь охватывает весь первый том («Братство Кольца»). В сыром виде состоит из 11.690 записей в формате «терм – перевод – номер главы». Хранится в Excel.

Как и в прошлый раз, я сгруппировала свой словарь по словарным гнездам с помощью функции pivot_table() из pandas. Осталось 5.404 записи, а после ручного редактирования - 5.354.

Больше всего меня беспокоили неправильные глаголы, поскольку в моем словаре они хранились в инфинитиве, а в романе чаще всего употреблялись в прошедшем времени. Ввиду так называемого аблаута (например, run – ran – run) установить инфинитив по словоформе прошедшего времени невозможно.

Я скачала словарь неправильных глаголов. Он насчитывал 294 штуки, многие из которых допускали два варианта. Пришлось проверить все вариации по тексту Толкиена, чтобы установить, какая форма характерна для его речи: например, cloven (p.p. от cleave) вместо cleft (что у него существительное). Оказалось, что многие неправильные глаголы у него правильные (например, burn), а leap даже существует в обеих версиях - leaped и leapt.

Теперь вариации неправильных глаголов унифицированы, а их список хранится в обычном текстовом файле:

Остается считать этот файл в датафрейм с помощью функции read_csv(), указав в качестве разделителей пробелы:

import pandas as pd
verb_data = pd.read_csv(pathlib.Path('c:/', 'ALL', 'LotR', 'неправильные глаголы.txt'),
                       sep=" ", header=None, names=["Inf", "Past", "PastParticiple"], index_col=0)

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

Считаем наш главный словарь в другой датафрейм:

excel_data = pd.read_excel(pathlib.Path('c:/', 'ALL', 'LotR', 'словарь Толкиена сведенный.xlsx'), dtype = str)
df = pd.DataFrame(excel_data, columns=['Word', 'Russian', 'Chapters'])

Теперь объявим функцию, которая для каждого словарного терма проверит наличие в нем неправильного глагола и в зависимости от результата сгенерирует словоформы. Для простоты будем считать, что неправильный глагол всегда стоит на первом месте.

def check_irrverbs(word):
    global verb_data

    # берем часть выражения до первого пробела
    arr = word.split(' ')
    w, *tail = arr # = arr[0], arr[1:]
    # запоминаем хвост
    tail = " ".join(tail)

    # проверяем, не является ли она неправильным глаголом
    if w in verb_data.index:
        # формируем формы Past и Past Participle
        # если они одинаковые, то достаточно хранить одну форму
        if verb_data.loc[w]["Past"] == verb_data.loc[w]["PastParticiple"]:
            return verb_data.loc[w]["Past"] + " " + tail
        return ", ".join([v + " " + tail for v in verb_data.loc[w].tolist()])

    return ""

Таким образом, для выражения make up one's mind функция вернет made up one's mind.

Применяем функцию к датафрейму, сохраняя результаты в новый столбец, и затем экспортируем результат в новый Excel-файл:

df['IrrVerb'] = df['Word'].apply(check_irrverbs)
df.to_excel(pathlib.Path('c:/', 'ALL', 'LotR', 'словарь Толкиена сведенный.xlsx'))

Теперь в Excel-таблице появился новый столбец, хранящий 2-ю (Past) и 3-ю (Past Participle) формы для всех неправильных глаголов, а для правильных столбец пуст.

Всего таких записей оказалось 662.

Спряжение потенциальных глаголов

Теперь сгенерируем все формы и для правильных, и для неправильных глаголов.

def generate_verbs(word, is_irrverb):
    forms = []

    # взять часть выражения до первого пробела
    verb, tail = word, ""
    pos = word.find(" ")
    if pos >= 0:
        verb = word[:pos]
        tail = word[pos:]

    consonant = "bcdfghjklmnpqrstvwxz"
    last = verb[-1]

    # глагол во 2 и 3 формах
    if not is_irrverb:
        if last in consonant:
            forms.append(verb + last + "ed" + tail) # stop -> stopped
            forms.append(verb + "ed" + tail) # и вариант без удвоения
        elif last == "y":
            if verb[-2] in consonant:
                forms.append(verb[:-1] + "ied" + tail) # carry -> carried
            else:
                forms.append(verb + "ed" + tail) # play -> played
        elif last == "e":
            forms.append(verb + "d" + tail) # arrive -> arrived
        else:
            forms.append(verb + "ed" + tail)

    # герундий, он же ing-овая форма глагола
    if verb[-2:] == "ie":
        forms.append(verb[:-2] + "ying" + tail) # lie -> lying
    elif last == "e":
        forms.append(verb[:-1] + "ing" + tail) # write -> writing
    elif last in consonant:
        forms.append(verb + last + "ing" + tail) # sit -> sitting
        forms.append(verb + "ing" + tail) # sit -> sitting
    else:
        forms.append(verb + "ing" + tail)

    return forms

Как и прежде, для простоты будем считать глаголом часть выражения до первого пробела либо все выражение целиком, если оно не содержит пробелов. Посмотрим, на какую букву (переменная last) оканчивается предполагаемый глагол. Для этого нужен список либо гласных, либо согласных. Список гласных был бы короче, но так как нам понадобится проверять именно на согласную, то нагляднее будет хранить список consonant.

Для правильных глаголов вторая и третья формы создаются путем прибавления флексий -d, -ed, -ied в зависимости от последнего и предпоследнего звука. Так как учитывается еще и ударение, то проще всего сгенерировать оба варианта, из которых грамматически корректен будет только один. Для неправильных глаголов мы уже нашли обе формы и записали в отдельный столбец.

Герундий образуется одинаково для правильных и неправильных глаголов, но опять-таки надо учитывать последний символ и ударение, поэтому снова создаем оба варианта.

Все варианты записываются в список forms, который функция и возвращает.

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

Подстановки

Кроме неправильных глаголов, словарь содержит еще один вид выражений, осложняющих полнотекстовый поиск, - подстановочные местоимения: притяжательное one’s, возвратное oneself и неопределенные somebody и something. В реальном тексте они должны заменяться на конкретные слова – соответственно, притяжательные местоимения (my, your, his и т.д.), возвратные местоимения (myself, yourself, himself и т.д.) и существительные. Поэтому надо сгенерировать все возможные формы с подстановками.

Начнем с one’s и oneself:

def replace_possessive_reflexive(word):
    possessive = ["my", "mine", "your", "yours", "his", "her", "hers", "its", "our", "ours", "their", "theirs"]
    reflexive = ["myself", "yourself", "himself", "herself", "itself", "ourselves", "yourselves", "themselves"]

    # заменить one's на все варианты из possessive
    if "one's" in word:
        forms = list(map(lambda p: word.replace("one's", p), possessive))
    elif "oneself" in word:
        # заменить oneself на все варианты из reflexive
        forms = list(map(lambda r: word.replace("oneself", r), reflexive))
    else:
        forms = [word]

    return forms

Здесь мы для простоты предполагаем, что one's и oneself не встречаются в одном выражении, а также не употребляются в реальном тексте. Если в терме есть одно из этих слов, то он интересует нас только с подстановками. В противном случае терм рассматривается как одна из форм самого себя, поэтому создается список, состоящий только из него.

Полный процесс замены обрабатывает также скобки и неопределенные местоимения:

def template_replace(word):
    forms = []
    forms = [word] if not "(" in word else [word.replace("(", "").replace(")", ""), re.sub("\([^)]+\)", "", word)]
    forms = list(map(lambda f: f.replace("somebody", "\S+").replace("something", "\S+"), forms))
    forms = list(map(replace_possessive_reflexive, forms))
    return sum(forms, [])

Замена происходит в три этапа, причем результат предыдущего подается на вход следующему.

1. Если терм содержит скобки, то рассматриваем два варианта – с их содержимым или без него: например, wild(ly) -> {wild, wildly}.

2. Что касается somebody и something, то они заменяются на \S+ – группу любых непробельных символов, то есть на заготовку для будущего регулярного выражения.

3. Наконец вызываем рассмотренную выше функцию replace_possessive_reflexive() для обработки one's и oneself.

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

Таким образом, основная идея данной реализации полнотекстового поиска – генерировать максимальное количество вариантов словоформ, чтобы затем искать их в тексте. Как велико это число? В простейшем случае, для термов, не содержащих неправильных глаголов и оканчивающихся на гласную, будет всего 3 формы – инфинитив, вторая/третья форма и герундий. Если терм кончается на согласную, то появляется второй вариант герундия. В худшем случае терм содержит скобки, притяжательное местоимение и неправильный глагол, оканчиваясь на согласную, тогда для первичного списка из 2 вариантов со скобками * 12 притяжательных местоимений будут сгенерированы по 24 формы инфинитива, двух вариантов герундия, а также прошедшего времени и причастия прошедшего времени, итого

Отдельной строкой, чтобы осознать масштаб этой цифры)

Впрочем, мой словарь не содержит настолько сложных случаев. Вот более характерный пример – hold one's breath (сочетание неправильного глагола, оканчивающегося на гласную, и притяжательного местоимения). Из него будет сгенерировано 48 форм:

• 12 вариантов инфинитива: 'hold my breath', 'hold mine breath', 'hold your breath', 'hold yours breath', 'hold his breath', 'hold her breath', 'hold hers breath', 'hold its breath', 'hold our breath', 'hold ours breath', 'hold their breath', 'hold theirs breath'

• 24 варианта герундия, с удвоенной согласной и с одинарной: 'holdding my breath', 'holding my breath', 'holdding mine breath', 'holding mine breath', 'holdding your breath', 'holding your breath', 'holdding yours breath', 'holding yours breath', 'holdding his breath', 'holding his breath', 'holdding her breath', 'holding her breath', 'holdding hers breath', 'holding hers breath', 'holdding its breath', 'holding its breath', 'holdding our breath', 'holding our breath', 'holdding ours breath', 'holding ours breath', 'holdding their breath', 'holding their breath', 'holdding theirs breath', 'holding theirs breath'

• 12 вариантов прошедшего времени, совпадающего с past participle: 'held my breath', 'held mine breath', 'held your breath', 'held yours breath', 'held his breath', 'held her breath', 'held hers breath', 'held its breath', 'held our breath', 'held ours breath', 'held their breath', 'held theirs breath'

Такие случаи довольно редки. Как уже говорилось, на весь 5-тысячный словарь нашлось всего 662 строки с неправильными глаголами. Что касается остальных сложных случаев, то в словаре 91 терм с притяжательными местоимениями, 31 – с подстановками somebody/something и 61 совмещает в себе и неправильный глагол, и какую-либо подстановку.

Поиск по тексту

Наконец приступаем к анализу оригинального текста, чтобы найти в нем пропущенные вхождения термов. Считаем датафрейм из Excel, не забывая, что заданные в списке columns заголовки столбцов должны фигурировать в первой строке листа Excel.

excel_data = pd.read_excel(pathlib.Path('c:/', 'ALL', 'LotR', 'словарь Толкиена сведенный.xlsx'), dtype = str)
df = pd.DataFrame(excel_data, columns=['Word', 'Russian', 'Chapters', 'IrrVerb'])

Прежде чем работать с текстом романа, возьмем на себя смелость слегка подправить великого автора, изменив нумерацию глав на сквозную. Вместо двух книг по 12 и 10 глав соответственно получится одна с 22-мя главами.

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

f = open(pathlib.Path('c:/', 'ALL', 'LotR', 'Fellowship.txt'))
text = f.read().replace('\n', ' ').replace('\t', ' ').replace('\r', ' ').replace('Mr. ', 'Mr')  # учтет Mr.Baggins

Теперь разобьем текст по главам.

lotr = []
text = re.split('Chapter\s\d+', text)

Тогда в 0-м элементе списка будет предисловие, в 1-м - глава 1 и т.д., то есть индексы будут соответствовать реальным номерам глав, что очень удобно.

for chapter in text:
    lotr.append(re.split('[\.?!]', chapter))

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

    ch = list(map(int, vec[0].split(',')))

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

    word = vec[1]
    if word[-1:] == "!" or word[-1:] == "?":
        forms = [word]

Для любого другого терма начнем с проверки, входит ли в него неправильный глагол, то есть заполнен ли соответствующий столбец (isnan()). Для неправильного глагола выделим 2-ю и 3-ю формы, которые могут различаться или совпадать.

    else:
        is_irrverb = False if isinstance(vec[2], float) and math.isnan(vec[2]) else True
        if is_irrverb:
            pos = vec[2].find(", ")
            if pos >= 0:
                past = vec[2][:pos]
                past_participle = vec[2][pos + 2:]
            else:
                past = past_participle = vec[2]

Произведем замены с помощью функции template_replace(), получим список словоформ. Проспрягаем каждый элемент этого списка.

        forms = template_replace(word)
        forms = forms + sum(list(map(lambda f: generate_verbs(f, is_irrverb), forms)), [])

Для неправильных глаголов отдельно произведем замены для 2-й и 3-й форм.

        if is_irrverb:
            forms = forms + template_replace(past)
            if past_participle != past:
                forms = forms + template_replace(past_participle)

Затем ищем каждую словоформу в каждой главе кроме ранее найденных глав, содержащихся в старом списке ch. Для этого используем функцию filter(), передав ей лямбда-функцию, которая будет обрабатывать каждое предложение. Поиск производится по регулярному выражению \b{f}, где \b - граница слова, а f - словоформа. Как уже говорилось, указание левой границы слова позволяет реализовать поиск с джокером на конце подстроки. Несмотря на весь написанный ранее код, мы все еще нуждаемся в этом нехитром приеме, так как флексии никто не отменял. Кроме того, от регулярного выражения мы никуда не денемся, так как ранее заменяли somebody/something на \S+.

    for f in forms:
        for i in range(1, len(lotr)): # 0-ю главу (предисловие) пока пропускаем
            if not i in ch:
                match = list(filter(lambda sentence: re.search(rf'\b{f}', sentence, flags=re.IGNORECASE), lotr[i]))
                if match:
                    ch.append(i)

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

Новые номера глав сохраняются в тот же список ch, который в конце концов сортируется и возвращается.

    ch.sort()
    return ch

Полный код функции check_chapters() выглядит следующим образом.

def check_chapters(vec):
    global lotr
    ch = list(map(int, vec[0].split(',')))

    word = vec[1]
    if word[-1:] == "!" or word[-1:] == "?":
        forms = [word]
    else:
        is_irrverb = False if isinstance(vec[2], float) and math.isnan(vec[2]) else True

        if is_irrverb:
            pos = vec[2].find(", ")
            if pos >= 0:
                past = vec[2][:pos]
                past_participle = vec[2][pos + 2:]
            else:
                past = past_participle = vec[2]
        forms = template_replace(word)

        forms = forms + sum(list(map(lambda f: generate_verbs(f, is_irrverb), forms)), [])
        if is_irrverb:
            forms = forms + template_replace(past)
            if past_participle != past:
                forms = forms + template_replace(past_participle)

    for f in forms:
        for i in range(1, len(lotr)): # 0-ю главу (предисловие) пока пропускаем
            if not i in ch:
                match = list(filter(lambda sentence: re.search(rf'\b{f}', sentence, flags=re.IGNORECASE), lotr[i]))
                if match:
                    ch.append(i)

    ch.sort()
    return ch

Осталось только применить эту функцию к датафрейму, сохранив результат в новый столбец New chapters:

df['New chapters'] = df[['Chapters', 'Word', 'IrrVerb']].apply(check_chapters, axis=1)
df.to_excel(pathlib.Path('c:/', 'ALL', 'LotR', 'словарь Толкиена сведенный.xlsx'))

Тестирование

Для тестирования была произведена выборка наиболее сложных термов – с неправильными глаголами и подстановками.

test = df[['Chapters', 'Word', 'IrrVerb']]
test = test[(test['IrrVerb'].str.len() > 0) & (test['Word'].str.contains("one's") | test['Word'].str.contains("something") | test['Word'].str.contains("somebody"))]
print(test.apply(check_chapters, axis=1))

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

Таким образом, в большинстве случаев словоформы обрабатываются корректно.

Итоги

Учитывая вышеприведенный расчет со 120 словоформами, порожденными одной строкой словаря, поиск всех вхождений вместо первого, наличие регулярных выражений и громоздкость решения в целом, я не ожидала от программы быстрых результатов. Однако на ноутбуке с 4-ядерным Intel i5-8265U и 8 Гб ОЗУ словарь из 5 тыс. строк был проработан за 1.187 секунд. В итоге найдены 3.330 новых вхождений в дополнение к прежним 10.482, записанным вручную.

Вот так несколько десятков строк кода показали вполне удовлетворительные результаты для полнотекстового поиска с поддержкой морфологии английского языка. Программа работает достаточно корректно и быстро. Конечно, она не лишена недостатков - не застрахована от ложных срабатываний, не учтет флексию в середине многословного терма (например, takes his advice). Однако с поставленной задачей успешно справилась.