Необходимость идентификации слов поискового запроса непосредственно вытекает из задачи поиска по базе текстов.
Чтобы не запутаться, в данной публикации будем использовать некоторые термины в следующих контекстах:
- информационная база – множество текстов, в которых бы будет выполнять поиск
- поисковый запрос – слово или словосочетание, которые будут искаться в информационной базе
- эффективность поиска – доля найденных текстов (фрагментов текста) соответствующих поисковому запросу в общей массе текстов информационной базы.
- поисковая система – совокупность программных средств, которая выполняет поиск в информационной базе. Включает логику поиска, которая определяет эффективность поиска.
Цель поиска – найти тексты (фрагменты текстов) из информационной базы, которые максимально точно соответствуют информационному смыслу поискового запроса. Исходя из цели, поиск “как есть”, т.е. с таким же написанием слов и их порядком в словосочетаниях наверняка даст низкую эффективность, хотя бы потому, что: 1) слово может быть написано с ошибкой – в этом случае оно не будет найдено. 2) поскольку целью является поиск близких по смыслу текстов (фрагментов), необходимо также учитывать все формы слов поискового запроса, а сделать это при поиске “как есть” невозможно.
Поэтому поисковые системы применяют другой подход. Прежде всего для поисковой системы задается словарь значимых слов – такие слова, которые с учетом их взаимного расположение в предложении полностью сохраняют информационный смысл предложения. Слова, не попавшие в словарь считаются незначимыми, при поиске не учитываются.
На этапе задания словаря необходимо решить следующие задачи
- определить, какие слова считать значимыми и включить их в словарь. Общий подход к решению задачи такой – либо используют уже существующие авторитетные словари общей лексики для каждого языка (например, для русского языка – это словарь Зализняка). Либо, если тематика текстов информационной базы достаточно специфична и имеет много не общеупотребимых слов (например, профессиональных терминов), отсутствующих в словарях общей лексики, то сначала из основе информационной базы (ее репрезентативной выборки) создают частотный словарь содержащихся в ней слов, уже на основании которого выделяют значимые слова и, например, дополняют ими существующий словарь. При анализе частотного словаря слов следует учитывать следующее 1) слова, которые встречаются практически во всех текстах не должны включаться в список значимых слов (поскольку они никак уникально не выделяют текст в котором содержатся) – это стоп-слова, их наоборот нужно исключать при поиске. К стоп-словам также относятся предлоги и союзы. Редкие слова тоже не имеет смысла включать в словарь значимых слов. Кроме того, на данном этапе необходимо, как правило, позаботиться о синонимах, аббревиатура, тезаурусе
2. Если слово считается значимым, то и все его формы также считаются значимыми и должны быть включены в словарь. Однако, это увеличивает размер словаря, а значит 1) будет замедлять скорость поиска и 2) различные формы слова будут идентифицироваться по-разному, хотя имеют одинаковый информационный смысл. Как лучше всего учитывать словоформы? Один из выходов – использовать нормальную форму слова и правила образования слов. Очевидно, что понятие “нормальная форма слова” и и правила образования словоформ для каждого языка разные. Например, для русского языка нормальная форма слова а) для существительных – именительный падеж единственного числа, б) для прилагательных – именительный падеж единственного числа мужского рода, в) для глаголов, причастий и деепричастий – глагол в инфинитиве. В настоящее время реализовано несколько вариантов синтаксиса описания правил образования слов для любого языка. Один из наиболее распространенных- ispell. Этот синтаксис достаточно компактен, словари ispell разработаны для многих языков и есть в свободном доступе для скачивания, поэтому, возможно, являются достаточно хорошим решением для задачи образования словоформ. Итак, создав словарь значимых слов, добавив в него (по необходимости) специальную терминологию, аббревиатуры, тезаурус и имея правила образования словоформ. можно эффективно идентифицировать слова поискового запроса… Если только слова в поисковом запросе или текстах информационной базы написаны без ошибок
3. Но ошибки встречаются достаточно часто, значит необходимо распознавать слова с учетом ошибок. Принципиальных решений данной задачи два, эффективность использования того или иного зависит от типа допущенной ошибки. а) применение одного из алгоритмов (Леванштейна, триграммного индекса, …) для нахождения самого близкого по написанию слова из словаря к исходному слову, написанному с ошибкой. Данный способ не привязан к какому -либо языку и конкретному словарю, однако, достаточно часто приводит к неопределенности выбора самого схожего слова, разрешить которую в автоматическом режиме достаточно сложно. б) использование эвристических правил поиска и корректировки ошибок. Алгоритмы данного способа наоборот используют закономерности допускаемых ошибок в словах конкретного словаря. Это позволяет им более точно распознавать допущенные ошибки
Идея: на основе существующих общесловарных словарей ispell разработать инструмент идентификации слов поисковой фразы с учетом грамматических ошибок.
Реализация идеи описана здесь, пример реализации – здесь
В данной публикации предложен один из вариантов идентификации слов при анализе текстов с помощью Python.
Задача: проверить, принадлежит ли заданное слово одному или нескольким имеющихся в нашем распоряжении словарям. Или же это слово, которого нет ни в одном из словарей? И, естественно, мы не знаем на каком языке будет написано проверяемое слово (предполагаем только, что на одном из наиболее востребованных). Данное ограничение определило главное требование к задаче – у нас должны быть словари (бесплатные) для различных, наиболее востребованных языках и простая возможность их подключения для поиска. Выбор оказался невелик – ispell, со всеми его преимуществами:
- свободный доступ для скачивания словарей для нескольких десятков языков
- сочетание значительного словарного запаса и компактность хранения. Например, словарь русского языка содержит более 120 тыс. уникальных форм, позволяющих генерировать более 4,1 млн. словоформ, и одновременно с этим занимает 1,6 МБ в распакованном виде.
Структура словаря позволяет выполнять идентификацию слова по всем словоформам О формате словаря ispell можно узнать отсюда
Осталось только проверить правильность нашего выбора. Для этого был написан вот этот скрипт.
Все возможности работы со словарями реализованы в виде методов класса: загрузка словаря для любого языка, составленного в синтаксисе ispell. Конвертация словаря базу типа {‘key’: ‘value’} в один из форматов по выбору ‘shelve’ или ‘cdb’ (для формата cdb необходимо подключение библиотек ‘cdb’ и simplejson)
my_dict=Dict('ru_RU.dic', 'ru_RU.aff')
my_dict.toShelve('russian')
my_dict=Dict('en_US.dic', 'en_US.aff')
my_dict.toCdb('english')
Поиск слова по одному или нескольким словарям
my_dict=Dict(dict_name='russian', db_type='shelve')
if __name__ == "__main__":
myDict=Dict(dict_name='russian', db_type='cdb')
myDict.addDict(dict_name='english', db_type='shelve')
myDict.addDict(dict_name='spain', db_type='cdb')
words=[u'абонированного', u'papering', u'abarañar']
for word in words:
word=myDict.findWord(word)
print 'word:', word[0]['word'], '; dict:', word[0]['dict']
Тестирование эффективности проводилось по трем показателям скорость работы скрипта объем занимаемой оперативной памяти Для оценки использования словарей ispell как инструмента идентификации в качестве исходного текста был взят Код скрипта можно скачать на Github там.же – описание структуры базы