Использование бинарного дерева поиска в качестве проверки орфографии

Question

Хотите узнать, как наиболее эффективно превратить бинарное дерево поиска в средство проверки орфографии, прочитав, например, файл словаря, состоящего из 1000 слов, и затем проверив другой документ, в котором, скажем, есть пара абзацев.

Answer 1

троичное дерево дерево будет более эффективным

Answer 2

Вы устали от использования бинарного дерева поиска? Фильтр Блума , вероятно, будет более эффективной структурой данных.

Answer 3

Этот сайт должен помочь вам это имеет реализацию в Java.

Answer 4

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

Например: скажем, в вашем словаре есть такие слова: машина, тележка, кошка, чашка, вырезать

- C
  - A
    - R
      - end
      - T
    - T
      - end
  - U
    - P
      - end
    - T
      - end

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

Check for "cat"
Does "C" exist at the root level? Yes, move to the next letter.
Does "A" exist underneath C? Yes, move on.
Does "T" exist underneath A? Yes, move on.
Is there a word ending after the T? Yes. Word exists.

Check for "cu"
Does "C" exist at the root level? Yes, move to the next letter.
Does "U" exist at the root level? Yes, move to the next letter.
Is there a word ending after the U? No. Word does not exist.

Как вы храните эту информацию, зависит от вас. Как указывал Стивен, Ternary Search Trie может быть подходящим способом: у каждого узла будет 27 возможных дочерних узлов.

Answer 5

Как и предполагалось, три будет более эффективным, чем двоичное дерево, но вы можете использовать хэш-карту и хэшировать каждое слово. У вас есть небольшой словарь (1000 записей). Просматривая документ, проверьте, есть ли слова в хэш-карте. Если это не так, предполагается, что слово написано с ошибкой.

Это не даст вам возможного исправления слова с ошибкой. Он просто говорит вам да или нет (правильно или нет).

Если вам нужны варианты правописания для неправильных слов, вы можете начать со слова в файле, а затем сгенерировать все слова на расстоянии 1 редактирования и добавить их в качестве потомков исходного слова. Таким образом, вы строите график. Пройдите 2 уровня глубины для максимальной скорости против точности. Если вы сгенерируете словарный узел, который находится в словаре, вы можете добавить его в список возможных предложений. В конце верните список возможных предложений.

Для лучшей проверки правописания также попробуйте добавить фонетическое соответствие.

море йу -> увидимся

Этот метод (создания графиков строк, которые редактируются 1) является "медленным". Но это хорошее академическое упражнение. Время выполнения - O (n ^ ветвей).

Если интересно, здесь ссылка на тот, который я построил сам (для удовольствия): https://github.com/eamocanu/spellcheck.graph

Некоторые примеры графиков: https://github.com/eamocanu/spellcheck.graph/tree/master/graph%20photos

Я также добавил компонент пользовательского интерфейса, который генерирует графики. Это внешняя библиотека.

Answer 6

Учитывая, что это домашний вопрос, я собираюсь предположить, что вы должны использовать простое старое двоичное дерево (без красно-черных деревьев, деревьев AVL, деревьев Radix и т. Д.). Тогда ответом будет попытаться сохранить дерево сбалансированным, когда вы строите его из списка слов. Один из подходов состоит в том, чтобы рандомизировать список перед его чтением, это дает разумные результаты. Но вы можете получить лучшие результаты, если упорядочите входную последовательность (используя то же сравнение, что и дерево), а затем рекурсивно разделите вход, возвращая среднюю точку, пока не останется никаких элементов. В результате получается сбалансированное дерево.

Я выбрал три разных способа сделать это в C #:

private static IEnumerable<T> BinaryTreeOrder<T>(IList<T> range, int first, int last)
{
  if (first > last)
  {
    yield break;
  }

  int mid = (first + last) / 2;
  yield return range[mid];
  foreach (var item in BinaryTreeOrder(range, first, mid - 1))
  {
    yield return item;
  }
  foreach (var item in BinaryTreeOrder(range, mid + 1, last))
  {
    yield return item;
  }    
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref IList<T> outList)
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  outList.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref outList);
  BinaryTreeOrder(range, mid + 1, last, ref outList);
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref BinaryTree<T> tree) where T : IComparable<T>
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  tree.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref tree);
  BinaryTreeOrder(range, mid + 1, last, ref tree);
}

Answer 7

В приведенном вами примере производительность, скорее всего, не будет иметь значения, поскольку на ПК вся операция займет примерно 1% времени, которое требуется пользователю для чтения первого показанного вами результата, при условии, что вы не используете совершенно тупой алгоритм. Но, тем не менее, я предполагаю, что проблема достаточно велика, чтобы производительность была проблемой.

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

Это выполняет работу, связанную с M log M сравнениями для сортировки, плюс не более N + M сравнений для итерации (возможно, меньше, но не сложнее). Это довольно близко к оптимальной сложности для одноразовой операции: чтобы избавиться от линейного члена в N, вам нужно найти способы вообще не читать весь словарь с диска. Я почти уверен, что можно выполнить поиск в файле, особенно если учесть, что слова довольно короткие, но для маленького N никто не знает, будет ли поиск места быстрее, чем последовательный доступ к данным.

Имеет следующие характеристики:

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

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

Если словарь действительно огромен, то вам может быть полезно хранить его на диске в предварительно обработанной форме, эквивалентной несбалансированному дереву, взвешенному в соответствии с относительными частотами различных слов в вашем языке. Тогда вы можете сделать меньше, чем O (N) доступ к диску для небольших текстов, и на большинстве ОС не загружать его вообще в память, просто mmap файл и позвольте ОС беспокоиться об этом. Для большого словаря не нужно трогать целые кластеры, содержащие слова, начинающиеся с «диметил».

Другое соображение - это дерево сплайнов для словаря. Splay-дерево разбалансирует себя, когда вы что-то ищите в нем, чтобы быстрее находить часто используемые значения. Большая часть текста использует небольшое количество слов несколько раз, поэтому, если текст достаточно длинный, чтобы оправдать накладные расходы, это в конечном итоге выиграет.

Оба вышеперечисленных предмета подчиняются пункту Стивена Лоу о том, что для строк три бьет нормальное дерево. Не знаю, найдёте ли вы готовый сплай-три.

Answer 8

Если вам нужно также выполнить автоматический поиск / префикс, то стоит посмотреть на дерево Патрисии или радикальное дерево.