Знакомство с BK-деревом и расстоянием Левенштейна
Материалом с подробностями о реализации средства проверки и исправления орфографии кхмерского языка, основного в Камбодже, делимся к старту флагманского курса по Data Science.
В попытке реализовать проверку и исправление орфографии, я наткнулся на популярный метод, основанный на двух концепциях из области орфографии: редакционное расстояние (также известное как расстояние Левенштейна) и BK-дерево. Итак, обсудим эти концепции и их недостатки, а также поделимся разработанной на их основе реализацией средства проверки орфографии кхмерского языка на Python.
II. Редакционное расстояние (или расстояние Левенштейна)
Редакционное расстояние — это минимальное количество шагов/операций, необходимых для преобразования одной строки в другую. Самый популярный метод расчёта — расстояние Левенштейна, предложенное советским математиком Владимиром Левенштейном. Его подход учитывает три типа строковых операций при редактировании: вставка, удаление и подстановка/замена. В контексте проверки орфографии редакционное расстояние позволяет измерить, "насколько отличаются" два слова друг от друга.
Алгоритм
Рассчитать редакционное расстояние эффективно можно с помощью динамического программирования. Оно использует матрицу, представленную двумерным массивом, для хранения временного расстояния между подстроками, чтобы сократить затраты на вычисления. Давайте посмотрим, как рассчитать редакционное расстояние между“កាល” и "ក្បាល".
Создать пустой 2D-массив размера (len(word1) + 1, len(word2) +1).
Шаг 2. Заполнить ячейки в первых строках их индексом столбца.
Шаг 3. Заполнить ячейки в первых столбцах их индексом строки.
Шаг 4. В позиции (1, 1) мы смотрим на символы обоих слов в этой позиции: word1 (ក) и word2 (ក). Поскольку они одинаковы, мы устанавливаем текущее значение ячейки как значение соседней сверху слева от неё. Значит, значение ячейки (1, 1) становится равным 0. Затем мы переходим к следующему столбцу в строке 1.
Шаг 5. В позиции (1, 2) мы снова сравниваем символы обоих слов в позиции: word1 (ក) и word2 (្). На этот раз два символа разные. Итак, значение текущей ячейки равно min([left, top, top-left]) + 1. Повторяем шаги 4 и 5 для оставшихся ячеек.
Шаг 6. После заполнения всех ячеек, минимальное редакционное расстояние — это нижние правые ячейки 2D-матрицы, а значит, минимальное расстояние редактирования между словами "កាល" и "ក្បាល" равно 2.
Кроме того, чтобы узнать, какая комбинация операций редактирования приводит к минимальному редакционному расстоянию, нужно найти кратчайший путь из верхней левой в нижнюю правую ячейку. Конечно, к нижней правой ячейке может быть несколько путей и комбинаций.
III. BK-дерево
Наивный подход к созданию средства проверки орфографии — найти редакционное расстояние между словом, предоставленным пользователем, и всеми другими словами в словаре, и выдать слова с наименьшим расстоянием редактирования до этого слова. Однако такой подход потребует времени и расчётов, если словарь обширен. BK-дерево позволит выполнять поиск быстрее, ограничивая количество необходимых сравнений, используя древовидную структуру данных матрицы редакционного расстояния. Каждый узел дерева является словом. Каждое ребро, соединяющее разные узлы, является редакционным расстоянием между этим узлом и его родителем. Чтобы лучше понять BK-дерево, посмотрим на пример построения дерева словаря из 4 слов: {"ស្គម”, “ស្អាត”, “កាល”, “ក្បាល”}. Затем мы пойдём дальше и посмотрим, как мы можем искать в дереве совпадающие узлы.
Алгоритм построения BK-дерева
Шаг 1. Добавьте первое слово "ស្គម" в качестве корневого узла дерева. Затем перейдите к следующему слову "ស្អាត".
Шаг 2. Установите корневой узел в качестве текущего узла. Затем рассчитайте редакционное расстояние между "ស្អាត" и текущим узлом. Итак, dist(ស្អាត, ស្គម) = 3. После этого смотрим на потомков текущего узла. Текущий узел не имеет дочерних элементов, расстояние которых равно dist(ស្អាត, ស្គម), поэтому вставляем "ស្អាត" в качестве дочернего элемента текущего узла. Затем переходим к следующему слову "កាល".
Шаг 3. Установите корневой узел в качестве текущего узла. Затем рассчитайте редакционное расстояние между "កាល" и текущим узлом. Таким образом, мы получаем dist(កាល, ស្គម) = 4. Как и в шаге 2, текущий узел не имеет потомков, расстояние до которых равно dist(កាល, ស្គម), а значит, как дочерний элемент текущего узла вставляем "កាល". Затем переходим к следующему слову "ក្បាល".
Шаг 4. Установите корневой узел в качестве текущего узла. Затем вычислите редакционное расстояние между "ក្បាល" и текущим узлом, что даст dist(ក្បាល, ស្គម) = 4. На этот раз у текущего узла есть дочерний элемент, расстояние до которого равно 4, то есть dist(កាល, ស្គម). В этом сценарии мы назначаем процесс вставки на этот дочерний узел, устанавливая его в качестве текущего узла. После этого мы повторяем процесс вставки с текущим узлом как "កាល", что даст dist(ក្បាល, កាល) = 2. На этом этапе нет дочернего элемента "កាល", расстояние до которого равно dist(ក្បាល, កាល). Значит, как дочерний элемент "កាល" вставляем "ក្បាល".
После построения дерева мы можем искать в нём совпадающие узлы в качестве исправлений слов.
Поиск по BK-дереву
Для поиска в BK-дереве можно применить любой алгоритм поиска в дереве вообще. Я выбрал поиск в глубину. Однако есть одна особенность, которую даёт нам BK-дерево, — это возможность обрезать/пропустить большую часть узлов за счёт того, что просматривать можно только узлы с редакционным расстоянием в пределах определённого порога допуска. В частности, мы смотрим только на дочерние элементы текущего узла, редакционное расстояние которого находится между [dist(word, current_node)-N, dist(word, current_node) + N], где N — уровень допуска.
Давайте посмотрим, что вернётся пользователю, если он введёт слово "កាក" и уровень допуска N = 2.
Шаг 1. Создать пустой стек и пустой список совпадений.
Шаг 2. Добавить корневой узел (ស្គម) в стек.
Шаг 3. Берём узел на вершине стека (ស្គម). После этого находим, что dist(ស្គម, កាក) = 4 > N, а значит, не добавляем его в список совпадений. Затем смотрим на его дочерние элементы "ស្អាត" и "កាល". Для каждого потомка если dist(ស្គម, កាក) — 2 ≤ dist(child, ស្គម) ≤ dist(ស្គម, កាក) + 2, то добавляем его в стек. В этом случае в стек добавляются как "ស្អាត", так и "កាល", поскольку 2 ≤ dist(ស្អាត, ស្គម) = 3 ≤ 6 и 2 ≤ dist(កាល, ស្គម) = 4 ≤ 6.
Шаг 4. Берём узел на вершине стека (កាល). Тогда dist(កាល, កាក) = 1 ≤ N. Поэтому добавляем его в список совпадений. Cнова находим потомков "កាល", которые можно добавить в стек, но теперь можно добавить только "ក្បាល", поскольку -1 ≤ dist(ក្បាល, កាល) = 2 ≤ 3.
Шаг 5. Берём узел на вершине стека (ក្បាល). Тогда dist(ក្បាល, កាក) = 3 > N, значит, не добавляем его в список совпадений. Поскольку у "ក្បាល" нет дочерних элементов, мы не добавляем в стек больше узлов.
Шаг 6. Берём узел на вершине стека (ស្អាត). Тогда dist(ស្អាត, កាក) = 4 > N. Следовательно, мы не добавляем его в список совпадений. Поскольку у "ស្អាត" нет дочерних элементов, узлы в стек больше не добавляются.
Шаг 7. Поскольку узлов в стеке больше нет, алгоритм завершается.
В примере выше поиск проходил по всем узлам. Однако, когда количество слов в словаре велико, этот метод позволит пропустить много ненужных узлов.
IV. Недостатки
Этот метод проверки орфографии и формирования подсказок даёт неплохие результаты, но не лишён недостатков:
Построение дерева может занять довольно много времени, поэтому его необходимо предварительно рассчитать и сохранить в файл.
Качество предложений сильно зависит от наличия слов в словаре. Если слова нет в словаре, его нельзя предложить.
В нём нет предшествующих контекстных слов, поэтому подсказки могут не соответствовать общей структуре предложения.
V. Код
Узнав об этих алгоритмах, я смог написать пакет Python, который их использует. Первым делом я подготовил словарь кхмерских слов. Для этого я загрузил набор данных кхмерских слов с открытым исходным кодом (лицензия MIT) из SBBIC и провёл некоторую предварительную обработку, получив в итоге список из примерно 40 тысяч уникальных слов. Затем я использовал приведённый ниже код для построения BK-дерева, сохранения дерева в XML-файл и использования его для проверки орфографии. Кроме того, я также упаковал его в библиотеку Python, которую вы можете установить через pip.
Редакционное расстояние
def edit_distance(word1: str, word2: str) -> int:
""" Расчёт расстояния Левенштейна между `word1` и `word2`.
Args:
---
- `word1`: Первое слово.
- `word2`: второе слово.
Возвращает:
---
Дистанцию между `word1` и `word2`
"""
num_cols = len(word1) + 1
num_rows = len(word2) + 1
memoize = [[None for c in range(num_cols)] for r in range(num_rows)]
for col_idx in range(0, num_cols):
memoize[0][col_idx] = col_idx
for row_idx in range(0, num_rows):
memoize[row_idx][0] = row_idx
for row_idx in range(1, num_rows):
for col_idx in range(1, num_cols):
left_n = memoize[row_idx][col_idx-1]
top_n = memoize[row_idx-1][col_idx]
cross_n = memoize[row_idx-1][col_idx-1]
neighbours = [left_n, top_n, cross_n]
min_n = min(neighbours)
if word1[col_idx-1] != word2[row_idx-1]:
memoize[row_idx][col_idx] = min_n + 1
else:
memoize[row_idx][col_idx] = cross_n
return memoize[num_rows-1][num_cols-1]Построение BK-дерева
from typing import List
import xml.etree.cElementTree as ET
from .node import Node
from .edit_distance import edit_distance
class Dictionary:
def __init__(self, dict_path: str) -> None:
""" Инициализация класса Dictionary.
Args
---
- `dict_path`: Путь к файлусловаря.
"""
self.words = self.__read_words(dict_path)
def save(self, output_filepath: str) -> None:
""" Сохранение BK-дерева в файл xml по пути `output_filepath`.
Args
---
- `output_filepath`: Путь к сохранённому xml-файлу.
"""
print("-- building bk-tree")
root = self.__build_bk_tree()
print("-- writing tree to xml file.")
xml_root = ET.Element("root")
xml_tree = ET.ElementTree(xml_root)
queue = [(0, root)]
while len(queue) != 0:
(w, curr_node) = queue.pop(0)
if curr_node.parent is None:
parent_node_xml = xml_root
else:
parent_node_xml = xml_root.find(f".//node[@word='{curr_node.parent.word}']")
parent_node_xml = parent_node_xml.find("children")
curr_node_xml = ET.Element("node", word=curr_node.word, weight=str(w))
curr_node_node_children_xml = ET.Element("children")
curr_node_xml.append(curr_node_node_children_xml)
for child in curr_node.children:
queue.append(child)
parent_node_xml.append(curr_node_xml)
xml_tree.write(output_filepath, encoding="UTF-8")
def __build_bk_tree(self) -> Node:
root = Node(self.words[0], parent=None, children=[])
for word_idx in range(1, len(self.words)):
current_word = self.words[word_idx]
self.__insert(root, current_word)
return root
def __insert(self, root: Node, word: str):
curr_node = root
inserted = False
while not inserted:
dist_curr_node = edit_distance(word, curr_node.word)
same_weight_child = curr_node.same_weight_child(dist_curr_node)
if same_weight_child is not None:
curr_node = same_weight_child
else:
if curr_node.word != word:
new_node = Node(word, parent=curr_node, children=[])
curr_node.children.append((dist_curr_node, new_node))
inserted = True
def __read_words(self, path: str) -> List[str]:
with open(path, "r") as dict_file:
return [word.strip("\n") for word in dict_file.readlines()]Поиск по BK-дереву / Проверка орфографии и подсказки
import os
from typing import List
import xml.etree.cElementTree as ET
from .node import Node
from .edit_distance import edit_distance
class SpellChecker:
""" Проверка орфографии использует популярную комбинацию расстояния Левенштейна и BK-дерева для быстрого поиска корректной подсказки. """
def __init__(self, model_path: str = None) -> None:
if model_path is None:
model_path = os.path.join(os.path.abspath(os.path.dirname(__file__)), "model.xml")
self.root = ET.parse(model_path).getroot().getchildren()[0]
def suggest(self, word: str, num_suggestions: int = 3, N: int = 2) -> List[str]:
""" Список исправлений для слова `word`.
Args
---
- `word`: Слово, которое нужно исправить.
- `num_suggestions`: Количество предложений.
Возвращает
---
Список предлагаемых исправлений.
"""
matches = []
stack: List[ET.Element] = [self.root]
while len(stack) != 0:
curr_node = stack.pop()
curr_node_word = curr_node.attrib["word"]
distance_curr_node = edit_distance(word, curr_node.attrib["word"])
if distance_curr_node <= N and (curr_node_word, distance_curr_node) not in matches:
matches.append((curr_node_word, distance_curr_node))
for child in curr_node.find("children").getchildren():
child_weight = int(child.attrib["weight"])
if child_weight >= (distance_curr_node - N) and child_weight <= (distance_curr_node + N):
stack.append(child)
return [match[0] for match in sorted(matches, key=lambda x: x[1])][:num_suggestions]VI. Заключение
Знакомство с редакционным расстоянием и BK-деревом позволило мне реализовать простую, но эффективную проверку орфографии и функцию подсказок. Надеюсь, этот пост поможет вам реализовать эти алгоритмы на других языках программирования и, возможно, расширить их до чего-то большего, чем просто проверка орфографии.
А мы поможем прокачать ваши навыки или с самого начала освоить профессию, востребованную в любое время:
Выбрать другую востребованную профессию.
