Как стать автором
Обновить

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

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров9.2K

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

Любимая книга, снятая на любимый светосильный объектив
Любимая книга, снятая на любимый светосильный объектив

В первой версии 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 формы инфинитива, двух вариантов герундия, а также прошедшего времени и причастия прошедшего времени, итого

24*5=120

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

Впрочем, мой словарь не содержит настолько сложных случаев. Вот более характерный пример – 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))

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

Терм

Найденные вхождения

find one's way

Chapter 12:  We could perhaps find our way through and come round to Rivendell from the north; but it would take too long, for I do not know the way, and our food would not last

Chapter 2: He found his way into Mirkwood, as one would expect

make one's way

Chapter 3:  My plan was to leave the Shire secretly, and make my way to Rivendell; but now my footsteps are dogged, before ever I get to Buckland

Chapter 16:  Make your ways to places where you can find grass, and so come in time to Elrond's house, or wherever you wish to go

Chapter 6:  Coming to the opening they found that they had made their way down through a cleft in a high sleep bank, almost a cliff

Chapter 11:  Merry's ponies had escaped altogether, and eventually (having a good deal of sense) they made their way to the Downs in search of Fatty Lumpkin

Chapter 12:  They made their way slowly and cautiously round the south-western slopes of the hill, and came in a little while to the edge of the Road

make up one's mind

Chapter 10:  You must make up your mind

Chapter 19:  But before Sam could make up his mind what it was that he saw, the light faded; and now he thought he saw Frodo with a pale face lying fast asleep under a great dark cliff

Chapter 16:  The eastern arch will probably prove to be the way that we must take; but before we make up our minds we ought to look about us

Chapter 22:  'Yet we must needs make up our minds without his aid

Chapter 4:  I am leaving the Shire as soon as ever I can – in fact I have made up my mind now not even to wait a day at Crickhollow, if it can be helped

Chapter 21: Sam had long ago made up his mind that, though boats were maybe not as dangerous as he had been brought up to believe, they were far more uncomfortable than even he had imagined

one's heart sink

Chapter 11:  'It is getting late, and I don't like this hole: it makes my heart sink somehow

Chapter 14: "  '"The Shire," I said; but my heart sank

shake one's head

Chapter 2:   ‘They are sailing, sailing, sailing over the Sea, they are going into the West and leaving us,’ said Sam, half chanting the words, shaking his head sadly and solemnly

Chapter 4:  Too near the River,’ he said, shaking his head

Chapter 9: '  ‘There's some mistake somewhere,' said Butterbur, shaking his head

Chapter 14: ' he said, shaking his head

Chapter 16:  'I am too weary to decide,' he said, shaking his head

Chapter 12: '  When he heard what Frodo had to tell, he became full of concern, and shook his head and sighed

Chapter 15:   Gimli looked up and shook his head

Chapter 22: Sam, who had been watching his master with great concern, shook his head and muttered: 'Plain as a pikestaff it is, but it's no good Sam Gamgee putting in his spoke just now

sleep on something

Chapter 3:  ‘Well, see you later – the day after tomorrow, if you don’t go to sleep on the way

Chapter 13:  His head seemed sunk in sleep on his breast, and a fold of his dark cloak was drawn over his face

Chapter 18:  I cannot sleep on a perch

spring to one's feet

Chapter 2: ’ cried Gandalf, springing to his feet

Chapter 11: ' asked Frodo, springing to his feet

Chapter 14: ' cried Frodo in amazement, springing to his feet, as if he expected the Ring to be demanded at once

Chapter 16:   With a suddenness that startled them all the wizard sprang to his feet

Chapter 8:   The hobbits sprang to their feet in alarm, and ran to the western rim

Chapter 9:   The local hobbits stared in amazement, and then sprang to their feet and shouted for Barliman

take one's advice

Chapter 3:  If I take your advice I may not see Gandalf for a long while, and I ought to know what is the danger that pursues me

Chapter 11:  When they saw them they were glad that they had taken his advice: the windows had been forced open and were swinging, and the curtains were flapping; the beds were tossed about, and the bolsters slashed and flung upon the floor; the brown mat was torn to pieces

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

Итоги

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

Для сравнения: 4-й столбец содержит старый список вхождений, 6-й – новый
Для сравнения: 4-й столбец содержит старый список вхождений, 6-й – новый

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

Теги:
Хабы:
Всего голосов 9: ↑8 и ↓1+7
Комментарии3

Публикации

Истории

Работа

Data Scientist
87 вакансий
Python разработчик
129 вакансий

Ближайшие события

Конференция HR API 2024
Дата14 – 15 июня
Время10:00 – 18:00
Место
Санкт-ПетербургОнлайн
Конференция «IT IS CONF 2024»
Дата20 июня
Время09:00 – 19:00
Место
Екатеринбург
Summer Merge
Дата28 – 30 июня
Время11:00
Место
Ульяновская область