Сегментация запросов и исправление орфографии

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

орехи

шоколадные конфеты без орехов

Но машина не сможет этого сделать, если мы их не научим. Вот свидетельство:

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

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

например «Орехи чаколата» или «скоммедмилк»

Здесь мы видим, что шоколадные конфеты написаны неправильно. Но, чтобы исправить это, предварительным условием является идентификация сегментов, то есть границ слов, чтобы в первую очередь иметь входные данные для алгоритма Коррекция орфографии.

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

Здесь мы видим, что алгоритм исправления орфографии зависит от сегментации слова. Итак, давайте сначала посмотрим, как мы можем провести сегментацию:

Сегментация запроса может быть достигнута путем разделения строки несколькими способами. Но подождите, сколько возможных различных композиций может существовать при таком наивном подходе. Фактически, это экспонента, и для слова длины n это {2 ^ (n − 1)} возможных составов, потому что для данной строки будет (n-1) границ. Окончательный список действительной и подлинной композиции запросов будет определяться на основе того, состоит ли композиция из действительных слов и упорядочена или отсортирована на основе наиболее вероятной комбинации слов в запросе, то есть композиции, имеющей наивысшую вероятность. Позже объясню, как эта вероятность будет рассчитываться для каждой композиции. Теперь, при таком наивном подходе, запрос «шоколадные конфеты без орехов» (длина, n = 17) содержит 2¹⁶ = 65 536 композиций. По мере увеличения длины запроса он не масштабируется и требует больших вычислительных мощностей. Для большей эффективности я проанализировал два алгоритма:

Подход к динамическому программированию:

В наивном подходе мы снова и снова выполняли аналогичные вычисления, чтобы найти наиболее вероятный сегмент префикса запроса, который можно запоминать, чтобы повысить сложность с экспоненциальной (O (2 ^ n)) до полиномиальной функции ( O (n²)). Давайте разберемся на примере:

For query: “isit” [Total Segment = 2^3 = 8]
It can be either segmented in 2 parts or 3 parts or 4 parts
Start with 4: [Possible composition = 3C3 = 1]
"i" "s" "i" "t = P(i|'')*P(s|i)*P(i|t)*P(t|i)
Start with 3: [Possible composition = 3C2 = 3]
"i" "s" "it" = P(i|'')*P(s|i)*P(it|s)
"is" "i" "t" = P(is|'')*P(i|is)*P(t|i)
"i" "si" "t" = P(i|'')*P(si|i)(P(t|si)
"Start with 2: [Possible composition = 3C1 = 3] 
"i" "sit" = P(i|'')*P(sit|i)
"is" "it" = P(is|'')*P(it|is)
"isi" "t" = P(isi|'')*P(t|isi)
where P(A|B) is conditional probability of happening of A given that B has already occured. The bigram probability is introduced for more context. Unigram probability can also be used to find the probability of composition.

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

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

P (A) = freq (A) / сумма частот (все слова)

и P (состав) = log (P (word1)) + log (P (word2)) +…. где композиция состоит из word1, word2 и т. д.

потому что наивная байесовская вероятность композиции будет произведением вероятностей независимых слов, то есть P (AB) = P (A) * P (B)

Если слово отсутствует в словаре, то согласно http://norvig.com/ngrams/ch14.pdf

P (A) = 10 / (сумма частот (все слова) * 10 ^ len (A))

Код можно найти здесь: https://github.com/grantjenks/python-wordsegment

Треугольный матричный подход:

Вместо того, чтобы запоминать все композиции префикса запроса, здесь только композиция префикса с наибольшей вероятностью будет перезаписана поверх более низкой вероятности. Этот подход гораздо лучше объяснен здесь: https://towardsdatascience.com/fast-word-segmentation-for-noisy-text-2c2c41f9e8da

Исправление орфографии также может быть выполнено с использованием многих подходов. Но они могут быть очень дорогостоящими. Здесь я рассмотрю два оптимизированных подхода, отличных от наивного подхода:

Подход Питера Норвига: он состоит из генерации кандидатов на расстояние редактирования n с использованием операций вставки, удаления, замены и транспонирования по запросу, предоставляемому на каждой итерации. Затем, модель языка, в которой оценка / вероятность возможных кандидатов, сгенерированных на первом этапе, вычисляется, если она найдена в словаре, и модель ошибки, где слова, не найденные в словаре, пройдут еще одну итерацию вставки. , операции удаления, замены и транспонирования, и снова будет применена языковая модель. Но это очень дорого, так как список кандидатов, созданный при каждом редактировании, будет увеличиваться (54 n +25) раз для каждого слова. Для запроса nutfreechacolatas в нашем примере длина равна 17. Таким образом, на первой итерации расчета правок будет 54 * 17 + 25 = 943 кандидата. Опять же, во второй итерации каждого кандидата количество возможных кандидатов будет 54 * 943 + 25 = 50 947. Таким образом, он не будет масштабироваться из-за расстояния редактирования и длинного запроса.
Коррекция орфографии с использованием симметричных удалений [SymSpell]: здесь сложность была оптимизирована за счет предварительной обработки перед обработкой запроса онлайн. В производственном сценарии задача предварительной обработки требует времени и зависит от размера словаря, поэтому мы можем создать одноэлементный класс класса коррекции орфографии, который загружает словарь при первой попытке создания его объекта. Основная идея состоит в том, чтобы сгенерировать кандидатов, удалив только символы в запросе из словаря, а также данный запрос, который нужно исправить и встретить посередине. Четыре операции здесь будут выполняться следующим образом:

а) Удаление и вставка: удаление символа из словаря эквивалентно добавлению символа в данный запрос и наоборот.

delete (словарная статья, edit_distance) = входная запись

словарная статья = удалить (входная запись, edit_distance)

б) Подстановка и транспонирование: удаление символа как из словаря, так и из данного запроса эквивалентно замене, а удаление двух последовательных символов как из словаря, так и из данного запроса будет эквивалентно операции транспонирования.

delete (словарная запись, edit_distance) = delete (вводная запись, edit_distance)

В этом подходе нам необходимо рассчитать расстояние редактирования между кандидатами, сгенерированными операцией удаления данного запроса, и словарными словами, также сформированными операцией удаления, поскольку расстояние редактирования может измениться во время одновременного удаления как на стороны. Например, для слова: банк после предварительной обработки в словаре введите bank = ban [Edit distance = 1], а если данный запрос = ”xban”. При удалении данного запроса xban = ban [edit distance = 1], но bank! = Xban, поскольку расстояние редактирования между ними равно 2.

Есть несколько способов расчета расстояний редактирования:

Расстояние Хэмминга: допускает только замену, следовательно, применяется только к строкам одинаковой длины.
Самая длинная общая подпоследовательность (LCS): разрешает только вставку и удаление.
Расстояние Левенштейна: позволяет вставку, удаление, замену, но не транспонирование. то есть переход AC- ›CA будет засчитан как 2 дистанции редактирования путем замены.
Расстояние Дамерау Левенштейна: оно позволяет выполнять все четыре операции, которые мы выполняем для создания кандидатов. Фактически, этот алгоритм имеет два варианта: a) Ограниченное расстояние Дамерау-Левенштейна (алгоритм оптимального выравнивания строк): смежная транспозиция считается как 1 редактирование, но подстроки нельзя редактировать более одного раза: ed (CA, ABC) = 3 с двумя заменами (CA- ›AC) и одной вставкой (AC-› ABC). б) Истинное расстояние Дамерау-Левенштейна: смежное транспонирование считается как 1 редактирование, подстроки можно редактировать более одного раза: ed (CA, ABC) = 2 с 1 транспонированием (CA- ›AC) и 1 вставкой AC-› ABC. Последний уже реализуется.

Код для расчета расстояния редактирования с использованием расстояния True Damerau-Levenshtein: можно найти здесь: https://github.com/mammothb/symspellpy/blob/master/symspellpy/editdistance.py

Здесь вместо использования двумерного DP для расчета расстояния редактирования используются два одномерных массива, размер которых равен длине запроса. Здесь сделан еще один уровень оптимизации с точки зрения пространственной сложности. Подробный обзор можно найти здесь: https://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm-2

Этот алгоритм оптимизирован и имеет постоянное время сложности. Все возможные удаления слов из словаря хешируются и индексируются со списком их исходных слов, чтобы ускорить поиск. Словарь был создан с использованием трех источников: 1. Торговые марки продуктов, 2. Отображаемые названия продуктов, 3. Первые n тысяч ключевых слов, по которым выполнялся поиск ранее.

Для нашего варианта использования в словаре содержится около 350 тыс. Слов, длина префикса 7 используется для генерации кандидатов и занимает в среднем 5 мс для запроса средней длины 8 символов.

Спасибо за прочтение. Пожалуйста, прочтите предыдущие истории, чтобы узнать больше, и следите за новостями.

Использованная литература:

Сегментация запросов и исправление орфографии

Подход к динамическому программированию:

Треугольный матричный подход:

Вопросы по теме