Поиск списка смежных слов между двумя словами

Я работаю над проблемой программирования для практики, и у меня возникают проблемы с поиском хорошей структуры данных/алгоритма для использования для реализации решения.

Фон:

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

"Список слов" - это упорядоченный список уникальных слов, в которых соседние слова смежны.

Проблема:

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

<сильные > Примеры:

hate  → love:     hate, have, hove, love
dogs  → wolves:   dogs, does, doles, soles, solves, wolves
man   → woman:    man, ran, roan, roman, woman
flour → flower:   flour, lour, dour, doer, dower, lower, flower

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

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

Ответ 1

Эта головоломка впервые была сформулирована Чарльзом Доджсоном, который написал "Приключения Алисы в Стране Чудес" под его псевдонимом Льюис Кэрролл.

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

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

Ответ 2

Я не знаю, является ли это типом решения, которое вы ищете, но активная область исследований заключается в создании словарей "edit distance 1" для быстрого поиска смежных слов (чтобы использовать ваш язык) для предложения поискового запроса, коррекция ввода данных и биоинформатика (например, поиск сходства в хромосомах). См., Например, этот исследовательский документ. Если вы не индексируете весь словарь, по крайней мере, это может предложить эвристику поиска, которую вы можете использовать.

Ответ 3

Я сделал это сам и использовал его для создания (не очень хорошей) игры Windows.

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

Сложная часть - это построение графика. Плохая новость в том, что это O (n ^ 2). Хорошей новостью является то, что ее не нужно делать в режиме реального времени - вместо того, чтобы ваша программа читала словарные слова из файла, она читается в структуре данных, которую вы испекли ранее.

Ключевое понимание заключается в том, что порядок не имеет значения, на самом деле он мешает. Вам нужно создать еще одну форму, в которой можно удерживать слова, которые вытесняют информацию о заказе, и позволяет легче сравнивать слова. Вы можете сделать это в O (n). У вас много выбора; Я покажу два.

Для головоломок я часто использую кодировку, которую я вызываю в словаре анаграмм. Слово представлено другим словом, которое имеет одинаковые буквы, но в алфавитном порядке. Поэтому "автомобили" становятся "акрами". Оба списка и разрезы становятся "ильст". Это лучшая структура для сравнения, чем исходное слово, но существуют гораздо лучшие сравнения (однако, это очень полезная структура для других головоломок).
Число букв. Массив из 26 значений, которые показывают частоту этой буквы в слове. Так что для "автомобилей" он начинается 1,0,1,0,0... так как есть один "а" и один "с". Держите внешний список ненулевых записей (какие буквы появляются в слове), поэтому вам нужно всего лишь проверить 5 или 6 значений максимум, а не 26. Очень просто сравнить два слова, содержащиеся в этой форме, быстро, обеспечивая не более двух подсчеты разные. Это тот, который я использовал бы.

Итак, так я это сделал.

Я написал программу, в которой реализована структура данных выше.

У него был класс под названием WordNode. Это содержит оригинальное слово; Список всех других WordNodes, которые отличаются друг от друга; массив из 26 целых чисел, дающий частоту каждой буквы, список ненулевых значений в массиве счетчиков букв.

Инициализатор заполняет частотный массив букв и соответствующий список ненулевых значений. Он устанавливает список подключенных WordNodes равным нулю.

После того, как я создал экземпляр класса WordNode для каждого слова, я запускаю метод сравнения, который проверяет, отличается ли число частот не более чем в двух местах. Обычно это немного меньше, чем буквы в словах; не плохо. Если они отличаются друг от друга ровно в двух местах, они отличаются одной буквой, и я добавляю этот WordNode в список WordNodes, отличающихся только одной буквой.

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

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

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

Жаль, что моя игра была дерьмой.

Ответ 4

Самый простой (рекурсивный) алгоритм - я могу думать (ну, я могу думать только в данный момент)

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

Может быть, кто-то с немного большим временем может добавить для этого код ruby?

Ответ 5

Попробуйте это

x = 'hate'
puts x = x.next until x == 'love'

И если вы соедините его со словарным поиском, вы получите список всех допустимых слов между ними в этом словаре.