Блог

Мне было поручено создать простую проверку орфографии для задания, но я не дал почти никаких указаний, поэтому мне было интересно, может ли кто-нибудь мне помочь. Я не хочу, чтобы кто-то выполнял задание за меня, но любое направление или помощь с алгоритмом были бы потрясающими! Если то, о чем я спрашиваю, не входит в список гильдий сайта, то мне жаль, и я буду искать в другом месте. 🙂

Проект загружает правильно написанные строчные слова, а затем должен сделать предложения по правописанию на основе двух критериев:

• Разница в одну букву (добавляется или вычитается, чтобы слово совпадало со словом в словаре). Например, ‘stack’ будет предложением для ‘staick’, а ‘cool’ будет предложением для ‘coo’.

• Замена одной буквы. Так, например, ‘bad’ было бы предложением для ‘bod’.

Итак, просто чтобы убедиться, что я правильно объяснил.. Я мог бы загрузить слова [hello, goodbye, fantastic, good, god], а затем предложения для (неправильно написанного) слова «godd» будут [good, god] .

Скорость — мое главное соображение здесь, поэтому, хотя я думаю, что знаю способ выполнить эту работу, я действительно не слишком уверен в том, насколько это будет эффективно. Способ, которым я собираюсь это сделать, состоит в том, чтобы создать map<string, vector<string>> , а затем для каждого загруженного слова с правильным написанием, добавить правильно написанную работу в качестве ключа на карте и заполнить вектор всеми возможными «неправильными» перестановками этого слова.

Затем, когда я захочу найти слово, я просмотрю каждый вектор на карте, чтобы увидеть, является ли это слово перестановкой одного из правильно написанных слов. Если это так, я добавлю ключ в качестве предложения по правописанию.

Похоже, что это займет КУЧУ памяти, хотя, потому что наверняка будут тысячи перестановок для каждого слова? Также кажется, что это было бы очень медленно, если бы мой первоначальный словарь правильно написанных слов был большим?

Я подумал, что, возможно, я мог бы немного сократить время, только просматривая ключи, похожие на слово, на которое я смотрю. Но опять же, если они чем-то похожи, это, вероятно, означает, что ключом будет предложение, означающее, что мне не нужны все эти перестановки!

Так что да, я немного озадачен тем, в каком направлении мне следует искать. Я был бы очень признателен за любую помощь, поскольку я действительно не уверен, как оценить скорость различных способов выполнения действий (нас этому вообще не учили в классе).

Более простым способом решения проблемы действительно является предварительно вычисленная карта [плохое слово] -> [предложения].

Проблема в том, что, хотя удаление буквы создает несколько «плохих слов», для добавления или замены у вас есть много кандидатов.

Поэтому я бы предложил другое решение 😉

Примечание: расстояние редактирования, которое вы описываете, называется расстоянием Левенштейна

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

0. Предварительный

• Реализация алгоритма расстояния Левенштейна
• Храните словарь в отсортированной последовательности ( std::set например, хотя сортировка std::deque или std::vector была бы более эффективной с точки зрения производительности)

Ключевые моменты:

• Вычисление расстояния Левенштейна использует массив, на каждом шаге следующая строка вычисляется исключительно с предыдущей строкой
• Минимальное расстояние в строке всегда больше (или равно) минимальному значению в предыдущей строке

Последнее свойство допускает реализацию с коротким замыканием: если вы хотите ограничить себя 2 ошибками (пороговым значением), то всякий раз, когда минимум текущей строки превышает 2, вы можете отказаться от вычисления. Простая стратегия заключается в возврате порога 1 в качестве расстояния.

1. Первый предварительный

Давайте начнем с простого.

Мы реализуем линейное сканирование: для каждого слова мы вычисляем расстояние (короткое замыкание) и перечисляем те слова, которые достигли меньшего расстояния до сих пор.

Он очень хорошо работает с небольшими словарями.

2. Улучшение структуры данных

Расстояние Левенштейна, по крайней мере, равно разнице в длине.

Используя в качестве ключа пару (длина, слово) вместо просто word, вы можете ограничить поиск диапазоном длины [length - edit, length edit] и значительно сократить пространство поиска.

3. Префиксы и обрезка

Чтобы улучшить это, мы можем заметить, что когда мы строим матрицу расстояний, строка за строкой, один мир полностью сканируется (слово, которое мы ищем), а другой (референт) — нет: мы используем только одну букву для каждой строки.

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

Помните, что я прошу вас сохранить словарь отсортированным ? Это означает, что слова, имеющие один и тот же префикс, являются смежными.

Предположим, что вы проверяете свое слово cartoon и car понимаете, что оно не работает (расстояние уже слишком велико), тогда любое слово, начинающееся с car , тоже не будет работать, вы можете пропускать слова, пока они начинаются car .

Сам пропуск может быть выполнен либо линейно, либо с помощью поиска (найдите первое слово, у которого префикс выше, чем car ):

• линейный работает лучше всего, если префикс длинный (несколько слов для пропуска)
• двоичный поиск лучше всего подходит для короткого префикса (много слов, которые нужно пропустить)

Длина «long» зависит от вашего словаря, и вам придется измерить. Я бы начал с бинарного поиска.

Примечание: разделение по длине работает против разделения по префиксу, но оно значительно сокращает пространство поиска

4. Префиксы и повторное использование

Теперь мы также попытаемся повторно использовать вычисления как можно чаще (а не только результат «это не работает»)

Предположим, что у вас есть два слова:

• Мультфильм
• автомойка

Сначала вы вычисляете матрицу, строка за строкой, для cartoon . Затем при чтении carwash вам нужно определить длину общего префикса (здесь car ), и вы можете сохранить первые 4 строки матрицы (соответствующие void, c , a , r ).

Поэтому, когда вы начинаете вычисления carwash , вы фактически начинаете итерацию w .

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

5. Использование «лучшей» структуры данных

Чтобы упростить работу с префиксами, вы могли бы использовать дерево Trie или дерево Patricia для хранения словаря. Однако это не структура данных STL, и вам нужно будет дополнить ее, чтобы сохранить в каждом поддереве диапазон длины слов, которые хранятся, поэтому вам придется создать свою собственную реализацию. Это не так просто, как кажется, потому что есть проблемы с расширением памяти, которые могут уничтожить локальность.

Это крайний вариант. Это дорого для реализации.

Вы должны взглянуть на это объяснение Питера Норвига о том, как написать корректор орфографии .

Как написать корректор орфографии

В этой статье все хорошо объяснено, в качестве примера код python для проверки орфографии выглядит следующим образом :

 import re, collections

def words(text): return re.findall('[a-z] ', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f]  = 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word)   1)]
   deletes    = [a   b[1:] for a, b in splits if b]
   transposes = [a   b[1]   b[0]   b[2:] for a, b in splits if len(b)>1]
   replaces   = [a   c   b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a   c   b     for a, b in splits for c in alphabet]
   return set(deletes   transposes   replaces   inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)
  

Надеюсь, вы сможете найти то, что вам нужно, на веб-сайте Питера Норвига.

для проверки орфографии многие структуры данных были бы полезны, например, BK-Tree. Проверьте чертовски крутые алгоритмы, часть 1: BK-деревья, для которых я сделал реализацию здесь

Моя предыдущая ссылка на код может вводить в заблуждение, эта верна для корректора правописания.

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

должно быть довольно быстро, но я не уверен в самом коде, я не очень хорошо разбираюсь в c