Простой алгоритм проверки орфографии

Question

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

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

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

• Подстановка одной буквы.Так, например, «плохой» будет предложением для «бод».

Итак, просто чтобы убедиться, что я все правильно объяснил ... Я мог бы загрузить слова [привет,до свидания, фантастика, хорошо, бог], и тогда предложения для (неправильно написанного) слова «год» будут [хорошо, бог].

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

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

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

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

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

Answer 1

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

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

Так что я бы предложил другое решение;)

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

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

---

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

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

Ключи Очки:

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

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

---

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

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

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

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

---

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

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

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

---

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

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

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

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

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

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

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

Как долго будет "long", зависит от вашего словаря, и вам придется измерять. Я хотел бы начать с двоичного поиска.

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

---

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

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

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

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

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

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

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

---

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

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

Это последний вариант. Это дорого обходится.

Answer 2

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

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

EveryThing хорошо объяснитьВ этой статье в качестве примера код 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)

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

Answer 3

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

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

Answer 4

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

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