Узнайте о Soundex, фонетическом алгоритме проверки орфографии.
Проверка орфографии — одна из важнейших частей любой поисковой системы, играющая важную роль в исправлении распространенных опечаток и повышении релевантности результатов поиска.
Может быть много причин, по которым пользователь может ввести неправильное написание. Сюда входят опечатки на клавиатуре (например, «the» и «thw»), фонетические ошибки (например, «wiskie» и «whisky»), неправильно объединенные слова (например, «youare» и «you are») и многое другое. Для решения этих проблем поисковые системы обычно используют комбинацию алгоритмов, нацеленных на разные проблемы, что приводит к наилучшему результату.
Однако в этой статье мы сосредоточимся только на фонетическом алгоритме проверки орфографии под названием Soundex. Итак, без лишних слов, начнем.
Как работают фонетические алгоритмы проверки орфографии?
В основе фонетических алгоритмов проверки орфографии лежит фонетическое представление слов. Эти алгоритмы нацелены на сопоставление слов с похожим произношением или фонетическими характеристиками с такими же или похожими представлениями. Таким образом, они позволяют выявлять и исправлять орфографические ошибки на основе их фонетического сходства, а не их точной текстовой формы. Но как это достигается?
Важнейшей частью всего процесса является создание фонетического хеша слова, а затем сравнение его с остальными. В то время как разные алгоритмы производят разные хэши, Soundex, например, генерирует четырехбуквенный код.
Следуйте приведенному ниже алгоритму, чтобы понять, как с помощью Soundex генерируется фонетический хэш слова.
Алгоритм Soundex, как вы можете заметить, удивительно прост, но способен обрабатывать сложные случаи. Чтобы проиллюстрировать его эффективность, давайте рассмотрим пример с названием бренда Skullcandy и его различными фонетическими ошибками. Ниже приведено изображение для того же самого.
В этом примере только одно написание (skullcandy) было правильным, а два других (scullkendy и skalkandy) звучали одинаково, но не правильно. Интересно, что, несмотря на их различия, все три написания имеют один и тот же фонетический хэш (S425), и, следовательно, они будут рассматриваться как одно и то же слово.
Вы можете использовать этот онлайн-инструмент, если хотите поиграть с алгоритмом.
Как все это сочетается?
Этот раздел даст вам краткое представление о том, как любой алгоритм проверки орфографии используется в реальной поисковой системе.
Когда пользователь отправляет запрос, он изначально делится на отдельные токены, обычно на основе пробелов. Например, токенизация фразы «Livais jeens» даст список токенов, содержащий [«Livais», «jeens»].
После токенизации мы вычисляем фонетический хэш для каждого токена. Например, при использовании Soundex результирующие хэши будут ["L120", "J520"].
Теперь идет немного более сложный шаг. Для каждого токена мы ищем инвертированный индекс, чтобы получить список слов, которые имеют один и тот же фонетический хэш. Этот шаг предварительно вычисляется, чтобы избежать дополнительных вычислительных затрат во время выполнения. Стоит отметить, что на этом этапе, известном как генерация кандидатов, может появиться несколько кандидатов для каждого хеш-токена.
Реальная проблема заключается в ранжировании этих кандидатов и выборе наиболее подходящего. Как правило, этот процесс ранжирования, называемый выбором кандидатов, облегчается другим компонентом поисковой системы.
Рассмотрение рейтинговой части выходит за рамки этой статьи. Однако в качестве общего обзора базовый подход предполагает наличие списка всех возможных слов в словаре вместе с их соответствующими частотами, хранящимися в базе данных. Эти данные могут помочь в сортировке списка слов-кандидатов по частоте появления, что во многих случаях дает удовлетворительные результаты.
И все, если все работает нормально, то, скорее всего, в качестве исправленного запроса на поисковую фразу «Livais jeens» вы получите «джинсы Levis».
Ограничения
Как мы видели в предыдущих разделах, Soundex — это очень простой, но мощный алгоритм фонетической коррекции орфографии. Тем не менее, он страдает от некоторых ограничений. Некоторые из них перечислены ниже:
- Он ориентирован в первую очередь на английский язык. Приведение его в соответствие с фонетическими правилами и характеристиками целевого языка может потребовать значительных усилий и итераций.
- Из-за сохранения первой буквы некоторые похожие по звучанию имена могут иметь разные фонетические хэши. Например, «Клара как C460» и «Клара как K460».
- Коды Soundex имеют фиксированную длину и могут неадекватно представлять более длинные или короткие имена. Более длинные имена могут быть усечены, что может привести к потере информации, а более короткие имена могут не давать достаточной фонетической детализации.
Заключительные примечания
Создание системы проверки орфографии требует гораздо больше, чем описано в этой статье. Но понимание его основ может помочь вам самостоятельно исследовать мир информационно-поисковых систем. Ниже приведены некоторые ресурсы, которые помогут вам углубиться в это.
https://discovery.ucl.ac.uk/id/eprint/10065716/1/DEXA-2014-FPSS.pdf
https://nlp.stanford.edu/IR-book/html/htmledition/phonetic-correction-1.html
https://www.openbookproject.net/py4fun/soundex/soundex.html
Надеюсь, вы сегодня узнали что-то новое.
А вы знали, что рассказу истории можно хлопнуть до 50 раз? Не забудьте похлопать и поделиться, если вам понравилась эта статья. Удачного кодирования!
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
