Ваш браузер устарел и не обеспечивает полноценную и безопасную работу с сайтом.
Установите актуальную версию вашего браузера или одну из современных альтернатив.
Графовое представление информации широко применятеся в различных сферах, например, при моделировании, при решении задач оптимизации. Одной из перспективных областей применеия графов является искуственный интеллект, направленный на обработку естественного языка. Язык, на котором общаются люди, состоит из слов, причем слово является минимальной осмысленной единицей, одно слово можно рассматривать отдельно от всего, что его окружает: от знаков препинания, от контекста, от других слов.
Слова часто бывают очень похожими как по написанию, так и по произношению (например, посветить и посвятить), что затрудняет обработку компьютерным разумом. «Похожесть» слов определяется специальными метриками, одна из которых — расстояние Левенштейна (редакционное расстояние). Цель данной работы — рассмотреть возможности графового представления при анализе схожести слов на примере визуализации взаимосвязей между словами на основе расстояния Левенштейна.
Задачи работы:
Неориентированным (ориентированным) графом называется пара множеств
где V — конечное множество, элементы которого называются вершинами; E — множество (упорядоченных) пар на V, элементы которого называются ребрами (дугами).
Пара , где — граф; ω(e) — весовая функция (функция разметки), ставящая в соответствие каждому ребру (дуге) e ∈ E некоторое значение, например, время прохождения по дуге или расстояние между вершинами, называется взвешенным (размеченным графом) [1].
На рис. 1, 2 представлены примеры неориентированного и ориентированного графов соответственно.
С помощью графов возможно придать новую интуитивно понятную структуру привычным задачам, причём графовое представление не только отлично подходит для математических вычислений, но и поощряет пространственное мышление. Графы позволяют по-новому взглянуть на решение некоторых задач.
Графовые структуры это математические структуры, используемые для представления отношений между двумя или более объектами. Эти структуры предоставляют различным дисциплинам конкретный механизм для выражения, манипулирования и изучения отношений.
В геоинформационных системах связи между объектами на карте традиционно представляются в виде графов (по [2] — структур «узел — связь»), при этом вершинами графа являются различные географические объекты (например, города, перекрестки), дуги выражают некоторую взаимосвязь объектов (например, время в пути). Такое представление имеет значительное преимущество в контексте навигации, так как путь в графе легко выражается через серию решений в узлах этого графа.
Область данных данного проекта — лингвистика. Понятия лингвистики и графов во многом совпадают. Структуры графов обладают многими чертами, сходными с теми, которые можно найти в человеческом языке.
Согласно определению, структура графа состоит из двух меньших единиц, а именно вершин и ребер. Первое естественное отображение состоит в том, что узел и вершина для теории графов — то же, что морфема (или слово) для лингвистики. Конструкция графа состоит из двух строительных блоков, подобно тому, как предложения строятся из морфологических строительных блоков. Второе отображение возникает из наблюдения, что граф выполняет ту же функцию, что и понятие предложения в лингвистическом синтаксисе. Граф и предложение являются более крупной единицей выражения смысла.
Функция инцидентности определяет строгие ограничения на то, как можно расположить единицы графа. Явно ребро разрешено только для соединения вершин, это означает, что ребро не может соединяться с другим ребром. Следовательно, функция инцидентности выполняет ту же роль, что и лингвистический синтаксис, определяя правила для языка.
Также с помощью графа можно отобразить семантическую близость слов в виде сети, т. е. показать в сочетании с какими словами и как часто используется конкретное слово в конкретном языке.
В этом графе вершины – слова, ребра формируют пару слов, а длина ребер отображает частоту использования этой пары в языке. Такую сеть можно построить на основе заготовленной векторной семантической модели — она сохраняет информацию о частых и редких контекстах слова в виде упорядоченного списка чисел.
В данной работе в вершинах графа будут находиться слова, а веса ребер графа будут заданы метрикой между ними — редакционным расстоянием. В результате построения такого графа можно будет увидеть, какие слова наиболее схожи друг с другом, что поможет исправлять большинство орфографических ошибок, также будет видно какие слова могут быть с большой вероятностью перепутаны.
Расстояние Левенштейна между двумя строками — это минимальное количество редакторских операций — операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую [3].
Указанные операции имеют цену (штраф), при этом в общем случае цены операций могут не совпадать. В этой работе будут рассматриваться алгоритмы, в которых цены редакторских операций одинаковы и равны 1. Задача поиска расстояния Левенштейна предполагает поиск последовательности применения редакторских операций для преобразования некоторой строки в некоторую другую с минимально возможной суммарной ценой операций в последовательности.
Рассмотрим две строки S1 и S2, а также строки S1' и S2', где последние две получены путем отбрасывания последних символов в строках S1 и S2 соответственно. Тогда редакционное расстояние между строками S1 и S2 выражается одним из следующих способов:
Минимальной ценой преобразования S1 в S2 будет минимальное значение из четырех названных выше. Если на каждом шаге преобразований редакторскими операциями выбирать наименьший по цене вариант, то в итоге получим минимальную цену для преобразования строки S1 и S2. При этом целесообразно начать с пустых строк, так как цена преобразования одной пустой строки в другую очевидна и равна 0. Кроме этого, тривиальна и цена преобразования пустой строки в строку, состоящую из одного символа (и обратно): цена эта равна 1.
Пусть mij — это редакторское расстояние от подстроки S1 до символа i включительно до подстроки S2 до символа j включительно. При этом для удобства нумерацию строк и столбцов матрицы будем вести с нуля. Тогда, в соответствии со сказанным выше, если ST[k] — k-й слева символ строки ST, то
В качестве источника данных предполагается использовать словари русского языка, для ограничения количества слов — вершин графа — планируется применить один из вариантов:
Удобным способом представления описанных действий по поиску расстояния Левенштейна является матрица. Примем, что каждая строка матрицы 𝑀 соответствует одному символу строки 𝑆1, а каждый столбец — одному символу строки 𝑆2, добавив при этом одну строку и один столбец для пустых строк, а в ячейке с индексами 𝑖,𝑗 содержится значение 𝑚𝑖𝑗, рассчитанное по формуле выше.
Таким образом, задача поиска растояния Левенштейна сводится к заполнению матрицы 𝑀 по формулам выше, а ответом будет значение 𝑚𝐿1, 𝐿2, где 𝐿1, 𝐿2 — длины строк 𝑆1 и 𝑆2 соответственно. Ниже приводится реализация на языке Python (рис. 3).
Первый эксперимент. Каждый из авторов работы выбрал ключевое слово, в список вошли: «вода», «снег», «работа», «друг», что «сад», «бег». Были подобраны однокоренные слова к каждому из слов и вычислены редакционные расстояния между всеми парами слов в каждой из семи групп. Также были вычислены расстояния Левенштейна между всеми парами ключевых слов. Для визуализации графа использован алгоритм раскладки Камада — Каваи, суть которого заключается в представлении графа как механической системы, состоящей из нескольких прожин, и минимизации энергии этой системы [9]. Использованы библиотеки networkx [10] и matplotlib [11].
В результате получен граф, который был оформлен к приближающемуся Новому году: ребра покрашены в зеленый цвет, вершины выполнены в виде елочных украшений — шаров. Каждый шар имеет свою бирку, на которой указано соответствующее ему слово. Результат приводится ниже на рис. 4. и представлен на Выставке алгоритмических полотен, разработанных стуентами МГТУ им. Н.Э. Баумана в ходе практикума по обработке и визуализации графов, проводимой в Актовом зале ГУК МГТУ 16 декабря 2022 г. Название: «Новогодний лес Левенштейна».
Эксперимент на суперкомпьютере «Тераграф». Следующий этап в исследовании — организация построения и визуализации графа на отечественном аппаратном обеспечении. В МГТУ им. Н.Э. Баумана созданы первые в мире микропроцессор Леонард Эйлер (Leonhard) и суперкомпьютер «Тераграф», в которых на аппаратном уровне реализован набор команд дискретной математики DISC (Discrete Mathematics Instruction Set computer). Суперкомпьютер «Тераграф» предназначен для хранения и обработки графов сверхбольшой размерности [12].
Граф из эксперимента выше был построен и визуализирован с использованиям микропроцессора Леонард Эйлер. Результат приводится на рис. 5, где отчетливо видны вершины, соответствующие ключевым словам, выбранным авторами проекта.
Поисковые системы с программным модулем поисковых расширений. Поисковые расширения — это модули, добавляющие в текст запроса пользователя новые слова, связанные с запросом. Это позволяет при ранжировании документов вывести на более высокие позиции документы, содержащие эти добавленные слова.
Автоматический поиск и исправление опечаток текстах. Например, для некорректного слова будет подобрано на выбор пользователя несколько близких по редакционному расстоянию слов.
Распознавание человеческой речи. Рассматриваемое представление информации о редакционных расстояниях можно использовать в голосовых ассистентах для улучшения качества распознания человеческой речи. Например, если человек неразборчиво сказал какое-либо слово, а голосовой помощник его не понял, то по графу можно найти слово максимально близкое к тому, которое произнес человек, и использовать его в ассистенте.
Анализ геномов. Данная технология может применяться и в биоинформатике для сравнения генов, хромосом и белков. Только в этом случае в вершинах графа будут находиться генные последовательности, и тогда, анализируя граф, мы будем иметь возможность сравнивать их.
На основании проделанной работы можно сделать следующий вывод. Графы, построенные на основе расстояния Левенштейна, действительно наглядно демонстрируют похожесть слов и могут быть использованы в различных направлениях информационных технологий, как связанных с обработкой ествественного языка, так и не связанных.
Цель работы была достигнута. Решены следующие задачи:
